CODEWITHSUNDEEP
pythontreehuffman-code
Big Puncho
Big Puncho

Reputation: 301

Decoding bit sequence by iterating a tree

phrase='hello overflow'
sequence='00100011101010000110101011000110110100'
tree=[
       [
         [
           [' ', 'f'],
           ['h', 'r']
         ],
         [
           ['w', 'v'],
           'e'
         ]
       ],
       ['l', 'o']
     ]

I'm having a bit of a problem doing the iteration of the list "tree". What I want to do is, given an input stream of bits, "sequence" in this case, "tree" is iterated accordingly to each bit, for example:

If I want the letter 'h', in "phrase", wich corresponds to the 4 first bits in "sequence", (0010), I must go to tree[0][0][1][0].

I have 2 ideas on how to do this, one of them is by using a for loop like this:

for bit in phrase:
    if len(tree[bit])>1:
        calls recursive method, plus some rules

def recursive(list,bit):
    return list[bit]

But this gives me a problem, as I cannot feed new bits from the stream, while inside the loop from the recursive method.

The other is by using some sort of parallel iteration between "sequence" and "tree".

Can anyone shed some light on this?

Upvotes: 1

Views: 181

Answers (1)

Mark Adler
Mark Adler

Reputation: 112394

You don't need recursion. Just loop over the bits in the sequence. Start with pos = tree. For each bit, move down the tree: pos = pos[bit]. If pos is still a list, continue with the next bit. If pos is not a list, then output the character there and set pos back to the root tree and continue with the next bit. If you leave the loop with pos not equal to tree, then note an error that you received an incomplete code.

Upvotes: 1

Related Questions