動態規劃分詞

-1

假設我有一個像'meetateight'這樣的字符串，我需要使用動態規劃將它分成有意義的單詞，如''八'''見面''。動態規劃分詞

要判斷一個塊/段「x = x1x2x3」是多麼「好」，我給出了一個黑盒子，在輸入x上返回一個實數質量（x），使得：質量的正值很大（x）表示x接近英文單詞，而大負數表示x與英文單詞很遠。

我需要幫助設計一個相同的算法。

我試着考慮一個算法，在這個算法中，當質量下降時，我會根據它們的質量和段迭代地添加字母。但是這在上面的例子中失敗了，因爲它切斷了我而不是見面。

我需要一個更好的算法的建議。

感謝

來源

2012-11-09 parth

[將字符串拆分爲使用動態編程的有效字符串]（http://stackoverflow.com/questions/5310756/split-a-string-to-a-string-of-valid-words -using-dynamic-programming） – Woot4Moo

此問題已被提問。 – Woot4Moo

什麼用英語詞典建設Trie和導航下來與所有可能的路徑葉掃描您的字符串（回溯，當你有一個以上的選擇）。

來源

2012-11-09 13:35:10

-1

我寫了一個程序來做到這一點在my blog;包含在這裏太長了。基本思想是刪除形成單詞的前綴，然後遞歸處理其餘的輸入，當不能分割整個字符串時回溯。

來源

2012-11-09 13:43:03 user448810

您可以使用動態編程，並跟蹤每個輸入前綴的分數，一次添加一個字母。每次添加一個字母時，請查看是否可以將任何後綴添加到已使用的前綴（選擇具有最佳分數的前綴）。例如：

m = 0 
me = 1 
mee = 0 
meet = 1 
meeta = 1 (meet + a) 
meetat = 1 (meet + at) 
meetate = 1 (meet + ate) 
meetatei = 1 (meetate + i) 
meetateig = 0 
meetateigh = 0 
meetateight = 1 (meetat + eight)

0和1之間的值，就可以一起將它們相乘。同時保存你已經使用過的單詞，這樣你就可以在最後分割整個字符串。

來源

2012-11-09 13:45:59 fgb

動態規劃分詞

回答

相關問題