Scinde une chaîne en mots

Je suis à la recherche d'algorithme efficace pour former toutes les combinaisons possibles de mots à partir d'une chaîne. Par exemple:

Input String: forevercarrot

Output:

forever carrot
forever car rot
for ever carrot
for ever car rot

(Tous les mots doivent être à partir d'un dictionnaire).

Je pense à une approche par force brute. (trouver tous les possible de sous-chaînes et match), mais ce serait mieux?

Votre force brute est une bonne solution. Imaginez-vous ont eu le même problème, sauf pour la demande de mots dans une langue étrangère.

OriginalL'auteur | 2011-01-21

6

Utiliser un préfixe de l'arbre pour votre liste de mots connus. Probablement libs comme myspell déjà le faire. Essayez d'utiliser un prêt-à-un.

Une fois que vous avez trouvé un match (par exemple "voiture"), diviser votre calcul: on branche commence à regarder pour un nouveau mot ('pourrir'), l'autre continue à explorer des variantes de courant début ("carotte").

Efficacement gérer une file d'attente de paires (start_position, current_position) de décalages dans votre chaîne chaque fois que vous divisez le calcul. Plusieurs threads peuvent pop de cette file d'attente en parallèle et essayer de continuer un mot qui commence à partir de start_position et est déjà connu jusqu'à current_position de la paire, mais ne s'arrête pas là. Lorsqu'un mot est trouvé, il est signalé et l'autre paire est sortie de la file d'attente. Lorsque c'est impossible, aucun résultat n'est généré. Lorsqu'une scission se produit, une nouvelle paire est ajouté à la fin de la file d'attente. Initialement, la file d'attente contient un (0,0).

Plus assurez-vous de ne pas répéter le calcul des fractionnements de "carotte" deux fois - une fois pour "forever" et une fois pour les "pour toujours". Cache partielle résultat: Set(possible splits) pour chaque [i..n].

OriginalL'auteur 9000
1

Le voir, cette question qui a même avoir de meilleures réponses. C'est un standard de programmation dynamique problème:

Comment découper une chaîne en mots. Ex: "stringintowords" -> "Chaîne des Mots"?

OriginalL'auteur Martin Konicek
0

Un psuedocode mise en œuvre, en exploitant le fait que chaque partie de la chaîne doit être un mot, nous ne pouvons pas sauter quoi que ce soit. Nous travaillons en avant depuis le début de la chaîne jusqu'à ce que le premier bit est un mot, puis de générer toutes les combinaisons possibles du reste de la chaîne. Une fois que nous l'avons fait, nous continuons le long jusqu'à ce que nous trouver d'autres possibilités pour le premier mot, et ainsi de suite.
```
allPossibleWords(string s, int startPosition) {
    list ret
    for i in startPosition..s'length
        if isWord(s[startPosition, i])
            ret += s[startPostion, i] * allPossibleWords(s, i)
    return ret    
}
```
L'épouvantail dans ce code, c'est que vous aurez à répéter les calculs dans votre exemple, vous finirez par avoir à calculer allPossibleWords("carrot") deux fois - une fois dans ["forever", allPossibleWords["carrot"]] et une fois dans ["for", "ever", allPossibleWords["carrot"]]. Donc memoizing c'est quelque chose à considérer.

OriginalL'auteur Anon.

Chaîne d'entrée: forevercarrot

De sortie:

jamais carotte
jamais voiture de la pourriture
pour jamais de la carotte
pour voiture jamais pourriture

programme :

#include<iostream>
#include<string>
#include<vector>
#include<string.h>
void strsplit(std::string str)
{
   int len=0,i,x,y,j,k;
   len = str.size();
   std::string s1,s2,s3,s4,s5,s6,s7;
   char *c = new char[len+1]();
   char *b = new char[len+1]();
   char *d = new char[len+1]();
   for(i =0 ;i< len-1;i++)
   {
       std::cout<<"\n";
       for(j=0;j<=i;j++)
       {
          c[j] = str[j];
          b[j] = str[j];
          s3 += c[j];
          y = j+1;
       }
       for( int h=i+1;h<len;h++){
          s5 += str[h];
       }
       s6 = s3+" "+s5;
       std::cout<<" "<<s6<<"\n";
       s5 = "";
       for(k = y;k<len-1;k++)
       {
          d[k] = str[k];
          s1 += d[k];
          s1 +=  " ";
          for(int l = k+1;l<len;l++){
           b[l] = str[l];
           s2 += b[l];
         }
       s4 = s3+" "+s1+s2;
       s7 = s4;
       std::cout<<" "<<s4<<"\n";
       s3 = "";s4 = "";
       }
       s1 = "";s3 = "";
    }
}

int main(int argc, char* argv[])
{
    std::string str;
    if(argc < 2)
                std::cout<<"Usage: "<<argv[0]<<" <InputString> "<<"\n";
    else{
                str = argv[1];
                strsplit(str);
    }

return 0;
}

OriginalL'auteur sssss

Vous devez vous connecter pour publier un commentaire.