Python中文网

一个关于 编程问题的解答网站.

有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

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

4 月，1 周 Questions & Answers

现在我知道之前有关于这个算法的问题，但是我真的没有遇到一个简单的java实现。许多人在他们的GitHub配置文件中复制并粘贴了相同的代码，这让我很恼火

因此，为了进行面试练习，我计划使用不同的方法来制定和实施算法

算法往往非常具有挑战性。我真的不知道该怎么做。这种逻辑根本没有道理。我花了将近4天的时间画出了这个方法，但都没有用

因此，请用你的智慧来启发我们

我主要是根据这些信息^{}来做算法

如果能在这里实现自己的解决方案，那将是一个巨大的好处

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

如果你对代码过于熟悉，主要问题在于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" }); } }

我已经设置了一个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也是一样

节点。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) {...} }
Tags:  

共 (2) 个答案

  1. # 1 楼答案

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

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

    1. 建造trie。阿霍·科拉西克（Aho Corasick）自动机的核心是一个带有额外箭头的trie。算法的第一步是构造这个trie，好消息是，这就像常规的trie构造一样进行。事实上，我建议通过假装你只是在做一个trie来实现这个步骤，而不做任何事情来预测后面的步骤

    2. 添加后缀（失败）链接。算法中的这一步添加了重要的失败链接，匹配器在遇到无法用于跟踪trie边缘的字符时使用这些链接。我对这些工作的最好解释是在链接的课堂幻灯片中。该算法的这一步是在trie上进行广度优先搜索。在编写这篇文章之前，我建议您先手动完成几个示例，以确保获得一般模式。一旦这样做了，编写代码就不是特别棘手了。然而，试图在不完全了解其工作原理的情况下编写代码将使调试成为一场噩梦

    3. 添加输出链接。这一步是添加链接，用于报告trie中给定节点上匹配的所有字符串。它是通过第二次广度优先搜索在trie上实现的，同样，我对它如何工作的最好解释是在幻灯片中。好消息是，这一步实际上比后缀链接构造简单得多，因为你将更熟悉如何进行BFS，以及如何在trie上下移动。再次强调，除非你能轻松地用手操作，否则不要尝试编写代码！你不需要min代码，但你不想被困在调试你不理解其高级行为的代码中

    4. 实现匹配器。这一步还不错！你只需沿着trie往下走，读取输入中的字符，在每一步输出所有匹配项，并在遇到卡滞且无法向下推进时使用失败链接

    我希望这能给你提供一个更模块化的任务分解，以及整个过程应该如何工作的参考。祝你好运

  2. # 2 楼答案

    阅读一些源代码并不能很好地理解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