こんにちは、次のプログラムを実行してプログラムを実行しようとしています...
from hashtable import *
def word_count( hTable, filename ):
"""
Record the frequency of all words in the named file in the hashtable.
word_count : HashTable String -> HashTable
"""
# Read the words of the text file into the word count table.
fd = open( filename )
for line in fd:
for word in line.split():
# using a regular expression argument to strip(),
# strip out punctuation and convert token to lower-case.
word = word.strip(",.\"\';:-!?").lower()
if contains( hTable, word ):
count = get( hTable, word )
put( hTable, word, count + 1 )
else:
put( hTable, word, 1 )
fd.close() # closing the file is a 'good practice'.
return hTable
def printSummary( theTable ):
"""
printSummary prints a summary of information about the hash table contents.
printSummary : HashTable -> NoneType
"""
# Display the entire table!
print( "Unique words:", theTable.size )
# Find the most common word in the text file.
total = 0
maxWord = ""
maxCount = 0
for key in keys( theTable ):
thisCount = get( theTable, key )
total += thisCount
if thisCount > maxCount:
maxCount = thisCount
maxWord = key
print( "There are " + str( len( keys( theTable ) ) ) + " words." )
print( "Total words:", total )
print( '"' + maxWord + "\" appeared ", str( maxCount ),
" times, more than any other word." )
def printTable( hTable ):
"""
Print the contents of the given hash table.
Each key/value pair is displayed in parentheses, tuple-style.
All pairs appear on a single line.
printTable : HashTable -> NoneType
"""
print( "Word Count Data ---------------" )
lcount = 0
ltext = 0
for key in keys( hTable ):
# print( "(" + key + "," + str( get( hTable, key ) ) + ")", end=" " )
txt = "(" + key + "," + str( get( hTable, key ) ) + ")"
ltext += len( txt )
if ltext > 51:
print( txt )
ltext = 0
else:
print( txt, end=" " )
print()
def main():
capacity = int( input( "Enter capacity (-1 for default): " ) )
if capacity < 0:
hTable = HashTable()
else:
hTable = HashTable( capacity )
filename = input( "Enter filename: " )
wordTable = word_count( hTable, filename )
printSummary( wordTable )
while True:
print( "Commands: k[ey] <word> f[ind] <word> q[uit] ? ", end=" " )
response = input( ":- " ) # the displayed prompt
query = response.split()
if len( response ) == 0 or not response[0] in "fkq":
print( response + " invalid. Please enter a command and a word." )
response = ""
continue
if query[0] == "k":
print( "( " + query[1] + " in text ) is " \
+ str( contains( wordTable, query[1] ) ) + "." )
if query[0] == "f":
if contains( wordTable, query[1] ):
print( query[1] + " appears " \
+ str( get( wordTable, query[1] ) ) + " times." )
else:
print( query[1] + " in not in the text." )
if query[0] == "q":
break
#
answer = input( "Do you want to see the entire table?(y/n) " )
if answer != "y":
return
printTable( wordTable )
# run the main program
main()
このプログラムは...
class HashTable( ):
"""
The HashTable data structure contains a collection of values
where each value is located by a hashable key.
No two values may have the same key, but more than one
key may have the same value.
"""
__slots__ = ( "table", "size" )
def mkHashTable(capacity=100):
aHashTable = HashTable()
aHashTable.table = [[] for _ in range(capacity)]
aHashTable.size = 0
return aHashTable
def HashTableToStr(hashtable):
result = ""
for i in range( len( hashtable.table ) ):
if i != None:
result += str( i ) + ": "
result += EntryToStr( hashtable.table[i] ) + "\n"
return result
class _Entry( ):
"""
A class used to hold key/value pairs.
"""
__slots__ = ( "key", "value" )
def EntryToStr(entry):
"""
return the string representation of the entry.
"""
return "(" + str( entry.key ) + ", " + str( entry.value ) + ")"
def mkEntry(key, value):
aEntry = _Entry();
aEntry.key = key;
aEntry.value = value;
return aEntry;
def hash_function( val, n ):
"""
Compute a hash of the val string that is in [0 ... n).
"""
hashcode = hash( val ) % n
# hashcode = 0
# hashcode = len(val) % n
return hashcode
def keys( hTable ):
"""
Return a list of keys in the given hashTable.
"""
result = []
for entry in hTable.table:
if entry != []:
for item in entry:
if item.key not in results:
result.append( entry.key )
return result
def contains( hTable, key ):
"""
Return True iff hTable has an entry with the given key.
"""
index = hash_function( key, len( hTable.table ) )
startIndex = index # We must make sure we don't go in circles.
while hTable.table[ index ] != None and hTable.table[ index ].key != key:
index = ( index + 1 ) % len( hTable.table )
if index == startIndex:
return False
return hTable.table[ index ] != None
def put( hTable, key, value ):
"""
Using the given hash table, set the given key to the
given value. If the key already exists, the given value
will replace the previous one already in the table.
If the table is full, an Exception is raised.
"""
hashCode = hash(key)
loc = hashCode % len(hTable.table)
if hTable.table[loc] == []:
hTable.table[loc] = HashTable._Entry(key, value)
hTable.size += 1
else:
hTable.table[loc].value = value
def get( hTable, key ):
"""
Return the value associated with the given key in
the given hash table.
Precondition: contains(hTable, key)
"""
hashCode = hash(key)
loc = hashCode % len(hTable.table)
for entry in hTable.table[loc]:
if entry.key == key:
return entry.value
次のエラーが表示されます...
Enter capacity (-1 for default): -1
Enter filename: words.txt
Traceback (most recent call last):
File "/Users/sps329/Desktop/word_count.py", line 126, in <module>
main()
File "/Users/sps329/Desktop/word_count.py", line 92, in main
wordTable = word_count( hTable, filename )
File "/Users/sps329/Desktop/word_count.py", line 29, in word_count
if contains( hTable, word ):
File "/Users/sps329/Desktop/hashtable.py", line 83, in contains
index = hash_function( key, len( hTable.table ) )
AttributeError: table
このプログラムでの私の目標は、ハッシュ プログラムに連鎖を実装し、より優れたハッシュ関数を考え出すことです。