Всем привет! Поступил на факультет компьютерной инженерии, препод по проф предмету дал задачку, и пообещал поставить 5 балов за год, если услышит правильный ответ)
Итак: недавно я узнал что такое архивирование, и как оно приблизительно работает. Алгоритм Хафмана анализирует файл, анализирует в нём самые часто попадающиеся символы и кодирует их в самые мелкие битовые значения. Символы, которые попадаются реже - кодирует в более длинное битовое значение. Тот, кто знает как это работает - в курсе.
Вопрос: как этот алгоритм правильно расшифровывает весь файл, если допустим код 010001011011010101, символ "а" - 01, а символ "я" - 010001. Как он понимает что нужно преобразовывать символ "а", а не "я"?
В интернетах толкового ответа не нашел, везде только написано как он шифрует, а как расшифровывает - пара слов о префиксных кодах, которые я так и не понял.
Прошу как можно проще дать ответ на вопрос, буду благодарен)
eg01st, описанная Вами ситуация:
допустим код 010001011011010101, символ "а" - 01, а символ "я" - 010001 »
невозможна в принципе. Ибо алгоритм кодирования построен таким образом, что кодовая последовательность для кодирования символа формируется таким образом, что она (кодовая последовательность) однозначно идентифицирует исходный символ.
Принцип достаточно прост: минимизировать среднее количество кодовых символов, приходящихся на одну букву. Кодируемые элементы сообщения (буквы) располагаются в порядке убывания частот их появления в сообщении. Затем они разделяются на две группы таком образом, чтобы сумма вероятностей появления букв в верхней группе была примерно равна сумме вероятностей появления букв букв в нижней группе (например, в верхней группе не больше, нежели в нижней). Верхней группе приписывается символ «0», а нижней, соответственно, — «1». Эти символы обозначают первый знак кодовой последовательности.
Далее, каждая из двух групп, полученных на предыдущем этапе, в свою очередь делится на две подгруппы, каждой из которых так же присваивается очередной символ кодовой последовательности. Новые полученные символы обозначают второй знак в соответствующих кодовых последовательностях.
Процесс продолжается до тех пор, пока в каждой подгруппе не останется ровно одна буква, которая будет закодирована кодовой последовательностью полученных двоичных символов.
Например, закодируем сообщение:
синий, синий иней
Начинаем с частот появления букв в исходном сообщении:
«с» — 2;
«и» — 5;
«н» — 3;
«й» — 3;
« » — 3;
«,» — 1;
«е» — 1
Таким образом, общее число букв в исходном сообщении — 18 (2+5+3+3+3+1+1).
Вероятности появления букв в исходном сообщении:
«с» — 2/18;
«и» — 5/18;
«н» — 3/18;
«й» — 3/18;
« » — 3/18;
«,» — 1/18;
«е» — 1/18
Располагаем буквы в таблицу в соответствии с вероятностями их появления в исходном сообщении и делаем присвоение первого двоичного символа:
┌─────┬──────┬───┐
│ «и» │ 5/18 │ 0 │
│ │ │ │
│ «н» │ 3/18 │ │
│ │ ├───┤
│ «й» │ 3/18 │ 1 │
│ │ │ │
│ « » │ 3/18 │ │
│ │ │ │
│ «с» │ 2/18 │ │
│ │ │ │
│ «,» │ 1/18 │ │
│ │ │ │
│ «е» │ 1/18 │ │
└─────┴──────┴───┘
Замечание: при равной вероятности порядок следования исходных букв выбирается произвольно (в нашем случае это [«н», «й», « »] и [«,» , «е»]).
Далее, каждую половину делим опять же пополам по вероятностям:
┌─────┬──────┬───┬───┐
│ «и» │ 5/18 │ 0 │ 0 │
│ │ │ ├───┤
│ «н» │ 3/18 │ │ 1 │
│ │ ├───┼───┤
│ «й» │ 3/18 │ 1 │ 0 │
│ │ │ ├───┤
│ « » │ 3/18 │ │ 1 │
│ │ │ │ │
│ «с» │ 2/18 │ │ │
│ │ │ │ │
│ «,» │ 1/18 │ │ │
│ │ │ │ │
│ «е» │ 1/18 │ │ │
└─────┴──────┴───┴───┘
Повторяем эту операцию до тех пор, пока каждая буква исходного сообщения не будет закодирована:
┌─────┬──────┬───┬───┬───────────┬───────┐
│ «и» │ 5/18 │ 0 │ 0 │ │ 00 │
│ │ │ ├───┼───────────┼───────┤
│ «н» │ 3/18 │ │ 1 │ │ 01 │
│ │ ├───┼───┼───────────┼───────┤
│ «й» │ 3/18 │ 1 │ 0 │ │ 10 │
│ │ │ ├───┼───────────┼───────┤
│ « » │ 3/18 │ │ 1 │ 0 │ 110 │
│ │ │ │ ├───┬───────┼───────┤
│ «с» │ 2/18 │ │ │ 1 │ 0 │ 1110 │
│ │ │ │ │ ├───┬───┼───────┤
│ «,» │ 1/18 │ │ │ │ 1 │ 0 │ 11110 │
│ │ │ │ │ │ ├───┼───────┤
│ «е» │ 1/18 │ │ │ │ │ 1 │ 11111 │
└─────┴──────┴───┴───┴───┴───┴───┴───────┘
Таким образом, символы исходного сообщения могут быть закодированы следующими кодовыми последовательностями:
«и» — «00»;
«н» — «01»;
«й» — «10»;
« » — «110»;
«с» — «1110»;
«,» — «11110»;
«е» — «11111».
Соответственно, исходное сообщение:
┌─────┬───────┐
│ «с» │ 1110 │
├─────┼───────┤
│ «и» │ 00 │
├─────┼───────┤
│ «н» │ 01 │
├─────┼───────┤
│ «и» │ 00 │
├─────┼───────┤
│ «й» │ 10 │
├─────┼───────┤
│ «,» │ 11110 │
├─────┼───────┤
│ « » │ 110 │
├─────┼───────┤
│ «с» │ 1110 │
├─────┼───────┤
│ «и» │ 00 │
├─────┼───────┤
│ «н» │ 01 │
├─────┼───────┤
│ «и» │ 00 │
├─────┼───────┤
│ «й» │ 10 │
├─────┼───────┤
│ « » │ 110 │
├─────┼───────┤
│ «и» │ 00 │
├─────┼───────┤
│ «н» │ 01 │
├─────┼───────┤
│ «е» │ 11111 │
├─────┼───────┤
│ «й» │ 10 │
└─────┴───────┘
кодируется последовательностью:
1110000100101111011011100001001011000011111110
…а как расшифровывает - пара слов о префиксных кодах, которые я так и не понял.»
Термин «префиксные» обозначает, что никакая кодовая последовательность не является префиксом любой другой кодовой последовательности. Данное свойство позволяет однозначно декодировать любое сообщение. Если Вы посмотрите на полученное нами в примере:
1110000100101111011011100001001011000011111110
то убедитесь в этом сами. Выборки одного символа — «1», двух — «11», трёх — «111» входят сразу в несколько кодовых последовательностей, а вот выборка четырёх символов — «1110» — однозначно входит только в одну последовательность, что и позволяет её однозначно идентифицировать с символом исходного сообщения («с» — «1110»).
Данный алгоритм именуется кодом Шеннона — Фано (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0_%E2%80%9 4_%D0%A4%D0%B0%D0%BD%D0%BE). Как Вы можете увидеть по изложенному выше примеру (и сделанному замечанию), данный алгоритм может давать различные кодовые последовательности, в зависимости от нашего выбора, причём от нашего выбора, сделанного на определённом шаге, будет зависеть разбиение на всех последующих шагах, что, соответственно, не всегда может приводить к наилучшему результату — максимальное сокращение средней длины кодовых последовательностей.
В отличие от вышеизложенного алгоритма Шеннона — Фано, алгоритм Хаффмана (http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%A5%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0), хотя и строится на тех же основных принципах, подразумевает хотя и более сложную реализацию для построения дерева, но приводящую к более лучшему результату. Можно сказать, что, если построить все возможные комбинации кодовых последовательностей по алгоритму Шеннона — Фано (для конкретного сообщения), то среди них будут и все возможные комбинации кодовых последовательностей, построенные по алгоритму Хаффмана.
Впрочем, решив написать данное сообщение, я не ставил задачу обучить Вас тонкостям реализации алгоритма Шеннона — Фано, Хаффмана или Лемпеля — Зива — Велча (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%BC%D0%BF%D0%B5%D0%BB%D1%8F_%E2%80%9 4_%D0%97%D0%B8%D0%B2%D0%B0_%E2%80%94_%D0%92%D0%B5%D0%BB%D1%87%D0%B0) ;). Для этих целей хватает и монографий, и пухлых исследований. Я хотел, чтобы Вы примерно поняли сам механизм кодирования с практически нулевой избыточностью (это термин) и саму идею этого алгоритма — максимальное сокращение средней длины кодовых последовательностей. Лучший учитель — практика. Возьмите коллегу. Попросите его закодировать по изложенному выше алгоритму какое-либо сообщение. Пусть он передаст Вам закодированное сообщение и сам словарь. Попробуйте его раскодировать. Тогда Вам станет воочию ясно, что такое префиксные коды и почему «он понимает что нужно преобразовывать символ "а", а не "я"».
Предваряя следующий вопрос, «а что будет, если в переданном сообщении будет искажёны/потеряны какие-либо символы?», скажу, что для этого вводится обратное понятие — избыточность кода, например, широко известные CRC — коды циклического контроля, позволяющие столь же однозначно узнать, было ли сообщение при передаче искажено, и суметь восстановить его. Впрочем, как говорил сказочник, это уже другая история ;).
Большое спасибо за выложенный материал, сейчас пробежал глазами - уже более ясно стало, сегодня вечером буду применять это всё на практике)
Iska, если так же понятно расскажешь про арифметическое кодирование, то вообще расцелую
Полностью понял и даже проверил. На всякий случай задам вопрос: самые часто встречающиеся 3 символа будут иметь код 00 01 или 10, остальные же, будут иметь код 1110, 11110, 111110, 1111110, 111111110 и дт., а последний, самый редкий символ, будет иметь код 111111111111, то есть, символы с 4-го по n-1 будут заканчиваться на 0, а n - на 1?
vBulletin v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.