Схема байтового кодирования

Схема байтового кодирования Материал, изложенный ранее, основан на работе Шолера и др. (Scholer et al., 2002). Эти авторы выяснили, что схема байтового кодирования переменной длины позволяет обработать запрос вдвое быстрее, чем схема побитового сжатия индекса или отказ от сжатия вообще. При этом коэффициент сжатия оказался на 30% хуже, чем в лучшей схеме побитового сжатия. Кроме того, они показали, что сжатые индексы имеют преимущество перед несжатыми не только за счет экономии дисковой памяти, но и за счет более быстрой обработки запросов. В одном из экспериментов коды, основанные на “переменных полубайтах” (variable nibbles), оказались на 5-10% компактнее схемы байтового кодирования переменной длины, но их эффективность оказалась на треть ниже (Anh and Moffat, 2005). Тротман (Trotman, 2003) также рекомендует использовать схему байтового кодирования переменной длины, если только дисковое пространство не является критическим ресурсом. В своих последних работах Ан и Моффат (Anh and Moffat, 2005, 2006а), а также Жуковский и др. (Zukowski et al., 2006) сконструировали бинарные коды, выровненные по границам машинных слов, которые не уступают схеме байтового кодирования переменной длины по степени сжатия, при этом обеспечивая более быстрое декодирование. Чжан и др. (Zhang et al., 2007) исследовал повышенную эффективность кэширования в сочетании с использованием многочисленных методов сжатия инвертированных списков на современном аппаратном обеспечении.

Схемы 8- и у-кодирования были предложены Элиасом (Elias, 1975). доказавшим, что оба эти кода являются универсальными. Кроме того, 8-коды являются асимптотически оптимальными при Н(Р) —» При доминировании больших чисел (больше 15) схема-кодирования является более эффективной, чем схема у-кодирования. Хорошим введением в теорию информации, включая концепцию энтропии, является книга Кавера и Томаса (Cover and Thomas, 1991). В то время как коды Элиаса являются лишь асимптотически оптимальными, можно построить арифметические коды (Witten et al., 1999), сколь угодно близкие к оптимальному значению Н(Р) при любом распределении Р.

tel-icq