Jak ustalić, czy sekwencja znaków jest angielskim słowem czy szumem

Jakie funkcje spróbujesz wyodrębnić z listy słów do przewidywania w przyszłości, czy to istniejące słowo, czy tylko bałagan znaków?

Tam jest opis zadania, które tam znalazłem .

Musisz napisać program, który może odpowiedzieć, czy dane słowo jest angielskim. To byłoby łatwe - wystarczy wyszukać słowo w słowniku - jest jednak ważne ograniczenie: twój program nie może być większy niż 64 KiB.

Pomyślałem więc, że do rozwiązania problemu można zastosować regresję logistyczną. Nie mam dużego doświadczenia w eksploracji danych, ale zadanie jest dla mnie interesujące.

Dzięki.

Podczas analizy NLP i analizy tekstu można wyodrębnić kilka odmian funkcji z dokumentu zawierającego słowa, które mają zostać wykorzystane do modelowania predykcyjnego. Należą do nich następujące.

ngramy

Weź losową próbkę słów z words.txt . Dla każdego słowa w próbce wyodrębnij każdy możliwy bi-gram liter. Na przykład siła słowa składa się z tych bi-gramów: { st , tr , re , en , ng , gt , th }. Grupuj według bi-gramów i oblicz częstotliwość każdego bi-gramu w twoim ciele. Teraz zrób to samo dla tri-gramów, ... aż do n-gramów. W tym momencie masz ogólne pojęcie o rozkładzie częstotliwości łączenia liter rzymskich w celu tworzenia angielskich słów.

ngram + granice słów

Aby przeprowadzić prawidłową analizę, prawdopodobnie powinieneś utworzyć znaczniki wskazujące n-gramów na początku i na końcu słowa ( pies -> { ^ d , do , og , g ^ }) - to pozwoli ci uchwycić fonologię / ortografię ograniczenia, które w innym przypadku mogłyby zostać pominięte (np. sekwencja ng nigdy nie może wystąpić na początku rodzimego angielskiego słowa, dlatego sekwencja ^ ng jest niedozwolona - jeden z powodów, dla których wietnamskie nazwy takie jak Nguyễn są trudne do wymówienia dla osób posługujących się językiem angielskim) .

Nazwij tę kolekcję gramów zestawem słów . Jeśli odwrócisz sortowanie według częstotliwości, twoje najczęstsze gramy będą na górze listy - będą one odzwierciedlać najczęstsze sekwencje w angielskich słowach. Poniżej pokazuję (brzydki) kod za pomocą pakietu {ngram}, aby wyodrębnić literę ngram ze słów, a następnie obliczyć częstotliwości gramów:

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

Twój program po prostu pobierze przychodzącą sekwencję znaków jako wejście, podzieli ją na gramy, jak omówiono wcześniej, i porówna z listą najwyższych gramów. Oczywiście będziesz musiał zmniejszyć liczbę najlepszych wyborów, aby spełnić wymagania dotyczące rozmiaru programu .

spółgłosek i samogłosek

Inną możliwą cechą lub podejściem byłoby przyjrzenie się sekwencji samogłoskowej spółgłoski. Zasadniczo przekonwertuj wszystkie słowa w ciągach samogłosek samogłoskowych (np. Pancake -> CVCCVCV ) i postępuj zgodnie z tą samą strategią, którą omówiono wcześniej. Ten program prawdopodobnie byłby znacznie mniejszy, ale miałby mniejszą dokładność, ponieważ dzieli telefony na jednostki o wysokim poziomie.

nchar

Kolejną przydatną funkcją będzie długość łańcucha, ponieważ wraz ze wzrostem liczby znaków zmniejsza się liczba dozwolonych angielskich słów.

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

Analiza błędów

Typami błędów generowanych przez ten typ maszyny powinny być bzdury - słowa, które wyglądają tak, jakby były angielskimi słowami, ale które nie są (np. Ghjrtg zostałby poprawnie odrzucony (prawda przecząca), ale szczekanie nieprawidłowo sklasyfikowane jako słowo angielskie (fałszywie dodatni)).

Co ciekawe, zyzzyvas zostałby niepoprawnie odrzucony (fałszywie ujemny), ponieważ zyzzyvas to prawdziwe angielskie słowo (przynajmniej zgodnie z words.txt ), ale jego sekwencje gramów są niezwykle rzadkie, a zatem prawdopodobnie nie wniosą dużej mocy dyskryminacyjnej.