Zerlegt eine Zeichenkette in Wörter

Ich bin auf der Suche nach der effizienteste Algorithmus bilden alle möglichen Kombinationen der Wörter aus einem string. Zum Beispiel:

Input String: forevercarrot

Output:

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

(Alle Wörter aus einem Wörterbuch).

Ich denken kann ein brute-force-Ansatz. (finden alle möglichen Teilstrings und match), aber was wäre besser Möglichkeiten?

Ihre brute-force-Ansatz ist richtig. Stellen Sie sich vor Sie gegeben wurden das gleiche problem, außer für die Anfrage für Worte in einer fremden Sprache.

InformationsquelleAutor | 2011-01-21

6

Verwenden Präfix-Baum für die Liste der bekannten Wörter. Wahrscheinlich libs wie myspell dies bereits tun. Versuchen Sie, eine ready-made-man.

Sobald Sie eine übereinstimmung gefunden (z.B. "Auto"), teilen Ihre Berechnung: ein Zweig beginnt zu schauen, für ein neues Wort ('rot'), anderen weiter zu erforschen Varianten der aktuellen Anfang ('Zuckerbrot').

Effektiv pflegen Sie eine queue von Paaren (start_position, current_position) von offsets in den string jedes mal, wenn Sie teilen Sie die Berechnung. Mehrere threads können pop aus dieser Warteschlange parallel und versuchen Sie weiterhin ein Wort, das beginnt start_position und ist schon bekannt bis zu current_position des Paares, aber nicht zu Ende. Wenn ein Wort gefunden ist, wird es gemeldet und ein weiteres paar aufgetaucht, aus der Warteschlange. Wenn es nicht möglich ist, wird kein Ergebnis erzeugt. Wenn ein split geschieht, ein paar neue Hinzugefügt, um das Ende der Warteschlange. Zunächst die Warteschlange enthält ein (0,0).
- Plus stellen Sie sicher, dass Sie nicht wiederholen Sie die Berechnung der Zwischenzeiten der 'Karotte' zweimal - einmal für 'forever' und einmal für 'für immer'. Cache teilweise resuts: Set(mögliche splits) für jedes [i..n].
InformationsquelleAutor 9000
1

Sehen, diese Frage, die hat auch bessere Antworten. Es ist ein standard, der dynamische Programmierung problem:

Wie teilt eine Zeichenkette in Wörter. Ex: "stringintowords" -> "String In Worten"?

InformationsquelleAutor Martin Konicek
0

Einen psuedocode Umsetzung, ausnutzen der Tatsache, dass jeder Teil des Strings muss ein Wort sein, wir können nicht überspringen Sie nichts. Wir arbeiten uns aus dem Anfang der Zeichenfolge, bis das erste bit ist ein Wort, und erzeugen dann alle möglichen Kombinationen der rest der Zeichenkette. Sobald wir dies getan haben, können wir weiter entlang, bis wir finden andere Möglichkeiten für das erste Wort, und so weiter.
```
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    
}
```
Den Popanz in diesem code ist, dass Sie am Ende werde sich wiederholende Berechnungen - in deinem Beispiel werden Sie am Ende mit zu berechnen allPossibleWords("carrot") zweimal - einmal in ["forever", allPossibleWords["carrot"]] und einmal in ["for", "ever", allPossibleWords["carrot"]]. So memoizing das ist etwas zu prüfen.

InformationsquelleAutor Anon.

Input String: forevercarrot

Ausgabe:

ewig Karotte
für immer Auto rot
für immer Karotte
für immer Auto rot

Programm :

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

InformationsquelleAutor sssss

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.