Introduction
用Python代写一个Hashing的程序，对自然语言进行统计排序，由于是自然语言，存在大量的标点符号，以及大小写的处理。
给的测试文件篇幅较大，都是几千字的，调试还是比较花时间的。
此外还需要找到合适的Hashing大小，使得collision最小，这个就是对n进行循环，找到collision最小的那个数即可。
Requirement
Write a program that uses hashing for the following problem. Given a natural
language text, generate a table of distinct words with the number of
occurrences of each word in the text. A word is defined as a series of
alphanumeric characters. Note that punctuation and spaces can both (separately
or together) delineate a word. There are some hyphenated words in the text;
for these words there will be no space before or after the hyphen and the
hyphen should be considered part of the word. Capitalized versions of a word
are considered the same as the lowercase version, so feel free to change all
words to either upper- or lowercase. Plural possessives and contractions
should remain and be counted as a unique word (such as can’t or widows’).
You must use the provided input file, which contains the first chapter of
Tolkien’s “The Hobbit” found on herePreview the documentView in a new window.
Your resulting program will be an interactive one allowing the user to type in
a word (that may or may not appear in the table) and receive the number of
occurrences of that word in the text until the user wishes to quit.
The challenge
Find the combination of hash function and collision resolution that will
minimize the collisions. A collision is defined as an attempt to store a new
word in a location already occupied by another word. Consequently, it is
possible for a new word to collide more than once before it is finally stored.
To qualify for full credit on the assignment, you must have fewer than 625
collisions and your table size must be appropriate for the number of words
(see below) and the collision resolution used. Your instructor was able to
reach 514 collisions simply using a version of one of the hash functions
discussed in class and linear probe. The student(s) with the least collisions
and proper table size will receive 5 bonus points.
Hints
There are 663 unique words in the file (using the above definition of a unique
word). There are 1976 words in total.
Program description
Your program should hash the values from the file and then print (neatly
formatted) the number of collisions, number of unique words and total number
of words to the standard output (screen) before allowing the user to input a
word to see the number of times it appeared. The user should be able to input
as many words as desired before choosing to quit.
Suggestions & Notes
Reading in one word at a time from the file, create a function that pre-
processes a word, changing capital letters to lowercase and removing any
quotation marks or other unnecessary punctuation that may have been read from
the file. Then send the pre-processed string into your hash function.
When counting collisions, do not count additional instances of a word. So you
will want to keep a “temporary” collision count for a word until you know if
the word is already in the table.
Note that the table size must be “reasonable” and depends upon the number of
entries expected and the collision resolution used. Using a larger table than
required by these factors (simply to reduce collisions) will mean a deduction.
The final load factor must be between 0.5 and 0.7.
Get your program up and running by using one of the hash functions discussed
in class and a simple collision resolution (such as linear probe). Make sure
you are pre-processing your words correctly, etc. before attempting to
minimize the collisions.
