Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

7 Citations (Scopus)

Abstract

In this article, we introduce a new and simple data structure, the prefix table under Hamming distance, and present two algorithms to compute it efficiently: one asymptotically fast; the other very fast on average and in practice. Because the latter approach avoids the computation of global data structures, such as the suffix array and the longest common prefix array, it yields algorithms much faster in practice than existing methods. We show how this data structure can be used to solve two string problems of interest: (a) approximate string matching under Hamming distance; and (b) longest approximate overlap under Hamming distance. Analogously, we introduce the prefix table under edit distance, and present an efficient algorithm for its computation. In the process, we also define the border array under both distance measures, and provide an algorithm for conversion between prefix tables and border arrays.
Original languageUndefined/Unknown
Title of host publicationCombinatorial Algorithms
Subtitle of host publication25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers
EditorsKratochvil Jan, Mirka Miller, Dalibor Froncek
PublisherSpringer International Publishing
Pages49-61
Number of pages13
ISBN (Electronic)978-3-319-19315-1
ISBN (Print)978-3-319-19314-4
DOIs
Publication statusPublished - 2015
Event25th International Workshop, IWOCA 2014 - Duluth, MN, United States
Duration: 15 Oct 201417 Oct 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume8986
ISSN (Print)0302-9743

Conference

Conference25th International Workshop, IWOCA 2014
Country/TerritoryUnited States
CityDuluth, MN
Period15/10/201417/10/2014

Cite this