使用動態編程進行分詞

Question

所以首先，我對Python非常陌生，所以如果我做了一件糟糕的事情，我正在爲這篇文章寫一篇抱歉的文章。我已經分配了這個問題：

我們想爲以下問題設計一個動態編程解決方案：有一串字符可能是所有空格都被刪除的單詞序列，我們想要查找一種方法，如果有的話，插入空格分隔有效的英語單詞。例如，他們可能來自「發泄你」，「青年事件」或「他們發泄」。如果輸入是eaglehaslande，那麼就沒有這種方法。你的任務是實現兩個獨立的方式動態編程解決方案：

• 迭代自下而上版本
• 遞歸記憶版本

假設字的原始序列沒有其他標點符號（如作爲句號），沒有大寫字母，也沒有專有名稱 - 所有單詞都將在將提供給您的字典文件中提供。

所以我有兩個主要問題：

1. 我知道，這可以而且應該爲O完成（N^2），我不認爲我是
2. 查找表ISN 「T將所有的話似乎這樣就可以減少時間複雜度

我想什麼：

1. 任何類型的輸入（更好的辦法要做到這一點，你在代碼中看到錯誤，如何讓查找表工作，如何使用布爾表來構建一系列有效的單詞）
2. 有關如何解決遞歸版本的一些想法，儘管我感覺一旦我能夠解決迭代解決方案，我將能夠從中設計遞歸的解決方案。

一如既往地感謝任何人給予此任何時間和努力，但總是感激。

這裏是我的嘗試：

#dictionary function returns True if word is found in dictionary false otherwise 
def dictW(s): 
    diction = open("diction10k.txt",'r') 
    for x in diction: 
     x = x.strip("\n \r") 
     if s == x: 
      return True 
    return False 

def iterativeSplit(s): 
    n = len(s) 
    i = j = k = 0 
    A = [-1] * n 
    word = [""] * n 
    booly = False 
    for i in range(0, n): 
     for j in range(0, i+1): 
      prefix = s[j:i+1] 
      for k in range(0, n): 

       if word[k] == prefix: 
        #booly = True 
        A[k] = 1 
        #print "Array below at index k %d and word = %s"%(k,word[k]) 
        #print A 
      # print prefix, A[i] 
      if(((A[i] == -1) or (A[i] == 0))): 
       if (dictW(prefix)): 
        A[i] = 1 
        word[i] = prefix 
        #print word[i], i 
       else: 
        A[i] = 0 
    for i in range(0, n): 
     print A[i] 

Answer 1

用C++ Here is the solution。閱讀並理解概念，然後執行。

這個video對理解DP方法非常有幫助。

我覺得可以幫助的另一種方法是數據結構Trie。這是解決上述問題的更好方法。

Answer 2

有關如何進行英文分詞的另一個實際示例，請參閱Python wordsegment module的source。它有點複雜，因爲它使用單詞和詞組頻率表，但它說明了記憶方法。

尤其segment說明了記憶化的方法：

def segment(text): 
    "Return a list of words that is the best segmenation of `text`." 

    memo = dict() 

    def search(text, prev='<s>'): 
     if text == '': 
      return 0.0, [] 

     def candidates(): 
      for prefix, suffix in divide(text): 
       prefix_score = log10(score(prefix, prev)) 

       pair = (suffix, prefix) 
       if pair not in memo: 
        memo[pair] = search(suffix, prefix) 
       suffix_score, suffix_words = memo[pair] 

       yield (prefix_score + suffix_score, [prefix] + suffix_words) 

     return max(candidates()) 

    result_score, result_words = search(clean(text)) 

    return result_words 

如果更換了score功能，使得它在你的字典中返回的「1」字和「0」，如果不是，那麼只需在枚舉所有積極評分的候選人爲您的答案。