Algorithme de recherche/remplacement de chaînes de caractères

Question

J'aimerais pouvoir rechercher différents mots dans une chaîne de caractères. Lorsque j'en trouve un, je veux diviser la chaîne de caractères à ce moment-là en 3 parties (gauche, correspondance, droite), le texte correspondant serait exclu, et le processus continuerait avec la nouvelle chaîne de caractères gauche+droite.

Maintenant, une fois que j'ai fait toutes mes correspondances, je dois inverser le processus en réinsérant les mots correspondants (ou un remplacement pour eux) à l'endroit où ils ont été retirés. Je n'ai jamais vraiment trouvé ce que je voulais dans aucune de mes recherches, alors j'ai pensé que je demanderais une contribution ici sur SO.

Veuillez me faire savoir si cette question nécessite une description plus approfondie.

BTW - pour le moment, j'ai un algorithme très pauvre qui remplace le texte correspondant par une chaîne de caractères unique, puis remplace les chaînes de caractères par le texte de remplacement pour la correspondance appropriée après que toutes les correspondances ont été faites.

C'est l'objectif :

one two three four five six 

match "three" replace with foo (rappelez-vous que nous avons trouvé trois, et où nous l'avons trouvé)

one two four five six
       |
     three

correspond à "deux quatre" et l'empêche d'être égalé par quoi que ce soit (édité pour plus de clarté)

one five six
   |
 two four 
       |
     three

à ce stade, vous ne pouvez pas correspondre par exemple à "un deux".

toutes les correspondances ont été trouvées, remettez maintenant leurs remplaçants (dans l'ordre inverse)

one two four five six
       |
     three

one two foo four five six

Quel est l'intérêt ? Empêcher le texte de remplacement d'une correspondance d'être apparié par un autre motif. (tous les motifs 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 le langage importe, mais j'utilise Lua dans ce cas.

Je vais essayer de reformuler : j'ai une liste de motifs que je veux trouver dans une chaîne de caractères donnée, si j'en trouve un, je veux supprimer cette partie de la chaîne de caractères pour qu'elle ne corresponde à rien d'autre, mais je veux garder la trace de l'endroit où je l'ai trouvé pour pouvoir y insérer le texte de remplacement une fois que j'ai fini d'essayer de faire correspondre ma liste de motifs.

Voici une question connexe :

Shell script - recherche et remplacement de texte dans plusieurs fichiers à l'aide d'une liste de chaînes de caractères.

Answer 1

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

Voici un exemple :

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

2. Choisissez l'un des deux pour obtenir 'foo bar' comme résultat :

   a. remplacez "un deux" par "foo" et "quatre cinq six" par "bar".

   b. remplacer "un deux quatre cinq six" par "foo bar".

3. Insérez 'trois' dans la chaîne 'foo bar' de l'étape 2.

À l'étape 3, le mot "trois" est-il placé avant ou après le mot "barre" ?

Une fois que vous avez défini des règles claires pour la réinsertion, vous pouvez facilement implémenter l'algorithme comme une méthode récursive ou comme une méthode itérative avec une pile de remplacements.

Answer 2

Étant donné 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);
}

Il s'agit en fait de faire exactement ce que vous avez dit dans la description de votre problème. Passez par 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 deuxième moitié, cela se produit dans l'ordre inverse de sorte que l'"emplacement" stocké s'applique à l'état actuel de l'inputString.

Modifié avec une correction potentielle pour la critique du commentateur. Est-ce que le bloc commenté dans le premier tient compte de vos critiques, ou est-ce qu'il est encore bogué dans certains scénarios ?

Answer 4

Ce que vous voulez faire, c'est avoir une deuxième chaîne de caractères qui stocke le nom de l'utilisateur. sortie . Vous traitez le entrée et chercher motifs en elle. Si aucune correspondance motif n'est pas trouvé, aucun remplacement n'a lieu et il suffit d'ajouter les caractères lus directement dans le fichier sortie . Si un motif est trouvé, ajoutez le remplacement à la chaîne 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 effectuez une recherche caractère par caractère (recherche par force brute), vous devrez déterminer comment classer les motifs par ordre de priorité : par longueur ou par ordre d'ajout à la liste des motifs.

Sinon, vous devrez faire une recherche mot par mot ou phrase par phrase, ce qui revient à faire une recherche en utilisant un tampon. Pour cela, vous devrez déterminer les séparateurs (pour les mots, ce seront des espaces, pour les phrases, des points d'exclamation et d'autres choses de ce genre, pour un fichier de valeurs séparées par des virgules, ce seront des virgules).