Нахождение длины сжатого текста (код Хаффмана) - PullRequest
Новая
       26

Нахождение длины сжатого текста (код Хаффмана)

0 голосов
/ 22 мая 2018

Дан текст из n символов и двоичное дерево, сгенерированное кодированием Хаффмана, такое, что у конечных узлов есть атрибуты: строка (сам символ) и целое число (его частота в тексте).Путь от корня до любого листа представляет его кодовое слово.

Я хотел бы написать рекурсивную функцию, которая вычисляет длину сжатого текста и находит его Большой O-complexitiy.

Так что дляНапример, если у меня есть текст 

abaccab

, и каждый символ имеет соответствующую частоту и глубину в дереве Хаффмана: 

   4 
  / \ 
 a:3 5 
    / \ 
   b:2 c:2

, тогда общая длина сжатого текста составляет 11

Я придумал это, но это кажется очень грубым: 

def get_length(node, depth):
    #Leaf node
    if node.left_child is None and node.right_child is None: 
        return node.freq*depth

    #Node with only one child
    elif node.left_child is None and node.right_child is not None: 
        return get_length(node.right_child, depth+1)
    elif node.right_child is None and node.left_child is not None:
        return get_length(node.left_child, depth+1)

    #Node with two children
    else:
        return get_length(node.left_child, depth+1) + get_length(node.right_child, depth+1)

get_length(root,0)

Сложность: O (log 2n), где n - количество символов.

Как я могу улучшить это?Какова будет сложность в этом случае?

Ответы [ 2 ]

0 голосов
/ 05 августа 2019

Чтобы узнать точную общую длину сжатого текста, я не вижу способа обойтись индивидуально с каждым уникальным символом и счетчиком того, сколько раз он встречается в тексте, что в сумме составляет O (n) где n - количество уникальных символов в тексте (также n - количество листовых узлов в дереве Хаффмана).Существует несколько различных способов представления преобразования из кодов Хаффмана в незашифрованные буквы.Ваше двоичное представление дерева подходит для нахождения точной общей длины сжатого текста;в дереве всего 2 * n - 1 узлов, где n - количество уникальных символов в тексте, а для рекурсивного сканирования каждого узла требуется 2 * n - 1 время, что также эквивалентноO (n). 

def get_length(node, depth):
    #Leaf node
    if node.left_child is None and node.right_child is None: 
        return node.freq*depth

    #null link from node with only one child, either left or right:
    elif node is None:
        print("not a properly constructed Huffman tree")
        return 0

    #Node with two children
    else:
        return get_length(node.left_child, depth+1) + get_length(node.right_child, depth+1)

get_length(root,0)
0 голосов
/ 22 мая 2018

Хотя сложность определения длины сжатого текста должна составлять O(n) (с использованием простого len), сложность по времени для завершения кодирования должна составлять O(nlog(n)).Алгоритм выглядит следующим образом: 

t1 = FullTree
for each character in uncompressed input do: #O(n)
  tree_lookup(t1, character) #O(log(n))

Цикл по несжатому входу равен O(n), тогда как поиск узла в сбалансированном двоичном дереве равен O(log(n)) (O(n) наихудший случай или нет).Таким образом, результат равен n*O(log(n)) => O(nlog(n)).Также обратите внимание, что O(log 2n) для сложности поиска точен, так как по правилам логарифмов может быть упрощен до O(log(2)+log(n)) => O(k + log(n)), for some constant k. Однако, поскольку Big-O проверяет только худшие приближения, O(k+log(n)) => O(log(n)).

Вы можете улучшить свое двоичное дерево, создав более простой поиск в своем дереве: 

from collections import Counter

class Tree:
  def __init__(self, node1, node2):
     self.right = node1
     self.left = node2
     self.value = sum(getattr(i, 'value', i[-1]) for i in [node1, node2])
  def __contains__(self, _node):
     if self.value == _node:
       return True
     return _node in self.left or _node in self.right
  def __lt__(self, _node): #needed to apply sorted function
     return self.value < getattr(_node, 'value', _node[-1])
  def lookup(self, _t, path = []):
     if self.value == _t:
       return ''.join(map(str, path))
     if self.left and _t in self.left:
       return ''.join(map(str, path+[0])) if isinstance(self.left, tuple) else self.left.lookup(_t, path+[0])
     if self.right and _t in self.right:
       return ''.join(map(str, path+[1])) if isinstance(self.right, tuple) else self.right.lookup(_t, path+[1])
  def __getitem__(self, _node):
     return self.lookup(_node)

s = list('abaccab')
r = sorted(Counter(s).items(), key=lambda x:x[-1])
while len(r) > 1:
  a, b, *_r = r
  r = sorted(_r+[Tree(a, b)])

compressed_text = ''.join(r[0][i] for i in s)

Вывод: 

'10110000101'
...