# Composing variable length n-grams according to frequency

I have a corpus {text1, text2, text3, text4, ..., etc.}. I have no prior knowledge about the text. Lets say we extract all the n-grams (unigrams, bigrams, trigrams, 4-gram, 5-gram, ...) along with their frequency from the text.

My question is how can we merge the best N n-grams form the unigrams, bigrams, trigrams, 4-gram, 5-gram to one variable n-gram dictionary (that contains different n-gram lengths) with a simple "statistical" action?

• Do you mean How do I program it? If so this is off-topic here so perhaps you can clarify. – mdewey May 22 '17 at 11:34
• No I didn't mean how I program it. how to program I know excellent. I ask from the conceptual side. How I merge N different ngrams to one dictionary and take only the top K . (merge by frequency) – MAK May 22 '17 at 14:18

While a whole bunch of collocation detection strategies exist, from "normal" t-tests to calculating your n-grams' point-wise mutual information (PMI, see Church & Hanks (1990)) or via the Dice (1945) coefficient (see Smadja & McKeown (1994)), I prefer the likelihood ratio test by Dunning (1993) and as applied to non-compositional phrases by Lin (1993), because it is fairly robust for both excluding frequently co-occurring words and including infrequent collocations that are hard to detect. E.g., for bi-grams of a two word sequence $[1, 2]$ with counts $c$ for either word or the bi-gram, and a total number of words $N$ in your corpus, you get:
$$\lambda = {-2}\ log \frac{B(c_{12}, c_1, p_2) B(c_2-c_{12},N-c_1,p_2)}{B(c_{12},c_1,p_{2|1})B(c_2-c_{12},N-c_1,p_{2|\neg1})}$$
Where $B(k, n, p) = \binom{n}{k} p^k (1-p)^{n -k}$ (note that the binomial term $n$ over $k$ can be dropped), $p_2 = \frac{c_2}{N}$, $p_{2|1} = \frac{c_{12}}{c_1}$, and $p_{2|\neg1} = \frac{c_2-c_{12}}{N-c_1}$. The $-2$ multiplier is in there to make $\lambda$ asymptotically $\chi^2$ distributed. As cutoff, I'd recommend $\lambda > 10.83$, which is the critical value for $\chi^2$ with 99.9% confidence at 1 d.f., but you might use lower cutoffs for better recall, depending on what you want to do with those collocations.