Как найти коды Хаффмана переменной длины в строке для лучшего соответствия?

Question

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

Например, строка

"++----++--++--+-++++++-+-+-----++-+---+-+---+-++--" 

, из которой явручную создал следующий символ Хаффмана для преобразования строки в частоту:

In [1665]: symb2freq                                                                                                                                                                                       
Out[1665]: {'++--': 4, '-+-+-': 2, '--': 1, '+-++++++': 1, '----++-+--': 1, '--+-': 1}

Это позволило мне иметь двоичную строку Хаффмана 110011111000011010110011 для представления:

'++----++--++--+-++++++-+-+-----++-+---+-+---+-++--'

, что в два раза меньше и котороелучше, чем фиксированная длина символов symb2frequencies. Мой вопрос, есть ли регулярное выражение, или itertools, или метод программирования для создания symb2frequencies нескольких длин, с наибольшей длиной. В моем случае наибольшая длина равна 11. Самая короткая длина не имеет значения, но цель состоит в том, чтобы получить наилучшие возможные частоты, чтобы уменьшить размер кода Хаффмана для представления дерева. Если я группирую по размеру набора, я не могу получить короткую двоичную строку Хаффмана, чтобы представить лучший кодовый набор.

Поэтому мой вопрос заключается в том, как мне сделать это программно, используя regex или itertools, или любой другой метод дляконвертировать:

"++----++--++--+-++++++-+-+-----++-+---+-+---+-++--"

в:

In [1665]: symb2freq                                                                                                                                                                                       
Out[1665]: {'++--': 4, '-+-+-': 2, '--': 1, '+-++++++': 1, '----++-+--': 1, '--+-': 1}

, который я построил вручную.

Я думаю, что это сложная проблема, поэтому заранее спасибо за любые советы о том, какчтобы решить эту проблему.

Я написал этот код, чтобы показать, что вы можете использовать коды переменной длины для декодирования кода Хаффмана в показанный шаблон, который я использую для воссоздания числа 1009732533765201 вдвое меньше. Я создал sym2freq вручную, и мне нужна помощь по поводу того, как создать его программно, чтобы получить лучшее сжатие, чем заданный размер группировки. У меня есть программа, которая создает математический шаблон для воссоздания числа, и я ищу, чтобы создать коды переменной длины, чтобы наилучшим образом представить те шаблоны, которые находятся в формате + и - *

# Incorporated a better method of rebuilding the string from RoyM
# Uncompresses the number: 1009732533765201
# which has the binary:
# 0b11100101100101100010101100111111100100010001010001
# Our compressed binary is:
# 110011111000011010110011
# We compress a variable length pattern that is decoded 
# to try to achieve nearly as good compression (maybe better in this case )and to more importantly 
# to compare compression as this is a different approach
# to that of binary compression of Huffman using XOR Patterns
# S is a representation of XOR math that is required to rebuild the original number
# so we don't compress the number itself, we compress the XOR math to rebuild the number
# instead

s={'11': '++--', '01': '-+-+-', '000': '+-++++++', '001': '--', '100': '--+-', '101': '----++-+--'}
compressed_binary='110011111000011010110011'

def decodepattern(pattern, j=1):
   x=2
   for c in range(len(pattern)):
     if pattern[c]=='+' or pattern[c]=='1':
       j^=x
     else:
       j^=-x
     x<<=1
   return abs(j)


i = 0
j = 0
uncompressed_string = ''
while(j<len(compressed_binary)):
    if compressed_binary[i:j] in s:
        uncompressed_string += s[compressed_binary[i:j]]
        i = j
    else:
        j += 1
uncompressed_string += s[compressed_binary[i:j]]
answer = decodepattern(uncompressed_string)

print("Bin length of 1009732533765201 is 50 which is the same as the pattern length")
print("Original Bin of 1009732533765201 is: ")
print(bin(1009732533765201)[2:])
print("Original Pattern:")
print(uncompressed_string)
print("Compressed to: ", bin(13600435)[2:])
print("110011111000011010110011 uncompressed to the original string pattern of : ")
print(uncompressed_string)
print("Which then i was able to recreate the original integer of: ")
print(decodepattern(uncompressed_string))

Выводпрограммы:

Bin length of 1009732533765201 is 50 which is the same as the pattern length
Original Bin of 1009732533765201 is: 
11100101100101100010101100111111100100010001010001
Original Pattern:
b'++----++--++--+-++++++-+-+-----++-+---+-+---+-++--'
Compressed to:  110011111000011010110011
110011111000011010110011 uncompressed to the original string pattern of : 
b'++----++--++--+-++++++-+-+-----++-+---+-+---+-++--'
Which then i was able to recreate the original integer of: 
1009732533765201

Итак, вы можете видеть, что я могу использовать коды переменной длины для распаковки числа, я просто не знаю, как создавать коды переменной длины (до определенной длины), не делая этоговручную.

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

"++----++--++--+-++++++-+-+-----++-+---+-+---+-++--"

и создания такого symb2freq (как я сделал вручную):

In [1665]: symb2freq                                                                                                                                                                                       
Out[1665]: {'++--': 4, '-+-+-': 2, '--': 1, '+-++++++': 1, '----++-+--': 1, '--+-': 1}

Answer 1

Хотя я не уверен в правильности вопроса, вот как вы можете использовать все возможные кодовые книги:

#!/usr/bin/env python3

import huffman


def find_best_codebook(string, max_symbol_length, max_partitions):
    min_entropy = len(string)
    best_i = None
    best_weights = None
    best_codebook = None
    for i, tokens in enumerate(gen_partitions(string, max_partitions=max_partitions)):
        if any(len(t) > max_symbol_length for t in tokens):
            continue
        symbol_weights = compute_weights(tokens)
        codebook = huffman.codebook(symbol_weights.items())
        entropy = compute_entropy(symbol_weights, codebook)
        print(f'i={i} X={symbol_weights} H(X)={entropy}')

        if entropy < min_entropy:
            best_i = i
            best_weights = symbol_weights
            best_codebook = codebook
            min_entropy = entropy

    print(f'best i={best_i} X={best_weights} H(X)={min_entropy}')
    print('best codebook:', best_codebook)
    return best_codebook, min_entropy


def gen_partitions(string, max_partitions=None):
    if max_partitions is None:
        max_partitions = len(string)

    if max_partitions <= 0:
        yield [string]
        return

    for index in range(len(string) + 1):
        for rest in gen_partitions(string[index:], max_partitions - 1):
            yield [string[:index]] + rest


def compute_weights(tokens):
    freqs = {}
    for token in tokens:
        if not token:
            continue
        freqs[token] = freqs.get(token, 0) + 1
    return freqs


def compute_entropy(symbol_weights, codebook):
    return sum(len(code) * symbol_weights[symbol] for symbol, code in codebook.items())


if __name__ == '__main__':
    string = '++----++--++--+-++++++-+-+-----++-+---+-+---+-++--'
    max_symbol_length = 11
    max_partitions = len(string) - max_symbol_length
    find_best_codebook(string, max_symbol_length, max_partitions)

Обратите внимание, что разбиение строки длины N на все возможные разбиения является экспоненциальным вдлина строки (N точек разделения, два решения в каждом: разделение и отсутствие разделения, следовательно, O (2 ^ N)).

Кроме того, учитывая способ формирования вопроса, вы сможете получить лучшее сжатие, просто разбив входные данные на последовательные порции максимальной длины кодового слова. Например, используя максимальную длину символа 11, как указано в вопросе, вы можете сделать {'++----', '++--++--+-+', '+++++-+-+--', '---++-+---+', '-+---+-++--'}, чтобы получить 5 символов (не более 3-битных кодовых слов) и сжатый текст не более 15 битов.