最有效的分詞算法？

我一直在尋找一種高效的分詞算法，但沒有取得太大的成功。例如，給出單詞hello，我希望獲得該單詞的所有可能分區：{h，e，l，l，o}，{h，e，l，lo}，{h，e，llo} ,. ..，{你好}。我發現的所有關於分詞的討論都不是我的意思。最有效的分詞算法？

預先感謝您！

2011-03-19 jarandaf

您將展示一些示例，我們可以將注意力集中在逗號上。要麼有逗號，要麼沒有。

Word  Commas 
{h,e,l,l,o} 1111 
{h,e,l,l o} 1110 
{h,e,l l o} 1100 
... 
{h e l l o} 0000

所以看起來很明顯，在4個位置上，可能有逗號或不逗號，彼此獨立。你需要4位編碼的分區，這是2^4點的可能性，我想這是16

這樣你就可以形成一個循環：

for (int i = 0; i < 15; ++i) 
    bitsplit ("hello", i);

，並通過你的話重複而遍歷位的二進制表示。例如對於11，您有位：8 + 2 + 1 = 1011設置。這意味着{h，el，l，o}。

2011-03-19 09:31:36

很好！ – Dunaril 2011-03-19 10:44:43

非常感謝！似乎事情比我們預期的要簡單:)我得到它運行;） – jarandaf 2011-03-19 11:20:13

問題是NP完整，需要通過回溯來解決。

這個想法是在每個級別，你決定這個角色是屬於當前分區還是應該去一個新的。以遞歸方式進行此操作，並且每次達到該單詞的結尾時，都有一個分區。

2011-03-19 09:14:35

我不這麼認爲。您可以定義所有解決方案的枚舉，並如上所示進行翻譯。 – 2011-03-19 09:32:50

你提到的會有相同的複雜性:)。但是的確如此，你的方法更好。 – 2011-03-19 09:36:57

這不是NP完整的。你可能的意思是它需要指數時間的輸入大小，這是可以理解的，看看輸出的大小如何在輸入大小上同樣呈指數形式。 – 2011-03-19 17:38:22

大多數喜歡你想構造一個後綴-tree。

2011-03-19 10:47:02 Bytemain

回答