4551
правка
Индексирование сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
м
Индексирование сжатого текста (посмотреть исходный код)
Версия от 14:59, 5 апреля 2021
, 5 апреля 2021→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дана ''текстовая строка'' <math>T = t_1 t_2... t_n</math> над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''индексирования сжатого текста'' (compressed text indexing, CTI) заключается в ''замене'' строки 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. | ||