Aho-Corasick算法在全词匹配上的应用？

Question

我正在使用Aho-Corasick文本匹配算法，想知道是否可以更改以匹配“术语”而不是字符。换句话说，我希望将术语作为匹配的基础，而不是字符。例如：

搜索查询：“He”，

句子：“Hello world”，

Aho-Corasick将在索引2处将“he”与句子“hello world”匹配，但我希望没有匹配。因此，我的意思是“术语”指单词而不是字符。

- DotNet

---

“terms”是什么意思？你能举个例子吗？ - templatetypedef

Answer 1

一种方法是通常使用Aho-Corasick算法，然后执行过滤步骤以消除所有误报。例如，每次找到匹配时，您可以确认输入中的下一个和上一个字符是否为非字母字符，如空格或标点符号。这样，您就可以获得Aho-Corasick查找的速度，但仅考虑作为整个单词出现在文本中的匹配项。

希望这有所帮助！

- templatetypedef

---

这就是我所想的，但是在检查下一个字母时很简单，而在UTF-8编码的字符串中检查前一个字母实际上相当复杂，因为你不能只退回一个字节，而必须考虑到该前一个字符的完整可变长度编码。 - FGM

Answer 2

一种可能的方法是将空格字符包含在您的搜索项中，可能需要对输入进行预处理以将各种空白（空格、换行、回车、制表符等）转换为相同的空格字符。

另一种可能性是，就Aho-Corasick算法而言，将字母表中的字符视为单词。使用大小为2^32的字母表，在输入文本中看到的每个单词都编码为一个单一字符，与使用大小为2^8的字母表不同，其中一个字符通常只是一个字节，Aho-Corasick将像之前一样快速地工作（如果不是更快）。

在任何一种情况下，您都必须决定预处理过程对标点符号的处理方式。

- mcdowella

Answer 3

如果你只使用方法onlyWholewords()，那么对于你上面的例子将不会有任何结果。 例如：

Trie trie = Trie.builder()
             .onlyWholeWords()
             .addKeyword("He")
             .build();
Collection<Emit> emits = trie.parseText("Hello World");

在这种情况下，emits将为空。

它只会产生整个单词，即“he”。

尽管如此，请注意不是[a-z A-Z]的字符。例如，如果您：

"He//Is" 

它会捕获"He"并忽略"//"

添加两个内容：

1. 如果您想断言单词边界，可以使用：

   onlyWholeWordsWhiteSpaceSeparated() 而不是

   onlyWholeWords()

2. 如果您想“白名单”一些字符，则此 read 可能有所帮助：

使用的单词字符是默认字符集修改后的字符，并且布尔标志指示字符的开启和关闭状态。当您只想关闭默认字符集中的特定字符时，这非常有用。例如：

使用的单词字符是默认字符集修改后的字符，并且布尔标志指示字符的开启和关闭状态。当您只想关闭默认字符集中的特定字符时，这非常有用。例如：

new WholeWordMatchSet(keywords, true, ['_', '='], [false, true])

将生成一个集合，其中字母、数字、-和=被视为单词字符，但不包括_。

- HBizzle

Answer 4

很晚才参加派对，但另一个选项是将一些表示单词开头和结尾的符号插入到 trie 中。然后，在匹配阶段，它们必须相应地匹配。我正准备尝试这种方法。

- Edward Falk