4551
правка
Индексирование сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
м
нет описания правки
Irina (обсуждение | вклад) м (Irina переименовал страницу Индексация сжатого текста в Индексирование сжатого текста) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Экономичное по объему памяти индексирование текста; полнотекстовое индексирование сжатого текста; само-индексирование | |||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дана ''текстовая строка'' <math>T = t_1 t_2... t_n</math> над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача '' | Пусть дана ''текстовая строка'' <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. | ||
| Строка 69: | Строка 69: | ||
* [[Сжатый суффиксный массив]] | * [[Сжатый суффиксный массив]] | ||
* [[Последовательное точное сравнение строк]] | * [[Последовательное точное сравнение строк]] | ||
* [[ | * [[Индексирование текста]] | ||
== Литература == | == Литература == | ||