我在理解Haskell中的Knuth-Morris-Pratt算法的实现时遇到了麻烦.
http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell
特别是我不了解自动机的结构.我知道它使用"绑结"方法来构造它,但我不清楚,我也不知道为什么它应该具有正确的复杂性.
我想知道的另一件事是你是否认为这个实现可以很容易地推广到实现Aho-Corasick算法.
谢谢你的回答!
我想在一个文本文档中搜索关键短语数据库中出现的关键短语(从维基百科文章标题中提取).(即,给定一个文档,我想找出是否有任何短语都有相应的维基百科文章)我发现了Aho-Corasick算法.我想知道为数百万条目的字典构建Aho-Corasick自动机是否有效且可扩展.
我正在尝试理解aho-corasick字符串匹配算法.假设我们的模式是abcd和bc.我们最终得到了这样一棵树
[]
/\
[a]..[b]
/ : |
[b].: [c]
| :
[c].....
|
[d]
虚线表示故障功能.
现在假设我们输入字符串abcd.这将跟随树并检测匹配"abcd",但是,据我所知,匹配bc将不会被报告.我误解了算法吗？
在PHP中是否有Aho-Corasick的工作实现？维基百科文章中提到的PHP中有一个Aho-Corasick字符串匹配:
<?php
/*
This class performs a multiple pattern matching by using the Aho-Corasick algorythm, which scans text and matches all patterns "at once".
This class can:
- find if any of the patterns occours inside the text
- find all occourrences of the patterns inside the text
- substitute all occourrences of the patterns with a specified string (empty as well)
Example of usage:
$words = array{ "ananas", "antani", "assassin" };
$pm = …是否有类似Aho-Corasick的算法,它可以同时匹配一组模式,适用于反恶意软件比较？所有已知的商业防病毒软件都使用Aho-Corasick算法吗？
与Boyer-Moore相比,Aho-Corasick算法有哪些优势？
我无法理解下面使用Aho-Corasick alg进行字符串模式匹配的算法.
Procedure AC(y,n,q0)
INPUT: y<-array of m bytes representing the text input
(SQL Query Statement)
n<-integer representing the text length
(SQL Query Length)
q0<-initial state (first character in pattern)
2: State <-q0
3: For i = 1 to n do
4: While g ( State, y[i] = = fail) do
5: State ? f (State)
6: End While
7: State ? g(State,.y[i])
8: If o(State) then
9: Output i
10: Else
11: Output
12: End If
13: End for …现在我知道之前有关于这个算法的问题，但是老实说我还没有遇到一个简单的 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 = ""; …我正在使用Aho-Corasick文本匹配,并想知道它是否可以更改为匹配术语而不是字符.换句话说,我希望条款成为匹配而不是字符的基础.举个例子:
搜索查询:"他",
句子:"你好世界",
Aho-Corasick将"he"与句号"hello world"匹配,但是我希望没有匹配.所以,我的意思是"术语"而不是字符.
java algorithm full-text-search string-matching aho-corasick