Кодирование Хаффмана: обработка отрицательной неоднозначности с помощью нуля

Я написал простой компрессор текстовых файлов, использующий кодирование Хаффмана. Я кодирую текст и записываю двоичный файл, полученный в результате Хаффмана, в файл. Для декодирования я читаю двоичный код и прохожу по дереву Хаффмана.

Эта часть проста. Проблема возникает с 0 и отрицательными числами. Для практики/развлечения/обучения я решил использовать свои собственные методы двоичного преобразования (из байта Java в строку и наоборот) и решил представить отрицательные числа, изменив последний бит на 1.

Например, -2 = 00000101;; 2 = 00000100 (дополнительные 0 для заполнения, поскольку даже ненужные 0 важны в Хаффмане... хотя это не имеет значения)

Однако 0 = 00000000 = 00000001

Это может не показаться проблемой, но эти две двоичные строки сопоставляются с двумя разными символами в дереве Хаффмана.

Есть ли лучший способ обработки негативов в двоичном формате, который обойдет это?


binary negative-number huffman-code
person Thomas Shields    schedule 15.04.2013    source источник
comment
Если кто-то хочет увидеть код: github.com/thomas4g/huffman-coding   -  person Thomas Shields    schedule 15.04.2013

Ответы (1)


arrow_upward
0
arrow_downward

Я не уверен, что это поможет вам, но я попробую:

Во-первых, есть разные виды бинарников, чистые или другие. Чистый двоичный код НЕ допускайте отрицаний, он начинается с 0 .......

Вы можете использовать величину и знак, другой тип двоичного кода, он допускает отрицательные числа, а знак - или + представлен самым важным битом числа, например: Число с 4 битами:

0100=2

1100=-2

(1 бит для знака, самый важный, первый слева, а остальные 3 для числа)

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

Я надеюсь, что смог помочь вам, и извините за много ошибок на английском языке!

person carlos    schedule 15.04.2013
comment
Проблема в том, чтобы записать это в файл, который я пишу байт за байтом. Байт - это 8 бит. Поэтому мне нужно захватить 8-битные двоичные фрагменты за раз из закодированной строки Хаффмана. Байт в Java содержит от -128 до 127, поэтому я в основном вынужден обрабатывать отрицательные числа. Тем не менее, я полагаю, что простое перемещение бита знака вперед может сработать, хотя раньше у меня были проблемы с этим. Я попробую. - person Thomas Shields; 15.04.2013
comment
Таким образом, хотя бит знака в начале имеет больше смысла, он не решает проблему: 10000000 = 0 = 00000000, и проблема остается. - person Thomas Shields; 15.04.2013