4
$\begingroup$

The main issue is that several research building their solution of detecting and classifying English language is based on bigram distribution. However, I would like to know if it possible to generate a random set of words that are not English (rubbish words) but still respect the bigram of the English language. Is there any idea on how we can construct that if possible?

$\endgroup$
  • $\begingroup$ Do you want to create a language with the same bigram or just a sequence of words without actual meaning ? $\endgroup$ – Anthony Martin Sep 18 '14 at 8:36
  • $\begingroup$ yes i want words without any meaning ... $\endgroup$ – user2085339 Sep 18 '14 at 9:17
  • $\begingroup$ Do you want to generate words which are surely rubbish? I mean your problem is that is expensive to check if a word is rubbish or not and you want a procedure which produces only rubbish? $\endgroup$ – rapaio Sep 18 '14 at 12:26
  • $\begingroup$ Please do not change your question after it has been discussed and answered. If you have a new question, then you may begin a new thread. $\endgroup$ – whuber Nov 8 '14 at 13:37
8
$\begingroup$

Sure: run a Markov chain.

This Markov chain should begin with a letter chosen randomly from the alphabet with probabilities proportional to the letter frequencies. In order to distinguish words, the alphabet needs to include spaces (and other word separators, if they are being tracked, such as punctuation) and the bigrams need to include the spaces.

At each step in the chain, a transition is made from the current letter to another letter with probabilities proportional to the bigram frequencies. The relevant bigrams are only those beginning with the current letter. Transition frequencies are conveniently (and conventionally) maintained in a square array: the current letter indexes the rows and the next letter indexes the columns.

As an example, let's read the actual question text in this post, clean it a little to remove punctuation and sequences of whitespace, compute its bigrams, and estimate a transition matrix from these bigrams. This code uses R:

#
# Create the bigram information.
#
text <- readLines("http://stats.stackexchange.com/q/115883")
i <- grep("\"post-text\"", text)[1]         # Find the post text
j <- grep("</div", text)                    # Find where it ends
j <- min(j[j > i])
s <- paste(text[(i+1):(j-1)], collapse=" ") # Paste lines together
s <- gsub("[^[:alnum:] ]+", " ", s)         # Remove non-alpha
s <- gsub("[[:blank:]]+", " ", s)           # Remove sequences of ws
s <- tolower(s)                             # Ignore case
s <- unlist(strsplit(s, character(0), fixed=TRUE)) # Convert to vector
bigrams <-table(s[-length(s)], s[-1])       # Bigram frequencies: rows->cols
s.freq <- table(s)                          # Letter frequencies

To illustrate, the letter frequency array s.freq begins like this:

                    a          b          c          d ...
0.17934783 0.05978261 0.02717391 0.01902174 0.02717391 ...

Spaces occur 18% of the time, "a" occurs 6% of the time, "b" occurs 2.7%, and so on. The transition array in bigrams begins like this:

                        a          b          c          d ...
    0.00000000 0.06153846 0.07692308 0.04615385 0.03076923 ...
  a 0.09090909 0.00000000 0.00000000 0.00000000 0.00000000 ...
  b 0.00000000 0.10000000 0.10000000 0.00000000 0.00000000 ...
  c 0.00000000 0.14285714 0.00000000 0.00000000 0.00000000 ...
  d 0.30000000 0.00000000 0.00000000 0.00000000 0.00000000 ...
... ...        ...        ...        ...        ...

For instance--reading across the first row--a space is followed by an "a" 6% of the time, by a "b" 7.7% of the time, and so on. A "b" is never followed by a space, is followed by an "a" 10% of the time, and so on.

Let's run this chain for the same length as the original post:

#
# Run a Markov chain.
#
set.seed(17)
a <- sample(names(s.freq), 1, prob=s.freq)  # Select a random start
text.sim <- sapply(1:length(s), function(i) {
  a.old <- a
  a <<- sample(colnames(bigrams), 1, prob=bigrams[a, ])
  return(a.old)
})
text.sim <- paste(text.sim, collapse="")    # Put the letters together
#text.sim <- strsplit(text.sim, " ")         # Split into words

The output in text.sim is

m en ist ra lll ilderdes aguth lag por ecth i cthon ibl is tis ibinge liglds ige ore dsuthain asiso idetenglire instid w il bishagre la isetisis tiblas m isi t rdol oratist asere pony wo bbld bul g she we sh pe le ne of t ke m p s buany ralildike t tissh of s ibbbbangeve pongre blectinon m onguco we westingled buba t ing te lirdsuaruath bbutr we ilithange isp worch

It doesn't look very English-like because the post was such a specialized subset of English. For a more realistic result I used the text of the USA Declaration of Independence, which produced this:

ntese te heigluthasiolyr fothe bl abssucher apuriven ssthe tond f ong beantin ran whel nd c o ssthourfiry of lind dirbeng plan forn tarn arsth thecto peouredur h mplie ourn fo se cheghatofirin outt pratid pr woncatuf o theyr usthan athtse med hor thed as o tondeigize fis cin wis calalie iles tubal venetrs onid arild an ath te edeo ict he d ta ie aleiour in turincke pllenodinde one ren ollame than

Clearly bigrams are not very good: they do not consistently enforce basic rules, such as requiring a vowel to appear in each word. But this approach does produce pseudo-words of the right lengths and, by and large, the words of more than one letter bear some facsimile to English. "... o theyr usthan athtse med hor thed ..." could even be mistaken for something out of an Old English text.

Some of the generated words, like "plan" and "of", are legitimate. That's usually not a problem when simulating words to study text-mining algorithms, but if true non-words are needed, it's a simple matter to look all the words up in a dictionary and eliminate those that have a match. (A relational database join would make short work of this step.)

$\endgroup$
  • $\begingroup$ Thanks for the answer, however, the first part is very clear. the general approach is also clear. I am just confused with the last step. how do you create back the letters from the matrix? can you explain in plain english rathar than R $\endgroup$ – user2085339 Nov 6 '14 at 12:31
  • $\begingroup$ This question is answered in the second paragraph: each letter encountered during the Markov chain is output sequentially. $\endgroup$ – whuber Nov 6 '14 at 14:43

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.