任何人都知道使用動態編程進行分詞的示例算法？

Question

如果谷歌搜索分詞真的沒有很好的描述它，我只是想充分了解過程中的動態規劃算法需要找到一個字符串爲單個單詞的分割。有沒有人知道一個地方對分詞問題有很好的描述，或者任何人都可以描述它？

分詞基本上只是走個字符的字符串，並決定在哪裏分成了的話，如果你不知道，並使用動態規劃會考慮到子問題的一些量。這是非常簡單的使用遞歸做，但我一直沒能找到任何地方網上找到哪怕只是一個迭代算法這個網上的描述，因此，如果任何人有任何例子或者可以給一個算法，將是巨大的。

感謝您的任何幫助。

Answer 1

我要去假設我們不是在談論這個瑣碎的例子在這裏（即不只是圍繞分裂空格的字符串，因爲這會只是一個基本的標記生成器問題） - 而是，我們談論關於某些東西是不存在明確的單詞分隔字符的，因此我們不得不「猜測」字符串>單詞的最佳匹配是什麼 - 例如，一組連接單詞不帶空格的情況，如轉化的：

lotsofwordstogether 

成這樣：

lots, of, words, together 

在這種情況下，動態規劃方法可能是計算出一個表格，其中一個維度對應於序列中的M個字，另一個維度對應於輸入字符串中的每個N個字符。然後，你填寫的表格的每個平方值是「最佳匹配率，我們可以在N的位置，如果我們最終獲得（或替代，開始）的M個字。

Answer 2

看看Text mining handbook

Answer 3

以下是迭代風格的解決方案（主要思想是將問題分解爲：在輸入的特定範圍內找到具有正確的1,2,3..n分段單詞的分割。請問是否存在任何次要索引錯誤，這些天我的頭很模糊，但這對你來說是一個迭代的解決方案。）：

static List<String> connectIter(List<String> tokens) { 

    // use instead of array, the key is of the from 'int int' 
    Map<String, List<String>> data = new HashMap<String, List<String>>(); 

    int n = tokens.size(); 

    for(int i = 0; i < n; i++) { 
     String str = concat(tokens, i, n); 
     if (dictContains(str)) { 
      data.put(1 + " " + i, Collections.singletonList(str)); 
     } 
    } 

    for (int i = 2; i <= n; i++) { 
     for (int start = 0; i < n; start++) { 
      List<String> solutions = new ArrayList<String>(); 
      for (int end = start + 1; end <= n - i + 1; end++) { 
       String firstPart = concat(tokens, start, end); 

       if (dictContains(firstPart)) { 
        List<String> partialSolutions = data.get((i - 1) + " " + end); 
        if (partialSolutions != null) { 
         List<String> newSolutions = new ArrayList<>(); 
         for (String onePartialSolution : partialSolutions) { 
          newSolutions.add(firstPart + " " 
            + onePartialSolution); 
         } 
         solutions.addAll(newSolutions); 
        } 
       } 
      } 

      if (solutions.size() != 0) { 
       data.put(i + " " + start, solutions); 
      } 
     } 
    } 

    List<String> ret = new ArrayList<String>(); 
    for(int i = 1; i <= n; i++) { // can be optimized to run with less iterations 
     List<String> solutions = data.get(i + " " + 0); 
     if (solutions != null) { 
      ret.addAll(solutions); 
     } 
    } 

    return ret; 
} 


static private String concat(List<String> tokens, int low, int hi) { 
    StringBuilder sb = new StringBuilder(); 
    for(int i = low; i < hi; i++) { 
     sb.append(tokens.get(i)); 
    } 
    return sb.toString(); 
} 

Answer 4

Python wordsegment module有這樣一個算法。它使用遞歸和記憶來實現動態編程。

來源是可在Github，這裏的相關片段：

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 

注memo緩存如何調用search這又選擇從candidates最大。