Repetition-Based Text Indexes
Juha Kärkkäinen · 1999
Repetition-based indexing is a new scheme for preprocessing a text to support samestringinthetext, andforusingtheinformationinpatternmatching. fastpatternmatchingqueries. Theschemeprovidesageneralframeworkfor representinginformationaboutrepetitions,i.e., multipleoccurrencesofthe instancesofthescheme. theirvariations, whichwecollectivelycallsuffix indexes, can be seen as Well-known text indexes, such as suffix trees, suffix arrays, DAWGs and Basedonthescheme, weintroducetheLempel-Ziv index, a newtextindex textcompressionmethods. The Lempel-Zivindexoersapossibilityfora earlieroccurrences,andwhichisalsousedintheZiv-Lempelfamilyof forstringmatching.Itusestherepetitioninformationina Lempel-Ziv space-timetradeoff. Thespacerequirementcanbesmallerthanfor suffix parse,whichisadivisionofthetextintonon-overlappingsubstringswith indexesbyuptoalogarithmicfactor, whilethequerytimeislargerbutstill sublinearinthelengthofthetext. Theonlyprevioustextindexoeringa ontheresultsofthesparsesuxtreeinmanycases. space-timetradeoisthesparsesuxtree. TheLempel-Zivindeximproves q,areusedinsomeapproximatestringmatchingalgorithms. We introduce Text indexes for q-gram matching, i.e., for matching string patterns of length