Декодирование кода Хаффмана со словарем

Question

Мне нужно декодировать код Хаффмана, который я кодировал с помощью моей программы, используя файл, содержащий перевод между битами ASCII и Хаффмана. У меня уже есть словарь в проножке из «кодов» в ASCII, как это:

{'01110': '!', '01111': 'B', '10100': 'l', '10110': 'q', '10111': 'y'} 

Я создал функцию:

def huffmanDecode (dictionary, text) : 

Это необходимо словарь и код. Я попытался найти текст для ключа в словаре и использовать как заменить образуют метод Струнные а также к югу отповторного но ни один из них декодирует сообщение правильно. , например, если код:

011111011101110 

Он должен быть простым, чтобы расшифровать его:

By! 

Но я не был в состоянии сделать это путем перебора кода и поиска матчей словарь!

Как я могу декодировать код с помощью ключей и их значений в словаре, найдя ключ внутри текста и заменив его на его значение?

Любая помощь очень ценится.

Answer 1

Не знаете, что вы пробовали, но re.sub или replace, вероятно, не сработали, потому что они не обязательно заменяются с начала строки. Вы должны посмотреть, с какого кода начинается строка, затем заменить этот код и продолжить работу с остальной частью строки.

Например, так:

def huffmanDecode (dictionary, text): 
    res = "" 
    while text: 
     for k in dictionary: 
      if text.startswith(k): 
       res += dictionary[k] 
       text = text[len(k):] 
    return res 

Или рекурсивно:

def huffmanDecode (dictionary, text): 
    if text: 
     k = next(k for k in dictionary if text.startswith(k)) 
     return dictionary[k] + huffmanDecode(dictionary, text[len(k):]) 
    return "" 

Вы также могли бы сделать регулярное выражение из ваших кодов и использовать re.match, чтобы найти следующий:

import re 
def huffmanDecode (dictionary, text): 
    p = "|".join(dictionary) # join keys to regex 
    res = "" 
    while text: 
     m = re.match(p, text) 
     res += dictionary[m.group()] 
     text = text[len(m.group()):] 
    return res 

Примечание: ни у одного из них нет правильной обработки ошибок, и он будет терпеть неудачу или цикл навсегда, если коды не соответствует сообщению, но это должно помочь вам начать.

Answer 2

с помощью bitarray модуля Вы получаете Хаффмана ен-/де-кодирования бесплатно и, вероятно, более эффективным, чем все остальное:

from bitarray import bitarray 

huffman_dict = { 
    '!': bitarray('01110'), 'B': bitarray('01111'), 
    'l': bitarray('10100'), 'q': bitarray('10110'), 
    'y': bitarray('10111') 
} 

a = bitarray() 
a.encode(huffman_dict, 'Bylly!') 
print(a) 

dec = bitarray('011111011101110').decode(huffman_dict) 
print(dec) 
print(''.join(dec)) 

# # output: 
# bitarray('011111011110100101001011101110') 
# ['B', 'y', '!'] 
# By! 

, если вы не хотите, чтобы установить модуль, прочитайте раздел ниже.

---

здесь является вариантом с использованием дерева Хаффмана для декодирования - программа работает, но может быть лучше варианты для представления бинарного дерева (я выбрал кортеж).

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

код в древовидной форме выглядит следующим образом (слишком отступом, чтобы сделать древовидную структуру видимой):

huffman_tree = \ 
    ( # 0 
     ( # 00 
      None, 
      # 01 
      ( # 010 
       None, 
       # 011 
       ( # 0110 
        None, 
        # 0111 
        ( # 01110 
         '!', 
         # 01111 
         'B')))), 
     # 1 
     ( # 10 
      ( # 100 
       None, 
       # 101 
       ( # 1010 
        ( # 10100 
         'l', 
         # 10101 
         None 
        ), 
        # 1011 
        ( # 10110 
         'q', 
         # 10111 
         'y'))), 
      # 11 
      None)) 

с помощью который вы можете декодировать с:

def huffman_decode(strg): 
    ret = '' 
    cur_node = huffman_tree 
    for char in strg: 
     cur_node = cur_node[int(char)] 
     if cur_node is None: 
      raise ValueError 
     elif isinstance(cur_node, str): 
      ret += cur_node 
      cur_node = huffman_tree 
    return ret 

print(huffman_decode('011111011101110')) 

если в результате декодирования None произошла ошибка, и ValueError поднят. как только декодирование попадает в строку, текущий узел cur_node сбрасывается в «корневой узел», и игра начинается с начала дерева.

и только потому, что я могу: здесь это визуальное отображение вашего (неполном) дерево Хаффмана (это может помочь понять, что делает алгоритм: всякий раз, когда вы сталкиваетесь с 0: идите направо + вниз, каждый раз, когда вы столкнулись с 1: перейти правый + вверх); если вы нажмете конечный узел: верните символ на этом узле и перезапустите его в корневом узле.