Unified Compression-Based Acceleration of Edit-Distance Computation

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( N2) time. To t...

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 65, No. 2 (2013), p. 339-353
Main Author: Hermelin, Danny
Other Involved Persons: Landau, M. ; Landau, Shir ; Weimann, Oren
Format: electronic Article
Language:English
ISSN:1432-0541
Item Description:Gad M. Landau partially supported by the National Science Foundation Award 0904246, Israel Science Foundation grant 347/09, Yahoo, Grant No. 2008217 from the United States-Israel Binational Science Foundation (BSF) and DFG.
Physical Description:Online-Ressource
DOI:10.1007/s00453-011-9590-6
Subjects:
QR Code: Show QR Code