Аноним

Индексирование сжатого текста: различия между версиями

Материал из WEGA
 
(не показаны 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)
[[Категория: Совместное определение связанных терминов]]