Bard College – Computer Science – Data Structures
In this lab we will explore Zipf's Law, and compare two different methods for frequency counting. We will compare Symbol Tables based on Sequential Search vs. Self-Organizing Search. Self-organizing search uses a heuristic: recently accessed items are likely to be accessed again soon, and thus, they should be moved to the front of the list.This approach takes advantage of locality of reference: an important notion from from computer systems.
Validate Zipf's law which as wikipedia,"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." Fun video on Zipf’s law(thanks, Ian!):
Find the most frequent 50 words from a large text corpus. The words should be presented in order of 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 3503