I need to search some data encoded by a Huffman tree, but not by simply walking the tree: I need test combinations of the data for a property and continue searching based on whether the test is positive or not. To this end, I've also returned the intermediate steps of the Huffman algorithm>
Here is the code I use to generate the extended tree:
import heapq def encode(symbfreq): tree = [[wt, [sym, ""]] for sym, wt in symbfreq] heapq.heapify(tree) while len(tree)>1: lo, hi = sorted([heapq.heappop(tree), heapq.heappop(tree)], key=len) for pair in lo[1:]: pair = '0' + pair for pair in hi[1:]: pair = '1' + pair heapq.heappush(tree, [lo + hi] + lo[1:] + hi[1:]) return sorted(heapq.heappop(tree)[1:], key=lambda p: (len(p[-1]), p)) def next_power_of_two(n): return int(2**( ceil(log(n,2)))) def full_encode(tree): huffman_tree = encode(tree) complete_tree = huffman_tree get_intermediate_node = lambda val, arr : ''.join( [ char for char,binary in itertools.ifilter( lambda node : node.startswith(val),arr)] ) for val in range( next_power_of_two( len(huffman_tree) ) ): bvalue = bin(val)[2:] node = [ get_intermediate_node( bvalue , huffman_tree) , bvalue ] if node not in complete_tree: complete_tree.append( node) complete_tree =[y for y in complete_tree if y!=''] complete_tree = sorted( complete_tree , key=lambda p: (len(p[-1]), p) ) return complete_tree
So for example this input:
tree = [('0',0.25),('0',0.25),('0',0.25),('0',0.125),('1',0.125)]
produces this output:
tree = [['00', '0'], ['0', '00'], ['0', '01'], ['0', '10'], ['0', '110'], ['1', '111']]
Once I've done that, I need to search the tree. Since I've got access to all the intermediate stages, I start by checking whether the data in the first leaf contains a '1' (this leaf is encoded by '0'): if this is true then I check the next leaf which has a '0' in the second position of it's code. If false, I check the leaf whose begins with '10'. I keep on doing this until I've found the leaf (and the encoding) which has only a '1' in the data. The code is below:
#searching an extended huffman list 0=>left branch 1=>right branch def search_huff_list(complete_tree, max_depth): defective = 0 loops = 0 stage = 0 code = ['0'] while defective == 0: loops += 1 current = complete_tree[stage] print(stage) if current == '1': defective = complete_tree[stage] return defective,loops if len(current) == max_depth: if current=='1': defective = complete_tree[stage] return defective, loops else: defective = complete_tree[stage+1] return defective, loops if not '1' in current: code[-1] = '1' code.append('0') partial_code = ''.join(code) print(partial_code) stage = complete_tree.index(next(x for x in complete_tree if x.startswith(partial_code) ) ) else: code.append('0') partial_code = ''.join(code) stage = complete_tree.index(next(x for x in complete_tree if x.startswith(partial_code) ) ) return 0
For the input above, this algorithm finds the '1' (it's easier to debug, if the labels are 'a','b','c','d','e'). I'm building up a partial code and searching the original tree (the extended list) for the first code that begins with that series of bits.
The main problem I have is that this is that this algorithm is complicated enough already: yet I've got to get it to find a 1 in a random tree next. There's already enough corner-case if-else catching going on (for example if I get right down to the end, and the test on the left branch comes back negative, then I know the '1' is in the right branch and I don't need to do another test).
What could I do to make the code more readable/easier to debug? I guess what I'm actually doing isn't that efficient, but I'm struggling to think of another way to do it.