09 сентября 2003 - Shelwien

Вчера разбирался с TTA - я тащусь с этих ребят. Такая наукообразная статья написана, экзешник на 70k, zip исходников - 418k... а если нормально скомпилить, то выходит 10k, а их "адаптивный фильтр" - штука в лучшем духе компрессорной эмпирики на 16 строчек (если оптимизацию свернуть).

Зато я там кое-что интересное в другом месте обнаружил, в т.н. энтропийном кодировании. Действительно интересное. Оказывается, я со своей моделью в geopack был неправ еще в одном (как минимум) месте - не следовало отдельно моделировать логарифмы самплов. В TTA вообще используется битовое кодирование, но длины чисел отдельно не кодируются. Вместо этого берется "средняя длина кода", а если число за него вылазит, то Number>>AvCodeLen кодируется унарно. И вот это дает лучшие результаты, чем базовая модель из geopack (не весь geopack, правда ;) - с тамошним order2-BFA и прочим. Это к вопросу о вредности разделения данных на несколько потоков ;)

И тут еще один момент - я, наконец, понял, почему дельты логарифмов кодировались хуже самих логарифмов, хотя по виду должно быть наоборот:

06 03 03 04 05 06 04 04 04 06 04 04 02 06 02 03
02 05 05 05 05 02 02 05 06 05 03 02 03 02 01 06
05 06 03 05 06 03 03 03 04 04 05 04 04 05 06 05
04 06 06 04 03 05 04 05 05 05 03 03 04 05 04 02

Просто дельты оказывались избыточным представлением - декодируя случайный код можно было получить любой логарифм, тогда как реально есть очень ограниченное множество значений.

Это, уже само по себе, вероятно, даст возможность улучшить модель логарифмов в geopack. Но фишка в том, что такую же избыточность там можно пронаблюдать и в основной модели - дельты, которые могут вывести значение за допустимые рамки, не отсекаются!

Вместо этого, правда, там есть BFA-смешивание (в т.ч. и с моделью исходных данных), которое избыточность несколько уменьшает. Но сам факт! Раньше мне как-то не попадалось примеров ситуаций, когда линейное смешивание может настолько плохо работать. Ведь по-хорошему, очевидно, надо считать как-то совсем иначе. По крайней мере, когда одна из моделей выдает для каких-то значений стремящиеся к нулю вероятности. Но вот какими средствами это делать?.. У SSE имхо просто не хватит адаптивности, чтобы его вместо смешивания можно было поставить.