EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Compressed Dictionary Matching on Run-Length Encoded Strings

Philip Bille, Inge Li Gørtz, Simon J. Puglisi, Simon Rumle Tarnow

Algorithmica · 2026-06 · 88 (3)

DOI: 10.1007/s00453-026-01398-0 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 28.05.2026. Verfasst von Philip Bille und 3 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Teknologi og Produktion, Det Frie Forskningsråd, Denmark.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a set of pattern strings $$\mathcal {P}=\{P_1, P_2,\ldots P_k\}$$ P = { P 1 , P 2 , … P k } and a text string S , the classic dictionary matching problem is to report all occurrences of each pattern in S . We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns $$\mathcal {P}$$ P and the length of the text string S , respectively, and let $$\overline{m}$$ m ¯ and $$\overline{n}$$ n ¯ be the total number of runs in the run-length encoding of the patterns in $$\mathcal {P}$$ P and S , respectively. Our main result is an algorithm that achieves $$O( (\overline{m} + \overline{n})\log \log m + \textrm{occ})$$ O ( ( m ¯ + n ¯ ) log log m + occ ) expected time, and $$O(\overline{m})$$ O ( m ¯ ) space, where $$\textrm{occ}$$ occ is the total number of occurrences of patterns in S . This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within a $$\log \log m$$ log log m factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.

Förderung

  • Teknologi og Produktion, Det Frie Forskningsråd, Denmark

Zitieren

APA

Bille, P., Gørtz, I. L., Puglisi, S. J., & Tarnow, S. R. (2026). Compressed Dictionary Matching on Run-Length Encoded Strings. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01398-0

Vancouver

Bille P, Gørtz IL, Puglisi SJ, Tarnow SR. Compressed Dictionary Matching on Run-Length Encoded Strings. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01398-0

BibTeX
@article{Bille2026,
  author = {Bille, Philip and Gørtz, Inge Li and Puglisi, Simon J. and Tarnow, Simon Rumle},
  title = {Compressed Dictionary Matching on Run-Length Encoded Strings},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {3},
  doi = {10.1007/s00453-026-01398-0}
}
Kostenlos starten →