АЛГОРИТМ ШЕННОНА ФАНО PYTHON

Алгоритм Шеннона-Фано - это алгоритм сжатия данных, предложенный в 1948 году Клодом Шенноном и Робертом Фано. Он основан на принципе разделения множества символов на две группы, которые имеют схожую частоту появления в исходном тексте. Рекурсивное применение этого принципа позволяет получить оптимальный код для сжатия данных.

Алгоритм Шеннона-Фано может быть реализован на языке Python следующим образом:

def build_tree(symbols):    if len(symbols) == 1:        return (symbols[0], None, None)    freqs = [symbol[1] for symbol in symbols]    mid = len(freqs) // 2    left = build_tree([(symbols[i][0], freqs[i]) for i in range(mid)])    right = build_tree([(symbols[i][0], freqs[i]) for i in range(mid, len(symbols))])    return (None, left, right)    def assign_codes(node, code):    if node[0]:        codes[node[0]] = code    else:        assign_codes(node[1], code + '0')        assign_codes(node[2], code + '1')        def encode(text):    freqs = {}    for char in text:        if char in freqs:            freqs[char] += 1        else:            freqs[char] = 1    symbols = [(char, freqs[char]) for char in freqs]    symbols.sort(key=lambda x: -x[1])    assign_codes(build_tree(symbols), '')    result = ''    for char in text:        result += codes[char]    return resultdef decode(encoded):    node = tree    result = ''    for bit in encoded:        if not node[0]:            node = node[int(bit) + 1]        if node[0]:            result += node[0]            node = tree    return result

Этот код реализует алгоритм сжатия данных с использованием кодов Шеннона-Фано. Он состоит из трех основных функций:

build_tree(symbols) - строит бинарное дерево кодов Хаффмана для заданного множества символов и их частоты появления в исходном тексте;
assign_codes(node, code) - присваивает коды Шеннона-Фано для каждого символа в дереве;
encode(text) - кодирует исходный текст с использованием полученных кодов;
decode(encoded) - декодирует закодированный текст с использованием дерева кодов Шеннона-Фано.