Термин сжатый структура данных возникает в вычислительной технике подполей алгоритмов , структур данных , и теоретической информатики . Это относится к структуре данных, операции которой примерно такие же быстрые, как и у стандартной структуры данных для проблемы, но размер которой может быть значительно меньше. Размер сжатой структуры данных обычно сильно зависит от энтропии представляемых данных.
Важные примеры сжатых структур данных включают в себя сжатый массив суффикса [1] [2] и FM-индекс , [3] оба из которых может представлять произвольный текст символов Т для сравнения с шаблоном . Принимая во внимание любой вход модели Р , они поддерживают операцию обнаружения когда и если P появится в T . Время поиска пропорционально сумме длины шаблона P , очень медленно растущей функции длины текста T и количества зарегистрированных совпадений. Место, которое они занимают, примерно равно размеру текста Tв сжатой энтропией форме, например, полученной с помощью Prediction by Partial Matching или gzip . Более того, обе структуры данных являются самоиндексируемыми, в том смысле, что они могут восстанавливать текст T произвольным образом, и, таким образом, базовый текст T может быть отброшен. Другими словами, они одновременно обеспечивают сжатым и быстрый поиск представление текста T . Они представляют собой существенное улучшение по сравнению с пространством обычного дерева суффиксов и суффиксов массива , которые занимают много раз больше места , чем размер T . Они также поддерживают поиск произвольных шаблонов, в отличие от инвертированного индекса., который поддерживает только поиск по словам. Кроме того, инвертированные индексы не имеют функции самоиндексации.
Важное связанное с этим понятие - это краткая структура данных , которая использует пространство, примерно равное теоретико-информационному минимуму, что является наихудшим понятием пространства, необходимого для представления данных. Напротив, размер сжатой структуры данных зависит от конкретных представляемых данных. Когда данные являются сжимаемыми, как это часто бывает на практике для текста на естественном языке, сжатая структура данных может занимать пространство, очень близкое к теоретико-информационному минимуму, и значительно меньше места, чем большинство схем сжатия [ необходим пример ] [ необходима ссылка ] .
Ссылки
- ^ Р. Гросси и Дж. С. Виттер, Сжатые массивы суффиксов и деревья суффиксов с приложениями для индексирования текста и сопоставления строк], Труды 32-го симпозиума ACM по теории вычислений , май 2000 г., стр. 397-406. Версия журнала в SIAM Journal on Computing , 35 (2), 2005, 378-407.
- ^ Р. Гросси, А. Гупта и Дж. С. Виттер, Энтропийно сжатые текстовые индексы высокого порядка, Труды 14-го ежегодного симпозиума SIAM / ACM по дискретным алгоритмам , январь 2003 г., 841-850.
- ^ П. Феррагина и Г. Манзини, Оппортунистические структуры данных с приложениями, Труды 41-го симпозиума IEEE по основам информатики , ноябрь 2000 г., стр. 390-398. Версия журнала в индексировании сжатого текста, Журнал ACM , 52 (4), 2005, 552-581.
