String attractors: Verification and optimization

Research output: Research - peer-reviewArticle in proceedings – Annual report year: 2018

Documents

DOI

View graph of relations

String attractors [STOC 2018] are combinatorial objects recently introduced to unify all known dictionary compression techniques in a single theory. A set γ ⊆ [1.n] is a k-attractor for a string S ∈ Σn if and only if every distinct substring of S of length at most k has an occurrence crossing at least one of the positions in γ. Finding the smallest k-attractor is NP-hard for k ≥ 3, but polylogarithmic approximations can be found using reductions from dictionary compressors. It is easy to reduce the k-attractor problem to a set-cover instance where the string's positions are interpreted as sets of substrings. The main result of this paper is a much more powerful reduction based on the truncated suffix tree. Our new characterization of the problem leads to more efficient algorithms for string attractors: we show how to check the validity and minimality of a k-attractor in near-optimal time and how to quickly compute exact solutions. For example, we prove that a minimum 3-attractor can be found in O(n) time when |Σ| ∈ O(3+ϵ√log n) for some constant ϵ > 0, despite the problem being NP-hard for large Σ.

Original languageEnglish
Title of host publicationProceedings of 26th European Symposium on Algorithms
Number of pages13
Volume112
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Aug 2018
ISBN (Print)9783959770811
DOIs
StatePublished - 1 Aug 2018
Event26th Annual European Symposium on Algorithms - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018

Conference

Conference26th Annual European Symposium on Algorithms
CountryFinland
CityHelsinki
Period20/08/201822/08/2018
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • Dictionary compression, Set cover, String attractors
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 154948198