0

我对 Aho-Corasick 算法的输出函数的实现有疑问。一般来说，我不太了解输出功能是如何工作的。根据这篇论文，在 goto 函数中，我将适当的模式索引放在输出中，就像output[currentState] = patternIndex; 在失败函数中一样，我将状态 S 的现有输出与失败状态 S 的输出合并，就像output[s] += output[fail[s]];在搜索函数中我使用这样的条件：if (output[state]) != 0) then we find our pattern. 但是这种方法不起作用并且我有胡说八道的结果。也许，输出函数的伪代码在那篇论文中还有其他含义，我不知道。

我在这里得到的具有按位映射的输出函数在大多数情况下也不能正常工作。错误的模式与此条件匹配if ((output[currentState] & (1 << j)) != 0) 此外，我不太明白为什么按位运算用于输出计算。

对于澄清输出功能的实现，我将不胜感激。

EDIT1：看来，这个问题是在移位操作后溢出： 到目前为止，尝试使用 BigInteger，但似乎它会导致性能问题output[currentState] |= (1 << i);。out[currentState] & (1 << j)

EDIT2：尝试了 BitSet，但性能仍然很差。也许，算法的实现有问题，我不知道。

4

1 回答 1

0

如下所示的 32 位按位运算

图案：he, she, his, hers

input: shethehishetheehershehehishe

总状态数为9，2, 5, 7, 9状态为最终状态，如下图 AC 自动化

输出函数表示您在当前状态下匹配的模式。喜欢 ：

out[2] = he, out[5] = she/he, out[7] = his, out[9] = hers

The code "out[currentState] |= (1 << i)" just like below 

out[2] = 0000 0000 0000 0000 0000 0010 <-- means number 1(he) pattern matched 

out[5] = 0000 0000 0000 0000 0000 0110 <-- means number 1(he) and number 2(she) matched

所以output[currentState] & (1 << j)用来计算匹配哪个模式。

这个操作就像 one-hot 编码一样。操作问题是输出函数的类型。如果输出函数类型是32位，我们最多只能搜索31模式。因为在31模式之上，它会因移位而溢出。

于 2017-08-08T07:03:00.507 回答