Первое свойство

Первое свойство Кроме универсальности, у-коды обладают еще двумя свойствами, полезными при сжатии индекса. Первое свойство — у-код является беспрефиксным (prefix free), т.е. ни один у-код не является префиксом другого кода. Это значит, что декодирование последовательности у-кодов всегда является однозначным, и нам не нужны разделители между ними, которые снижают эффективность кодов. Второе свойство заключается в том, что у-коды являются непараметрическими (parameter free). При использовании многих других эффективных кодов необходимо уточнять параметры распределения интервалов в индексе (например, параметры биномиального распределения). Это усложняет реализацию сжатия и распаковки. Например, параметры необходимо хранить в памяти и извлекать из нее. Кроме того, при динамическом индексировании распределение интервалов может изменяться, поэтому исходные параметры больше использовать нельзя. Непараметрический код позволяет избежать этих проблем.

Следовательно, относительная частота i-ro термина примерно равна 1/(13/), а ожидаемое среднее количество терминов в документе длины L равно

Здесь вероятность появления термина заменена его относительной частотой. Напомним, что 200 — это среднее количество лексем в документе из коллекции Reuters-RCV 1.

Итак, мы определили статистические показатели термина, характеризующие распределение термина в коллекции и распределение интервалов в инвертированном списке. На основе этих показателей можно вычислить требования к памяти, необходимой для хранения инвертированного индекса, сжатого с помощью у-кодирования. Сначала разобьем отсортированный по убыванию частоты лексикон терминов коллекции на квантили, размеры которых равны Lc- 15. В среднем i-й термин в документе встречается 15/i раз. Следовательно, среднее количество появлений в документе / для терминов из первого квантиля удовлетворяет условию / > 1, что соответствует общему количеству интервалов в расчете на один термин (gaps per term), равному N. Среднее количество появлений терминов из второго квантиля в документе удовлетворяет условию — < / <1, что соответствует общему количеству интервалов в расчете на один термин, равному N12. Среднее количество появлений терминов из третьего квантиля в документе удовлетворяет условию д - / < 2 > 410 соответствует общему количеству интервалов в расчете на один термин, равному N13 и т.д. (Мы выбираем нижнюю границу, поскольку это упростит дальнейшие вычисления. Как будет показано, даже при таком предположении окончательный результат слишком пессимистичен.) Примем довольно нереалистичное предпо- тожение, что все интервалы для заданного термина имеют одинаковые размеры.

tel-icq