Index podřetězce - Substring index
v počítačová věda, a index podřetězce je datová struktura který dává podřetězec hledat v textu nebo sbírce textů v sublearní čas. Pokud máte dokument délky nebo soubor dokumentů celkové délky , můžete vyhledat všechny výskyty vzoru v čas. (Vidět Velká O notace.)
Fráze fulltextový rejstřík se také často používá pro index všech podřetězců textu. Ale je nejednoznačný, protože se také používá pro běžné indexy slov, jako je obrácené soubory a načítání dokumentů. Vidět fulltextové vyhledávání.
Indexy podřetězce zahrnují:
- Příponový strom
- Pole přípon
- N-gram index, an obrácený soubor pro všechny N gramů textu
- Pole komprimované přípony[1]
- FM index
- LZ-index
Reference
- ^ R. Grossi a J. S. Vitter, Komprimovaná pole přípon a stromy přípon s aplikacemi pro indexování textu a shodu řetězců, SIAM Journal on Computing, 35(2), 2005, 378-407.