2026-07-25T06:17:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20367 2024-07-11T07:11:31Z ddc:004 open_access

Engineering Zuffix Arrays Boldi, Paolo Marchini, Stefano Vigna, Sebastiano Suffix trees suffix arrays z-fast tries Searching patterns in long strings is a classical algorithmic problem with countless practical applications. Suffix trees and suffix arrays (and their variants) are a long-established solution that yields linear-time search (in the size of the pattern). In [Paolo Boldi and Sebastiano Vigna, 2018] it is shown that a z-map gadget can be attached to (enhanced) suffix arrays to improve their theoretical query time, obtaining a data structure called zuffix array. The main contribution of this paper is to show that a carefully engineered implementation of the z-map gadget does provide significant speedups with respect to enhanced suffix arrays on real-world datasets, albeit doubling the required space. In particular, for large alphabets we observe a sevenfold improvement in query time with respect to enhanced suffix arrays; even in the worst case (small alphabets), the query time is almost halved. Thus, zuffix arrays provide a very interesting new point in the space-time tradeoff spectrum. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paolo Boldi and Stefano Marchini and Sebastiano Vigna 2024 Is Part Of LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2024.2 urn:nbn:de:0030-drops-203677 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.2 eng https://creativecommons.org/licenses/by/4.0/legalcode