language to group words that have a similar function.

Brown et al. [@Brown:1992] start by assigning each word to a distinct class, and then merge classes in a greedy fashion. A naive algorithm would evaluate the objective function for each pair of classes. One iteration of the naive algorithm would on average run in $\mathcal{O}(N_V^4)$ time, where $N_V$ is the size of the vocabulary. This involves a lot of redundant computation that can be eliminated by storing some statistics between iterations, reducing the time required to run one iteration to $\mathcal{O}(N_V^2)$.

To further reduce the computational complexity, they propose an approximation where, at any given iteration, only a subset of the vocabulary is considered. Starting from the most frequent words, $N_C$ words are assigned to distinct classes. On each iteration, the next word is considered for merging to one of the classes. The running time of one iteration is $\mathcal{O}(N_C^2)$. The algorithm stops after $N_V - N_C$ iterations, and results in all the words being in one of the $N_C$ classes.

The exchange algorithm proposed by Kneser and Ney [@Kneser:1993] starts from some initial clustering that assigns every word to one of $N_C$ classes. The algorithm iterates through all the 