1294
правки
Индексирование сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
→Ключевые слова и синонимы
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Экономичное по объему памяти индексирование текста; полнотекстовое индексирование сжатого текста; само-индексирование | Экономичное по объему памяти индексирование текста (''Space-efficient text indexing''); полнотекстовое индексирование сжатого текста (''Compressed full-text indexing''); само-индексирование (''Self-indexing'') | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дана ''текстовая строка'' <math>T = t_1 t_2... t_n</math> над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''индексирования сжатого текста'' (compressed text indexing, CTI) заключается в ''замене'' строки T экономичной с точки зрения используемой памяти структурой данных, способной эффективно отвечать на основные запросы по сравнению строк и подстрок над T. Примеры типичных запросов, требующих ответов с использованием подобного индекса: | Пусть дана ''текстовая строка'' <math>T = t_1 t_2... t_n</math> над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''индексирования сжатого текста'' (''compressed text indexing, CTI'') заключается в ''замене'' строки T экономичной с точки зрения используемой памяти структурой данных, способной эффективно отвечать на основные запросы по сравнению строк и подстрок над T. Примеры типичных запросов, требующих ответов с использованием подобного индекса: | ||
• count(P): подсчитать, сколько раз заданная ''строка шаблона'' <math>P = p_1 p_2... p_m</math> встречается в T. | • count(P): подсчитать, сколько раз заданная ''строка шаблона'' <math>P = p_1 p_2... p_m</math> встречается в T. | ||