language: en

Lempel-Ziv Index for q-Grams

Juha Karkkainen and Erkki Sutinen
Department of Computer Science,
P.O. Box 26 (Teollisuuskatu 23),
FIN-00014
University of Helsinki,
Finland
fJuha.Karkkainen,Erkki.Sutineng@cs.Helsinki.FI

Abstract. We present a new sublinear-size index structure for q-grams. A q-gram index of the text is used in many approximate pattern matching algorithms. All earlier q-gram indexes have at least linear size. The new method takes advantage of repetitions in the text found by Lempel-Ziv parsing.

1 Introduction