Impossible bigrams in the English Language

Question

Is there a list that contains every two letter combination that is not found in any English words? I have searched for a very long time and found nothing. It would also be useful if I had three letter combinations that do not exist. I have to search through a large text file looking for strings that can contain actual words. (And another list of things that only a few words are apart of, like qa)

EDIT: I have compiled a list myself, here it is for anyone who may need it:

bk  fq  jc  jt  mj  qh  qx  vj  wz  zh
bq  fv  jd  jv  mq  qj  qy  vk  xb  zj
bx  fx  jf  jw  mx  qk  qz  vm  xg  zn
cb  fz  jg  jx  mz  ql  sx  vn  xj  zq
cf  gq  jh  jy  pq  qm  sz  vp  xk  zr
cg  gv  jk  jz  pv  qn  tq  vq  xv  zs
cj  gx  jl  kq  px  qo  tx  vt  xz  zx
cp  hk  jm  kv  qb  qp  vb  vw  yq
cv  hv  jn  kx  qc  qr  vc  vx  yv
cw  hx  jp  kz  qd  qs  vd  vz  yz
cx  hz  jq  lq  qe  qt  vf  wq  zb
dx  iy  jr  lx  qf  qv  vg  wv  zc
fk  jb  js  mg  qg  qw  vh  wx  zg

I used 70,000 words, but there are more so some other bigrams could exit. Doubtful though. (A commenter mentions teriyaki, so it's not foolproof, but the above list still solved my personal problem of finding the needle in the haystack that I was looking for)

Answer 1

To elaborate on jlawler and Ryno's comments, you are very very very unlikely to find the kind of data you want precompiled and available on the web. The reason is A) it's pretty easy to do yourself, and B) it isn't particularly useful once you get past an introductory level, i.e. there are probably better ways to judge the "Englishness" of words than just looking at their bigrams.

First, you need a corpus. Obviously not every corpus will have every word in it which might leave some rare, but valid, bigrams out. You could use multiple corpora but realistically it won't make much difference. The Brown Corpus is freely available and is used a lot in this sort of thing. Alternatively, you could grab a bunch of books off of Project Gutenberg.

I'm assuming you have at least some programming knowledge since you talk about needing to scan a large text, so once you have your reference corpus it should be trivial to scan through it and create a list of all unique bigrams or compute bigram probabilities. Typically when computing bigram probabilities you should use Naive Bayes (P(AB) = P(B|A) = C(AB)/C(A), where C() is the count) instead of raw probabilities (count of the bigram / total number of bigrams). This is because the independence assumption (P(AB) = P(B|A)) means you can compute probabilities one [additional] letter at a time.

Beyond bigram or full-word based solutions, there is a similar question over on StackOverflow about English-like word generation (instead of detection) which takes a syllabic approach. Essentially you have 2 lists; valid onset/nucleus (or onset/vowel, i.e. the first half of a syllable) pairs and valid nucleus/coda (i.e. the second half of the syllable) pairs. These are then stitched together in a Markov chain resulting in valid English syllables. The important part is that these pairs are not a fixed length, for example "-a" + "at" = "at" vs. "-stre" + "ength" = "strength". From here building valid English words is trivial (off the top of my head I can't think of invalid coda/onset combinations nor any valid syllable-initial/final pairs that cannot also be word-initial/final). Of course, this still leaves the problem of data since syllabifying itself is non-trivial.

Answer 2

Of the 676 total possible bigrams "there are only seven bigrams that do not occur among the 2.8 trillion mentions: JQ, QG, QK, QY, QZ, WQ, and WZ."

Norvig also produced data for trigrams through 9-grams "by position within word ... and also by word length." Of the 17576 (26**3) possible trigrams, Norvig found 8,653 (see types count in ngrams3 fusion table), so 8923 (50.768%) trigrams did not occur.

From http://norvig.com/mayzner.html English Letter Frequency Counts: Mayzner Revisited or ETAOIN SRHLDCU

Norvig is a Google research scientist. Analysis was based on the Google Books corpus mid 2012. Norvig normalized words (so word=Word=WORD) and then excluded those that occurred fewer than 100,000 times. Thus these 7 bigrams might legitimately exist (e.g., "howzat" per Ken Grace in the comments) but are very rare (unless you are interested in cricket).

Similarly, some bigrams might not occur depending upon what you mean by "English words." Note that some Roman numerals and abbreviations were included (e.g., no Scrabble word contains "qc" but "QC" for "quality control" was common in my technical books). The list also contains some names and some clearly foreign words (e.g., "forschungsgemeinschaft" in the longest words list must have appeared more than 100,000 times, probably due to funding acknowledgements of the German equivalent of the NSF in scientific papers per Christopher Orr in the comments). I'm unaware of an English "dictionary" word that contains "xx" but the bigram appeared 79 million times in "Exxon" (formed in 1972), "ExxonMobile" (in 1999), "XXX" (whether strike-through, placeholder, hardcore sex rating, movie or album name, Roman numeral 30, genetic abnormality, kisses, extra strong, elided XXXL size, poison/dangerous label, ... [and now a top level domain]), etc.

This list excluded all words that contained numbers or punctuation (presumably also therefore excluding contractions, possessives, and hyphenations).

In addition to Norvig's post, Google Books, and the Brown Corpus (mentioned by acattle), see the Corpus of Contemporary American English (or British or International or others) for easy to use tools and datasets that could be used to extract data patterns that might be of more interest. Google and Microsoft also provide tools and ngram datasets based on web content. Wiktionary might also be useful when considering specific bigrams. Scrabble, word finder, or other game aids might be useful as well.

http://corpus.byu.edu/coca/ http://corpus.byu.edu/ http://ngrams.googlelabs.com/ http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html http://research.microsoft.com/web-ngram https://en.wiktionary.org/wiki/Appendix:Two-letter_combinations

Note that this answer addresses the limited question of "two [and three] letter combination[s] ... not found in any English words" but not how best to identify "English words" mixed with other text (or vice versa).

Edit: Primarily added Trigram count, links list, and last paragraph.