Новинки:

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

И вот так... :)


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

Автор: Phil Andrey,
22 сентября 2004 года в 01:15:28

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


Вот, кстати, доказал простую теорему.

-=-=-=-=-=-=-=-=-=-=-=-
Пусть существует такая строка A , что
для любой константы С: BWT(IBWT(A,C))!=A
тогда не существует такой строки M, что
BWT(M)=A (тоесть строку A невозвожно
получить в результате BWT).


От противного, пусть такая M существует:
BWT(M)=A.
Пусть С получено в результате BWT(M)
Т.к.
IBWT(BWT(M),C)=M
IBWT(A,C)=M
BWT(IBWT(A,C))=BWT(M)=A
BWT(IBWT(A,C))=A, а это противоречит
условию теоремы.
-=-=-=-=-=-=-=-=-=-=-=-

Следовательно любая строка A для которой
BWT(IBWT(A,C))!=A, для любой С не может
быть получена в результате BWT.
На самом деле, конечно достаточно
выбрать любое C, и если для него
BWT(IBWT(A,C))!=A, то это будет верно
вообще и для другого С, но чтоб доказать
это видимо придется думать покруче, так
сразу у меня не получилось. Да и не надо
оно тут, итак черезчюр :)

>В comp.compression разговоры о биективности - добрая половина трафика ;

Ну, так я не совсем об этом, я больше об избыточности в BWT.

Кстати, а Vadim, это не Vadim Yoockin ли?

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


Ответы:



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

Тема:

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

E-Mail:

URL:

Город:

Страна:

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

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