Aho-Corasick 2.0

Aho-Corasick 2.0

×

由 Francesco 维护。

Aho-Corasick 2.0

  • 作者
  • Francesco Perrotti-Garcia

Swift 中的 Aho-Corasick 算法

CI Status Version License Platform

介绍

如今，大多数免费文本搜索都是基于类似于 Lucene 的方法，搜索文本被解析成各个组件。对每个关键词进行查找以查看其出现的位置。当寻找一两个关键词时，这种方法很好。但是，如果您寻找的不是一两个关键词，而是 100,000 个关键词呢？比如，检查一个字典吗？

这就是 Aho-Corasick 算法大放异彩的地方。它不将搜索文本拆分，而是使用所有关键词构建一个称为 Trie 的结构。Aho-Corasick 有三个关键组件

  • goto
  • fail
  • output

遇到的每个字符都会提供给 goto 结构中的状态对象。如果有匹配的状态，它将被提升为新的当前状态。

然而，如果没有匹配的状态，算法将触发 fail 信号、并回退到深度更浅的状态（即更短的匹配），然后从那里继续，直到找到匹配的状态或达到根状态。

当达到匹配整个关键词的状态时，它会被发射到一个输出集合中，这个集合可以在整个扫描完成后被读取。

该算法的美丽之处在于它是 O(n)。无论您有多少关键字母表，或者搜索文本有多大，性能将以线性方式下降。

您可以使用 Aho-Corasick 算法的示例

  • 在文本中查找某些单词以对 URL 链接或强调它们
  • 为纯文本添加语义
  • 与字典检查以查看是否犯了语法错误

此库是实现上述 Aho-Corasick 算法的 Swift 库，用于高效的字符串匹配。算法在 Aho 和 Corasick 编写的白皮书中进行了详细解释：[http://cr.yp.to/bib/1975/aho.pdf](http://cr.yp.to/bib/1975/aho.pdf)

使用方法

设置Trie非常简单

    let trie = Trie.builder()
        .add(keyword: "hers")
        .add(keyword: "his")
        .add(keyword: "she")
        .add(keyword: "he")
        .build()
        
    let emits = trie.parse(text: "ushers")

现在可以读取集合。在这种情况下，它会找到以下内容

  • "she" 开始位置1，结束位置3
  • "he" 开始位置2，结束位置3
  • "hers" 开始位置2，结束位置5

在正常情况下，你可能会想要移除重叠实例，保留最长和左对齐的匹配。

    let trie = Trie.builder()
        .removeOverlaps()
        .add(keyword: "hot")
        .add(keyword: "hot chocolate")
        .build()
    let emits = trie.parse(text: "hot chocolate")

removeOverlaps方法告诉Trie移除所有重叠匹配。为此，它依赖于以下冲突解决规则：1) 更长的匹配胜过更短的匹配，2) 左边的胜过右边的。现在只有一个结果。

  • "hot chocolate" 开始位置0，结束位置12

如果您希望算法仅检查分隔（完整）单词，可以指示Trie这样做

    let trie = Trie.builder()
        .onlyDelimited()
        .add(keyword: "sugar")
        .build()
    let emits = trie.parse(text: "sugarcane sugarcane sugar canesugar")

在这种情况下，它只会找到一个匹配项，而通常会有四个。sugarcane/canesugar单词被丢弃，因为它们是部分匹配。onlyDelimited()使用TR#29定义的单词边界。

有些文本是混合小写和大写的，因此很难识别。您可以安排Trie将整个searchText转换为小写以简化匹配过程。小写扩展到关键词。

    let trie = Trie.builder()
        .caseInsensitive()
        .add(keyword: "casing")
        .build()
    let emits = trie.parse(text: "CaSiNg")

通常，这种匹配不会找到。在caseInsensitive设置下，在开始匹配之前将整个搜索文本全部转换为小写。因此，它将找到一个确切匹配项。由于您仍然控制原始搜索文本并且确切知道匹配位置，您仍然可以使用原始大小写。

还有选择性地在搜索时忽略重音符号。当处理具有重音符号的语言时，如法语、葡萄牙语、西班牙语、德语、捷克语、意大利语等，这很有用。

    let trie = Trie.builder()
        .diacriticInsensitive()
        .add(keyword: "café")
        .build()
    let matches = trie.containsMatch(text: "je bois du cafe tous les matins")

也有可能仅询问文本是否与任何关键词匹配，或者仅返回找到的第一个匹配项。

     let trie = Trie.builder()
            .removeOverlaps()
            .add(keyword: "ab")
            .add(keyword: "cba")
            .add(keyword: "ababc")
            .build()
    let firstMatch = trie.firstMatch(text: "ababcbab")

firstMatch现在将是位于位置0的"ababc"。containsMatch仅检查是否存在第一个匹配项，并在存在时返回true。

在许多情况下，你可能想要对非匹配和匹配的文本都做些有用的事情。在这种情况下，你可能最好使用Trie.tokenize()。它允许你遍历整个文本，并在遇到它们时立即处理匹配项。让我们看一个例子，我们想要在HTML中突出显示HGttG中的单词

    let speech = "The Answer to the Great Question... Of Life, " +
            "the Universe and Everything... Is... Forty-two,' said " +
            "Deep Thought, with infinite majesty and calm."
    let trie = Trie.builder()
        .removeOverlaps()
        .onlyDelimited()
        .caseInsensitive()
        .add(keyword: "great question")
        .add(keyword: "forty-two")
        .add(keyword: "deep thought")
        .build()
    let tokens = trie.tokenize(text: speech)
    var html = ""
    html.append("<html><body><p>")
    for token in tokens {
        if token.isMatch {
            html.append("<i>")
        }
        html.append(token.fragment)
        if token.isMatch {
            html.append("</i>")
        }
    }
    html.append("</p></body></html>")
    print(html)

许可证

根据Apache许可证版本2.0（“许可证”）授权；除非遵守许可证，否则不得使用此文件。您可以在以下位置获取许可证副本：

https://apache.ac.cn/licenses/LICENSE-2.0

除非适用法律要求或者以书面形式同意，否则在许可证下分发的软件均按“现状”分发，不提供任何形式（明示或暗示）的保证或条件。有关许可证中的具体语言、许可权限和限制，请参阅许可证。

鸣谢

灵感来源于 robert-bor/aho-corasick