Revision 087e2cfb
Added by dsorber almost 12 years ago
| software/term_freq_sim/simulator.py | ||
|---|---|---|
|
import hashlib
|
||
|
import sys
|
||
|
|
||
|
from lxml import etree
|
||
|
|
||
|
MEDIA_WIKI_NAMESPACE = 'http://www.mediawiki.org/xml/export-0.8/'
|
||
|
from gen_proxy import generator_method
|
||
|
|
||
|
def main():
|
||
|
# class InputSource(object):
|
||
|
#
|
||
|
# def __init__(self, input_file):
|
||
|
# pass
|
||
|
#
|
||
|
# def get_next_word():
|
||
|
# pass
|
||
|
|
||
|
# Validate the input
|
||
|
if len(sys.argv) < 2:
|
||
|
print '\nERROR: Not enough arguments provided!'
|
||
|
print '\nUSAGE: simulator.py <xml input file>\n'
|
||
|
return -1
|
||
|
|
||
|
# Attempt to open the input file
|
||
|
class WikiMediaInput(object):
|
||
|
|
||
|
punctuation= ['`', '~', '@', '#', '$', '%', '^', '&', '*', '(', ')', '+',
|
||
|
'=', '{', '[', '}', ']', ':', ';', '"', '\'', '<', '>', ',',
|
||
|
'.', '!', '?', '/', '|']
|
||
|
media_wiki_namespace = 'http://www.mediawiki.org/xml/export-0.8/'
|
||
|
|
||
|
def __init__(self, input_file, scrub_words=False):
|
||
|
|
||
|
self.scrub_words = scrub_words
|
||
|
|
||
|
# Attempt to open the input file
|
||
|
try:
|
||
|
input_xml = open(input_file, 'r')
|
||
|
except IOError:
|
||
|
print '\nERROR: unable to open file "{:s}"'.format(input_file)
|
||
|
return
|
||
|
|
||
|
# Parse the input file into an ElementTree
|
||
|
self.tree = etree.parse(input_xml)
|
||
|
input_xml.close()
|
||
|
self.root = self.tree.getroot()
|
||
|
|
||
|
def scrub(self, word):
|
||
|
for punc_char in self.punctuation:
|
||
|
word = word.replace(punc_char, '')
|
||
|
return word.strip().lower()
|
||
|
|
||
|
@generator_method('WikiMediaInput')
|
||
|
def get_next_word(self):
|
||
|
"""
|
||
|
This method is a generator and using the generator_method decorator
|
||
|
it works as you would expect with no additional hassle.
|
||
|
"""
|
||
|
# Get all article titles
|
||
|
# tree.xpath('//w:page/w:title/text()',
|
||
|
# namespaces={'w': 'http://www.mediawiki.org/xml/export-0.8/'})
|
||
|
|
||
|
namespace_mapping = {'w': self.media_wiki_namespace}
|
||
|
|
||
|
# Get all article text using an XPath expression
|
||
|
all_article_text = self.tree.xpath('(//w:page/w:revision/w:text/text())',
|
||
|
namespaces=namespace_mapping)
|
||
|
|
||
|
for article_text in all_article_text:
|
||
|
for word in article_text.split():
|
||
|
# Scrub word before returning if desired
|
||
|
if self.scrub_words:
|
||
|
word = self.scrub(word)
|
||
|
if word:
|
||
|
yield word
|
||
|
|
||
|
|
||
|
class Simulator(object):
|
||
|
|
||
|
def __init__(self, input_source, hash_func, table_size):
|
||
|
|
||
|
self.input_source = input_source
|
||
|
self.hash_func = hash_func
|
||
|
self.table_size = table_size
|
||
|
|
||
|
self.divider = '-' * 100
|
||
|
|
||
|
# Simulation state variables
|
||
|
self.clock_cycle = 0
|
||
|
self.table = {}
|
||
|
self.eviction_count = 0
|
||
|
|
||
|
def table_stats(self):
|
||
|
|
||
|
used = sum([1 for key in self.table.keys()])
|
||
|
percent = (float(used) / self.table_size) * 100
|
||
|
return '{:d} of {:d} ({:.2f}%) entries used'.format(used, self.table_size, percent)
|
||
|
|
||
|
def simulate(self):
|
||
|
|
||
|
print 'Starting simulation'
|
||
|
print 'table size: {:d}'.format(self.table_size)
|
||
|
print self.divider
|
||
|
|
||
|
# Simulation loop
|
||
|
while True:
|
||
|
self.clock_cycle += 1
|
||
|
|
||
|
# Grab the next word then using the hash function calculate its
|
||
|
# index into the table
|
||
|
try:
|
||
|
word = self.input_source.get_next_word()
|
||
|
except StopIteration:
|
||
|
print self.divider
|
||
|
print 'Stopping on cycle {:d}'.format(self.clock_cycle)
|
||
|
print 'Total evictions: {:d}'.format(self.eviction_count)
|
||
|
break
|
||
|
idx = self.hash_func(word) % self.table_size
|
||
|
|
||
|
if idx not in self.table:
|
||
|
# If the table entry is unused, add the word with a count of 1
|
||
|
self.table[idx] = (word, 1)
|
||
|
else:
|
||
|
# If the table entry is used, grab the entry for comparison
|
||
|
word_tuple = self.table[idx]
|
||
|
|
||
|
if word == word_tuple[0]:
|
||
|
# The new word and the entry word match, increment the count
|
||
|
self.table[idx] = (word, word_tuple[1] + 1)
|
||
|
else:
|
||
|
# The new word and the entry word do not match, evict the
|
||
|
# entry then insert the new word with a count of 1
|
||
|
self.eviction_count += 1
|
||
|
|
||
|
evict_args = (word_tuple[0].encode('ascii', 'replace'),
|
||
|
word_tuple[1])
|
||
|
|
||
|
print 'Cycle {:d}'.format(self.clock_cycle)
|
||
|
print '\teviction ({:s}, {:d})'.format(*evict_args)
|
||
|
print '\t{:s}'.format(self.table_stats())
|
||
|
self.table[idx] = (word, 1)
|
||
|
|
||
|
def hash_simplest(word):
|
||
|
""" A very, very simple hash function.
|
||
|
"""
|
||
|
return ord(word[0])
|
||
|
|
||
|
def hash_simpler(word):
|
||
|
""" A very simple hash function.
|
||
|
"""
|
||
|
try:
|
||
|
xml_file = open(sys.argv[1], 'r')
|
||
|
except IOError:
|
||
|
print '\nERROR: unable to open file "{:s}"'.format(sys.argv[1])
|
||
|
return -2
|
||
|
return ord(word[0]) + ord(word[1]) + ord(word[2])
|
||
|
except:
|
||
|
return ord(word[0])
|
||
|
|
||
|
# Parse the input file into an ElementTree
|
||
|
tree = etree.parse(xml_file)
|
||
|
xml_file.close()
|
||
|
root = tree.getroot()
|
||
|
def hash_simple(word):
|
||
|
""" A simple hash function.
|
||
|
"""
|
||
|
return int(hashlib.sha1(word.encode('ascii', 'replace')).hexdigest(), 16)
|
||
|
|
||
|
# Get all article titles
|
||
|
# tree.xpath('//w:page/w:title/text()',
|
||
|
# namespaces={'w': 'http://www.mediawiki.org/xml/export-0.8/'})
|
||
|
def main():
|
||
|
|
||
|
# Get article text
|
||
|
article_text = tree.xpath('(//w:page/w:revision/w:text/text())[130]',
|
||
|
namespaces={'w': MEDIA_WIKI_NAMESPACE})
|
||
|
# Validate the input
|
||
|
if len(sys.argv) < 3:
|
||
|
print '\nERROR: Not enough arguments provided!'
|
||
|
print '\nUSAGE: simulator.py <input file> <table size>\n'
|
||
|
return -1
|
||
|
|
||
|
# print len(article_text)
|
||
|
# print article_text
|
||
|
table_size = int(sys.argv[2])
|
||
|
|
||
|
word_list = [word for word in article_text[0].split()]
|
||
|
# Load the input file
|
||
|
sys.stdout.write('Loading input...')
|
||
|
sys.stdout.flush()
|
||
|
wiki_input = WikiMediaInput(sys.argv[1], True)
|
||
|
sys.stdout.write('DONE')
|
||
|
|
||
|
for word in word_list:
|
||
|
print word
|
||
|
# Create the simulator object and run the simulation
|
||
|
sim = Simulator(wiki_input, hash_simple, table_size)
|
||
|
sim.simulate()
|
||
|
|
||
|
|
||
|
if __name__ == '__main__':
|
||
Once again I forgot that I need to add modified files...