WikiSort.ru - Не сортированное

Пример

Допустим, необходимо зашифровать сообщение «AABA<EOM>», где <EOM> — это символ конца сообщения (англ. end of message). Для этого примера предполагается, что декодировщик знает, что мы намерены закодировать ровно пять символов в десятичной системе счисления (алгоритм в данном случае поддерживает 10⁵ различных комбинаций символов в диапазоне [0, 100000)) используя распределение вероятностей {A: 0.60; B: 0.20; <EOM>: 0.20}. Кодировщик делит диапазон [0, 100000) на три поддиапазона:

A:     [     0,  60000)
B:     [ 60000,  80000)
<EOM>: [ 80000, 100000)

Поскольку наш первый символ — A, это снижает наш первоначальный диапазон до [0, 60000). Второй символ делит этот диапазон еще на три части:

AA:     [     0,  36000)
AB:     [ 36000,  48000)
A<EOM>: [ 48000,  60000)

С двумя закодированными символами наш диапазон становится [0, 36000) и наш третий символ предоставляет следующие варианты:

AAA:     [     0,  21600)
AAB:     [ 21600,  28800)
AA<EOM>: [ 28800,  36000)

На этот раз выбор падает на второй из трех вариантов, которые представляют собой сообщение, которое мы хотим закодировать, и наш диапазон становится [21600, 28800). Может показаться, что стало сложнее определить наши поддиапазоны в данном случае, но на самом деле это не так: мы можем просто вычесть нижнюю границу из верхней границы, чтобы определить, что в нашем диапазоне доступно 7200 чисел; первые 4320 из них представляют 0,60 от общего числа, следующие 1440 представляют следующие 0,20, а остальные 1440 представляют оставшиеся 0,20 от общего диапазона. Прибавка нижней границы дает нам наши диапазоны:

AABA:     [21600, 25920)
AABB:     [25920, 27360)
AAB<EOM>: [27360, 28800)

Наконец, наш диапазон сузился до [21600, 25920), у нас остался только один символ для кодирования. Используя ту же технику, как и прежде, для разделения диапазона между нижней и верхней границей мы находим три оставшихся поддиапазона:

AABAA:     [21600, 24192)
AABAB:     [24192, 25056)
AABA<EOM>: [25056, 25920)

И так как <EOM> — это наш последний символ — наш конечный диапазон - [25056, 25920). Так как все пятизначные числа, начинающиеся с «251», попадают в наш последний ряд, то мы могли бы передать один из трехзначных префиксов, чтобы однозначно выразить исходное сообщение (тот факт, что на самом деле существует восемь таких префиксов, говорит о том, что можно оптимизировать алгоритм. Но они возникли из-за использования десятичной системы счисления, а не двоичной).