algorithm - 将字符串拆分为单词

Question

我正在寻找最有效的算法来从一个字符串中形成所有可能的单词组合。例如:

Input String: forevercarrot

Output:

forever carrot
forever car rot
for ever carrot
for ever car rot

(所有单词都应该来自字典)。

我能想到一种蛮力方法。 (找到所有可能的子串并匹配)但是什么是更好的方法？

Answer 1

使用 prefix tree为您的已知单词列表。可能像 myspell 这样的库已经这样做了。尝试使用现成的。

找到匹配项(例如“汽车”)后，拆分您的计算:一个分支开始寻找新词(“rot”)，另一个分支继续探索当前开头的变体(“carrot”)。

实际上，每次拆分计算时，您都会在字符串中维护一对 (start_position, current_position) 偏移量队列。多个线程可以并行地从这个队列中弹出，并尝试继续从 start_position 开始并且已知到该对的 current_position 的单词，但不会在那里结束。当找到一个词时，它会被报告并从队列中弹出另一对。如果不可能，则不会生成任何结果。当发生 split 时，一个新的对被添加到队列的末尾。最初队列包含一个 (0,0)。