Romper una cadena aparte en una secuencia de palabras

Question

Recientemente me encontré con la siguiente pregunta de la entrevista:

Dada una cadena de entrada y un diccionario de palabras, poner en práctica un método que rompe la cadena de entrada en un espacio- cadena separada de palabras del diccionario que un motor de búsqueda podría usar para "¿Querías decir?" Por ejemplo, una entrada de "applepie" debería producir una salida de "pastel de manzana".

Parece que no puedo encontrar una solución óptima en lo que a complejidad se refiere. ¿Alguien tiene alguna sugerencia sobre cómo hacer esto de manera eficiente?

Answer 1

Parece que la pregunta es exactamente mi problema de entrevista, hasta el ejemplo que utilicé en el post en The Noisy Channel. Me alegro de que le haya gustado la solución. Estoy bastante seguro de que no se puede vencer a la solución de programación/memorización dinámica O (n^2) que describo para el peor de los casos.

Puede hacerlo mejor en la práctica si su diccionario y su entrada no son patológicos. Por ejemplo, si puede identificar en tiempo lineal, las subcadenas de la cadena de entrada están en el diccionario (p., con un trie) y si el número de tales subcadenas es constante, entonces el tiempo total será lineal. Por supuesto, eso es una gran cantidad de suposiciones, pero los datos reales a menudo son mucho mejores que un peor caso patológico.

También hay variaciones divertidas del problema para dificultar, como enumerar todas las segmentaciones válidas, generar una mejor segmentación basada en alguna definición de mejor, manejar un diccionario demasiado grande para caber en la memoria y manejar segmentaciones inexactas (por ejemplo, corrigiendo errores de ortografía). Siéntase libre de comentar en mi blog o de lo contrario contácteme para dar seguimiento.

Answer 2

Una opción sería almacenar todas las palabras válidas en inglés en un trie. Una vez que haya hecho esto, puede comenzar a caminar desde la raíz hacia abajo, siguiendo las letras de la cadena. Cada vez que encuentre un nodo que está marcado como una palabra, tiene dos opciones:

1. romper la entrada en este punto, o
2. seguir extendiendo la palabra.

Puede afirmar que ha encontrado una coincidencia una vez que ha dividido la entrada en un conjunto de palabras que son todas legales y no le quedan caracteres restantes. Como en cada carta tiene una opción forzada (o bien está construyendo una palabra que no es válida y debe detenerse -o bien puede seguir ampliando la palabra) o dos opciones (dividir o seguir), podría implementar esta función utilizando la recursividad exhaustiva:

PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode): 
    // If you walked off the trie, this path fails. 
    if trieNode is null, return. 

    // If this trie node is a word, consider what happens if you split 
    // the word here. 
    if trieNode.isWord: 
     // If there is no input left, you're done and have a partition. 
     if lettersLeft is empty, output wordBreaks + wordSoFar and return 

     // Otherwise, try splitting here. 
     PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root) 

    // Otherwise, consume the next letter and continue: 
    PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0], 
        wordBreaks, trieNode.child[lettersLeft[0]) 

En el peor de los casos patológicamente esto mostrará todas las particiones de la cadena, que puede t exponencialmente larga. Sin embargo, esto solo ocurre si puede particionar la cadena de muchas formas, todas comienzan con palabras válidas en inglés y es poco probable que ocurra en la práctica. Si la cadena tiene muchas particiones, podríamos pasar mucho tiempo buscándolas. Por ejemplo, considere la cadena "dotheredo". Podemos dividir este muchas maneras:

do the redo 
do the red o 
doth ere do 
dot here do 
dot he red o 
dot he redo 

Para evitar esto, es posible que desee establecer un límite del número de respuestas que reporta, tal vez dos o tres.

Como cortamos la recursión cuando salimos del trie, si alguna vez intentamos una división que no deje el resto de la cadena válida, lo detectaremos rápidamente.

Espero que esto ayude!

Answer 3

link describe este problema como una pregunta de entrevista perfecta y proporciona varios métodos para resolverlo. Esencialmente implica recursive backtracking. En este nivel produciría una complejidad O (2^n). Una solución eficiente que utiliza la memorización podría reducir este problema a O (n^2).

Answer 4

import java.util. *;

class Position { 
    int indexTest,no; 
    Position(int indexTest,int no) 
    { 
     this.indexTest=indexTest; 
     this.no=no; 
    } } class RandomWordCombo { 
    static boolean isCombo(String[] dict,String test) 
    { 
     HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>(); 
     Stack<Position> pos=new Stack<Position>(); 
     for(String each:dict) 
     { 
      if(dic.containsKey(""+each.charAt(0))) 
      { 
       //System.out.println("=========it is here"); 
       ArrayList<String> temp=dic.get(""+each.charAt(0)); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
      else 
      { 
       ArrayList<String> temp=new ArrayList<String>(); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
     } 
     Iterator it = dic.entrySet().iterator(); 
    while (it.hasNext()) { 
     Map.Entry pair = (Map.Entry)it.next(); 
     System.out.println("key: "+pair.getKey()); 
     for(String str:(ArrayList<String>)pair.getValue()) 
     { 
      System.out.print(str); 
     } 
    } 
     pos.push(new Position(0,0)); 
     while(!pos.isEmpty()) 
     { 
      Position position=pos.pop(); 
      System.out.println("position index: "+position.indexTest+" no: "+position.no); 
      if(dic.containsKey(""+test.charAt(position.indexTest))) 
      { 
       ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest)); 
       if(strings.size()>1&&position.no<strings.size()-1) 
        pos.push(new Position(position.indexTest,position.no+1)); 
       String str=strings.get(position.no); 
       if(position.indexTest+str.length()==test.length()) 
        return true; 
       pos.push(new Position(position.indexTest+str.length(),0)); 
      } 
     } 
     return false; 
    } 
    public static void main(String[] st) 
    { 
     String[] dic={"world","hello","super","hell"}; 
     System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman")); 
    } } 

he hecho problema similar. Esta solución da verdadero o falso si la cadena dada es una combinación de palabras del diccionario. Se puede convertir fácilmente para obtener una secuencia separada por espacios. Su complejidad promedio es O (n), donde n: no de palabras del diccionario en cadena dada.

Answer 5

Usando python, podemos escribir dos funciones, la primera segment devuelve la primera segmentación de un fragmento de texto contiguo en palabras dadas a un diccionario o None si no se encuentra dicha segmentación. Otra función segment_all devuelve una lista de todas las segmentaciones encontradas. La peor complejidad de caso es O (n ** 2) donde n es la longitud de la cadena de entrada en caracteres.

La solución que aquí se presenta se puede ampliar para incluir correcciones ortográficas y análisis de bigram para determinar la segmentación más probable.