/usr/share/doc/python-bitarray/examples/decoding.py is in python-bitarray 0.8.0-2build4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | import time
from bitarray import bitarray
from huffman import freq_string, huffCode
def traverse(it, tree):
"""
return False, when it has no more elements, or the leave node
resulting from traversing the tree
"""
try:
subtree = tree[next(it)]
except StopIteration:
return False
if isinstance(subtree, list) and len(subtree)==2:
return traverse(it, subtree)
else: # leave node
return subtree
def insert(tree, sym, ba):
"""
insert symbol which is mapped to bitarray into tree
"""
v = ba[0]
if len(ba) > 1:
if tree[v] == []:
tree[v] = [[], []]
insert(tree[v], sym, ba[1:])
else:
if tree[v] != []:
raise ValueError("prefix code ambiguous")
tree[v] = sym
def decode(codedict, bitsequence):
"""
this function does the same thing as the bitarray decode method
"""
# generate tree from codedict
tree = [[], []]
for sym, ba in codedict.items():
insert(tree, sym, ba)
# actual decoding by traversing until StopIteration
res = []
it = iter(bitsequence)
while True:
r = traverse(it, tree)
if r is False:
break
else:
if r == []:
raise ValueError("prefix code does not match data")
res.append(r)
return res
def main():
txt = open('README').read()
code = huffCode(freq_string(txt))
sample = 2000 * txt
a = bitarray()
a.encode(code, sample)
# Time the decode function above
start_time = time.time()
res = decode(code, a)
Py_time = time.time() - start_time
assert ''.join(res) == sample
print('Py_time: %.6f sec' % Py_time)
# Time the decode method which is implemented in C
start_time = time.time()
res = a.decode(code)
C_time = time.time() - start_time
assert ''.join(res) == sample
print('C_time: %.6f sec' % C_time)
print('Ratio: %f' % (Py_time / C_time))
if __name__ == '__main__':
main()
|