Re: BWT по двустороннему контексту


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

Автор: Vadim,
28 июня 2004 года в 11:05:22

В ответ на : BWT по двустороннему контексту от captain cobalt в 27 июня 2004 года в 22:49:25:


> А что если проводить сортировку по ДВУСТОРОННЕМУ
> контексту? Есть подозрение, что это может улучшить
> степень сжатия ;) Существуют такие разработки?

Года 3 назад Эдгар Биндер пробовал так делать. Выигрыш был около 25-30%. Правда, декодировать не удалось :)

> Мои собственные потуги изобрести такое сводятся к
> "а что если брать не последний столбец" ;)
> Возможно ли всё-таки как-то обратимо отсортировать
> по двустороннему контексту???

В принципе, возможно. Более того, возможен еще взвешенный учет символов подстроки (в традиционном BWT вес ближайшего символа в бесколнечное кол-во раз больше веса следующего символа).

Главное, чтобы не было взаимозависмых символов, т.е. такой ситуации, в которой символы определяли бы положение в BWT-выходе друг друга.

И, наконец, практические соображения. BWT интересен возможностью быстрого преобразования. Если брать нетривиальную функцию сортировки, преимущество BWT сойдет на нет. Не удасться применить трюки по исключению подстрок из процесса сортировки, да и с т.зр. кэша может оказаться неудобно...

А пока контекст в отличном от выбранного направления можно учесть 1) словарной заменой и 2) переворотом фраз.

Ответы:



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

Тема:

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

E-Mail:

URL:

Город:

Страна:

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

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