LEMPEL-ZIV-INDEX FOR Q-GRAMS

Authors
KARKKAINEN J SUTINEN E
Citation
J. Karkkainen et E. Sutinen, LEMPEL-ZIV-INDEX FOR Q-GRAMS, Algorithmica, 21(1), 1998, pp. 137-154
Citations number
24
Categorie Soggetti
Mathematics,"Computer Science Software Graphycs Programming",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
21
Issue
1
Year of publication
1998
Pages
137 - 154
Database
ISI
SICI code
0178-4617(1998)21:1<137:>2.0.ZU;2-S
Abstract
We present a new sublinear-size index structure for finding all occurr ences of a given q-gram in a text. Such a q-gram index is needed in ma ny approximate pattern matching algorithms. All earlier q-gram indexes require at least O(n) space, where n is the length of the text. The n ew Lempel-Ziv index needs only O(n/log n) space while being as fast as previous methods. The new method takes advantage of repetitions in th e text found by Lempel-Ziv parsing.