檢查分詞是否可能

這是對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] or for any j in {2..i}：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是一個函數，它只是查看列表中給定的單詞。我還沒有實現它作爲一個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這兩個這些。

來源

2012-04-22 Ricardo Altamirano

你有沒有得到這個工作？ – thinkdevcode 2012-08-14 07:01:29

@thinkdevcode是的。看到我對[接受的答案]（http://stackoverflow.com/a/10274435/869912）的評論。 – 2012-08-14 10:40:59

這裏是修飾VERS你的代碼應該返回好的結果。請注意，您的錯誤僅僅在於從僞代碼數組索引（從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 FALSE 

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

來源

2012-04-23 03:23:36

謝謝你的幫助。該代碼有效。我更正了打印語句中的錯誤（結尾']'缺失，所以最後一行看起來像這樣：'print（S [len（a_string）-1]）'並添加了我自己的習慣字典函數，看起來像在工作。 – 2012-04-26 16:09:29

1）乍一看，看起來不錯。有一件事：for j in range(1, str_len):應該是for j in range(1, i):我認爲

2）如果S [str_len-1] == true，那麼整個字符串應該只包含整個字。

畢竟S [i]爲真當且僅當

從0整個字符串爲i由單個字典字
的OR存在S [J-1] == TRUE與j<i和字符串[J：i]爲單個dictionaryword

因此，如果S [str_len-1]爲真，那麼整個字符串由選自詞典詞語

來源

2012-04-22 22:33:23 HugoRune

我更新了我的問題，因爲算法仍未返回正確的解決方案。 – 2012-04-23 01:06:32

對於如何做英文分詞一個真實世界的例子，看看Python wordsegment module的來源。它有點複雜，因爲它使用單詞和詞組頻率表，但它說明了遞歸方法。通過修改score功能，您可以優先考慮更長時間的匹配。

安裝很容易與pip：

$ pip install wordsegment

而且segment回報單詞的列表：

>>> import wordsegment 
>>> wordsegment.segment('carrotfever') 
['carrot', 'forever']

來源

2015-09-02 23:17:09 GrantJ

檢查分詞是否可能

回答

相關問題