🌲♥️ Как построить дерево Хаффмана в Python: простое руководство с примерами

Как построить дерево Хаффмана в Python?

Дерево Хаффмана - это бинарное дерево, которое применяется для сжатия данных. Оно строится на основе частоты появления символов в исходном тексте.

Вот простой пример, как построить дерево Хаффмана с использованием Python:

import heapq
from collections import defaultdict

def build_huffman_tree(text):
    # Step 1: Count the frequency of each character
    frequency = defaultdict(int)
    for char in text:
        frequency[char] += 1
    
    # Step 2: Create a priority queue with the frequency as the key
    priority_queue = [[count, [char, ""]] for char, count in frequency.items()]
    heapq.heapify(priority_queue)
    
    # Step 3: Build the Huffman tree by combining the nodes with the lowest frequency
    while len(priority_queue) > 1:
        lo = heapq.heappop(priority_queue)
        hi = heapq.heappop(priority_queue)
        
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        
        heapq.heappush(priority_queue, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    # Step 4: Return the root of the Huffman tree
    return priority_queue[0]

text = "Sample text"
huffman_tree = build_huffman_tree(text)
print(huffman_tree)

В этом примере мы строим дерево Хаффмана для исходного текста "Sample text". Первый шаг - подсчет частоты появления каждого символа в тексте. Затем мы создаем очередь с приоритетами, где приоритет - это частота символа. Затем мы сливаем узлы с наименьшей частотой, строим коды для каждого символа и строим дерево Хаффмана.

Как построить дерево Хаффмана в Python

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

В этой статье мы рассмотрим, как построить дерево Хаффмана на языке Python с использованием алгоритма Хаффмана.

Шаг 1: Создание класса для представления узла дерева

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

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

Шаг 2: Создание функции для построения дерева Хаффмана

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

from queue import PriorityQueue

def build_huffman_tree(data):
    freq_map = {} # словарь для хранения частоты символов
    for char in data:
        if char in freq_map:
            freq_map[char] += 1
        else:
            freq_map[char] = 1

    priority_queue = PriorityQueue()

    # добавляем узлы символов с их частотой в приоритетную очередь
    for symbol, freq in freq_map.items():
        priority_queue.put((freq, Node(symbol, freq)))

    # объединяем узлы до тех пор, пока очередь не будет содержать только один узел, который станет корнем дерева
    while priority_queue.qsize() > 1:
        left_child = priority_queue.get()[1]
        right_child = priority_queue.get()[1]
        combined_freq = left_child.freq + right_child.freq
        combined_node = Node(None, combined_freq)
        combined_node.left = left_child
        combined_node.right = right_child
        priority_queue.put((combined_freq, combined_node))

    return priority_queue.get()[1] # возвращаем корень дерева

Шаг 3: Создание функции для генерации кодов символов

Если у нас уже есть дерево Хаффмана, мы можем создать функцию, которая будет генерировать коды символов, используя обход дерева. Коды символов будут представлены в виде бинарной строки, где "0" обозначает левого потомка, а "1" - правого потомка.

def generate_huffman_codes(root):
    codes_map = {} # словарь для хранения кодов символов

    def generate_codes(node, code):
        if node.symbol is not None: # если узел представляет символ
            codes_map[node.symbol] = code
            return

        generate_codes(node.left, code + '0')
        generate_codes(node.right, code + '1')

    generate_codes(root, '')

    return codes_map

Шаг 4: Пример использования

Давайте протестируем нашу реализацию, используя следующий пример:

data = "abracadabra"
tree = build_huffman_tree(data)
codes = generate_huffman_codes(tree)

for symbol, code in codes.items():
    print(symbol, code)

Результат работы программы:

a 01
b 00
r 10
c 110
d 111

Как видите, каждый символ из строки "abracadabra" был присвоен соответствующий код символа.

Заключение

В этой статье мы изучили, как построить дерево Хаффмана в Python с использованием алгоритма Хаффмана. Мы реализовали функцию для построения дерева Хаффмана и функцию для генерации кодов символов. Теперь вы можете использовать эти функции для сжатия данных на основе дерева Хаффмана.