Comment déterminer si la séquence de caractères est un mot anglais ou du bruit

Quel genre de fonctionnalités que vous essayerez d'extraire de la liste de mots pour une prédiction future, est-ce un mot existant ou simplement un désordre de caractères?

Il y a une description de la tâche que j'ai trouvée là-bas .

Vous devez écrire un programme qui peut répondre si un mot donné est anglais. Ce serait facile - il vous suffirait de rechercher le mot dans le dictionnaire - mais il y a une restriction importante: votre programme ne doit pas dépasser 64 Ko.

J'ai donc pensé qu'il serait possible d'utiliser la régression logistique pour résoudre le problème. Je n'ai pas beaucoup d'expérience avec l'exploration de données mais la tâche est intéressante pour moi.

Merci.

Pendant la PNL et l'analyse de texte, plusieurs variétés de fonctionnalités peuvent être extraites d'un document de mots à utiliser pour la modélisation prédictive. Il s'agit notamment des éléments suivants.

ngrams

Prenez un échantillon aléatoire de mots dans words.txt . Pour chaque mot de l'échantillon, extrayez chaque gramme de lettres possible. Par exemple, le mot force se compose de ces bi-grammes: { st , tr , re , en , ng , gt , th }. Groupez par bi-gramme et calculez la fréquence de chaque bi-gramme dans votre corpus. Maintenant, faites la même chose pour les tri-grammes, jusqu'à n-grammes. À ce stade, vous avez une idée approximative de la distribution de fréquence de la façon dont les lettres romaines se combinent pour créer des mots anglais.

ngram + limites des mots

Pour faire une analyse correcte, vous devriez probablement créer des balises pour indiquer les n-grammes au début et à la fin d'un mot ( chien -> { ^ d , do , og , g ^ }) - cela vous permettrait de capturer phonologique / orthographique des contraintes qui pourraient autrement être manquées (par exemple, la séquence ng ne peut jamais se produire au début d'un mot anglais natif, donc la séquence ^ ng n'est pas autorisée - l'une des raisons pour lesquelles les noms vietnamiens comme Nguyễn sont difficiles à prononcer pour les anglophones) .

Appelez cette collection de grammes le word_set . Si vous inversez le tri par fréquence, vos grammes les plus fréquents seront en haut de la liste - ils refléteront les séquences les plus courantes sur les mots anglais. Ci-dessous, je montre du code (laid) en utilisant le package {ngram} pour extraire les ngrammes de lettres des mots puis calculer les fréquences de gramme:

#' 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 

Votre programme prendra simplement une séquence entrante de caractères en entrée, la divisera en grammes comme discuté précédemment et la comparera à la liste des premiers grammes. Évidemment, vous devrez réduire vos n premiers choix pour répondre à la taille du programme .

consonnes et voyelles

Une autre caractéristique ou approche possible serait d'examiner les séquences de voyelles consonantiques. Convertissez tous les mots en chaînes de voyelles consonantiques (par exemple, pancake -> CVCCVCV ) et suivez la même stratégie que celle discutée précédemment. Ce programme pourrait probablement être beaucoup plus petit, mais il souffrirait de précision car il résume les téléphones en unités de haut niveau.

nchar

Une autre caractéristique utile sera la longueur de chaîne, car la possibilité de mots anglais légitimes diminue à mesure que le nombre de caractères augmente.

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

Erreur d'analyse

Le type d'erreurs produites par ce type de machine devrait être des mots absurdes - des mots qui semblent être des mots anglais mais qui ne le sont pas (par exemple, ghjrtg serait correctement rejeté (vrai négatif) mais barkle serait incorrectement classé comme un mot anglais (faux positif)).

Fait intéressant, les zyzzyvas seraient rejetés à tort (faux négatif), car zyzzyvas est un vrai mot anglais (au moins selon words.txt ), mais ses séquences de grammes sont extrêmement rares et donc peu susceptibles de contribuer à un pouvoir discriminatoire important.