检查是否可以进行分词-Java 学习之路

这是this response以及用户发布的伪代码算法的后续问题 . 我没有需要实际拆分字符串 . 这是相关问题的回复：

设S [1..length（w）]是一个带有布尔条目的表 . 如果可以拆分单词w [1..i]，则S [i]为真 . 然后设置S [1] = isWord（w [1]）并且对于i = 2到长度（w），计算S [i] =（isWord [w [1..i]或者对于{2..i中的任何j） }：S [j-1]和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 是一个简单地在列表中查找给定单词的函数 . 我还没有实现它作为特里 .

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

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 这两个 .

3 回答

这是您的代码的修改版本，应该返回良好的结果 . 请注意，您的错误只是从伪代码数组索引（从1开始）到python数组索引（从0开始）的转换，因此S [0]和S [1]填充了相同的值，其中S [L-1]实际上从未计算过 . 您可以通过打印整个S值轻松跟踪此错误 . 您会发现S [3]在第一个示例中设置为true，其中单词“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

回复于 2024-05-03T22:29:09+08:00

1
有关如何进行英语分词的实际示例，请查看Python wordsegment module的来源 . 它有点复杂，因为它使用单词和短语频率表，但它说明了递归方法 . 通过修改 score 功能，您可以优先考虑更长的匹配 .

使用 pip 轻松安装：
```
$ pip install wordsegment
```
segment 返回一个单词列表：
```
>>> import wordsegment
>>> wordsegment.segment('carrotfever')
['carrot', 'forever']
```
回复于 2024-05-03T22:29:09+08:00
2
1）乍一看，看起来不错 . 一件事： for j in range(1, str_len): 应该 for j in range(1, i): 我想

2）如果S [str_len-1] == true，则整个字符串应仅包含整个单词 .

毕竟S [i]是真的iff
- 从0到i的整个字符串由单个字典单词组成
- 或者 j<i 存在S [j-1] == true，字符串[j：i]是单个字典
所以如果S [str_len-1]为真，则整个字符串由字典单词组成
回复于 2024-05-03T22:29:09+08:00