1294
правки
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 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. | ||
Строка 63: | Строка 63: | ||
== Ссылки на код и наборы данных == | == Ссылки на код и наборы данных == | ||
Сайт Pizza-Chili (http://pizzachili.dcc.uchile.cl или http://pizzachili.di.unipi.it) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и | Сайт Pizza-Chili (http://pizzachili.dcc.uchile.cl или http://pizzachili.di.unipi.it) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и результаты экспериментальных сравнений. | ||
== См. также == | == См. также == | ||
Строка 95: | Строка 95: | ||
12. Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242 (2002) | 12. Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242 (2002) | ||
[[Категория: Совместное определение связанных терминов]] |