String Find/Replace Algorithm

Question

Me gustaría poder buscar una cadena de varias palabras, cuando encuentre una, quiero dividir la cadena en ese punto en 3 partes (izquierda, coincidencia, derecha), el texto coincidente sería excluido, y el proceso continuaría con la nueva cadena izquierda + derecha.

Ahora, una vez que tengo todas las coincidencias hechas, necesito revertir el proceso reinsertando las palabras coincidentes (o un reemplazo para ellas) en el punto en que fueron eliminadas. Nunca he encontrado lo que quería en ninguna de mis búsquedas, así que pensé que pediría su opinión aquí en SO.

Háganme saber si esta pregunta necesita una descripción más detallada.

BTW - por el momento, tengo un algoritmo muy pobre que reemplaza el texto coincidente con un token de cadena único, y luego reemplaza los tokens con el texto de reemplazo para la coincidencia adecuada después de que se hayan hecho todas las coincidencias.

Este es el objetivo:

one two three four five six 

partido "tres" reemplazar con foo (recuerda que encontramos tres, y donde lo encontramos)

one two four five six 
     | 
    three 

partido "dos por cuatro" y evitar que se de ser igualada por cualquier cosa (editado para mayor claridad)

one five six 
    | 
two four 
     | 
    three 

en este punto, no se puede igualar por ejemplo "en la e dos"

todos los partidos se han encontrado, ahora ponen sus reemplazos de vuelta en (en orden inverso)

one two four five six 
     | 
    three 


one two foo four five six 

Cuál es el punto? Evitar que el texto de reemplazo de un partido coincida con otro patrón. (todos los patrones se ejecutan al mismo tiempo y en el mismo orden para cada cadena que se procesa)

No estoy seguro de que el idioma sea importante, pero estoy usando Lua en este caso.

Voy a tratar de reformular, tengo una lista de patrones que quiero encontrar en una cadena dada, si encuentro una, quiero eliminar esa parte de la cadena para que no coincida con ninguna otra cosa, pero quiero para realizar un seguimiento de dónde lo he encontrado para que pueda insertar el texto de reemplazo allí una vez he terminado de tratar de igualar mi lista de patrones

Aquí hay una pregunta relacionada:

Shell script - search and replace text in multiple files using a list of strings

Answer 1

La descripción del algoritmo no está clara. No existe una regla exacta donde los tokens extraídos se deben volver a insertar.

He aquí un ejemplo:

1. Find 'tres' en 'uno, dos, tres, cuatro, cinco y seis'

2. elegir uno de estos dos para conseguir 'foo bar' como resultado:

   una . reemplace 'uno dos' por 'foo' y 'cuatro cinco seis' por 'barra'

   b. sustituir 'uno, dos, cuatro, cinco, seis' con 'foo bar'

3. Insertar 'tres' de nuevo en la cadena 'foo bar' paso 2 resultante

En el paso 3 hace 'tres' va delante ' bar 'o después?

Una vez que haya encontrado reglas claras para reinsertar, puede implementar fácilmente el algoritmo como un método recursivo o como un método iterativo con una pila de reemplazos.

Answer 2

dada la estructura de la problema, probablemente probaría un algoritmo basado en un árbol binario.

Answer 3

pseudocódigo:

for(String snippet in snippets) 
{ 
    int location = indexOf(snippet,inputData); 
    if(location != -1) 
    { 
     // store replacement text for a found snippet on a stack along with the 
     // location where it was found 
     lengthChange = getReplacementFor(snippet).length - snippet.length; 
     for each replacement in foundStack 
     { 
      // IF the location part of the pair is greater than the location just found 
      //Increment the location part of the pair by the lengthChange to account 
      // for the fact that when you replace a string with a new one the location 
      // of all subsequent strings will be shifted 
     } 

     //remove snippet 
     inputData.replace(snippet, ""); 
    } 
} 

for(pair in foundStack) 
{ 
    inputData.insert(pair.text, pair.location); 
} 

Esto es, básicamente, sólo haciendo exactamente lo que dijo en su descripción del problema. Paso a paso por el algoritmo, colocando todo en una pila con la ubicación en la que se encontró. Usas una pila así que cuando reinsertes en la segunda mitad, ocurre en orden inverso de modo que la "ubicación" almacenada se aplica al estado actual de la cadena de entrada.

Editado con una solución potencial para la crítica del comentarista.¿El comentario sobre el bloqueo dentro del primero explica sus críticas, o sigue fallando en ciertos escenarios?

Answer 4

Lo que quiere hacer es tener una 2da secuencia que almacena la salida . Procesa la entrada y busca patrones en ella. Si no se encuentra el patrón coincidente, no se produce ningún reemplazo, por lo que solo debe agregar los caracteres que leyó directamente a la salida . Si se encuentra un patrón , agregue la cadena de reemplazo a la salida . Como siempre avanzas en la cuerda, no hay posibilidad de que un patrón coincida con un reemplazo anterior.

Si está buscando carácter por carácter (búsqueda de fuerza bruta), tendrá que averiguar cómo quiere priorizar los patrones; por longitud o por orden, se agregaron a la lista de patrones.

De lo contrario, estará buscando palabra por palabra o frase por frase que se generaliza en la búsqueda utilizando un búfer. Para eso tendrás que determinar los separadores (para las palabras será espacios, para las oraciones será puntos de exclamación de períodos y otras cosas así, para un archivo de valores separados por comas serán comas).