Кодировка Инвертированный список

Кодировка Инвертированный список Для более рационального представления инвертированных файлов, использующих менее 20 бит на документ, отметим, что словопозиции частых терминов имеют близкие значения. Мысленно пройдем по документам коллекции и поищем часто встречающийся термин computer. Мы найдем документ, содержащий слово computer, затем пропустим несколько документов, не содержащих это слово, после найдем документ, содержащий этот термин, и т.д.. Ключевая идея заключается в том, что интервалы между словопозициями являются короткими и для их хранения требуется меньше 20 бит. На практике интервалы между наиболее частыми терминами, таким как the и for, чаще всего равны единице. Однако пробелы между редкими терминами, встречающимися в коллекции лишь один или два раза (например, слово arachnocentric ), по величине мало отличаются от идентификаторов документов и требуют для хранения.

Как показал эксперимент, при использовании байтового кодирования переменной длины размер сжатого индекса для коллекции Reuters-RCVl равен 116 Мбайт. Это означает, что экономия памяти по сравнению с несжатым индексом превышает 50%.

Идею байтового кодирования переменной длины можно применить к единицам памяти, которые могут быть как больше, так и меньше байта: 32-, 16- и 4-битовые слова, или полубайты (nibbles). Более крупные слова еще сильнее уменьшают объем необходимых манипуляций битами за счет потери качества сжатия. Размеры слов, не превышающие байта, позволяют достичь еще более высоких степеней сжатия за счет увеличения количества манипуляций битами. В целом байты представляют собой приемлемый компромисс между степенью сжаггия и скоростью распаковки.

Для большинства систем информационного поиска байтовое кодирование переменной длины обеспечивает превосходный компромисс между скоростью поиска и размером памяти. Кроме того, его легко реализовать — большинство альтернатив, являются более сложными. Однако, если дисковая память ограничена, можно достичь более высокой степени сжатия, применив побитовое кодирование, в частности две тесно связанные одна с другой схемы: у-коды, которые будут рассмотрены ниже, и 6-коды (упражнение 5.9).

tel-icq