Revision 80fd5403
Added by dsorber almost 12 years ago
| software/key_classify/key_classify.py | ||
|---|---|---|
|
import math
|
||
|
import sys
|
||
|
|
||
|
from lxml import etree
|
||
|
|
||
|
def main():
|
||
|
# NOTE: Developed with Python 3.4 and lxml 3.3.5
|
||
|
|
||
|
# Validate the input
|
||
|
if len(sys.argv) < 3:
|
||
|
print('\nERROR: Not enough arguments provided!')
|
||
|
print('\nUSAGE: key_classify.py <input file> <table size>\n')
|
||
|
return -1
|
||
|
|
||
|
# Attempt to open the input file
|
||
|
try:
|
||
|
input_xml = open(sys.argv[1], 'r')
|
||
|
except IOError:
|
||
|
print('\nERROR: unable to open file "{:s}"'.format(sys.argv[1]))
|
||
|
return
|
||
|
|
||
|
# Determine the table size; test if the supplied table size argument is a
|
||
|
# power of 2; if not then use the next smallest power of 2
|
||
|
table_size = int(sys.argv[2])
|
||
|
table_size_log2 = math.log(table_size, 2)
|
||
|
compare_bits = math.floor(table_size_log2)
|
||
|
table_size_check = 2**compare_bits
|
||
|
if (table_size_check != table_size):
|
||
|
print('WARNING: {:d} is not a power of 2, using {:d}, which is the '
|
||
|
'next smallest power of 2, instead\n'.format(table_size,
|
||
|
table_size_check))
|
||
|
table_size = table_size_check
|
||
|
|
||
|
# Parse the input file into an ElementTree
|
||
|
sys.stdout.write('Parsing input xml file...')
|
||
|
sys.stdout.flush()
|
||
|
tree = etree.parse(input_xml)
|
||
|
input_xml.close()
|
||
|
sys.stdout.write('DONE\n')
|
||
|
|
||
|
# root = tree.getroot()
|
||
|
|
||
|
|
||
|
|
||
|
# Calculate the number of characters (bytes) to slice off the front of each
|
||
|
# title
|
||
|
compare_chars = math.ceil(compare_bits / 8.0)
|
||
|
|
||
|
# Calculate the number of bits to right shift the sliced bytes so that only
|
||
|
# "compare_bits" bits are left
|
||
|
shift_bits = (compare_chars * 8) - compare_bits
|
||
|
|
||
|
|
||
|
# Get all article title text using an XPath expression
|
||
|
namespace_mapping = {'w': 'http://www.mediawiki.org/xml/export-0.8/'}
|
||
|
article_titles = tree.xpath('(//w:page/w:title/text())',
|
||
|
namespaces=namespace_mapping)
|
||
|
|
||
|
# Iterate over the titles and classify them
|
||
|
counts = {}
|
||
|
for idx, article_title in enumerate(article_titles):
|
||
|
|
||
|
if article_title.startswith('Talk:'):
|
||
|
continue
|
||
|
|
||
|
# Conver the title to raw bytes, then slice based on the number of
|
||
|
# "compare_chars" and covert to an integer
|
||
|
title_bytes = bytearray(article_title, 'utf-8')
|
||
|
sliced_bytes_int = int.from_bytes(title_bytes[0:compare_chars],
|
||
|
byteorder='big')
|
||
|
|
||
|
# Calculate the histogram index by taking the integer of the comparison
|
||
|
# characters and right shifting it so that only "compare_bits" are used
|
||
|
index = sliced_bytes_int >> shift_bits
|
||
|
|
||
|
# Debug
|
||
|
# print(idx, article_title, title_bytes[0:compare_chars], sliced_bytes_int,
|
||
|
# '0x{:X}'.format(sliced_bytes_int), '0x{:X}'.format(index))
|
||
|
|
||
|
# Classify, i.e. build the histogram
|
||
|
if index in counts:
|
||
|
counts[index] += 1
|
||
|
else:
|
||
|
counts[index] = 1
|
||
|
|
||
|
# After building the histogram print out the results
|
||
|
for index in sorted(counts.keys()):
|
||
|
print(index, counts[index])
|
||
|
|
||
|
|
||
|
if __name__ == '__main__':
|
||
|
sys.exit(main())
|
||
Created a script to test the key classify primitive operation using Wikipedia dump xml files as input.