Bard College – Computer Science – Data Structures
In this lab we will compare two different methods for frequency counting, specifically within the context of Zipf's Law. We will compare Symbol Tables based on Sequential Search vs. what our book calls a Self-Organizing Search. Self-organizing search uses a heuristic: recently accessed items are likely to be accessed again, and thus, should be moved to the front of the list.This approach takes advantage of locality of reference: an important notion from from computer systems architecture.
Validate Zipf's law which wikipedia states"given some corpus of natural language utterances, the frequency of any word is inversely proportional to its rank in the frequency table. Thus the most frequent word will occur approximately twice as often as the second most frequent word, three times as often as the third most frequent word, etc."
Find the most frequent 50 words from a large text corpus. The data should be presented in order of word frequency. Plot the results on a log-log plot; if Zipf's law holds, you should see a line.
HINTS: The FrequencyCounter class from page 372 is a good place to start. Consider using Quick.select to find the top 50 words. The SymbolTable API is on page 363.
Part 1: Zipf's Law
java Zipf < bible.txtthe 62252and 38641of 34548to 13457And 12735that 12464in 12221shall 9762he 9510unto 8932I 8708his 8362a 7999for 7160they 6895be 6736is 6720with 5995not 5859all 5256thou 4629it 4469thy 4451was 4448which 4275my 4135LORD 3930their 3873have 3825will 3757from 3592ye 3566them 3503as 3265