One-Gapped q-Gram Filters for Levenshtein Distance

Burkhardt, Stefan; Kärkkäinen, Juha; Apostolico, Alberto; Takeda, Masayuki

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

One-Gapped q-Gram Filters for Levenshtein Distance

MPS-Authors

/persons/resource/persons44209

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

/persons/resource/persons44717

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

Apostolico, Alberto
Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

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: https://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.