Hermelin, Danny ;
Landau, Gad M. ;
Landau, Shir ;
Weimann, Oren
A Unified Algorithm for Accelerating EditDistance Computation via TextCompression
Abstract
The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamicprogramming solution for this problem computes the editdistance between a pair of strings of total length $O(N)$ in $O(N^2)$ time. To this date, this quadratic upperbound has never been substantially improved for general strings. However, there are known techniques for breaking this bound in case the strings are known to compress well under a particular compression scheme. The basic idea is to first compress the strings, and then to compute the edit distance between the compressed strings.
As it turns out, practically all known $o(N^2)$ editdistance algorithms work, in some sense, under the same paradigm described above. It is therefore natural to ask whether there is a single editdistance algorithm that works for strings which are compressed under any compression scheme. A rephrasing of this question is to ask whether a single algorithm can exploit the compressibility properties of strings under any compression method, even if each string is compressed using a different compression. In this paper we set out to answer this question by using \emph{straightline programs}. These provide a generic platform for representing many popular compression schemes including the LZfamily, RunLength Encoding, BytePair Encoding, and dictionary methods.
For two strings of total length $N$ having straightline program representations of total size $n$, we present an algorithm running in $O(n^{1.4}N^{1.2})$ time for computing the editdistance of these two strings under any rational scoring function, and an $O(n^{1.34}N^{1.34})$time algorithm for arbitrary scoring functions. This improves on a recent algorithm of Tiskin that runs in $O(nN^{1.5})$ time, and works only for rational scoring functions.
BibTeX  Entry
@InProceedings{hermelin_et_al:LIPIcs:2009:1804,
author = {Danny Hermelin and Gad M. Landau and Shir Landau and Oren Weimann},
title = {{A Unified Algorithm for Accelerating EditDistance Computation via TextCompression}},
booktitle = {26th International Symposium on Theoretical Aspects of Computer Science},
pages = {529540},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897095},
ISSN = {18688969},
year = {2009},
volume = {3},
editor = {Susanne Albers and JeanYves Marion},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1804},
URN = {urn:nbn:de:0030drops18040},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1804},
annote = {Keywords: Edit distance, Straightline Programs, Dynamic programming acceleration via compression, Combinatorial pattern matching}
}
Keywords: 

Edit distance, Straightline Programs, Dynamic programming acceleration via compression, Combinatorial pattern matching 
Seminar: 

26th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2009 
Date of publication: 

2009 