Content deleted Content added
fgrep not a good example |
Text should mention Rabin-Karp |
||
Line 18:
Not a great example. There were better algorithms for finding a single fixed string in text which fgrep could have used (eg, Knuth-Morris-Pratt). Remember that the strength of Aho-Corasick lies in finding a match for any of a large set of fixed strings in text; and this is not what fgrep does. Aho-Corasick was easily extended to implement Kleene's regular expressions and this extension is used in grep and egrep. So Aho-Corasick's use in fgrep was simply a case of ease of implementation. A virus scanner is by far the best example of the use of Aho-Corasick: in one sequential read of a file there is a set of many thousands of virus "signature" strings compared. [[User:Gdt|Gdt]] ([[User talk:Gdt|talk]]) 06:16, 10 August 2012 (UTC)
The text should also mention the Rabin-Karp algorithm with Bloom filters, as that is the major alternative to Aho-Corasick. The two algorithms have differing strengths and weaknesses, so one can't be recommended over the other. [[User:Gdt|Gdt]] ([[User talk:Gdt|talk]]) 06:24, 10 August 2012 (UTC)
== Visualization ==
| |||