4

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

让 S[1..length(w)] 是一个带有布尔条目的表。如果单词 w[1..i] 可以拆分,则 S[i] 为真。然后设置 S[1] = isWord(w[1]) 并为 i=2 到 length(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这两个。

4

3 回答 3

2

这是您的代码的修改版本,应该会返回良好的结果。请注意,您的错误只是从伪代码数组索引(从 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
于 2012-04-23T03:23:36.760 回答
2

有关如何进行英语分词的真实示例,请查看Python wordsegment 模块的源代码。它更复杂一点,因为它使用单词和短语频率表,但它说明了递归方法。通过修改score函数,您可以优先考虑更长的匹配。

安装很容易pip

$ pip install wordsegment

segment返回一个单词列表:

>>> import wordsegment
>>> wordsegment.segment('carrotfever')
['carrot', 'forever']
于 2015-09-02T23:17:09.397 回答
1

1)乍一看,看起来不错。一件事:for j in range(1, str_len):应该是for j in range(1, i):我认为

2) 如果 S[str_len-1]==true,那么整个字符串应该只包含整个单词。

毕竟 S[i] 为真当且仅当

  • 从 0 到 i 的整个字符串由一个字典单词组成
  • 或者存在一个 S[j-1]==true j<i,并且字符串 [j:i] 是一个字典词

所以如果 S[str_len-1] 为真,那么整个字符串由字典单词组成

于 2012-04-22T22:33:23.300 回答