2013/01/28 by Shoshana Marcus Dina Sokol, Sokol, Shoshana Marcus Dina · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.1301.6428
openalex publication_date 2013/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The dictionary matching problem is to locate occurrences of any pattern among a set of patterns in a given text. Massive data sets abound and at the same time, there are many settings in which working space is extremely limited. We introduce dictionary matching software for the space-constrained environment whose running time is close to linear. We use the compressed suffix tree as the underlying data structure of our algorithm, thus, the working space of our algorithm is proportional to the optimal compression of the dictionary. We also contribute a succinct tool for performing constant-time lowest marked ancestor queries on a tree that is succinctly encoded as a sequence of balanced parentheses, with linear time preprocessing of the tree. This tool should be useful in many other applications. Our source code is available at http://www.sci.brooklyn.cuny.edu/~sokol/dictmatch.html