Fast and simple computations using prefix tables under hamming and edit distance

Carl Barton, Costas S. Iliopoulos, Solon P. Pissis*, William F. Smyth

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationCombinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers
EditorsDalibor Froncek, Jan Kratochvíl, Mirka Miller
PublisherSpringer Verlag
Pages49-61
Number of pages13
ISBN (Electronic)9783319193144
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event25th International Workshop on Combinatorial Algorithms, IWOCA 2014 - Duluth, United States
Duration: 15 Oct 201417 Oct 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8986
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Workshop on Combinatorial Algorithms, IWOCA 2014
CountryUnited States
CityDuluth
Period15/10/1417/10/14

Fingerprint

Dive into the research topics of 'Fast and simple computations using prefix tables under hamming and edit distance'. Together they form a unique fingerprint.

Cite this