string - sinonimos - ¿Cómo desglosar un texto dado en palabras del diccionario?

rae

Question

Esta es una pregunta de entrevista. Supongamos que tiene un text cadena y un dictionary (un conjunto de cadenas). ¿Cómo se divide el text en subcadenas de manera que cada subcadena se encuentre en el dictionary ?

Por ejemplo, puede desglosar "thisisatext" en ["this", "is", "a", "text"] usando /usr/share/dict/words .

Creo que el backtracking puede resolver este problema (en pseudo-Java):

void solve(String s, Set<String> dict, List<String> solution) { if (s.length == 0) return for each prefix of s found in dict solve(s without prefix, dict, solution + prefix) } List<String> solution = new List<String>() solve(text, dict, solution)

¿Tiene sentido? ¿Optimizaría el paso de buscar los prefijos en el diccionario? ¿Qué estructuras de datos recomendarías?

Answer 1

En esta publicación del blog hay un resumen muy detallado de la solución a este problema .

La idea básica es simplemente memorizar la función que ha escrito y tendrá un algoritmo de tiempo O (n ^ 2), espacio O (n).

Answer 2

Esta solución asume la existencia de la estructura de datos Trie para el diccionario. Además, para cada nodo en Trie, asume las siguientes funciones:

1. node.IsWord (): devuelve true si la ruta a ese nodo es una palabra
2. node.IsChild (char x): Devuelve true si existe un elemento secundario con etiqueta x
3. node.GetChild (char x): devuelve el nodo secundario con la etiqueta x

Function annotate( String str, int start, int end, int root[], TrieNode node):
i = start
while i<=end:
    if node.IsChild ( str[i]):
        node = node.GetChild( str[i] )
        if node.IsWord():
            root[i+1] = start
        i+=1
    else:
        break;

end = len(str)-1
root = [-1 for i in range(len(str)+1)]
for start= 0:end:
    if start = 0 or root[start]>=0:
        annotate(str, start, end, root, trieRoot)

index  0  1  2  3  4  5  6  7  8  9  10  11
str:   t  h  i  s  i  s  a  t  e  x  t
root: -1 -1 -1 -1  0 -1  4  6 -1  6 -1   7

Le dejaré la parte para que enumere las palabras que forman la cadena haciendo un recorrido inverso de la raíz.

La complejidad del tiempo es O (nk) donde n es la longitud de la cadena y k es la longitud de la palabra más larga del diccionario.

PS: Estoy asumiendo las siguientes palabras en el diccionario: esto es, a, text, ate.

Answer 3

Puedes resolver este problema utilizando la programación dinámica y el Hashing .

Calcula el hash de cada palabra en el diccionario. Usa la función hash que más te guste. Yo usaría algo como (a1 * B ^ (n - 1) + a2 * B ^ (n - 2) + ... + an * B ^ 0)% P, donde a1a2 ... an es una cadena, n es la longitud de la cadena, B es la base del polinomio y P es un número primo grande. Si tiene el valor hash de una cadena a1a2 ... y puede calcular el valor hash de la cadena a1a2 ... ana (n + 1) en tiempo constante: (hashValue (a1a2 ... an) * B + a (n + 1))% P.

La complejidad de esta parte es O (N * M), donde N es el número de palabras en el diccionario y M es la longitud de la palabra más larga en el diccionario.

Luego, usa una función DP como esta:

   bool vis[LENGHT_OF_STRING];
   bool go(char str[], int length, int position)
   {
      int i;

      // You found a set of words that can solve your task.
      if (position == length) {
          return true;
      }

      // You already have visited this position. You haven''t had luck before, and obviously you won''t have luck this time.
      if (vis[position]) {
         return false;
      }
      // Mark this position as visited.
      vis[position] = true;

      // A possible improvement is to stop this loop when the length of substring(position, i) is greater than the length of the longest word in the dictionary.
      for (i = position; position < length; i++) {
         // Calculate the hash value of the substring str(position, i);
         if (hashValue is in dict) {
            // You can partition the substring str(i + 1, length) in a set of words in the dictionary.
            if (go(i + 1)) {
               // Use the corresponding word for hashValue in the given position and return true because you found a partition for the substring str(position, length).
               return true;
            }
         }
      }

      return false;
   }

La complejidad de este algoritmo es O (N * M), donde N es la longitud de la cadena y M es la longitud de la palabra más larga en el diccionario u O (N ^ 2), dependiendo de si codificó la mejora o no.

Entonces, la complejidad total del algoritmo será: O (N1 * M) + O (N2 * M) (o O (N2 ^ 2)), donde N1 es el número de palabras en el diccionario, M es la longitud del La palabra más larga en el diccionario y N2 es la longitud de la cadena).

Si no puede pensar en una buena función hash (donde no hay ninguna colisión), otra solución posible es usar Tries o Patricia Trie (si el tamaño del trie normal es muy grande) (no pude publicar enlaces) para estos temas porque mi reputación no es lo suficientemente alta como para publicar más de 2 enlaces). Pero al usar esto, la complejidad de su algoritmo será O (N * M) * O (Tiempo necesario para encontrar una palabra en el trie), donde N es la longitud de la cadena y M es la longitud de la palabra más larga en el diccionario.

Espero que ayude, y me disculpo por mi pobre inglés.

Answer 4

Enfoque 1- Trie parece ser un ajuste perfecto aquí. Generar trie de las palabras en el diccionario de inglés. Este edificio es un costo de tiempo. Después de que se haya construido trie, su string se puede comparar fácilmente letra por letra. si en algún punto encuentra una hoja en el trío, puede asumir que encontró una palabra, agregue esto a una lista y continúe con su recorrido. Haz el recorrido hasta que hayas llegado al final de la string . La lista es de salida.

Complejidad de tiempo para la búsqueda - O (word_length).

Complejidad del espacio - O (charsize * word_length * no_words). Tamaño de su diccionario.

Enfoque 2: he oído hablar de los árboles de sufijo , nunca los usé, pero podría ser útil aquí.

Enfoque 3: es una alternativa más pedante y pésima. Usted ya ha sugerido esto.

Podrías probar al revés. Ejecutar el dict es verificar la concordancia de sub-cadena. Aquí estoy asumiendo que las claves en dict son las words del diccionario de inglés /usr/share/dict/words . Así que el código psuedo se parece a esto.

(list) splitIntoWords(String str, dict d)
{
    words = []
    for (word in d)
    {
        if word in str
            words.append(word);
    }
    return words;
}

Complejidad: O (n) que se ejecuta a través de todo dict + O (1) para la concordancia de subcadenas.

Espacio: caso más desfavorable O (n) si len(words) == len(dict)

Como otros han señalado, esto requiere un retroceso.