Новинки:

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

Ну, так...


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

Автор: Phil Andrey,
21 сентября 2004 года в 15:29:07

В ответ на : Re: Небиективность BWT от Vadim в 21 сентября 2004 года в 09:28:53:


> Честно говоря, не вижу, почему бы BWT
не быть биективным. Если не считать
необходимости куда-то девать номер
исходной строки, остальные данные можно
крутить в любую сторону :)


ПОЧЕМУ????

Ну, так смотри:

Для реализации BWT, необходимо что бы
вектор обратного преобразования
образовывал элементарный цикл, длинной
равнрой длине данных, попробуй построить
векиор для отфонарных данных, и
посмотреть выполнится ли это условие.

Избитый пример:
BWT("абракадабра")="рдакраааабб"
поэтому с любой константой IBWT("рдакраааабб")=циклический сдвиг
строки "абракадара" и, следовательно
BWT(IBWT("рдакраааабб"))="рдакраааабб",
какую бы константу для обратного
преобразования мы не выбирали.

Теперь поменяй любой символ строки
рдакраааабб, возьмем вот "рдакраааабр".
BWT(IBWT("рдакраааабр"))!="рдакраааабр",
для людой константы, причем, при
вычислении с произвольной константой
IBWT("рдакраааабр"), вообще будут
получаться строки не являющиеся
циклическими сдвигами друг - друга!


Очень простой пример:


сторока "abbс" (или любая другая
начинающаяся с "a"). Вектор обратного
преобразования начинается с 0. Вычислим
IBWT c константой 0, получим "aaaa" %)

Вычисляя с константой не 0, т.к больше 0
в векторе нет, то получим стоку без
символа "a".


Вот, такая вот биективность :)


С уважением,
Андрей


Ответы:



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

Тема:

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

E-Mail:

URL:

Город:

Страна:

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

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