文本分割：將輸入與字典中最長單詞匹配的算法

Question

我需要將字符串拆分爲單詞，以使每個單詞來自字典。還要確保選擇左側最長的單詞。因此

thisisinsane => this is insane (correct as longest possible word from left) 
thisisinsane => this is in sane(wrong) 
Assuming 'this', 'is', 'in', 'insane' are all words in the dictionary. 

我從字符串的結尾遍歷到開始匹配最長的單詞可能成功地解決了這個問題。但問題開始裁剪我們像這些問題..

shareasale => share as ale(wrong as 'ale' not in the dictionary) 
shareasale => share a sale(correct) 
Assuming 'share', 'a', 'sale' are all words in the dictionary unlike 'ale'. 

我試圖通過刪除遇到的錯誤，即

shareasale => 'share' and 'as' (error = 'ale') 

，並從字典中刪除一次他們之前發現的有效的段來解決這個問題然後解決問題。所以

shareasale => no valid segments when share is removed 
shareasale => share a sale (when 'as' is removed from the dictionary. 

因此，我也設法解決這個問題。但後來我無法解決這個

asignas => 'as' (error = 'ignas') 

我的解決方案，然後會從字典中刪除「爲」，並試圖解決它

asignas => 'a' 'sign' (error = 'as') 

因爲在新的遞歸調用「爲」已被刪除從字典中。我寫的功能是in this link。我希望有人可以通過它，並幫助我找到一個更好的算法來解決這個問題，建議修改我現有的算法。

Answer 1

基本上你的問題是樹的問題，在此，每一個級別都形成樹形分支的前綴詞。不留下部分字符串的分支是一個正確的解決方案。

     thisisinsane 
          | 
          | 
        (this)isinsane 
        /   \ 
        /   \ 
      (this,i)sinsane   (this,is)insane 
      /     /   \ 
      /     /   \ 
    (this,i,sin)ane   (this,is,in)sane (this,is,insane) 
           /
          /
         (this,is,in,sane) 

因此，在這個例子中，有兩種解決方案，但我們要選擇使用最長的單詞的解決方案，這是我們要利用深度優先搜索策略的正確探索的樹。

因此，我們的算法應該：

1. 排序字典的下降長度。
2. 查找當前字符串的所有前綴。如果沒有，請返回False。
3. 將prefix設置爲最長未探索前綴。
4. 將其從字符串中移除。如果字符串爲空，我們找到了解決方案，返回所有前綴的列表。
5. 遞歸到2.
6. 此分支失敗，返回False。

---

該解決方案的實現：

def segment(string,wset): 
    """Segments a string into words prefering longer words givens 
    a dictionary wset.""" 
    # Sort wset in decreasing string order 
    wset.sort(key=len, reverse=True) 
    result = tokenize(string, wset, "") 
    if result: 
     result.pop() # Remove the empty string token 
     result.reverse() # Put the list into correct order 
     return result 
    else: 
     raise Exception("No possible segmentation!") 

def tokenize(string, wset, token): 
    """Returns either false if the string can't be segmented by 
    the current wset or a list of words that segment the string 
    in reverse order.""" 
    # Are we done yet? 
    if string == "": 
     return [token] 
    # Find all possible prefixes 
    for pref in wset: 
     if string.startswith(pref): 
      res = tokenize(string.replace(pref, '', 1), wset, pref) 
      if res: 
       res.append(token) 
       return res 
    # Not possible 
    return False 

print segment("thisisinsane", ['this', 'is', 'in', 'insane']) # this is insane 
print segment("shareasale", ['share', 'a', 'sale', 'as'])  # share a sale 
print segment("asignas", ['as', 'sign', 'a'])     # a sign as 

Answer 2

只要進行一次遞歸掃描，每次向最後一個單詞添加單個字母（如果它在字典中），並且還嘗試讓它開始一個新單詞。這意味着在每次通話時，您都有1或2個假設來測試（是否有空間）。 當你到達輸入的末尾，並且有一組有效的單詞時，保存此解決方案，如果其中的第一個單詞比迄今爲止找到的最佳解決方案長。

示例代碼：

words=['share','as','a','sale','bla','other','any','sha','sh'] 
wdict={} 
best=[] 

def scan(input,i,prevarr): 
    global best 
    arr=list(prevarr) 
    # If array is empty, we automatically add first letter 
    if len(arr)<1: 
     arr.append(input[0:1]) 
     return scan(input,i+1,arr) 
    # If no more input is available, evaluate the solution 
    if i>=len(input): 
     # Is the last word a valid word 
     if wdict.has_key(arr[-1]): 
      # Is there a current best solution? 
      if len(best)==0: 
       best=arr  # No current solution so select this one 
      elif len(arr[0])>len(best[0]): 
       best=arr  # If new solution has a longer first word 
     return best 
    # If the last word in the sequence is a valid word, we can add a space and try 
    if wdict.has_key(arr[-1]): 
     arr.append(input[i:i+1]) 
     scan(input,i+1,arr) 
     del arr[-1] 
    # Add a letter to the last word and recurse 
    arr[-1]=arr[-1]+input[i:i+1] 
    return scan(input,i+1,arr) 

def main(): 
    for w in words: 
     wdict[w]=True 
    res=scan('shareasasale',0,[]) 
    print res 

if __name__ == '__main__': 
    main() 

Answer 3

我會用會是這樣的算法：

• 有你的字典通過減少長度
• 建立一個功能prefix(s)整理其收益率，從而，字典單詞開始s
  • 即。 prefix("informativecow")產量第一 「信息」，然後在 「通知」，則 「信息」，然後 「在」
• 建立一個遞歸函數test(s)其中：
  • 如果s是空字符串，返回True
  • 對於每個前綴，從s中刪除前綴並用該字符串調用test()。如果你發現一個是真的，返回true。如果您沒有發現任何錯誤，請返回False。

Answer 4

對於如何做英文分詞一個真實世界的例子，看看Python wordsegment module的來源。它有點複雜，因爲它使用單詞和詞組頻率表，但它說明了記憶方法。

尤其score說明了分割方法：

def score(word, prev=None): 
    "Score a `word` in the context of the previous word, `prev`." 

    if prev is None: 
     if word in unigram_counts: 

      # Probability of the given word. 

      return unigram_counts[word]/1024908267229.0 
     else: 
      # Penalize words not found in the unigrams according 
      # to their length, a crucial heuristic. 

      return 10.0/(1024908267229.0 * 10 ** len(word)) 
    else: 
     bigram = '{0} {1}'.format(prev, word) 

     if bigram in bigram_counts and prev in unigram_counts: 

      # Conditional probability of the word given the previous 
      # word. The technical name is *stupid backoff* and it's 
      # not a probability distribution but it works well in 
      # practice. 

      return bigram_counts[bigram]/1024908267229.0/score(prev) 
     else: 
      # Fall back to using the unigram probability. 

      return score(word) 

如果更換了得分功能，使其恢復較高的分數更長的比賽在你的字典那麼，你希望它會怎麼做。