License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.12
URN: urn:nbn:de:0030-drops-169505
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16950/
Bannai, Hideo ;
Goto, Keisuke ;
Ishihata, Masakazu ;
Kanda, Shunsuke ;
Köppl, Dominik ;
Nishimoto, Takaaki
Computing NP-Hard Repetitiveness Measures via MAX-SAT
Abstract
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation of some of these measures is NP-hard, and straight-forward computation is infeasible for datasets of even small sizes. Three such measures are the smallest size of a string attractor, the smallest size of a bidirectional macro scheme, and the smallest size of a straight-line program. While a vast variety of implementations for heuristically computing approximations exist, exact computation of these measures has received little to no attention. In this paper, we present MAX-SAT formulations that provide the first non-trivial implementations for exact computation of smallest string attractors, smallest bidirectional macro schemes, and smallest straight-line programs. Computational experiments show that our implementations work for texts of length up to a few hundred for straight-line programs and bidirectional macro schemes, and texts even over a million for string attractors.
BibTeX - Entry
@InProceedings{bannai_et_al:LIPIcs.ESA.2022.12,
author = {Bannai, Hideo and Goto, Keisuke and Ishihata, Masakazu and Kanda, Shunsuke and K\"{o}ppl, Dominik and Nishimoto, Takaaki},
title = {{Computing NP-Hard Repetitiveness Measures via MAX-SAT}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {12:1--12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16950},
URN = {urn:nbn:de:0030-drops-169505},
doi = {10.4230/LIPIcs.ESA.2022.12},
annote = {Keywords: repetitiveness measures, string attractor, bidirectional macro scheme}
}
