de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

One-Gapped q-Gram Filters for Levenshtein Distance

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44209

Burkhardt,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44717

Kärkkäinen,  Juha
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Apostolico,  Alberto
Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Burkhardt, S., & Kärkkäinen, J. (2002). One-Gapped q-Gram Filters for Levenshtein Distance. In Combinatorial Pattern Matching: 13th Annual Symposium, CPM 2002 (pp. 225-234). Berlin, Germany: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-300B-B
Abstract
We have recently shown that $q$-gram filters based on gapped $q$-grams instead of the usual contiguous $q$-grams can provide orders of magnitude faster and/or more efficient filtering for the Hamming distance. In this paper, we extend the results for the Levenshtein distance, which is more problematic for gapped $q$-grams because an insertion or deletion in a gap affects a $q$-gram while a replacement does not. To keep this effect under control, we concentrate on gapped $q$-grams with just one gap. We demostrate with experiments that the resulting filters provide a significant improvement over the contiguous $q$-gram filters. We also develop new techniques for dealing with complex $q$-gram filters.