Cómo determinar si la secuencia de caracteres es palabra o ruido en inglés

¿Qué tipo de características tratará de extraer de la lista de palabras para predecir en el futuro, es una palabra existente o solo un desorden de caracteres?

Hay una descripción de la tarea que encontré allí .

Tienes que escribir un programa que pueda responder si una palabra determinada es inglés. Esto sería fácil, solo necesitaría buscar la palabra en el diccionario, pero hay una restricción importante: su programa no debe ser mayor de 64 KiB.

Entonces, pensé que sería posible usar la regresión logística para resolver el problema. No tengo mucha experiencia con la minería de datos, pero la tarea es interesante para mí.

Gracias.

Durante la PNL y el análisis de texto, se pueden extraer varias variedades de características de un documento de palabras para usarlas en el modelado predictivo. Estos incluyen lo siguiente.

ngrams

Tome una muestra aleatoria de palabras de words.txt . Para cada palabra en la muestra, extraiga cada bi-gramo de letras posible. Por ejemplo, la palabra fuerza consiste en estos dos gramos: { st , tr , re , en , ng , gt , th }. Agrupe por bi-gramo y calcule la frecuencia de cada bi-gramo en su corpus. Ahora haga lo mismo para tri-gramos, ... hasta n-gramos. En este punto, tiene una idea aproximada de la distribución de frecuencias de cómo las letras romanas se combinan para crear palabras en inglés.

ngram + límites de palabras

Para hacer un análisis adecuado, probablemente debería crear etiquetas para indicar n-gramos al principio y al final de una palabra, ( perro -> { ^ d , do , og , g ^ }) - esto le permitiría capturar fonología / ortografía restricciones que de otro modo podrían pasarse por alto (por ejemplo, la secuencia ng nunca puede ocurrir al comienzo de una palabra nativa en inglés, por lo tanto, la secuencia ^ ng no está permitida, una de las razones por las que los nombres vietnamitas como Nguyễn son difíciles de pronunciar para los hablantes de inglés) .

Llame a esta colección de gramos el conjunto de palabras . Si invierte la clasificación por frecuencia, sus gramos más frecuentes estarán en la parte superior de la lista; estos reflejarán las secuencias más comunes en las palabras en inglés. A continuación muestro un código (feo) usando el paquete {ngram} para extraer las letras ngrams de las palabras y luego calcular las frecuencias de gramo:

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

Su programa solo tomará una secuencia entrante de caracteres como entrada, la dividirá en gramos como se discutió anteriormente y la comparará con la lista de los mejores gramos. Obviamente, tendrá que reducir sus n mejores opciones para ajustarse al requisito de tamaño del programa .

consonantes y vocales

Otra posible característica o enfoque sería observar secuencias de vocales consonantes. Básicamente convertir todas las palabras en cuerdas vocales consonantes (por ejemplo, panqueque -> CVCCVCV ) y seguir la misma estrategia discutido previamente. Este programa probablemente podría ser mucho más pequeño pero sufriría de precisión porque abstrae los teléfonos en unidades de alto orden.

nchar

Otra característica útil será la longitud de la cadena, ya que la posibilidad de palabras legítimas en inglés disminuye a medida que aumenta el número de caracteres.

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

Análisis de errores

El tipo de errores producidos por este tipo de máquina debería ser palabras sin sentido , palabras que parecen ser palabras en inglés pero que no lo son (por ejemplo, ghjrtg sería rechazado correctamente (verdadero negativo) pero Barkle se clasificaría incorrectamente como una palabra en inglés (falso positivo)).

Curiosamente, zyzzyvas sería rechazado incorrectamente (falso negativo), porque zyzzyvas es una palabra real en inglés (al menos de acuerdo con words.txt ), pero sus secuencias de gram son extremadamente raras y, por lo tanto, no es probable que aporten mucho poder discriminatorio.