String Find/Replace Algorithm

Question

Je voudrais être capable de rechercher une chaîne pour différents mots, quand j'en trouve un, je veux diviser la chaîne à ce point en 3 parties (gauche, match, droite), le texte correspondant serait exclu, et le processus continuerait avec la nouvelle chaîne gauche + droite.

Maintenant, une fois toutes mes correspondances effectuées, je dois inverser le processus en réinsérant les mots correspondants (ou en les remplaçant) au moment où ils ont été supprimés. Je n'ai jamais vraiment trouvé ce que je voulais dans mes recherches, alors j'ai pensé que je demanderais une contribution ici sur SO.

Faites-moi savoir si cette question nécessite une description plus détaillée.

BTW - pour l'instant, j'ai un très mauvais algorithme qui remplace le texte correspondant par un jeton de chaîne unique, puis remplace les jetons par le texte de remplacement pour la correspondance appropriée après que toutes les correspondances ont été faites.

Tel est l'objectif:

one two three four five six 

match de "trois" remplacer par foo (rappelez-vous, nous avons trouvé trois, et où nous l'avons trouvé)

one two four five six 
     | 
    three 

match de "deux quatre" et l'empêcher d'être apparié par quoi que ce soit (édité pour la clarté)

one five six 
    | 
two four 
     | 
    three 

à ce stade, vous ne pouvez pas correspondre par exemple "sur e deux »

tous les matchs ont été trouvés, maintenant mis leurs remplaçants en retour (dans l'ordre inverse)

one two four five six 
     | 
    three 


one two foo four five six 

Quel est le point? Empêcher le remplacement du texte d'un match par un autre motif. (tous les modèles sont exécutés en même temps et dans le même ordre pour chaque chaîne traitée)

Je ne suis pas sûr que la langue compte, mais j'utilise Lua dans ce cas. Je vais essayer de reformuler, j'ai une liste de modèles que je veux trouver dans une chaîne donnée, si j'en trouve un, je veux enlever cette partie de la chaîne de sorte qu'il ne correspond pas à autre chose, mais je veux de garder une trace de l'endroit où je l'ai trouvé pour que je puisse insérer le texte de remplacement il une fois que je suis fait essayer de faire correspondre ma liste des modèles

Voici une question connexe:

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

Answer 1

La description de votre algorithme n'est pas claire. Il n'y a pas de règle exacte où les jetons extraits doivent être réinsérés.

Voici un exemple:

1. Find 'trois' dans 'un deux trois quatre cinq six'

2. Choisissez l'une de ces deux pour obtenir 'foo bar' comme résultat:

   une . remplacer «un deux» par «foo» et «quatre cinq six» par «barre»

   b. remplacer « un deux quatre cinq six » avec « foo bar »

3. Insérer « trois » arrière dans l'étape 2 chaîne résultante « foo bar »

A l'étape 3 ne « trois » va avant ' bar »ou après? Une fois que vous avez défini des règles claires pour la réinsertion, vous pouvez facilement implémenter l'algorithme en tant que méthode récursive ou en tant que méthode itérative avec une pile de remplacement.

Answer 2

Compte tenu de la structure du problème, j'essaierais probablement un algorithme basé sur un arbre binaire.

Answer 3

pseudocode:

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); 
} 

Ceci est fondamentalement juste fait exactement comme vous l'avez dit dans votre description du problème. Étape par étape de l'algorithme, en mettant tout sur une pile avec l'emplacement où il a été trouvé. Vous utilisez une pile de sorte que lorsque vous réinsérez dans la seconde moitié, cela se passe dans l'ordre inverse, de sorte que la "position" stockée s'applique à l'état actuel de la chaîne inputString.

Edité avec un correctif potentiel pour la critique des commentateurs.Est-ce que le commentaire pour bloquer dans le premier compte pour vos critiques, ou est-ce encore bogué dans certains scénarios?

Answer 4

Ce que vous voulez faire est d'avoir une deuxième chaîne qui stocke la sortie . Vous traitez l'entrée et recherchez modèles dedans. Si aucun motif correspondant n'est trouvé, aucun remplacement ne se produit, vous ajoutez simplement les caractères que vous avez lus directement à la sortie . Si un modèle est trouvé, ajoutez la chaîne de remplacement à la sortie . Comme vous avancez toujours dans la chaîne, il n'y a aucune chance qu'un motif corresponde à un remplacement précédent.

Si vous recherchez un caractère par caractère (recherche par force brute), vous devrez déterminer comment vous souhaitez hiérarchiser les motifs; par longueur ou par ordre, ils ont été ajoutés à la liste des motifs. Dans le cas contraire, vous effectuerez une recherche mot par mot ou phrase par phrase qui généralisera la recherche à l'aide d'un tampon. Pour cela vous devrez déterminer les séparateurs (pour les mots ce sera des espaces, pour les phrases ce seront des points d'exclamation et d'autres choses comme ça, pour un fichier de valeurs séparées par des virgules, ce sera une virgule).