python - 检查是否可以分词

Question

这是对 this response 的后续问题以及用户发布的伪代码算法。由于它的年龄，我没有对这个问题发表评论。我只对验证字符串是否可以拆分成单词感兴趣。该算法不需要实际拆分字符串。这是链接问题的回复:

Let S[1..length(w)] be a table with Boolean entries. S[i] is true if the word w[1..i] can be split. Then set S[1] = isWord(w[1]) and for i=2 to length(w) calculate

S[i] = (isWord[w[1..i] or for any j in {2..i}: S[j-1] and isWord[j..i]).

我正在将这个算法翻译成简单的 Python 代码，但我不确定我是否理解正确。代码:

def is_all_words(a_string, dictionary)):
    str_len = len(a_string)
    S = [False] * str_len
    S[0] = is_word(a_string[0], dictionary)
    for i in range(1, str_len):
        check = is_word(a_string[0:i], dictionary)
        if (check):
            S[i] = check
        else:
            for j in range(1, str_len):
                check = (S[j - 1] and is_word(a_string[j:i]), dictionary)
                if (check):
                    S[i] == True
                    break
    return S

我有两个相关的问题。 1) 这段代码是否是链接算法到 Python 的正确翻译，如果是，2) 现在我有了 S，我如何使用它来判断字符串 是 是否仅由单词组成？在这种情况下，is_word 是一个简单地在列表中查找给定单词的函数。我还没有将它实现为 trie。

更新:更新代码以包含建议的更改后，它不起作用。这是更新后的代码:

def is_all_words(a_string, dictionary)):
    str_len = len(a_string)
    S = [False] * str_len
    S[0] = is_word(a_string[0], dictionary)
    for i in range(1, str_len):
        check = is_word(a_string[0:i], dictionary)
        if (check):
            S[i] = check
        else:
            for j in range(1, i): #THIS LINE WAS UPDATED
                check = (S[j - 1] and is_word(a_string[j:i]), dictionary)
                if (check):
                    S[i] == True
                    break
    return S

a_string = "carrotforever"
S = is_all_words(a_string, dictionary)
print(S[len(S) - 1]) #prints FALSE

a_string = "hello"
S = is_all_words(a_string, dictionary)
print(S[len(S) - 1]) #prints TRUE

它应该为这两个返回 True。

Answer 1

这是您的代码的修改版本，应该会返回良好的结果。请注意，您的错误只是在从伪代码数组索引(从 1 开始)到 python 数组索引(从 0 开始)的转换中，因此 S[0] 和 S[1] 填充了与 S[L-1] 相同的值实际上从未计算过。您可以通过打印整个 S 值来轻松追踪此错误。您会发现在第一个示例中 S[3] 设置为真，对于单词“car”它应该是 S[2]。您还可以通过存储目前找到的复合词的索引来加快该过程，而不是测试每个位置。

def is_all_words(a_string, dictionary):
    str_len = len(a_string)
    S = [False] * (str_len)
# I replaced is_word function by a simple list lookup, 
# feel free to replace it with whatever function you use. 
# tries or suffix tree are best for this.
    S[0] = (a_string[0] in dictionary) 
    for i in range(1, str_len):
        check = a_string[0:i+1] in dictionary # i+1 instead of i
        if (check):
            S[i] = check
    else:
        for j in range(0,i+1): # i+1 instead of i
            if (S[j-1] and (a_string[j:i+1] in dictionary)): # i+1 instead of i
            S[i] = True
            break


    return S

a_string = "carrotforever"
S = is_all_words(a_string, ["a","car","carrot","for","eve","forever"])
print(S[len(a_string)-1]) #prints TRUE

a_string = "helloworld"
S = is_all_words(a_string, ["hello","world"])
print(S[len(a_string)-1]) #prints TRUE