Abstract | ||
---|---|---|
We study the pattern matching automaton introduced in (1) for the purpose of seed-based similarity search. We show that our definition provides a compact automaton, much smaller than the one obtained by applying the Aho-Corasick construction. We study properties of this automaton and present an efficient implementation of the automaton construction. We also present some experimental results and show that this automaton can be successfully applied to more general situations. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-540-76336-9_18 | CIAA'13 Proceedings of the 18th international conference on Implementation and Application of Automata |
Keywords | Field | DocType |
automaton construction,efficient implementation,compact automaton,seed sensitivity.,subset seed automaton,subset seed,general situation,automaton,aho-corasick construction,spaced seed,seed-based similarity search,pattern matching,similarity search,aho corasick | Computer science,Automaton,Levenshtein automaton,Algorithm,Theoretical computer science,Pattern matching,Nearest neighbor search | Journal |
Volume | ISSN | ISBN |
abs/1408.6198 | LNCS 4783 (2007), pp 180-191 | 3-540-76335-X |
Citations | PageRank | References |
5 | 0.41 | 20 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gregory Kucherov | 1 | 1003 | 74.54 |
Laurent Noé | 2 | 230 | 13.94 |
Mikhail A. Roytberg | 3 | 114 | 54.66 |