Как создать двоичное дерево из частотного словаря - PullRequest
Новая
       15

Как создать двоичное дерево из частотного словаря

2 голосов
/ 07 марта 2019

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

Вот мой код: 

with open(input('enter a file: ')) as name:
    fh = name.read()
    print(fh)

#create the frequency dicitonary
freqdict = {}
for ch in fh:
    if ch in freqdict:
        freqdict[ch] += 1
    else:
        freqdict[ch] = 1
freqdict = sorted(freqdict.items(), key = lambda x: 
x[1], reverse = True)
print(freqdict)

class Node:
    def __init__(self, left = None, right = None, 
data):
        self.left = left
        self.right = right
        self.data = data

    def children(self):
        return (self.left, self.right)

    def nodes(self):
        return (self.left, self.right)

    def __str__(self):
        return str(self.left, self.right)

1 Ответ

0 голосов
/ 08 марта 2019

Чтобы создать базовое дерево Хаффмана, вы должны сначала отсортировать список частот в порядке возрастания и начать с объединения первых двух элементов в отсортированном контейнере с элементами, создающими новый узел дерева Хаффмана, добавив новый узел в контейнер,прибегают к контейнеру, а затем продолжают процесс, пока контейнер не содержит только один узел: полное дерево.Чтобы пройти по дереву, вы можете создать метод поиска в классе, который создает путь 1 s и 0 s: 1 регистрируется, если искомое значение находится в правом дочернем элементе текущего узла,или 0, если он слева: 

from collections import Counter
def get_frequencies(data):
  return sorted(Counter(data).items(), key=lambda x:x[-1])

class Node:
  def __init__(self, _a, _b):
    self.left, self._sum, self.right = _a, sum(i._sum if hasattr(i, '_sum') else i[-1] for i in [_a, _b]), _b
  def __contains__(self, _val):
    if isinstance(self.left, tuple) and self.left[-1] == _val or isinstance(self.right, tuple) and self.right[-1] == _val:
      return True
    return any([_val in self.left, _val in self.right])
  def _lookup(self, chr, _path = []):
    if isinstance(self.left, tuple) and self.left[-1] == chr:
      return _path+[0]
    if isinstance(self.right, tuple) and self.right[-1] == chr:
      return _path+[1]
    _flag = 'right' if chr in self.right else 'left'
    return getattr(getattr(self, _flag), '_lookup', lambda _, p:p)(chr, _path+[1 if _flag == 'right' else 0])
  def __getitem__(self, chr):
     return self._lookup(chr)

corpus = "Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding and/or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT"
fs = get_frequencies(corpus)
while len(fs) > 1:
  a, b, *_fs = fs
  fs = sorted(_fs+[Node(a, b)], key=lambda x:x._sum if hasattr(x, '_sum') else x[-1])

_tree = fs[0]
final_result = ''.join(''.join(map(str, _tree[i])) for i in corpus)

Вывод: 

'1001111010100000000010001101000011111101110110010110011100110111111101011101011101010010110100011110110101001100101010010111110100100110101111001111011000011110110101111010001110001101001100111010111001011000000001110011000111110111011001011001111101001000101011010111001101111111101110111000110001101100010110001001111101010011111000010111000010111001011101100101101110111011001100011101111110010101011010101011111011101110001010111001011000111011100111011000101101011101001010100011001110101110010101111011110001110111111101100001110000001100010010001100010110111111010000100101001100110111001011101010011100110001011011111011101010110110100011110101111101110110010110011101011100101011110111100110000100111111100000001001111110001110010100001011111110110000111100111101010000000001000110100001111110111011001000110001011011100110101111010000111110100110001101110111001000111101001000100011110010110010000011100011001011010111100001011110000000100111111000010101010000010011001011110011011011010111100111101010000000001000110100001111100001101000001101100110011101000110011110000111010011111110101111001110011011011010100001001101011101111101001010001011000001110101111010110101111001110101001000100101'

Окончательный сжатый результат генерируется путем зацикливания исходного ввода (corpus) и поискакодирование Хаффмана для каждого символа через Node.__getitem__.

...