====== Hash & Huffman code ======

Nella lezione del 17/12 abbiamo visto gli ultimi due argomenti del corso, [[wp>Hash_table|tabelle di hash]] e [[wp>Huffman_code|codifica di Huffman]].

Per quanto riguarda le tabelle di hash, abbiamo visto le principali strutture (chaining e open addressing) e funzioni di hash (resto della divisione e metodo moltiplicativo).

**Huffman code**
<code python>
from treeh import BinNode, IntlNode, LeafNode, preorder, postorder

def Huffman(chars, freq):
	Q = zip(freq,chars)
	Q.sort()
	while len(Q)>1 :
		print Q
		cx,x=Q.pop(0)
		cy,y=Q.pop(0)
		if not issubclass(type(x),BinNode) :
			x=LeafNode((cx,x))
		if not issubclass(type(y),BinNode) :
			y=LeafNode((cy,y))
		data=y.data[0]+x.data[0], y.data[1]+'+'+x.data[1]
		z=IntlNode(data,y,x)
		Q.append((cx+cy,z))
		Q.sort()
	return Q.pop(0)



def action(n):
	'''Prints the tree in Graphviz DOT language
	'''
	print id(n), '[ label="', n.data, '"];'
	try : 
		x = `id(n)`+' -> '+`id(n.left)`+';'
	except AttributeError, e : pass
	try : 
		x = `id(n)`+' -> '+`id(n.right)`+';'
	except AttributeError, e : pass


if __name__ == '__main__' :
	C=[ 'z', 'k', 'f', 'c', 'u', 'd', 'l', 'e' ]
	f=[  2,   7 ,  24,  32,  37,  42,  42, 120 ]
	T=Huffman(C,f)
	
	postorder(T,action)

</code>

**Tree implementation**
<code python>
#!/usr/bin/python

class BinNode(object):
	def __init__(self,content=None):
		self.data=content
		self.left=None
		self.right=None
	
	def __getitem__(self,side):
		if side in [ 0, 'left', 'l' ] :
			return self.left
		elif side in [ 1, 'right', 'r' ] :
			return self.right
		raise KeyError, side
	
	def __setitem__(self,side,item):
		if not isinstance(item,BinNode) :
			raise TypeError, item
		if side in [ 0, 'left', 'l' ] :
			self.left = item
		elif side in [ 1, 'right', 'r' ] :
			self.right = item
		else :
			raise KeyError, side
	
	def isLeaf(self):
		return self.left and self.right
	

class LeafNode(BinNode):
	def __init__(self,content):
		#if not isinstance(content,int) : 
		#	raise TypeError, 'LeafNode accepts only integers'
		self.data=content

	def __getitem__(self,side):
		raise TypeError, 'No children in leaf nodes!'
		
	def __setitem__(self,side,child):
		raise TypeError, 'No children in leaf nodes!'

	def isLeaf(self):
		return True

class IntlNode(BinNode):
	def __init__(self,content,left=None,right=None):
		#if content not in [ '*', '+', '-', '/' ] : 
		#	raise TypeError, 'IntlNode accepts only arithmetic operators as strings'
		BinNode.__init__(self,content)
		self.left=left
		self.right=right
		
	def isLeaf(self):
		return False


def preorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	action(node)
	if not node.isLeaf() : 
		preorder(node[direction[0]],action,direction)
		preorder(node[direction[1]],action,direction)

def postorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	if not node.isLeaf() : 
		preorder(node[direction[0]],action,direction)
		preorder(node[direction[1]],action,direction)
	action(node)

def inorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	if node.isLeaf() : 
		action(node)
		return
	else :
		inorder(node[direction[0]],action,direction)
		action(node)
		inorder(node[direction[1]],action,direction)


if __name__ == '__main__' :
	def action(node):
		print node.data,

	root = IntlNode('*')
	root['l'] = IntlNode('+')
	root['r'] = IntlNode('/')
	root['r']['r'] = LeafNode(2)
	root['r']['l'] = LeafNode(3)
	root['l']['r'] = LeafNode(4)
	root['l']['l'] = LeafNode(5)
	preorder(root,action)
	print ''
	inorder(root,action)
	print ''
	postorder(root,action)
</code>

{{teaching:info3:huffman.tgz}|Qui}} trovate i file sorgenti con il codice relativo alla codifica di Huffman.