Сжатая структура данных

Термин «структура сжатых данных» возникает в таких областях информатики , как алгоритмы , структуры данных и теоретическая информатика . Это относится к структуре данных, операции которой примерно такие же быстрые, как и у обычной структуры данных для задачи, но размер которой может быть существенно меньше. Размер структуры сжатых данных обычно сильно зависит от информационной энтропии представляемых данных.

Важные примеры структур сжатых данных включают сжатый суффиксный массив. ^[1]^[2] и FM-индекс , ^[3] оба из которых могут представлять произвольный текст символов T для сопоставления с образцом . Учитывая любой входной шаблон P , они поддерживают операцию поиска, появляется ли P в T и где и если да, то где . Время поиска пропорционально сумме длины шаблона P (очень медленно растущей функции длины текста T ) и количества зарегистрированных совпадений. Пространство, которое они занимают, примерно равно размеру текста T в энтропийно-сжатой форме, например, полученной с помощью Prediction by Partial Matching или gzip . Более того, обе структуры данных являются самоиндексируемыми, поскольку они могут восстанавливать текст T методом произвольного доступа, и, таким образом, базовый текст T может быть отброшен. они одновременно обеспечивают сжатое и доступное для быстрого поиска представление текста T. Другими словами , Они представляют собой существенное улучшение места по сравнению с обычным суффиксным деревом и суффиксным массивом чем размер T. , которые занимают во много раз больше места , Они также поддерживают поиск произвольных шаблонов, в отличие от инвертированный индекс , который может поддерживать только поиск по словам. Кроме того, инвертированные индексы не имеют функции самоиндексации.

Важным связанным с этим понятием является понятие краткой структуры данных , которая использует пространство, примерно равное минимуму теории информации, что является наихудшим понятием пространства, необходимого для представления данных. Напротив, размер сжатой структуры данных зависит от конкретных представляемых данных. Когда данные сжимаемы, как это часто бывает на практике с текстом на естественном языке, сжатая структура данных может занимать пространство, очень близкое к минимуму теории информации, и значительно меньше места, чем большинство схем сжатия. ^{[ нужен пример ]}^{[ нужна ссылка ]}

Ссылки [ править ]

^ Гросси, Роберто; Виттер, Джеффри Скотт (январь 2005 г.). «Сжатые суффиксные массивы и суффиксные деревья с приложениями для индексации текста и сопоставления строк» (PDF) . SIAM Journal по вычислительной технике . 35 (2): 378–407. дои : 10.1137/S0097539702402354 . hdl : 1808/18962 .
^ Р. Гросси, А. Гупта и Дж. С. Виттер, Текстовые индексы высокого порядка с энтропийным сжатием, Материалы 14-го ежегодного симпозиума SIAM/ACM по дискретным алгоритмам , январь 2003 г., 841-850.
^ Феррагина, П.; Манзини, Г. (2000). «Оппортунистические структуры данных с приложениями». Материалы 41-го ежегодного симпозиума по основам информатики . стр. 390–398. дои : 10.1109/SFCS.2000.892127 . ISBN 0-7695-0850-2 . S2CID 12530704 .

[1] Гросси, Роберто; Виттер, Джеффри Скотт (январь 2005 г.). «Сжатые суффиксные массивы и суффиксные деревья с приложениями для индексации текста и сопоставления строк» (PDF) . SIAM Journal по вычислительной технике . 35 (2): 378–407. дои : 10.1137/S0097539702402354 . hdl : 1808/18962 .

[2] Р. Гросси, А. Гупта и Дж. С. Виттер, Текстовые индексы высокого порядка с энтропийным сжатием, Материалы 14-го ежегодного симпозиума SIAM/ACM по дискретным алгоритмам , январь 2003 г., 841-850.

[3] Феррагина, П.; Манзини, Г. (2000). «Оппортунистические структуры данных с приложениями». Материалы 41-го ежегодного симпозиума по основам информатики . стр. 390–398. дои : 10.1109/SFCS.2000.892127 . ISBN 0-7695-0850-2 . S2CID 12530704 .

[1]

[2]

[3]