A unified algorithm for accelerating edit-distance computation via text-compression

DOI10.4230/LIPICS.STACS.2009.1804MaRDI QIDQ5390005zbMATH OpenFDO

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

Publication date 24 April 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_6907.html

zbMATH Keywords

combinatorial pattern matchingdynamic programming acceleration via compressionedit distancestraight-line programs

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32) Dynamic programming (90C39)

Recommendations

• Unified compression-based acceleration of edit-distance computation
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Edit distance for a run-length-encoded string and an uncompressed string
• The string edit distance matching problem with moves

Cited in

(20)

• Linear-time text compression by longest-first substitution
• Edit distance with block deletions
• On almost Monge all scores matrices
• Unified compression-based acceleration of edit-distance computation
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Compression-based distance between string data and its application to literary work classification based on authorship
• Generalized substring compression
• Efficient all path score computations on grid graphs
• Computing \(q\)-gram non-overlapping frequencies on SLP compressed texts
• Towards approximate matching in compressed strings: local subsequence recognition
• Faster subsequence and don't-care pattern matching on compressed texts
• Edit distance with duplications and contractions revisited
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• RLE edit distance in near optimal time
• A space-optimal grammar compression
• A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
• Random access to grammar-compressed strings and trees
• Boosting over non-deterministic ZDDs
• Extended formulations via decision diagrams
• A faster algorithm for the computation of string convolutions using LZ78 parsing

This page was built for publication: A unified algorithm for accelerating edit-distance computation via text-compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5390005)