2011/09/13 by Travis Gagie, Paweł Gawrychowski, Gagie, Travis +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.1109.2930
openalex publication_date 2011/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by the imminent growth of massive, highly redundant genomic databases, we study the problem of compressing a string database while simultaneously supporting fast random access, substring extraction and pattern matching to the underlying string(s). Bille et al. (2011) recently showed how, given a straight-line program with r rules for a string s of length n, we can build an \Ohr-word data structure that allows us to extract any substring of length m in \Ohlog n + m time. They also showed how, given a pattern p of length m and an edit distance (k ≤ m), their data structure supports finding all \occ approximate matches to p in s in \Ohr (min (m k, k4 + m) + log n) + \occ time. Rytter (2003) and Charikar et al. (2005) showed that r is always at least the number z of phrases in the LZ77 parse of s, and gave algorithms for building straight-line programs with \Ohz log n rules. In this paper we give a simple \Ohz log n-word data structure that takes the same time for substring extraction but only \Ohz min (m k, k4 + m) + \occ time for approximate pattern matching.