10 октября 2003 - Shelwien

From: Eugene D. Shelwien
  To: Богатов Р.Н.
Subj: Работа с памятью
Date: Fri, 10 Oct 2003 16:42:28 +0300

Ну, имхо это надо постараться, чтобы контекстная СД тормозила...
Вообще-то хотелось бы видеть описание того, что вы сделали.
Впрочем, могу попробовать сформулировать несколько возможных причин:

1. Хэши нынче не в моде (особенно размером в десятки мегабайт) - архитектура современных процессоров рассчитана на совершенно другой тип доступа к памяти.

2. Если контексты разных порядков искать всегда от корня, добавляется еще один множитель в формулу сложности O(..) - хотя с объективной т.з. это само по себе еще ни о чем не говорит - вон, у Филинского все СД такие.

Кстати, я недавно оценивал этот вариант, и выяснил, что и для экономии памяти он неприменим. По крайней мере, если не предполагается хранение статистики "с потерями". Иначе всегда есть возможность добавить в дескриптор символа s в контексте C указатель на контекст Cs, а для однозначной идентификации контекста в любом хэше, потребуется "контрольная сумма", которая ничем не лучше указателя.

3. "Оконностью" (и вообще методами отсечения "старой" статистики) лучше не пробовать заниматься сразу, до реализации модели. Модель и так обычно получается достаточно сильно завязанной на СД, а после подгонки под "отсечение" ее вообще не оторвешь. Например, PPM-субмодель PAQ1 (сама по себе) сжимает book1 в ~210k. Но если увеличить количество соответствующих одному хэш-индексу элементов (с 3 до 6, скажем), то получается 216k.. В общем, такие вещи заметно влияют на сжатие и может показаться, что очень даже положительно. Фактически же, обычно это происходит за счет неявной эксплуатации каких-то корреляций, при явном моделировании которых можно получить значительно больший эффект. В случае paq1/paq3 это проявляется в плохом поведении на некоторых типах данных, в т.ч. и в слабом эффекте от применения препроцессинга.

4. При малейшей возможности, стоит использовать массивы вместо списков. Дело в том, что на практике обычно получается крайне небольшое множество возможных размеров аллоцируемых блоков, что позволяет отводить их полностью независимо - без "сборки мусора" и прочих потенциальных сложностей. (См. PPMd, ash)

5. "Стандартным" для PPM решением является хранение в контексте указателя на собственный суффикс (т.е. "abcd"->"bcd"), что позволяет повысить (для PPM - существенно) скорость работы за счет некоторых дополнительных затрат памяти. Идея в том, что по этим ссылкам мы можем переходить к меньшим порядкам при искейпах.

Либо, в качестве альтернативы, можно хранить (и обновлять) указатели на текущие контексты всех порядков в "статической" таблице, что имхо является более выгодным решением для CM. В результате, с учетом всего вышеперечисленного, конструкция оптимальной контекстной СД оказывается практически фиксированной. Тем не менее, многое еще зависит от способов работы с детерминированными контекстами (на них затрачивается большая часть памяти), действий при отсутствии дополнительной памяти и пр.
В частности, есть даже идея попробовать хранить в обычном виде статистику только для нескольких (2-3) младших порядков, а для старших (или тех из них, что редко встречались) динамически вычислять статистику заново, пересканируя всю последовательность появлявшихся в таком контексте символов.

> Достаточно будет просто откусить большой кусок (например, 128Мб)

Лучше не надо сразу ничего "откусывать" - это только приведет к торможению во время инициализации и лишним ограничениям на возможность декодирования. Есть вполне внятные средства для реаллокации блоков памяти (кстати, под Win32 лучше применять VirtualAlloc и производные - структура Heap не позволяет получать больше 256M памяти), да они обычно и не нужны, т.к. бывает достаточно просто аллоцировать новый "суперблок" (1M, скажем), когда закончится очередной.

> и вести учёт дырок определённых размеров, когда узлы СД будут
> перемещаться на новое место?

Наверно. Если бы я еще точно знал, о чем идет речь... ;)