Abstract
Table 5.1: Word frequencies for the corpus in Figure 5.1
['rank', 'word', 'no. occurrences']
The initial merge window will have a size of C+1=4 and contain the words: Margrethe, to, the and II. After the first merge, the word . (period) will be inserted into the merge window, and the remaining words will be resorted. I will now focus only on the 5 words of rank 3. By computing the amount of mutual information between these words and clusters in the merge window, RESORT can derive a new ranking. We do not need to compute the values of mutual information to understand the example. We only need to count the number of co-occurrences with words already in the merge window. The word throne has one co-occurrence (the throne) and the word Majesty has two (both of the form Majesty Margrethe). Because of the higher number of co-occurrences, the word Majesty has more mutual information with clusters in the merge window and thus, becomes the next word to be included into the merge window. In this case, re-sorting words outside the window has managed to break the tie between words with the same frequency. By first inserting the word Majesty, the algorithm has also chosen to involve for merge considerations the word it knows most about, relative to the clusters already in the window. I ignored all other words in this analysis because they either have a mutual information value of 0 (because of no co-occurrences), or a small one (because of having only one co-occurrence). The resort_words function takes as input the current clustering, an ordering of words VS and a pointer i to one of the words in this ordering. It then resorts all words between i and |VS|. The resorting criteria can be any function that can provide a total ordering. I propose that words be ordered by the amount of mutual information they have with words already in the merge window. I chose the amount of mutual information with words in the merge window as a resorting criteria because it involves both connectivity and number of occurrences together with words already in the merge window. Connectivity is measures the number of unique words that appear in a bi-gram with any given word.