Автор: 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 ли? С уважением,
Андрей.
|