Bigram

From Wikipedia, the free encyclopedia

Bigrams are groups of two written letters, two syllables, or two words, and are very commonly used as the basis for simple statistical analysis of text. They are used in one of the most successful language models for speech recognition.[1] They are a special case of N-gram.

Gappy bigrams or skipping bigrams are word pairs which allow gaps (perhaps avoiding connecting words, or allowing some simulation of dependencies, as in a dependency grammar).

Head word bigrams are gappy bigrams with an explicit dependency relationship.

The term is also used in cryptography, where bigram frequency attacks have sometimes been used to attempt to solve cryptograms. See frequency analysis.

Bigrams help provide the conditional probability of a word given the preceding word, when Bayes' theorem is applied:

P(W_n|W_{n-1}) = { P(W_{n-1},W_n) \over P(W_{n-1}) }

That is, the probability P() of a word Wn given the preceding word Wn − 1 is equal to the probability of their bigram, or the co-occurrence of the two words P(Wn − 1,Wn), divided by the probability of the preceding word.

[edit] Bigram Frequency in the English language

The most common letter bigrams in the English language are listed below, with the expected number of occurrences per 2000 letters. In the analysis here, the bigrams are not permitted to span across consecutive words. [2]

TH 50      AT 25       ST 20
ER 40      EN 25       IO 18
ON 39      ES 25       LE 18
AN 38      OF 25       IS 17
RE 36      OR 25       OU 17
HE 33      NT 24       AR 16
IN 31      EA 22       AS 16
ED 30      TI 22       DE 16
ND 30      TO 22       RT 16
HA 26      IT 20       VE 16

However, these counts are different than other published results; one from the Cornell University Math Explorer's Project[3] (measured over 40,000 words or about 200,000 letters) gives the first five as follows:

th 5532   
he 4657    
in 3429   
er 3420   
an 3005

[edit] References

  1. ^ Michael Collins. A new statistical parser based on bigram lexical dependencies. In Proceedings of the 34th Annual Meeting of the Association of Computational Linguistics, Santa Cruz, CA. 1996. pp.184-191.
  2. ^ Friedman & Callimahos, Military Cryptanalytics Part I, Aegean Park Press, Laguna Hills, CA. 1985
  3. ^ Cornell Math Explorer's Project – Substitution Ciphers

[edit] See also