How to determine if character sequence is English word or noise

What kind of features you will try to extract from list of words for future predicting, is it existing word or just mess of characters ?

There is description of task that I found there.

You have to write a program that can answer whether a given word is English. This would be easy — you'd just need to look the word up in the dictionary — but there is an important restriction: your program must not be larger than 64 KiB.

So, I thought it would be possible to use logistic regression for solving the problem. I don't have a lot of experience with data-mining but the task is interesting for me.

Thanks.

• The letter n-grams. – Emre Apr 28 '16 at 17:26
• Look it up in a dictionary? What are you trying to do here, this isn't clear. Give examples. – Spacedman Apr 28 '16 at 17:35
• Sorry, maybe I didn't explain the problem completely. There is description of task that I found there You have to write a program that can answer whether a given word is English. This would be easy — you'd just need to look the word up in the dictionary — but there is an important restriction: your program must not be larger than 64 KiB. So, I thought it would be possible to use logistic regression for solving the problem. I don't have a lot of experience with data-mining but the task is interesting for me. – Vitalii Mishchenko Apr 28 '16 at 18:19

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"
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.

• fyi - no need to sample from words.txt, just use the entire list (i've been in big data land for a cpl years so the first words out of my mouth are always "take a random sample" lol). – Brandon Loudermilk Apr 29 '16 at 10:49
• I think the winner of this competition is likely to add some further insight than ngrams, although it may well include them as part of the strategy. I think that using solely ngrams will lead to many false positives, as the test description implies that "believable" but non-English words are in the the test set. – Neil Slater Apr 29 '16 at 11:46
• A generalization of your consonants & vowels strategy is skip-grams. – Emre Apr 29 '16 at 17:10
• @BrandonLoudermilk would it be possible to share the python code for the samples that you've shared? – iam.Carrot Sep 7 '18 at 17:43