Java Aho-Corasick 字符串匹配算法的实现？

Question

现在我知道以前有过关于此算法的问题，但老实说我还没有遇到过简单的 java 实现。许多人在他们的 GitHub 个人资料中复制并粘贴了相同的代码，这让我很恼火。

因此，出于面试练习的目的，我计划使用不同的方法来制定和实施算法。

该算法往往非常具有挑战性。老实说，我不知道该怎么做。逻辑只是没有意义。我几乎花了 4 天的时间来勾画这个方法，但无济于事。

所以请您用您的智慧开导我们。

我主要是根据这些信息做算法Intuition behind the Aho-Corasick string matching algorithm

如果能在这里实现自己的解决方案，那就太好了。

但以下是我真正陷入困境的不完整且无效解决方案：

如果您对代码不知所措，那么主要问题出在 Aho-Corasick 的主要算法上。我们已经很好地创建了字典树。

但问题是，现在我们有了 trie 结构，我们如何真正开始实施。

None 的资源很有帮助。

public class DeterminingDNAHealth {
  private Trie tree;
  private String[] dictionary;
  private Node FailedNode;


  private DeterminingDNAHealth() {

  }

  private void buildMatchingMachine(String[] dictionary) {
    this.tree = new Trie();
    this.dictionary = dictionary;

    Arrays.stream(dictionary).forEach(tree::insert);

  }

  private void searchWords(String word, String[] dictionary) {

    buildMatchingMachine(dictionary);

    HashMap < Character, Node > children = tree.parent.getChildren();

    String matchedString = "";

    for (int i = 0; i < 3; i++) {
      char C = word.charAt(i);

      matchedString += C;

      matchedChar(C, matchedString);

    }

  }

  private void matchedChar(char C, String matchedString) {


    if (tree.parent.getChildren().containsKey(C) && dictionaryContains(matchedString)) {

      tree.parent = tree.parent.getChildren().get(C);

    } else {

      char suffix = matchedString.charAt(matchedString.length() - 2);

      if (!tree.parent.getParent().getChildren().containsKey(suffix)) {
        tree.parent = tree.parent.getParent();

      }


    }
  }

  private boolean dictionaryContains(String word) {

    return Arrays.asList(dictionary).contains(word);

  }


  public static void main(String[] args) {

    DeterminingDNAHealth DNA = new DeterminingDNAHealth();

    DNA.searchWords("abccab", new String[] {
      "a",
      "ab",
      "bc",
      "bca",
      "c",
      "caa"
    });


  }
}

我已经设置了一个工作正常的 trie 数据结构。所以这里没问题

trie.java

public class Trie {
  public Node parent;
  public Node fall;

  public Trie() {
    parent = new Node('⍜');
    parent.setParent(new Node());
  }

  public void insert(String word) {...}

  private boolean delete(String word) {...}

  public boolean search(String word) {...}

  public Node searchNode(String word) {...}

  public void printLevelOrderDFS(Node root) {...}

  public static void printLevel(Node node, int level) {...}

  public static int maxHeight(Node root) {...}

  public void printTrie() {...}

}

Node 也一样。

Node.java

public class Node {

  private char character;
  private Node parent;
  private HashMap<Character, Node> children = new HashMap<Character, Node>();
  private boolean leaf;

  // default case
  public Node() {}

  // constructor accepting the character
  public Node(char character) {
    this.character = character;
  }

  public void setCharacter(char character) {...}

  public char getCharacter() {...}

  public void setParent(Node parent) {...}

  public Node getParent() {...}

  public HashMap<Character, Node> getChildren() {...}

  public void setChildren(HashMap<Character, Node> children) {...}

  public void resetChildren() {...}

  public boolean isLeaf() {...}

  public void setLeaf(boolean leaf) {...}
}

Answer 1

您不会通过阅读一些源代码来很好地理解 Aho-Corasick string matching algorithm。而且你不会找到一个简单的实现，因为算法是非平凡的。

原论文Efficient String Matching: An Aid to Bibliographic Search写得很好，很平易近人。我建议你下载那个 PDF，仔细阅读，想一想，然后再读一遍。学习论文。

您可能还会发现阅读其他人对算法的描述很有用。有很多很多带有文字说明、图表、Powerpoint 幻灯片等的页面。

您可能希望在尝试实施之前至少花一两天时间研究这些资源。因为如果您在没有完全理解其工作原理的情况下尝试实施它，您将会迷失方向，而您的实施将显示它。该算法并不十分简单，但非常容易理解。

如果您只需要一些代码，这里有一个很好的实现：https://codereview.stackexchange.com/questions/115624/aho-corasick-for-multiple-exact-string-matching-in-java。

Answer 2

我通常每隔一年教授一门高级数据结构课程，在探索字符串数据结构时，我们会介绍 Aho-Corasick 自动机。有幻灯片 here 展示了如何通过优化几个较慢的算法来开发算法。

一般来说，我会将实施分为四个步骤：

构建 trie。 Aho-Corasick 自动机的核心是一个带有一些额外箭头的 trie 树。算法的第一步是构建这个 trie 树，好消息是这就像常规的 trie 树构建一样进行。事实上，我建议只执行这一步，假装你只是在做一个尝试，而不做任何事情来预测后面的步骤。
添加后缀（失败）links。算法中的这一步添加了重要的失败 links，匹配器在遇到无法用于跟随 trie 边的字符时使用它。我在 linked 讲座幻灯片中对这些工作的最佳解释。该算法的这一步是作为遍历 trie 的广度优先搜索来实现的。在编写此代码之前，我建议您手动完成几个示例，以确保您了解一般模式。一旦你这样做了，编写代码就不是特别棘手了。然而，在没有完全了解其工作原理的情况下尝试对其进行编码将使调试成为一场噩梦！
添加输出 links。此步骤是您添加 links 的地方，用于报告在 trie 中的给定节点处匹配的所有字符串。它是通过对 trie 进行第二次广度优先搜索来实现的，而且我对它的工作原理的最好解释是在幻灯片中。好消息是，这一步实际上比后缀 link 构造更容易实现，因为您将更熟悉如何进行 BFS 以及如何遍历 trie。再次重申，除非您可以轻松地手动完成，否则不要尝试对此进行编码！您不需要最小代码，但您不想在调试您不理解的高级行为的代码时卡住。
实现匹配器。这一步还不错！您只需沿着 trie 树从输入中读取字符，在每一步输出所有匹配项，并在遇到问题且无法向下推进时使用失败 links。

我希望这能为您提供更加模块化的任务分解，并提供有关整个流程应该如何运作的参考。祝你好运！

Java Aho-Corasick 字符串匹配算法的实现？

Java implementation of Aho-Corasick string matching algorithm?

java

algorithm

data-structures

trie

aho-corasick