Изменения

Перейти к: навигация, поиск

Преобразование Барроуза-Уилера

2766 байт убрано, 01:03, 24 октября 2013
→‎Доказательство корректности
{{Теорема
|statement=
Для любого префиксного кода <tex>C</tex>, отображающего произвольный алфавит <tex>A</tex> на двоичный алфавит <tex> \{0,1\} </tex> , длины кодовых слов должны удовлетворять неравенству: <center><tex> \sum\limits_{i = 1}^{I} 2^{-l_i} \le 1 , </tex></center>где <tex>|A| = I</tex> , а <tex>l_i</tex> {{---}} длины кодовых слов.
|proof=
Рассмотрим отрезок <tex>[0;1]</tex> на числовой прямой.
 
Разделим его пополам, причем левую половину обозначим <tex>M_0</tex>, а правую <tex>M_1</tex>.
 
Затем поделим <tex>M_0</tex> пополам и обозначим его левую половину <tex>M_{00}</tex>, а правую <tex>M_{01}</tex>, и, проделав то же самое с <tex>M_1</tex>, получим <tex>M_{10}</tex>, а левую <tex>M_{11}</tex>.
 
Будем выполнять эти действия, пока длина индекса полученного отрезка <tex>M_j</tex> не превосходит <tex>max(l_1, l_2,\ldots,l_I)</tex>.
 
Заметим, что:
*любому кодовому слову <tex>C_j</tex> сопоставлен свой отрезок <tex>M_{C_j}</tex> (Например, кодовому слову <tex>1011</tex> соответствует отрезок <tex>M_{1011}</tex>);
*длина отрезка <tex>M_{C_i}</tex> равна <tex>2^{-l_i}</tex> (Например, <tex>M_0</tex> имеет длину <tex>\frac12</tex>, а <tex>M_{00}</tex> соответственно <tex>\frac14</tex>);
*Если кодовое слово <tex>x</tex> является префиксом кодового слова <tex>y</tex>, то отрезок <tex>M_x</tex> содержит <tex>M_y</tex> (Например, кодовое слово <tex>01</tex> является префиксом <tex>0111</tex>, а отрезок<tex>M_{01}</tex> содержит <tex>M_{0111}</tex>, это его самая правая четверть);
 
Рассмотрим префиксный код <tex>C</tex>: так как ни одно из кодовых слов не является префиксом никакого другого кодового слова, то никакие два отрезка не пересекаются.
 
Если на отрезке <tex>[0;1]</tex> выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет <tex>1</tex>, то есть <tex> \sum\limits_{i = 1}^{I} M_{C_i} \le 1</tex>.
 
Отсюда следует, что <tex>\sum\limits_{i = 1}^{I} M_{C_i} = \sum\limits_{i = 1}^{I} 2^{-l_i} \le 1</tex>.
}}
Alexchekmenev
147
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/33252»

Навигация