algoritmo para transformar una palabra a otra a través de palabras válidas

Question

me encontré con esta variación de edit-distance problema:

diseñar un algoritmo que transforma una palabra de origen a una palabra objetivo. por ejemplo: de la cabeza a la cola, en cada paso, solo puede reemplazar un carácter, y la palabra debe ser válida. Se te dará un diccionario.

Es claramente una variación del problema edit distance, pero en la distancia de edición no me importa si la palabra es válida o no. Entonces, ¿cómo agrego este requisito para editar la distancia?

Answer 1

Esto se puede modelar como un problema de gráfico. Puede pensar en las palabras como nodos del gráfico y dos nodos están conectados si y solo si son de la misma longitud y difieren en un carácter.

Usted puede procesar previamente el diccionario y crear este gráfico, debe ser similar:

stack jack 
    |  | 
    |  | 
    smack back -- pack -- pick 

A continuación, puede tener un mapeo de la palabra al nodo que representa la palabra, para ello se puede utilizar una tabla hash, altura balanceada BST ...

Una vez que tenga la asignación anterior en su lugar, todo lo que tiene que hacer es ver si existe una ruta entre los dos nodos gráficos, que se puede hacer fácilmente con BFS o DFS.

Así se puede resumir el algoritmo como:

preprocess the dictionary and create the graph. 
Given the two inputs words w1 and w2 
if length(w1) != length(w2) 
Not possible to convert 
else 
n1 = get_node(w1) 
n2 = get_node(w2) 

if(path_exists(n1,n2)) 
    Possible and nodes in the path represent intermediary words 
else 
    Not possible 

Answer 2

No creo que esta sea la distancia de edición.

Creo que esto se puede hacer mediante un gráfico. Simplemente construya un gráfico de su diccionario e intente navegar utilizando su algoritmo de cruce de gráficos favorito al destino.

Answer 3

enfoque gráfico de codaddict es válida, aunque se tarda un tiempo O (n^2) la construcción de cada gráfico, donde n es el número de palabras de un determinado longitud. Si eso es un problema, puede crear un bk-tree de manera mucho más eficiente, lo que hace posible encontrar todas las palabras con una distancia de edición dada (en este caso, 1) de una palabra objetivo.

Answer 4

Esto es claramente un problema de permutación. Usar un gráfico es excesivo. La declaración de problema le falta una restricción importante; que puede cambiar cada posición solo una vez. Esto hace implícito que la solución está dentro de 4 pasos. Ahora todo lo que hay que decidir es la secuencia de las operaciones de reemplazar:

operation1 = cambio "H" a "T"
En funcionamiento 2 = cambio "E" a "A"
Operation3 = cambio "A" para "I"
Operation4 = cambio "D a 'L'

la solución, la secuencia de operaciones, es alguna permutación de la cadena '1234', donde cada dígito representa la posición del carácter que se sustituye. ej "3124" indica que primero aplicamos operación3, luego operación1, luego operación2, luego operación 4. En cada paso, si la palabra resultante no está en el diccionario, salte a la siguiente permutación. Razonablemente trivial. ¿Oye a alguien?

Answer 5

Crea un gráfico con cada nodo que representa la palabra en el diccionario. Agregue un borde entre dos nodos de palabras, si sus palabras correspondientes están a una distancia de edición de 1.Entonces el número mínimo de transformaciones requeridas sería la longitud de la ruta más corta entre el nodo fuente y el nodo de destino.

Answer 6

Este es el código C# para resolver el problema usando BFS:

//use a hash set for a fast check if a word is already in the dictionary 
    static HashSet<string> Dictionary = new HashSet<string>(); 
    //dictionary used to find the parent in every node in the graph and to avoid traversing an already traversed node 
    static Dictionary<string, string> parents = new Dictionary<string, string>(); 

    public static List<string> FindPath(List<string> input, string start, string end) 
    { 
     char[] allcharacters = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 

     foreach (string s in input) 
      Dictionary.Add(s); 
     List<string> currentFrontier = new List<string>(); 
     List<string> nextFrontier = new List<string>(); 
     currentFrontier.Add(start); 
     while (currentFrontier.Count > 0) 
     { 
      foreach (string s in currentFrontier) 
      { 
       for (int i = 0; i < s.Length; i++) 
       { 
        foreach (char c in allcharacters) 
        { 
         StringBuilder newWordBuilder = new StringBuilder(s); 
         newWordBuilder[i] = c; 
         string newWord = newWordBuilder.ToString(); 
         if (Dictionary.Contains(newWord)) 
         { 
          //avoid traversing a previously traversed node 
          if (!parents.Keys.Contains(newWord)) 
          { 
           parents.Add(newWord.ToString(), s); 
           nextFrontier.Add(newWord); 
          } 

         } 
         if (newWord.ToString() == end) 
         { 
          return ExtractPath(start, end); 

         } 
        } 
       } 
      } 
      currentFrontier.Clear(); 
      currentFrontier.Concat(nextFrontier); 
      nextFrontier.Clear(); 
     } 
     throw new ArgumentException("The given dictionary cannot be used to get a path from start to end"); 
    } 

    private static List<string> ExtractPath(string start,string end) 
    { 
     List<string> path = new List<string>(); 
     string current = end; 
     path.Add(end); 
     while (current != start) 
     { 
      current = parents[current]; 
      path.Add(current); 
     } 
     path.Reverse(); 
     return path; 
    } 

Answer 7

simplemente podría utilizar recursiva posterior de seguimiento, pero esto está lejos de ser la solución más óptima.

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only 
# one letter at a time. The new word you get in each step must be in the 
# dictionary. 

# def transform(english_words, start, end): 

# transform(english_words, 'damp', 'like') 
# ['damp', 'lamp', 'limp', 'lime', 'like'] 
# ['damp', 'camp', 'came', 'lame', 'lime', 'like'] 


def is_diff_one(str1, str2): 
    if len(str1) != len(str2): 
     return False 

    count = 0 
    for i in range(0, len(str1)): 
     if str1[i] != str2[i]: 
      count = count + 1 

    if count == 1: 
     return True 

    return False 


potential_ans = [] 


def transform(english_words, start, end, count): 
    global potential_ans 
    if count == 0: 
     count = count + 1 
     potential_ans = [start] 

    if start == end: 
     print potential_ans 
     return potential_ans 

    for w in english_words: 
     if is_diff_one(w, start) and w not in potential_ans: 
      potential_ans.append(w) 
      transform(english_words, w, end, count) 
      potential_ans[:-1] 

    return None 


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like']) 
transform(english_words, 'damp', 'lame', 0) 

Answer 8

No creo que necesitemos gráficos u otra estructura de datos complicada. Mi idea es cargar el diccionario como HashSet y usar el método para averiguar si la palabra existe en el diccionario o no.

Por favor, marque esta pseudocódigo para ver mi idea:

Two words are given: START and STOP. 
//List is our "way" from words START to STOP, so, we add the original word to it first. 
    list.add(START); 
//Finish to change the word when START equals STOP. 
    while(!START.equals(STOP)) 
//Change each letter at START to the letter to STOP one by one and check if such word exists. 
    for (int i = 0, i<STOP.length, i++){ 
     char temp = START[i]; 
     START[i] = STOP[i]; 
//If the word exists add a new word to the list of results. 
//And change another letter in the new word with the next pass of the loop. 
     if dictionary.contains(START) 
      list.add(START) 
//If the word doesn't exist, leave it like it was and try to change another letter with the next pass of the loop. 
     else START[i] = temp;} 
    return list; 

Según entiendo mi código debería funcionar así:

entrada: húmedas como en

salida: AMPOLLA, LÁMPARA, LIMP, LIMA, COMO

entrada: BACK, Pick

salida: DE NUEVO, PAQUETE, Pick