3 java algorithm trie data-structures aho-corasick
现在我知道之前有关于这个算法的问题，但是老实说我还没有遇到一个简单的 java 实现。许多人在他们的 GitHub 个人资料中复制粘贴了相同的代码，这让我很恼火。
因此，出于面试练习的目的，我计划使用不同的方法来制定和实施算法。
该算法往往非常具有挑战性。老实说，我不知道如何去做。只是逻辑说不通。我几乎花了 4 天的时间来描绘这种方法，但无济于事。
因此，请用您的智慧启发我们。
我主要是根据这些信息做算法 Intuition behind the Aho-Corasick string matching algorithm
如果可以在这里实施他们自己的解决方案，那将是一个很大的好处。
但这是我真正陷入困境的以下不完整且无效的解决方案：
如果您对代码感到不知所措，那么主要问题在于 Aho-Corasick 的主要算法。我们已经很好地创建了字典树。
但问题是，既然我们有了 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"
});
}
}我已经设置了一个可以正常工作的特里数据结构。所以这里没问题
树.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() {...}
}节点也是一样。
节点.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) {...}
}我通常每隔一年教一门关于高级数据结构的课程，在探索字符串数据结构时我们会介绍 Aho-Corasick 自动机。有可用的幻灯片这里展示了如何通过优化几个较慢的开发的算法。
一般来说，我会将实现分为四个步骤：
构建特里。Aho-Corasick 自动机的核心是一个带有一些额外箭头的特里树。算法的第一步是构建这个特里树，好消息是这就像常规的特里树构造一样进行。事实上，我建议只执行这一步，假装你只是在做一个尝试，而不做任何事情来预测后面的步骤。
添加后缀（失败）链接。算法中的这一步添加了重要的失败链接，匹配器在遇到无法用于跟踪特里边缘的字符时使用这些链接。我对这些工作方式的最佳解释是在链接的讲座幻灯片中。该算法的这一步被实现为遍历树的广度优先搜索。在您编写此代码之前，我建议您手工完成几个示例，以确保您获得一般模式。一旦你这样做了，这对编码来说并不是特别棘手。但是，在没有完全了解其工作原理的情况下尝试对其进行编码将使调试成为一场噩梦！
添加输出链接。在此步骤中，您可以添加用于报告在树中的给定节点处匹配的所有字符串的链接。它是通过对特里树进行第二次广度优先搜索来实现的，同样，我对其工作原理的最佳解释是在幻灯片中。好消息是，这一步实际上比后缀链接构建更容易实现，因为您将更熟悉如何进行 BFS 以及如何上下搜索。同样，除非您可以轻松地手动完成，否则不要尝试编写代码！您不需要最小代码，但您不想在调试您不了解其高级行为的代码时陷入困境。
实现匹配器。这一步还不错！您只需从输入中读取字符，在每一步输出所有匹配项，并在卡住且无法向下推进时使用失败链接。
我希望这能给你一个更模块化的任务分解和关于整个过程应该如何工作的参考。祝你好运！
通过阅读一些源代码，您不会很好地理解Aho-Corasick 字符串匹配算法。而且你不会找到一个微不足道的实现，因为该算法是非微不足道的。
原论文，高效的字符串匹配：书目搜索的帮助，写得很好，很平易近人。我建议你下载那个PDF，仔细阅读，想一想，然后再读一遍。研究论文。
您可能还会发现阅读其他人对该算法的描述很有用。有很多很多带有文字说明、图表、Powerpoint 幻灯片等的页面。
在尝试实施这些资源之前，您可能希望至少花一两天时间研究这些资源。因为如果你在没有完全理解它是如何工作的情况下尝试实现它，你将会迷失方向，而你的实现会显示它。该算法并不完全简单，但非常平易近人。
如果您只想要一些代码，这里有一个很好的实现：https : //codereview.stackexchange.com/questions/115624/aho-corasick-for-multiple-exact-string-matching-in-java。