Python - Producing Huffman Tree From Nested Loops

Question

I decided to try and make a Huffman Tree program. So far, I've managed to have it produce a list of all the weighted outputs (which I believe is correct), but I'm having difficulties presenting this in a viewable format.

I messed with a recursive object I made called 'Node', but I know I've done something wrong, and the output is nonsensical. My code is as below:

main.py:

import sys

word = ' '.join(sys.argv[1:])

freq = {}

for char in word:
  if char in freq.keys():
    freq[char] += 1
  else:
    freq[char] = 1

freq = [[x, y] for x, y in freq.items()]
freq.sort(key=lambda x: x[1])

while len(freq) != 1:
  freq[1][0] = [freq[0][0], freq[1][0]]
  freq[1][1] = freq[0][1] + freq[1][1]
  freq.pop(0)
  freq.sort(key=lambda x: x[1])

print(freq[0][0])

freq = freq[0][0]

class Node(object):

  value = None

  def __init__(self, li):
    if type(li) not in [tuple, list, set, dict]:
      self.value = li

    else:
      if len(li) != 2:
        raise ValueError('\'Node\' object only takes 2-part iterables or raw values as an argument')
      self.left = Node(li[0])
      self.right = Node(li[1])

  def __repr__(self):
    if self.value != None:
      return '"' + str(self.value) + '"'

    return ' ' * self.left.size() + '|' + self.right.size() * ' ' + '\n' + str(self.left) + str(self.right)

  def size(self):
    if self.value != None:
      return 1

    return self.left.size() + self.right.size()

n = Node(freq)
print(n)

I'm currently not so bothered about errors in my actual Huffman creation code, since it'll be easier for me to go back and fix these once I can view the output nicer.

Example in/out:

she sells sea shells on the sea shore produces:

[[' ', ['h', 'l']], ['s', [[['t', ['n', 'r']], ['a', 'o']], 'e']]]

or,

   |
 |
" " |
"h""l" |
"s"     |
   |
 |
"t" |
"n""r" |
"a""o""e"

(clearly unclear 'tree' thing)

it is easier to build something like this https://i.stack.imgur.com/8amGY.png — furas, Jan 02 '18 at 23:51
@furas that would be just as good- still easy to the eyes. looks more manageable too- ill work on adding some sort of 'depth' attribute to the nodes, see if i can cook something up — , Jan 03 '18 at 01:20
I found module [AsciiTree](https://github.com/mbr/asciitree) — furas, Jan 03 '18 at 01:28
@furas cool, thanks. ill take a look. will it natively support the depth-nested list like ive presented in the output above? — , Jan 03 '18 at 01:29
it seems it uses nested elements but it uses dictionary instead list. I found other question on SO [How to “draw” a Binary Tree to the console](https://stackoverflow.com/questions/801740/c-how-to-draw-a-binary-tree-to-the-console) or [Displaying a tree in ASCII](https://stackoverflow.com/questions/15675261/displaying-a-tree-in-ascii) — furas, Jan 03 '18 at 01:33
@furas thanks. I'll take a look at those questions and the module, and see if i can figure this one out myself. Appreciated! — , Jan 03 '18 at 01:36

Python - Producing Huffman Tree From Nested Loops

0 Answers0