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

Question

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

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

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

所以请用您的智慧启发我们。

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

如果能在这里实现他们自己的解决方案，那将是一个很大的收获。

但这是我真正陷入困境的以下不完整且不起作用的解决方案:

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

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

没有任何资源有帮助。

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

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

一般来说，我会将实现分为四个步骤:

1. 构建 trie。 Aho-Corasick 自动机的核心是一个带有一些额外箭头的 trie 树。算法的第一步是构建这个 trie 树，好消息是这就像常规的 trie 树构建一样进行。事实上，我建议只执行这一步，假装你只是在尝试，而不做任何事来预测后面的步骤。

2. 添加后缀(失败)链接。算法中的这一步添加了重要的失败链接，匹配器在遇到无法用于跟随 trie 边的字符时使用这些链接。我对这些工作原理的最佳解释是在链接的讲座幻灯片中。该算法的这一步是作为遍历 trie 的广度优先搜索来实现的。在编写此代码之前，我建议您手动完成几个示例，以确保您了解一般模式。一旦你这样做了，编写代码就不是特别棘手了。然而，在没有完全了解其工作原理的情况下尝试对其进行编码将使调试成为一场噩梦!

3. 添加输出链接。此步骤是您添加链接的地方，这些链接用于报告在 trie 中的给定节点处匹配的所有字符串。它是通过对 trie 进行第二次广度优先搜索来实现的，而且我对它的工作原理的最好解释是在幻灯片中。好消息是，这一步实际上比后缀链接构造更容易实现，因为您会更熟悉如何进行 BFS 以及如何遍历 trie。再次重申，除非您可以轻松地手动完成，否则不要尝试对此进行编码!您不需要最小代码，但您不想在调试您不理解其高级行为的代码时卡住。

4. 实现匹配器。这一步还不错!您只需沿着 trie 树从输入中读取字符，在每一步输出所有匹配项，并在遇到困难且无法向下推进时使用失败链接。

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