2026-07-23T06:21:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9648 2024-03-06T10:44:37Z ddc:004 open_access

Fast Entropy-Bounded String Dictionary Look-Up with Mismatches Gawrychowski, Pawel Landau, Gad M. Starikovskaya, Tatiana Dictionary look-up Hamming distance compact data structures We revisit the fundamental problem of dictionary look-up with mismatches. Given a set (dictionary) of d strings of length m and an integer k, we must preprocess it into a data structure to answer the following queries: Given a query string Q of length m, find all strings in the dictionary that are at Hamming distance at most k from Q. Chan and Lewenstein (CPM 2015) showed a data structure for k = 1 with optimal query time O(m/w + occ), where w is the size of a machine word and occ is the size of the output. The data structure occupies O(w d log^{1+epsilon} d) extra bits of space (beyond the entropy-bounded space required to store the dictionary strings). In this work we give a solution with similar bounds for a much wider range of values k. Namely, we give a data structure that has O(m/w + log^k d + occ) query time and uses O(w d log^k d) extra bits of space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Gawrychowski and Gad M. Landau and Tatiana Starikovskaya 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.66 urn:nbn:de:0030-drops-96486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.66 eng https://creativecommons.org/licenses/by/3.0/legalcode