During NLP and text analytics, several varieties of features can be extracted from a document of words to use for predictive modeling. These include the following.
ngrams
Take a random sample of words from words.txt. For each word in sample, extract every possible bi-gram of letters. For example, the word strength consists of these bi-grams: {st, tr, re, en, ng, gt, th}. Group by bi-gram and compute the frequency of each bi-gram in your corpus. Now do the same thing for tri-grams, ... all the way up to n-grams. At this point you have a rough idea of the frequency distribution of how Roman letters combine to create English words.
ngram + word boundaries
To do a proper analysis you should probably create tags to indicate n-grams at the start and end of a word, (dog -> {^d, do, og, g^}) - this would allow you to capture phonological/orthographic constraints that might otherwise be missed (e.g., the sequence ng can never occur at the beginning of a native English word, thus the sequence ^ng is not permissible - one of the reasons why Vietnamese names like Nguyễn are hard to pronounce for English speakers).
Call this collection of grams the word_set. If you reverse sort by frequency, your most frequent grams will be at the top of the list -- these will reflect the most common sequences across English words. Below I show some (ugly) code using package {ngram} to extract the letter ngrams from words then compute the gram frequencies:
#' Return orthographic n-grams for word
#' @param w character vector of length 1
#' @param n integer type of n-gram
#' @return character vector
#'
getGrams <- function(w, n = 2) {
require(ngram)
(w <- gsub("(^[A-Za-z])", "^\\1", w))
(w <- gsub("([A-Za-z]$)", "\\1^", w))
# for ngram processing must add spaces between letters
(ww <- gsub("([A-Za-z^'])", "\\1 \\2", w))
w <- gsub("[ ]$", "", ww)
ng <- ngram(w, n = n)
grams <- get.ngrams(ng)
out_grams <- sapply(grams, function(gram){return(gsub(" ", "", gram))}) #remove spaces
return(out_grams)
}
words <- list("dog", "log", "bog", "frog")
res <- sapply(words, FUN = getGrams)
grams <- unlist(as.vector(res))
table(grams)
## ^b ^d ^f ^l bo do fr g^ lo og ro
## 1 1 1 1 1 1 1 4 1 4 1
Your program will just take an incoming sequence of characters as input, break it into grams as previously discussed and compare to list of top grams. Obviously you will have to reduce your top n picks to fit the program size requirement.
consonants & vowels
Another possible feature or approach would be to look at consonant vowel sequences. Basically convert all words in consonant vowel strings (e.g., pancake -> CVCCVCV) and follow the same strategy previously discussed. This program could probably be much smaller but it would suffer from accuracy because it abstracts phones into high-order units.
nchar
Another useful feature will be string length, as the possibility for legitimate English words decreases as the number of characters increases.
library(dplyr)
library(ggplot2)
file_name <- "words.txt"
df <- read.csv(file_name, header = FALSE, stringsAsFactors = FALSE)
names(df) <- c("word")
df$nchar <- sapply(df$word, nchar)
grouped <- dplyr::group_by(df, nchar)
res <- dplyr::summarize(grouped, count = n())
qplot(res$nchar, res$count, geom="path",
xlab = "Number of characters",
ylab = "Frequency",
main = "Distribution of English word lengths in words.txt",
col=I("red"))
Error Analysis
The type of errors produced by this type of machine should be nonsense words - words that look like they should be English words but which aren't (e.g., ghjrtg would be correctly rejected (true negative) but barkle would incorrectly classified as an English word (false positive)).
Interestingly, zyzzyvas would be incorrectly rejected (false negative), because zyzzyvas is a real English word (at least according to words.txt), but its gram sequences are extremely rare and thus not likely to contribute much discriminatory power.
