4430
правок
Сжатие целочисленных последовательностей и множеств: различия между версиями
Материал из WEGA
Сжатие целочисленных последовательностей и множеств (посмотреть исходный код)
Версия от 22:56, 3 марта 2018
, 3 марта 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 88: | Строка 88: | ||
'''Контекстно-зависимый код''' | '''Контекстно-зависимый код''' | ||
Ранее описанные статические коды используют один и тот же набор присваиваний кодовых слов на протяжении всего процесса кодирования сообщения. Большей эффективности сжатия можно достичь в ситуациях, когда распределение вероятности появления символов является гомогенным локально, но не глобально. | |||
Моффат и Стювер [ ] предложили оффлайновый алгоритм, который обрабатывает сообщение как единое целое – в данном случае не потому, что параметр требует вычисления (как это происходит при использовании двоичного кода), но потому, что символы сообщения кодируются непоследовательно. Предложенный ими интерполяционный код представляет собой рекурсивный метод кодирования, способный обеспечить исключительно компактное представление – особенно в случае, если пробелы не являются независимыми друг от друга. | |||
Рассмотрим сообщение, представленное в виде подмножеств, аналогично последовательности M2 в таблице 1. Предположим, что программа-декодер знает о том, что наибольшее значение в подмножестве не превышает 29. В таком случае про любой элемент в последовательности M можно сказать, что он больше или равен lo = 1 и меньше или равен hi = 29, и 29 различных вариантов могут быть закодированы при помощи двоичного кода, занимая менее dlog2(29 — 1 + 1)e = 5 бит каждый. В частности, среднее значение в M2, в данном примере s5 = 7 (неважно, какое именно среднее значение будет выбрано), определенно может быть передано декодеру при помощи пяти бит. После того, как среднее значение будет определено, остальные значения могут быть закодированы в рамках более точных диапазонов, в силу чего для каждого из них может потребоваться менее пяти бит. | |||
Теперь более детально рассмотрим диапазон значений, который может занимать вреднее значение. Поскольку в списке всего n = 10 значений, у нас есть четыре разных значения, предшествующих s5, и пять значений, следующих после него. Из этого соображения можно вывести более ограниченный диапазон для s5: lo = lo + 4 и hi = hi - 5, что означает, что пятое значение M2 (число 7) можно закодировать при помощи алгоритма минимального двоичного кода в диапазоне [5, 24], используя только 4 бита. Первая строка таблицы 1 иллюстрирует этот процесс. | |||
Теперь мы имеем дело с двумя рекурсивными подзадачами – передачей левой части h1, 4, 5, 6i, зная, что любое значение должно быть больше lo = 1 и меньше = 7 - 1 = 6, и правой части h17, 25, 27, 28, 29i, зная, что любое значение должно быть больше lo = 7 + 1 = 8 и меньше или равно = 29. Эти два подмножества рекурсивно обрабатываются в порядке, изображенном далее в таблице 1, с расчетом более узких диапазонов [lo, hi] и получением минимального двоичного кода. | |||
Важный аспект интерполяционного кода заключается в том, что могут возникнуть ситуации, в которых длина кодового слова равна 0, что становится понятным из равенства lo0 = hi0. В этом случае нет необходимости в выдаче битов, поскольку в обозначенный диапазон попадает только одно значение, и декодер может вычислить его. Четыре символа из последовательности M2 могут успешно воспользоваться этой возможностью. Благодаря этому свойству интерполяционное кодирование особенно эффективно в случаях, когда подмножества содержат кластеры последовательных элементов, либо локализованные области подмножеств имеют высокую плотность. В предельном случае, если подмножество содержит все элементы интервала, для его кодировки вообще не требуется ни одного бита при известном значении U. В более общем случае плотные множества могут быть представлены с использованием мене чем одного бита на символ. | |||
В таблице 1 приведен пример интерполяционного кода с использованием (в последнем столбце) минимального двоичного кода для каждого значения в его ограниченном диапазоне. В целях оптимизации можно использовать отцентрированный минимальный двоичный код, чтобы короткие кодовые слова приходились на середину диапазона, а не на его начало, используя тот факт, что среднее значение множества с большей вероятностью будет находиться ближе к середине диапазона элементов, чем к его границам. Для реализации этого расширения требуется тривиальная реструктуризация алгоритма минимального двоичного кодирования; на практике оно оказывается весьма результативным. Однако улучшение не гарантировано, а кроме того, при обработке последовательности M2 использование отцентрированного минимального двоичного кода добавляет один бит к сжатому представлению по сравнению с обычным минимальным двоичным кодом, что показано в таблице . | |||
Чен и др. [5] детально описали техники декодирования интерполяционных кодов. | |||
Таблица 1 | |||
Пример кодирования сообщения M2 = h1, 4, 5, 6, 7, 17, 25, 27, 28, 29i при помощи алгоритма интерполяционного кодирования. При использовании минимального двоичного кода требуется в сумме 20 бит. Если lo0 = hi0, ни одного бита не выводится | |||
Индекс i Значение si lo hi lo0 hi0 {si – lo’, hi – lo’} Binary MinBin | |||
'''Гибридные методы''' | |||
Ранее было отмечено, что сообщение должно предполагаться относительно коротким по сравнению с полной возможной совокупностью символов и что n <$; U. Фрэнкл и Кляйн [ ] заметили, что последовательность показателей степеней символов (т.е. последовательность значений dlog2sie) в сообщении должна образовывать намного более плотный и компактный диапазон, чем само сообщение, так что можно эффективно использовать упрощенный код в префиксных частях, обозначающих показатель степени, и прямолинейное двоичное кодирование для суффиксных частей. Иными словами, вместо использования для префиксной части унарного кода можно использовать код Хаффмана с минимальной избыточностью. | |||
В 1996 году Питер Фенвик в работе [13] описал аналогичный механизм, использующий арифметическое кодирование, добавив к нему еще одну модификацию. Его алгоритм структурного арифметического кодирования использует адаптивную оценку вероятностей и двухкомпонентные коды, представленные в виде показателя степени и суффиксной части, при этом обе части вычисляются адаптивным образом. У показателя степени небольшой диапазон, к тому же эта часть кода имеет возможность быстро менять вычисленную вероятность распределения, реагируя на локальные изменения вероятности. Этот двухэтапный процесс кодирования обладает уникальным преимуществом «размазывания» изменений вероятности по диапазону значений, не ограничивая их недавно обработанными фактическими значениями. | |||
'''Другие методы кодирования''' | |||
Среди других недавних примеров контекстно-зависимых кодов стоит упомянуть адаптивный последовательный двоичный код (Моффат и Ан [11]) и упакованные двоичные коды (Ан и Моффат [ ]). Уиттен и др. [ ], а также Моффат и Турпин [13] предложили модификации техник кодирования Хаффмана и арифметического кодирования, способные обеспечить более эффективное сжатие в случаях, когда длина сообщения M велика по отношению к размеру исходного алфавита U. | |||
== Применение == | |||
Основной областью применения техник сжатого представления множеств является хранение инвертированных индексов в больших системах поиска по всему тексту – например, у компаний, обеспечивающих поиск по Интернет-ресурсам [15]. | |||
== Открытые вопросы == | |||
В последнее время велась работа над сжатыми представлениями множеств, которые поддерживали бы такие операции, как ранжирование и выбор, не требуя декомпрессии множества (см, например, Гупта и др. [ ], Раман и др. [ ]). Исследователи активно работают над улучшением этих методов и нахождением баланса между требованиями эффективности сжатия и эффективности доступа к данным. | |||
== Экспериментальные результаты == | |||
В этой области хорошим тоном являются сравнения на типичных наборах данных реалистичного размера, требующие эффективного сжатия и эффективного же декодирования. Уиттен и др. [15], а также многие другие авторы приводят подробные сведения о фактической эффективности сжатия. | |||
== Ссылка на код == | |||
На странице http://www.csse.unimelb.edu.au/~alistair/codes/ можно ознакомиться с простой текстовой системой «сжатия», позволяющей исследовать различные типы алгоритмов кодирования, перечисленных в данном материале. | |||
См. также | |||
* [[Арифметическое кодирование для сжатия данных]] | |||
* [[Индексация сжатого текста]] | |||
* [[Операции ранжирования и выбора на двоичных строках]] | |||
== Литература == | |||
1. Anh, V.N., Moffat, A.: Improved word-aligned binary compression for text indexing. IEEE Trans. Knowl. Data Eng. 18(6), 857-861 (2006) | |||
2. Boldi, P., Vigna, S.: Codes for the world-wide web. Internet Math. 2(4), 405-427 (2005) | |||
3. Brisaboa, N.R., Farina, A., Navarro, G., Esteller, M.F.: (S; C)-dense coding: An optimized compression code for natural language text databases. In: Nascimento, M.A. (ed.) Proc. Symp. String Processing and Information Retrieval. LNCS, vol. 2857, pp. 122-136, Manaus, Brazil, October 2003 | |||
4. Chen, D., Chiang, Y.J., Memon, N., Wu, X.: Optimal alphabet partitioning for semi-adaptive coding of sources of unknown sparse distributions. In: Storer, J.A., Cohn, M. (eds.) Proc. 2003 IEEE Data Compression Conference, pp. 372-381, IEEE Computer Society Press, Los Alamitos, California, March 2003 | |||
5. Cheng, C.S., Shann, J.J.J., Chung, C.P.: Unique-order interpolative coding for fast querying and space-efficient indexing in information retrieval systems. Inf. Process. Manag. 42(2), 407-428 (2006) | |||
6. Culpepper, J.S., Moffat, A.: Enhanced byte codes with restricted prefix properties. In: Consens, M.P., Navarro, G. (eds.) Proc. Symp. String Processing and Information Retrieval. LNCS Volume 3772, pp. 1 -12, Buenos Aires, November 2005 | |||
7. de Moura, E.S., Navarro, G., Ziviani, N., Baeza-Yates, R.: Fast and flexible word searching on compressed text. ACM Trans. Inf. Syst. 18(2), 113-139(2000) | |||
8. Fenwick, P.: Universal codes. In: Sayood, K. (ed.) Lossless Compression Handbook, pp. 55-78, Academic Press, Boston (2003) | |||
9. Fraenkel, A.S., Klein, S.T.: Novel compression of sparse bitstrings -Preliminary report. In: Apostolico, A., Galil, Z. (eds) Combinatorial Algorithms on Words, NATO ASI Series F, vol. 12, pp. 169-183. Springer, Berlin (1985) | |||
10. Gupta, A., Hon, W.K., Shah, R., Vitter, J.S.: Compressed data structures: Dictionaries and data-aware measures. In: Storer, J.A., Cohn, M. (eds) Proc. 16th IEEE Data Compression Conference, pp. 213-222, IEEE, Snowbird, Utah, March 2006 Computer Society, Los Alamitos, CA | |||
11. Moffat, A., Anh, V.N.: Binary codes for locally homogeneous sequences. Inf. Process. Lett. 99(5), 75-80 (2006) Source code available from www.cs.mu.oz.au/~alistair/rbuc/ | |||
12. Moffat, A., Stuiver, L.: Binary interpolative coding for effective index compression. Inf. Retr. 3(1), 25-47 (2000) | |||
13. Moffat, A., Turpin, A.: Compression and Coding Algorithms. Kluwer Academic Publishers, Boston (2002) | |||
14. Raman, R., Raman, V., Srinivasa Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 233-242, San Francisco, CA, January 2002, SIAM, Philadelphia, PA | |||
15. Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann,San Francisco, (1999) | |||
