Есть ли лучший способ для реализации этого алгоритма Хаффмана на языке Python?


Я написал это осуществление кодирования Хаффмана. Пожалуйста, предложите способы, чтобы сделать этот код лучше, т. е. более подходящие для Python.

from collections import Counter

#####################################################################

class Node(object):
  def __init__(self, pairs, frequency):
    self.pairs = pairs
    self.frequency = frequency

  def __repr__(self):
    return repr(self.pairs) + ", " + repr(self.frequency)

  def merge(self, other):
    total_frequency = self.frequency + other.frequency
    for p in self.pairs:
      p[1] = "1" + p[1]
    for p in other.pairs:
      p[1] = "0" + p[1]
    new_pairs = self.pairs + other.pairs
    return Node(new_pairs, total_frequency)

#####################################################################

def huffman_codes(s):
  frequency_table = Counter(s)
  initial_table = []
  for k, v in frequency_table.items():
    initial_table.append([k, v])
  initial_table = sorted(initial_table, key = lambda p : p[1])
  # print(initial_table)
  table = []
  for entry in initial_table:
    ch = entry[0]
    freq = entry[1]
    table.append(Node([[ch, ""]], freq))
  # print(table)
  while len(table) > 1:
    first_node = table.pop(0)
    second_node = table.pop(0)
    new_node = first_node.merge(second_node)
    table.append(new_node)
    table = sorted(table, key = lambda n : n.frequency)
    # print(table)
  return dict(map(lambda p: (p[0], p[1]), table[0].pairs))

#####################################################################

print(huffman_codes('yashaswita'))

Спасибо



3931
7
задан 21 августа 2011 в 12:08 Источник Поделиться
Комментарии
3 ответа

Я согласен с АГФ , за исключением пункта 4.
Это мой попробовать на свой код:

from collections import Counter
import heapq

class Node(object):
def __init__(self, pairs, frequency):
self.pairs = pairs
self.frequency = frequency

def __repr__(self):
return repr(self.pairs) + ", " + repr(self.frequency)

def merge(self, other):
total_frequency = self.frequency + other.frequency
for p in self.pairs:
p[1] = "1" + p[1]
for p in other.pairs:
p[1] = "0" + p[1]
new_pairs = self.pairs + other.pairs
return Node(new_pairs, total_frequency)

def __lt__(self, other):
return self.frequency < other.frequency

def huffman_codes(s):
table = [Node([[ch, '']], freq) for ch, freq in Counter(s).items()]
heapq.heapify(table)
while len(table) > 1:
first_node = heapq.heappop(table)
second_node = heapq.heappop(table)
new_node = first_node.merge(second_node)
heapq.heappush(table, new_node)
return dict(table[0].pairs)

print(huffman_codes('yashaswita'))

5
ответ дан 21 августа 2011 в 02:08 Источник Поделиться

Действительно принадлежит на codereview.


  1. Используйте четыре пространства отступа. Это питон стандарти сделает код более "подходящие для Python". Редактировать: вы следуете Пеп-8 во всем остальном, насколько я могу сказать, так что если вам нравится два отступа, это не имеет большого значения. Ваш код очень легко читать.

  2. Вам не нужно разбираться каждый раз; вы даже не нужно полностью отсортированный список. Python имеет также тип данных для этого-это называется heapq. Используйте это heappush и heappop методов, поэтому вам не придется сортировать каждый раз. Можно написать один цикл строке, чтобы сделать дом на дереве. Читать то, что страница говорит о приоритетных очередей-это то, что вы используете.

  3. Вам не нужно ничего подобного

    return dict(map(lambda p: (p[0], p[1]), table[0].pairs))

    просто

    return dict(table[0].pairs)

    делает точно то же самое.


  4. Если вы действительно хотите свести к минимуму линии, все как и раньше а могут быть записаны в виде одной строки:

    table = sorted((Node([[p[0], ""]], p[1]) for p in Counter(s).iteritems()), key = lambda n : n.frequency)

6
ответ дан 21 августа 2011 в 01:08 Источник Поделиться

Как правило, петли не рекомендуется в Python, так как он интерпретируется, а не компилируется, следовательно, тело цикла будет "перекомпилировать" на каждой итерации.

с помощью карты/уменьшить один хороший способ, чтобы избежать петли. другой используется для.. В, например:

initial_table=[[k, v] for k, v in frequency_table.items()]

и аналогично для 2-й цикл.

3
ответ дан 21 августа 2011 в 01:08 Источник Поделиться