将字符串分割成单词 [英] Split string into words
问题描述
我正在寻找最有效的算法来形成字符串中所有可能的单词组合。例如:
I am looking for the most efficient algorithm to form all possible combinations of words from a string. For example:
Input String: forevercarrot
Output:
forever carrot
forever car rot
for ever carrot
for ever car rot
(所有单词应来自字典)。
(All words should be from a dictionary).
我可以想到一个强力的方法。 (找到所有可能的子字符串和匹配),但是什么是更好的方法?
I can think of a brute force approach. (find all possible substrings and match) but what would be better ways?
推荐答案
使用前缀树为您的已知单词列表。可能像 myspell
这样的libs已经这么做了。尝试使用一个现成的一个。
Use a prefix tree for your list of known words. Probably libs like myspell
already do so. Try using a ready-made one.
一旦你找到一个匹配(例如'car'),拆分你的计算:一个分支开始寻找一个新单词('腐烂'),另一个继续探索当前开始('胡萝卜')的变体。
Once you found a match (e.g. 'car'), split your computation: one branch starts to look for a new word ('rot'), another continues to explore variants of current beginning ('carrot').
有效地保持一对队列(start_position,current_position )
在您的字符串中每次拆分计算时的偏移量。几个线程可以并行从该队列弹出,并尝试继续从 start_position
开始的单词,并且已经知道最多 current_position
对,但不会在那里结束。当找到一个单词时,它被报告,另一对从队列中弹出。当不可能的时候,不会产生结果。当发生拆分时,将在队列的末尾添加一对新对。最初队列包含一个(0,0)
。
Effectively you maintain a queue of pairs (start_position, current_position)
of offsets into your string every time you split the computation. Several threads can pop from this queue in parallel and try to continue a word that starts from start_position
and is already known up to current_position
of the pair, but does not end there. When a word is found, it is reported and another pair is popped from the queue. When it's impossible, no result is generated. When a split occurs, a new pair is added to the end of the queue. Initially the queue contains a (0,0)
.
这篇关于将字符串分割成单词的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!