1 Search Results for "Landau, Shir"


Document
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression

Authors: Danny Hermelin, Gad M. Landau, Shir Landau, and Oren Weimann

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)


Abstract
The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic-programming solution for this problem computes the edit-distance between a pair of strings of total length $O(N)$ in $O(N^2)$ time. To this date, this quadratic upper-bound 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)$ edit-distance algorithms work, in some sense, under the same paradigm described above. It is therefore natural to ask whether there is a single edit-distance 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{straight-line programs}. These provide a generic platform for representing many popular compression schemes including the LZ-family, Run-Length Encoding, Byte-Pair Encoding, and dictionary methods. For two strings of total length $N$ having straight-line program representations of total size $n$, we present an algorithm running in $O(n^{1.4}N^{1.2})$ time for computing the edit-distance 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.

Cite as

Danny Hermelin, Gad M. Landau, Shir Landau, and Oren Weimann. A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 529-540, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.STACS.2009.1804,
  author =	{Hermelin, Danny and Landau, Gad M. and Landau, Shir and Weimann, Oren},
  title =	{{A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{529--540},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1804},
  URN =		{urn:nbn:de:0030-drops-18040},
  doi =		{10.4230/LIPIcs.STACS.2009.1804},
  annote =	{Keywords: Edit distance, Straight-line Programs, Dynamic programming acceleration via compression, Combinatorial pattern matching}
}
  • Refine by Author
  • 1 Hermelin, Danny
  • 1 Landau, Gad M.
  • 1 Landau, Shir
  • 1 Weimann, Oren

  • Refine by Classification

  • Refine by Keyword
  • 1 Combinatorial pattern matching
  • 1 Dynamic programming acceleration via compression
  • 1 Edit distance
  • 1 Straight-line Programs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2009

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail