Декодирование кодов, сгенерированных из алгоритма кодирования Шеннона Фано - PullRequest
Новая
       14

Декодирование кодов, сгенерированных из алгоритма кодирования Шеннона Фано

1 голос
/ 08 июня 2011

Я сгенерировал коды для различных символов в файле, используя алгоритм Шеннона Фано. Теперь моя проблема заключается в том, как я буду хранить эти коды в файле (так как файл в байтах), чтобы при чтении читатель мог убедиться, что в какой-то момент это конец кода для конкретного символа. Так что дополнительный код не будет прочитан.

1 Ответ

3 голосов
/ 08 июня 2011

Во-первых, вы можете использовать побитовые операции для считывания переменного байта (не кратного 8) из байтового массива.

Во-вторых, если код является действительным Код префикса , что удовлетворяет 

there is no valid code word in the system that is a prefix (start) of any other valid code word in the set

, тогда вы можете определить, где заканчивается код, сравнив префикс с таблицей.

Обычно это делается следующим образом:

  • Предположим, длина кода составляет от 1 до 16 бит.
  • Загрузить следующие 16 бит из файла в переменную.
  • Сравните 16-битную переменную стаблица, которая содержит следующие значения.Можно использовать бинарный или радикальный поиск.
    • Ключ: код Шеннона-Фано или Хаффмана, сдвинутый так, что старший бит находится в старшем значащем бите.
    • KeyLength: фактическое количество бит в коде Шеннона-Фано или Хаффмана.Это позволяет нам вычесть количество декодированных битов из переменной.
    • Значение: значение, в которое будет декодирован код.
  • Вычесть (удалить) декодированные битыот переменной в зависимости от кода.Например, если код имеет 9 битов, мы удалим 9 бит из MSB и оставим 7 битов.
  • Считаем следующие 9 бит из файла, соединив их с 7 некодированными битами.
  • Повторите процесс.
...