Интервальное кодирование
Интервальное кодирование (диапазонное кодирование) — энтропийный метод кодирования, предложенный Г. Найджелом и Н. Мартином в 1979 году[1]. Это разновидность арифметического кодирования[2].
Описание
Интервальное кодирование кодирует все символы сообщения в одно число, в отличие от, например, кода Хаффмана, который присваивает каждому символу последовательность бит и объединяет все битовые последовательности вместе.
Пример
Допустим, необходимо зашифровать сообщение «AABA<EOM>», где <EOM> — это символ конца сообщения (англ. end of message). Для этого примера предполагается, что декодировщик знает, что мы намерены закодировать ровно пять символов в десятичной системе счисления (алгоритм в данном случае поддерживает 105 различных комбинаций символов в диапазоне [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» попадают в наш последний ряд, то мы могли бы передать один из трехзначных префиксов, чтобы однозначно выразить исходное сообщение. (Тот факт, что на самом деле существует восемь таких префиксов говорит о том, что можно оптимизировать алгоритм. Но они возникли из-за использования десятичной системы счисления, а не двоичной.)
Связь с арифметическим кодированием
Арифметическое кодирование аналогично интервальному, использует дробные числа в диапазоне [0,1). Соответственно, в результате арифметический код интерпретируется как начало с неявным «0.», так как это просто разные интерпретации одних и тех же методов кодирования, то любой арифметический кодировщик — это соответствующий интервальный кодировщик, и наоборот.
На практике, однако, так называемое диапазонные кодировщики имеют тенденцию быть реализованными в значительной степени, как описано в статье Мартина,[1] в то время как арифметические кодировщики вообще не называют диапазонными. Часто разницей является побайтовая и побитовая ренормализация. Интервальные кодировщики склонны использовать байты, а не биты. Хотя это и снижает уровень сжатия, это быстрее, чем выполнение перенормировки для каждого бита.
См. также
Напишите отзыв о статье "Интервальное кодирование"
Примечания
- ↑ 1 2 [www.compressconsult.com/rangecoder/#download G. Nigel N. Martin, Range encoding: An algorithm for removing redundancy from a digitized message], Video & Data Recording Conference, Southampton, UK, July 24-27, 1979.
- ↑ «Source coding algorithms for fast data compression» Richard Clark Pasco, Stanford, CA 1976
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Отрывок, характеризующий Интервальное кодирование
Несмотря на всю силу тона усталости и уверенности, с которой произнесены были эти слова, Пьер, так долго думавший о своей карьере, хотел было возражать. Но князь Василий перебил его тем воркующим, басистым тоном, который исключал возможность перебить его речь и который употреблялся им в случае необходимости крайнего убеждения.– Mais, mon cher, [Но, мой милый,] я это сделал для себя, для своей совести, и меня благодарить нечего. Никогда никто не жаловался, что его слишком любили; а потом, ты свободен, хоть завтра брось. Вот ты всё сам в Петербурге увидишь. И тебе давно пора удалиться от этих ужасных воспоминаний. – Князь Василий вздохнул. – Так так, моя душа. А мой камердинер пускай в твоей коляске едет. Ах да, я было и забыл, – прибавил еще князь Василий, – ты знаешь, mon cher, что у нас были счеты с покойным, так с рязанского я получил и оставлю: тебе не нужно. Мы с тобою сочтемся.
То, что князь Василий называл с «рязанского», было несколько тысяч оброка, которые князь Василий оставил у себя.
В Петербурге, так же как и в Москве, атмосфера нежных, любящих людей окружила Пьера. Он не мог отказаться от места или, скорее, звания (потому что он ничего не делал), которое доставил ему князь Василий, а знакомств, зовов и общественных занятий было столько, что Пьер еще больше, чем в Москве, испытывал чувство отуманенности, торопливости и всё наступающего, но не совершающегося какого то блага.
Из прежнего его холостого общества многих не было в Петербурге. Гвардия ушла в поход. Долохов был разжалован, Анатоль находился в армии, в провинции, князь Андрей был за границей, и потому Пьеру не удавалось ни проводить ночей, как он прежде любил проводить их, ни отводить изредка душу в дружеской беседе с старшим уважаемым другом. Всё время его проходило на обедах, балах и преимущественно у князя Василия – в обществе толстой княгини, его жены, и красавицы Элен.
Анна Павловна Шерер, так же как и другие, выказала Пьеру перемену, происшедшую в общественном взгляде на него.
Прежде Пьер в присутствии Анны Павловны постоянно чувствовал, что то, что он говорит, неприлично, бестактно, не то, что нужно; что речи его, кажущиеся ему умными, пока он готовит их в своем воображении, делаются глупыми, как скоро он громко выговорит, и что, напротив, самые тупые речи Ипполита выходят умными и милыми. Теперь всё, что ни говорил он, всё выходило charmant [очаровательно]. Ежели даже Анна Павловна не говорила этого, то он видел, что ей хотелось это сказать, и она только, в уважение его скромности, воздерживалась от этого.
В начале зимы с 1805 на 1806 год Пьер получил от Анны Павловны обычную розовую записку с приглашением, в котором было прибавлено: «Vous trouverez chez moi la belle Helene, qu'on ne se lasse jamais de voir». [у меня будет прекрасная Элен, на которую никогда не устанешь любоваться.]
Читая это место, Пьер в первый раз почувствовал, что между ним и Элен образовалась какая то связь, признаваемая другими людьми, и эта мысль в одно и то же время и испугала его, как будто на него накладывалось обязательство, которое он не мог сдержать, и вместе понравилась ему, как забавное предположение.
Вечер Анны Павловны был такой же, как и первый, только новинкой, которою угощала Анна Павловна своих гостей, был теперь не Мортемар, а дипломат, приехавший из Берлина и привезший самые свежие подробности о пребывании государя Александра в Потсдаме и о том, как два высочайшие друга поклялись там в неразрывном союзе отстаивать правое дело против врага человеческого рода. Пьер был принят Анной Павловной с оттенком грусти, относившейся, очевидно, к свежей потере, постигшей молодого человека, к смерти графа Безухого (все постоянно считали долгом уверять Пьера, что он очень огорчен кончиною отца, которого он почти не знал), – и грусти точно такой же, как и та высочайшая грусть, которая выражалась при упоминаниях об августейшей императрице Марии Феодоровне. Пьер почувствовал себя польщенным этим. Анна Павловна с своим обычным искусством устроила кружки своей гостиной. Большой кружок, где были князь Василий и генералы, пользовался дипломатом. Другой кружок был у чайного столика. Пьер хотел присоединиться к первому, но Анна Павловна, находившаяся в раздраженном состоянии полководца на поле битвы, когда приходят тысячи новых блестящих мыслей, которые едва успеваешь приводить в исполнение, Анна Павловна, увидев Пьера, тронула его пальцем за рукав.
