Contando palabras en inglés en una cadena aleatoria

Question

Supongamos que tengo una cadena generada aleatoriamente s=t&^%JHGgfdteam*&HGEdfg, ¿cuál es el mejor enfoque para contar el número de palabras en inglés en esa cadena? (Palabras en inglés como se define en algún archivo de diccionario). Obviamente, la fuerza bruta no es una buena idea ... ¿funcionaría un sufijo-tri? ¿Búsqueda binaria? Tenga en cuenta que en el caso de s, hay dos palabras: "té" y "equipo". Alguna idea? Saludos

Answer 1

Yo cargaba las palabras del diccionario en una estructura Trie, luego leo la cadena de izquierda a derecha y verifico si las subcadenas están en el trie. Si lo son y hay niños, sigue adelante. Si resultan ser una hoja o una palabra válida, agréguela al recuento de incidencias.

En pseudocódigo:

Trie dict = ... // load dictionary 
Dictionary occurences = {} 

for i in length(string): 
    j = i + 1 
    # think of partial as string.Substring(i, j); 
    while dict.hasChildren(partial): 
     j++ 
     if isWord(partial): 
      dict[partial]++ 

esta manera usted garantiza que no se pierde ni un partido, mientras que todavía en busca de todas las posibilidades.

puede limitar la duración mínima de las palabras válidas cambiando lo j se inicializa o rechazando palabras cortas en el método isWord() (por lo a no habría una palabra "válida").

Answer 2

Aho-Corasick string matching algorithm construye la estructura coincidente en el tiempo lineal en el tamaño del diccionario y coincide con los patrones en el tiempo lineal en el tamaño del texto de entrada + número de coincidencias encontradas.