siEDM: an efficient string index and search algorithm for edit distance with moves

DOI10.3390/a9020026zbMath1461.68272arXiv1602.06688OpenAlexW2281094450MaRDI QIDQ1736784

Hiroshi Sakamoto, Kenta Nakashima, Yoshimasa Takabatake, Tetsuji Kuboyama, Yasuo Tabei

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.06688

zbMATH Keywords

self-indexedit distance with movesgrammar-based self-indexstring index for edit-distance with moves

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Related Items

Grammar index by induced suffix sorting ⋮ Efficient algorithms for computing the inner edit distance of a regular language via transducers ⋮ siEDM ⋮ A Space-Optimal Grammar Compression.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An online algorithm for lightweight grammar-based compression
• ESP-index: a compressed index based on edit-sensitive parsing
• Edit distance with move operations
• The string edit distance matching problem with moves
• Self-Indexed Grammar-Based Compression
• Rank/select operations on large alphabets
• Biological Sequence Analysis
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• A Succinct Grammar Compression
• LZ77-Based Self-indexing with Faster Pattern Matching