Автор: Олег Набатов, <oleg_nabatov@mail.ru>
Россия, 24 июля 2003 года в 21:55:43
HMM это Hidden Markov Model - Марковская модель со скрытым слоем.Флейм.
В ppm-архиве основной вес приходится на ошибки Марковской модели. Если файл содержит текст то наибольшая информация приходится на начало слов. Буквы внутри и особенно в конце слова ppm хорошо прогнозирует, поэтому улучшение сжатия должно быть направлено именно на устранение избыточности в предсказании первой буквы, а не совершенствование предсказания следующих. Пример.
Имеем 256 символов. Допустим ppm знает что за пробелом обычно идет одна из 32 букв. Самые популярные весят по 3 бита, редкие по 6, остальные из 256-и символов соответственно получают вес 9 бит. Это несколько упрощено.
В файле значительны объем приходится на буквы по 5 бит. 9-битные встречаются редко, основные символы это середина и конец слов, их размер 1-2 бита. Но.
Если мы знаем правила вроде того что за прилагательным обычно идет существительное то распределение сильно изменится. Основная масса будет по прежнему по 9 бит, а первые слова существительных по 4, плюс мы имеем некоторую поправку к вероятностям суффиксов и окончаний. Думаю общий выигрыш должен быть 10-20%. Это оставит позади все семейство ppm-архиваторов, которые между собой отличаются меньше. Идея.
Пока мне представляется что разница PPM и HMM в том что последний не предсказывает на каждом шаге следующий символ, а иногда должен просто перестраивать распределения. Он должен работать по словам - распаковываемые символы это описание слова во внутренней классификации а не сами буквы, последний символ распакованный из арифметика это, например, число букв. После чего система на автопилоте выдает собственно буквы. Алгоритм пока вырисовывается N*N*LogN но возможно может быть оптимизирован до N*LogN*LogN. В моем случае качество результата важнее скорости.
|