Как пройти по дереву Хаффмана? - PullRequest
Новая
       13

Как пройти по дереву Хаффмана?

2 голосов
/ 04 марта 2020

Я новичок в программировании и сейчас пытаюсь выучить Python. Я делаю, следую учебному пособию, которое состоит в создании приложения для кодирования Хаффмана в 4 этапа; У меня есть первые 3, но я застрял в четвертом. Первый шаг - это получение частоты уникального символа в строке, например: 

{'a': 8, 'b': 7, 'c': 6, 'd': 5, 'e': 4, 'f': 3, 'g': 2, 'h': 1}

Второй шаг - размещение символов и частоты в кортежах: 

[(8, 'a'), (7, 'b'), (6, 'c'), (5, 'd'), (4, 'e'), (3, 'f'), (2, 'g'), (1, 'h')]

Третий шаг - это создание дерево, которое выглядит примерно так: 

[(36, (15, (7, 'b'), (8, 'a')), (21, (9, (4, 'e'), (5, 'd')), (12, (6, 'c'), 
 (6, (3, 'f'), (3, (1, 'h'), (2, 'g'))))))]

Четвертым шагом является «обход» дерева при назначении каждой ветви кода, 1, если оно слева, и 0, если оно справа. Я думал о нескольких способах сделать это, но у меня не было большого успеха.

Я вижу, что каждый уровень списка дерева имеет два элемента (tree[1] и tree[2]), которые представляют левая и правая ветви, но я не знаю, какой самый эффективный способ повторения над деревом. Я подумал об использовании al oop, который продолжал бы углубляться в каждую ветвь, если бы он обнаружил принадлежащий ему символ, но это не сработало, и я не уверен, почему. 

def in_list(my_list, item):
    try:
        return any(item in sublist for sublist in my_list)
    except:
        return False


def get_codes(tree, tuples):

    tree = tree[0]

    for i in tuples:
        check = True
        while check is True:
            if in_list(tree[1], i) is True:
                print(i, 'is in 1')
                node1 = True
            else:
                node1 = False
            if in_list(tree[2], i) is True:
                print(i, 'is in 2')
                node2 = True
            else:
                node2 = False

            tree = tree[2]

            if node1 is False and node2 is False:
                check = False

    return 'test'

I ' Я даже не уверен, что это лучший способ подойти к этому.

Вот мой полный код на случай необходимости: 

def get_frequency(string):
    freq = dict.fromkeys(string, 0)   # fromKeys function takes every unique element of the given parameter.
    for i in string:                  # If given a string, it take each unique character.
        freq[i] += 1

    print('Step 1: ', freq)
    return freq


def get_nodes(dictionary):
    node_list = []

    list_keys = list(dictionary.values())
    list_values = list(dictionary.keys())

    for i in range(len(list_keys)):
        node_list.append((list_keys[i], list_values[i]))

    print('Step 2: ', node_list)
    return node_list


def get_tree(node_set):

    tree_list = node_set

    for i in range(len(tree_list)-1):

        # Sort nodes in ascending order. Lowest frequency first
        tree_list.sort(key=lambda tup: tup[0])

        # Defining the next node (f,l,r) based on the two tuples with the lowest frequency
        l_freq = tree_list[0][0]
        r_freq = tree_list[1][0]
        f = l_freq + r_freq

        l_tuple = tree_list[0]
        r_tuple = tree_list[1]

        # Append new node, delete old node
        node = (f, l_tuple, r_tuple)
        tree_list.remove(l_tuple)
        tree_list.remove(r_tuple)
        tree_list.append(node)

    print('Step 3: ', tree_list)
    return tree_list


def in_list(my_list, item):
    try:
        return any(item in sublist for sublist in my_list)
    except:
        return False


def get_codes(tree, tuples):

    tree = tree[0]

    for i in tuples:
        check = True
        while check is True:
            if in_list(tree[1], i) is True:
                print(i, 'is in 1')
                node1 = True
            else:
                node1 = False
            if in_list(tree[2], i) is True:
                print(i, 'is in 2')
                node2 = True
            else:
                node2 = False

            tree = tree[2]

            if node1 is False and node2 is False:
                check = False

    return 'test'


text = 'aaaaaaaabbbbbbbccccccdddddeeeefffggh'

frequency = get_frequency(text)
nodes = get_nodes(frequency)
huff_tree = get_tree(nodes)
codes = get_codes(huff_tree, get_nodes(frequency))

1 Ответ

1 голос
/ 04 марта 2020

Обычно наиболее удобный способ обхода дерева - рекурсивный. Это дерево имеет два вида узлов:

  • Кортежи с 2 элементами (_, letter) всегда являются листьями.
  • Кортежи с 3 элементами (_, left, right) всегда являются внутренними узлами.

Алгоритм такой: если вы находитесь на внутреннем узле, выполните рекурсию слева, расширив текущее кодовое слово на 0, а затем рекурсии справа, расширив текущее кодовое слово на 1. Если вы в листовом узле просто соедините букву с текущим кодовым словом. «Начальное» кодовое слово - пустая строка.

Вот реализация, использующая рекурсивную функцию генератора. 

def make_codewords(tree):
    def helper(node, codeword):
        if len(node) == 2:
            _, letter = node
            yield (codeword, letter)
        else:
            _, left, right = node
            yield from helper(left, codeword + '0')
            yield from helper(right, codeword + '1')

    root = tree[0]
    # convert (codeword, letter) pairs to dictionary
    return dict(helper(root, ''))

Пример: 

>>> tree = [(36, (15, (7, 'b'), (8, 'a')), (21, (9, (4, 'e'), (5, 'd')), (12, (6, 'c'), (6, (3, 'f'), (3, (1, 'h'), (2, 'g'))))))]
>>> make_codewords(tree)
{'00': 'b',
 '01': 'a',
 '100': 'e',
 '101': 'd',
 '110': 'c',
 '1110': 'f',
 '11110': 'h',
 '11111': 'g'}
...