7

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.

  • 2
    Given the vagaries of English spelling, and its even vaguer implementations, I doubt that there are any impossible bigrams in English, and damn few trigrams. – jlawler Jul 30 '13 at 19:00
  • @jlawler How about a list that contains the percent of words that use that bigram? That would be useful because I can list them from most likely an English word to probably German. :) – Nicholas Pipitone Jul 30 '13 at 19:03
  • 2
    To get a list of English word you will first have to decide which definition of "English word" you want. People who build English corpora will tell you that no matter how big a corpus is that previously unrecorded words appear in new texts constantly. – hippietrail Aug 2 '13 at 5:04
  • 9
    bk: lambkin, subkingdom; cb: Macbeth; cp: Macpherson; fk: Kafkaesque; gv: Longview; hk: fishkill, latchkey, Poughkeepsie; iy: multiyear, teriyaki; I'm listing these to underscore other commenters' points. What counts as an English word? What corpus do you use? I personally would accept all of these as English words. By doing a search in a dictionary with 130,000 entries, I found many other bigrams from your list, as well, although most of them were more peripheral proper nouns and loanwords. – musicallinguist Aug 2 '13 at 18:59
  • 1
    bk subkingdom bq subquery bx subxiphisternal cb ecbolic cf cf. cg ecgonine cj calcjarlite etc etc. There's exceptions to every rule and nothing is impossible. These may be rare bigrams but they're not impossible bigrams. I found these examples in Wiktionary. – hippietrail Aug 3 '13 at 4:19
7

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.

| improve this answer | |
  • I got a dictionary containing 70k words and compiled a list myself. It made a huge difference, because checking if a word is valid by going through the entire dictionary takes like 1/4 a second, while checking through invalid bigrams was done in a matter of milliseconds. I am looking to fish through thousands of words, most of which contain completely valid bigrams, so what other ways can I test the "Englishness" of words? – Nicholas Pipitone Aug 2 '13 at 17:33
  • 2
    One of the problems is that deciding if a word is valid in a language is a phonological process and although English spelling is relatively phonemic, it isn't perfect. Beyond that, we have loanwords that are valid words but may introduce rare bigrams (such as "qa" from "Qatar"). Even then, pure bigrams alone can't account for English consonant-vowel patterns. Your program might consider a word with 0 vowels as valid. Hand-coded rules may help but lack coverage. Similarly trigrams or 4-grams would better capture vowel patterns but your data would be too sparse to be useful, requiring smoothing. – acattle Aug 3 '13 at 3:38
  • My point is that it's actually a non-trivial problem. I did a bit more googling and I found a question over on StackOverflow that you should be able to adapt to suit your needs. It seems to work at the syllable-level (which is not a fixed length in English), which should help tremendously. – acattle Aug 3 '13 at 3:44
  • Well, one field where it would be pretty useful information would be typography. Maybe typographers have compiled some of this information. – brass tacks Aug 2 '15 at 17:45
11

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.

| improve this answer | |
  • 26*26=676 Good catch, Agnius Vasiliauskas. I tried to reinstate your edit but this comment is the best I can do. – BillR Dec 16 '17 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.