# Combinatorial searching of Huffman trees

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[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(tree, [lo[0] + hi[0]] + 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[1].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[0]!='']
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[0] == '1':
defective = complete_tree[stage]
return defective,loops
if len(current[1]) == max_depth:
if current[0]=='1':
defective = complete_tree[stage]
return defective, loops
else:
defective = complete_tree[stage+1]
return defective, loops
if not '1' in current[0]:
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[1].startswith(partial_code) ) )
else:
code.append('0')
partial_code = ''.join(code)
stage = complete_tree.index(next(x for x in complete_tree if  x[1].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.

• I don't understand what you are trying to achieve here. Can you explain the problem you are trying to solve? – Gareth Rees Nov 6 '13 at 11:31
• @GarethRees Hi Gareth, I've modified the data structure so that the groups are encoded in the Huffman tree. The new code can be found here: stackoverflow.com/questions/19817863/sorting-huffman-leaves – Tom Kealy Nov 6 '13 at 21:53
• @GarethRees I'm trying to solve a variant of the 12-coin problem, but where you believe some coins are more likely to be counterfeit than others - I'm encoding that info in a Huffman tree, and then looking for a sorting/searching algorithm to find the counterfeit. en.wikipedia.org/wiki/Counterfeit_coin_problem – Tom Kealy Nov 6 '13 at 21:55

I've change my data structure, so that the Huffman encoding procedure defines the combinations I need to test:

class Node(object):
left = None
right = None
weight = None
data = None
code = ''
length = len(code)

def __init__(self, d, w, c):
self.data = d
self.weight = w
self.code = c

def set_children(self, ln, rn):
self.left = ln
self.right = rn

def __repr__(self):
return "[%s,%s,(%s),(%s)]" %(self.data,self.code,self.left,self.right)

def __cmp__(self, a):
return cmp(self.code, a.code)

def __getitem__(self):
return self.code

def encode(symbfreq):
tree = [Node(sym,wt,'') for sym, wt in symbfreq]
heapify(tree)
while len(tree)>1:
lo, hi = sorted([heappop(tree), heappop(tree)])
lo.code = '0'+lo.code
hi.code = '1'+hi.code
n = Node(lo.data+hi.data,lo.weight+hi.weight,lo.code+hi.code)
n.set_children(lo, hi)
heappush(tree, n)
return tree[0]


Then I search the groups using a function like this:

def search(tree):
current = tree.right
loops = 0
#defective = 0
while current is not None:
#print(current)
loops+=1
previous = current
if current.data == 1:
current = current.left
else:
current = current.right
return loops,previous


There are still some changes I need to make: the data field needs to be a set (not the sum that's there currently), and I need to change the encoding strategy so that the left branch of each node always has a '0' appended to its code regardless of permutations of the labels of the input distribution.