Re: Неспешно делается неторопливый HMM-архиватор.


Сайт о сжатии >> Форум #Компрессор# >> [Ответить] [Ответы]

Автор: Олег Набатов, <oleg_nabatov@mail.ru>
25 июля 2003 года в 14:15:29

В ответ на : Re: Неспешно делается неторопливый HMM-архиватор. от Maxim Smirnov в 25 июля 2003 года в 09:44:40:


>> В ppm-архиве основной вес приходится на ошибки Марковской модели.
>Гм. А неосновной?

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

>Попробуй перевернуть _слова_ ;-)

Для русского языка будет лучше т.к. за пробелом будет окончание которых меньше, а зная окончания можно лучше догадаться корень какой части речи.
Если я правильно понимаю то ppm должен в обратную сторону жать русский текстр немного лучше, а hmm это что-то вроде русификации текста.

>Попробуй просто разметить слова
>флагами их принадлежности к части
>речи и построить смешанную модель.
>Может, 2-3% выигрыша и будет.

Как-то слишком дискретно, мне бы в оттенках и полутонах :)
Может не совсем о hmm речь, суть в том что строить не небольшой набор типов слов, а большое дерево в котором внизу будут типы слов, выше типы фраз, т.е. грамматика. Одно плавно переходит в другое. Слова заменяем символами типов и снова ищем "слова" в этом представлении, напримем "сг" - "существительное глагол".

> *флаг*-*слово*-*флаг*-*слово*-
Но новое представление должно быть не выжимкой где целому слову исходного файла соответствует единственный флаг, а перекодировка всего файла, т.е. таким же по объему. В этом вся суть. От -*слова*- только пробел останется.

> Алгоритм пока вырисовывается N*N*LogN но возможно может быть оптимизирован до N*LogN*LogN. В моем случае качество результата важнее скорости.

Адаптивный вариант должен будет перестраивать классификацию слов после поступления каждого нового. Сначала нужен не архиватор, а собственно модель, классификацию можно строить один раз. Пока слова предполагаю сравнивать каждое с каждым, так что даже N^3 выходит. Если выигрыш будет то можно и о скорости подумать.

> Может, 2-3% выигрыша и будет.
> По крайней мере, никто о большем
> не заявлял.

:)
Я придерживаюсь своей грубой оценки. Треть веса первых участков, т.е. 30% размера архива. Если ppm жмет файл до 33% исходного размера то hmm должен до 22%

Ответы:



Ответить на это сообщение

Тема:

Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.