如何从混乱的单词中找到单词

Question

我正试图找到一种方法来查找连续出现的加扰文本中的特定单词.未找到的字符将具有X到位.

例如,假设字典单词列表是:

jane
john
brownbag
foo
youth

和乱码文字:

ofozlhuoyt => fooXXyouth
yuawbnrobgajen => XXbrownbagjane
janjeohn => (nothing since jane and john aren't consecutive)

方法我正在尝试:

我说,我有钥匙的哈希a通过z与设定为每个键的值.集合中的每个数字将表示包含特定字符的单词的索引.

从上面的例子:

{a: [0,2]}
{b: [2]}
{c: []}
{e: [0]}
{f: [3]}
{g: [2]}
{h: [1,4]}
{j: [0,1]}
...
{n: [0,1,2]}
{o: [1,2,3,4]}
{r: [2]}
{u: [4]}
{t: [4]}
{w: [2]}
{y: [4]}
...
{z: []} 

在准备好上述内容之后,我们可以开始查看加扰文本的每个字符:

第一串: ofozlhuoyt

1. o =>存在于1,2,3和4中

2. 从1开始:jane(长度4)

3. 获得4个字符: ofoz

4. "jane".sort(false) == "ofoz".sort(false)?

5. 如果为假:重复步骤1到3为2(约翰)

6. 如果为true:将foo添加到好词列表中并使用开始步骤0 z

有没有更好的方法呢？我觉得有一个更好的数据结构来解决这样的事情,但我无法弄清楚使用哪个..

Answer 1

有一种可能更快的方法，只要您有足够的内存来实现它。

首先，生成每个单词的所有排列。所以对于“jane”你会有：

aejn
aenj
ajen
ajne
anej
anje
etc.

然后，为Aho-Corasick 算法构建一个状态机，单个单词的每个排列都进入相同的结束状态。该结束状态将输出您正在查找的字符串。

现在通过状态机运行文本。输出将是找到的单词及其位置。然后，您可以按位置对找到的单词进行排序并确定它们是否连续出现。

状态机可能非常大（每个单词有 n！个状态，其中 n 是单词中的字符数），并且需要一些时间来构建。但一旦建成，它的匹配速度非常快。如果您的单词列表是静态的并且您有大量文本需要搜索，那么这就是正确的选择。前提是你有足够的内存。

我使用了改进的 Aho-Corasick 算法，该算法在文本中搜索视频标题中出现的数百万个短语（乐队和歌曲名称）。状态机占用了大约10GB的RAM，构建花费了大约一个小时，但在匹配方面速度很快。