<s> import sys <EOL> import time <EOL> from bitarray import bitarray <EOL> from huffman import freq_string , huffCode <EOL> def traverse ( it , tree ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> subtree = tree [ it . next ( ) ] <EOL> except StopIteration : <EOL> return False <EOL> if isinstance ( subtree , list ) and len ( subtree ) == <NUM_LIT:2> : <EOL> return traverse ( it , subtree ) <EOL> else : <EOL> return subtree <EOL> def insert ( tree , sym , ba ) : <EOL> """<STR_LIT>""" <EOL> v = ba [ <NUM_LIT:0> ] <EOL> if len ( ba ) > <NUM_LIT:1> : <EOL> if tree [ v ] == [ ] : <EOL> tree [ v ] = [ [ ] , [ ] ] <EOL> insert ( tree [ v ] , sym , ba [ <NUM_LIT:1> : ] ) <EOL> else : <EOL> if tree [ v ] != [ ] : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> tree [ v ] = sym <EOL> def decode ( codedict , bitsequence ) : <EOL> """<STR_LIT>""" <EOL> tree = [ [ ] , [ ] ] <EOL> for sym , ba in codedict . iteritems ( ) : <EOL> insert ( tree , sym , ba ) <EOL> res = [ ] <EOL> it = iter ( bitsequence ) <EOL> while True : <EOL> r = traverse ( it , tree ) <EOL> if r is False : <EOL> break <EOL> else : <EOL> if r == [ ] : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> res . append ( r ) <EOL> return res <EOL> txt = open ( '<STR_LIT>' ) . read ( ) <EOL> code = huffCode ( freq_string ( txt ) ) <EOL> sample = <NUM_LIT:1000> * txt <EOL> a = bitarray ( ) <EOL> a . encode ( code , sample ) <EOL> start_time = time . time ( ) <EOL> res = decode ( code , a ) <EOL> Py_time = time . time ( ) - start_time <EOL> assert '<STR_LIT>' . join ( res ) == sample <EOL> print '<STR_LIT>' % Py_time <EOL> start_time = time . time ( ) <EOL> res = a . decode ( code ) <EOL> C_time = time . time ( ) - start_time <EOL> assert '<STR_LIT>' . join ( res ) == sample <EOL> print '<STR_LIT>' % C_time <EOL> print '<STR_LIT>' , Py_time / C_time </s>
