So teilen Sie eine Zeichenfolge in Wörter. Ex: "Stringintowords" -> "String in Worte"?

Question

Was ist der richtige Weg, um eine Zeichenfolge in Wörter zu teilen? (string enthält keine Leerzeichen oder Satzzeichen)

Zum Beispiel: „stringintowords“ -> „String in Wörter“

Könnten Sie bitte beraten, welche Algorithmus sollte hier verwendet werden?

! Update: Für diejenigen, die denken, diese Frage ist nur aus Neugier. Dieser Algorithmus könnte verwendet werden, um Domainnamen ("sportandfishing .com" -> "SportAndFishing .com") zu camelieren, und dieser Algo wird derzeit von aboutus dot org verwendet, um diese Umwandlung dynamisch durchzuführen.

Answer 1

Wie von vielen hier erwähnt, handelt es sich hier um ein normales, leicht dynamisches Programmierproblem: Die beste Lösung bietet Falk Hüffner.Zusätzliche Informationen jedoch:

(a) sollten Sie die Implementierung isWord mit einem Trie, die Sie viel Zeit sparen, wenn Sie richtig verwenden (das heißt durch inkrementelle Tests für Wörter) prüfen.

(b) Eingabe "Segmentierung dynamische Programmierung" ergibt eine Punktzahl von mehr Details Antworten, von der Universität Vorträge mit Pseudo-Code-Algorithmus, wie this lecture at Duke's (die sogar so weit gehen, um einen einfachen probabilistischen Ansatz zu behandeln was zu tun ist, wenn Sie Wörter haben, die in keinem Wörterbuch enthalten sind).

Answer 2

Am besten wäre es, einen Teilstring von 0 mit einem Wörterbuch zu vergleichen, und wenn Sie eine Übereinstimmung gefunden haben, dieses Wort zu extrahieren und eine neue Wörterbuchsuche zu beginnen ... aber es wird sehr fehleranfällig sein, und Sie werden Probleme mit Plural und Apostrophe (Senken, Sinks) und anderen Wortarten haben.

EDIT

würde "singleemotion" werden "Single Emotion" oder "Sünde Freude Bewegung"?

Answer 3

Die einzige Möglichkeit, diese Zeichenfolge in Wörter aufzuteilen, ist die Verwendung eines Wörterbuchs. Obwohl dies wahrscheinlich sehr ressourcenintensiv wäre.

Answer 4

Dies ist im Grunde eine Variation von knapsack problem, also was Sie brauchen, ist eine umfassende Liste von Wörtern und einer der Lösungen in Wiki abgedeckt.

Mit ziemlich großen Wörterbuch wird dies wahnsinnig ressourcenintensive und langwierige Operation sein, und Sie können nicht einmal sicher sein, dass dieses Problem gelöst wird.

Answer 5

Erstellen Sie eine Liste möglicher Wörter, sortieren Sie sie aus langen Wörtern in kurze Wörter.

Überprüfen Sie, ob jeder Eintrag in der Liste mit dem ersten Teil der Zeichenfolge übereinstimmt. Wenn es gleich ist, entferne dies und füge es an deinen Satz mit einem Leerzeichen an. Wiederholen Sie dies.

Answer 6

Wenn Sie sicherstellen möchten, dass Sie das richtig machen, haben Sie , um einen Wörterbuch-basierten Ansatz zu verwenden, und es wird horrend ineffizient sein. Sie müssen auch erwarten, mehrere Ergebnisse von Ihrem Algorithmus zu erhalten.

Zum Beispiel: windowsteamblog (von http://windowsteamblog.com/ Ruhm)

• windowsteamblog
• windowsteamblog

Answer 7

Es soll auf diese ein gutes Stück in der wissenschaftlichen Literatur sein. Die Schlüsselwörter, nach denen Sie suchen möchten, sind word segmentation. This paper sieht zum Beispiel vielversprechend aus.

In der Regel möchten Sie wahrscheinlich über markov models und die viterbi algorithm lernen. Letzteres ist ein dynamischer Programmieralgorithmus, der es Ihnen ermöglicht, plausible Segmentierungen für einen String zu finden, ohne jede mögliche Segmentierung erschöpfend zu testen.Die wesentliche Erkenntnis hier ist, dass, wenn Sie für die ersten m Zeichen n mögliche Segmentierungen haben und Sie nur die wahrscheinlichste Segmentierung finden möchten, müssen Sie nicht jedes einzelne dieser Zeichen für nachfolgende Zeichen auswerten - Sie müssen nur weiter bewerten der wahrscheinlichste.

Answer 8

Nehmen wir an, Sie haben eine Funktion isWord(w), die überprüft, ob w ein Wort ist, das ein Wörterbuch verwendet. Lassen Sie uns der Einfachheit halber auch davon ausgehen, dass Sie nur wissen wollen, ob für ein Wort w eine solche Aufteilung möglich ist. Dies kann leicht mit dynamischer Programmierung erfolgen.

Lassen Sie S[1..length(w)] eine Tabelle mit booleschen Einträgen sein. S[i] ist wahr, wenn das Wort w[1..i] geteilt werden kann. Dann setzte S[1] = isWord(w[1]) und for i=2 berechnen length(w)

S [i] = (isWord [w [1..i] oder für jeden j in {2..i}: S [j-1] und isWord [j. .ich]).

Dies dauert O (Länge (w)^2) Zeit, wenn Dictionary-Abfragen konstante Zeit sind. Um die Aufspaltung tatsächlich zu finden, speichern Sie einfach die Gewinnaufteilung in jedem S [i], das auf "Wahr" gesetzt ist. Dies kann auch angepasst werden, um alle Lösungen aufzuzählen, indem alle derartigen Aufteilungen gespeichert werden.

Answer 9

Betrachten Sie die schiere Anzahl der möglichen Aufteilungen für eine gegebene Zeichenfolge. Wenn Sie n Zeichen in der Zeichenfolge haben, gibt es n-1 mögliche Orte zu teilen. Zum Beispiel für die Zeichenfolge cat, können Sie vor der a teilen und Sie können vor der t teilen. Dies führt zu 4 möglichen Aufspaltungen.

Sie könnten dieses Problem als auswählen, wo Sie die Zeichenfolge teilen müssen. Sie müssen auch auswählen, wie viele Splits es geben wird. So gibt es Sum(i = 0 to n - 1, n - 1 choose i) mögliche Aufspaltungen. Durch die Binomial Coefficient Theorem, wobei x und y beide 1 sind, ist dies gleich pow (2, n-1).

Zugegeben, viele dieser Berechnungen basieren auf allgemeinen Teilproblemen, daher könnte Dynamic Programming Ihren Algorithmus beschleunigen. Von der Spitze meines Kopfes würde die Berechnung einer boolean matrix M such M[i,j] is true if and only if the substring of your given string from i to j is a word ziemlich viel helfen. Sie haben immer noch eine exponentielle Anzahl möglicher Segmentierungen, aber Sie könnten schnell eine Segmentierung eliminieren, wenn ein früher Split kein Wort gebildet hätte. Eine Lösung wäre dann eine Folge von ganzen Zahlen (i0, j0, i1, j1, ...) mit der Bedingung j sub k = i sub (k + 1).

Wenn Ihr Ziel korrekt Camel Case URLs ist, würde ich das Problem umgehen und für etwas direkteres gehen: Holen Sie sich die Homepage für die URL, entfernen Sie Leerzeichen und Groß- und Kleinschreibung aus dem Quell-HTML und suchen Sie nach Ihrer Zeichenfolge. Wenn es eine Übereinstimmung gibt, suchen Sie diesen Abschnitt im ursprünglichen HTML-Code und geben Sie ihn zurück. Sie würden eine Reihe von NumSpaces benötigen, das erklärt, wie viel Leerzeichen in der ursprünglichen Zeichenfolge auftritt wie so:

Needle:  isashort  
Haystack:  This is a short phrase  
Preprocessed: thisisashortphrase 
NumSpaces : 000011233333444444 

Und Ihre Antwort würde aus:

location = prepocessed.Search(Needle) 
locationInOriginal = location + NumSpaces[location] 
originalLength = Needle.length() + NumSpaces[location + needle.length()] - NumSpaces[location] 
Haystack.substring(locationInOriginal, originalLength) 

Natürlich würde dies brechen, wenn madduckets .com hatte keine "Mad Duckets" irgendwo auf der Homepage. Ach, das ist der Preis, den Sie zahlen, um ein exponentielles Problem zu vermeiden.

Answer 10

Dies kann tatsächlich (bis zu einem gewissen Grad) ohne Wörterbuch getan werden. Im Wesentlichen ist dies ein unüberwachtes Wortsegmentierungsproblem. Sie müssen eine große Liste von Domänennamen sammeln, einen unüberwachten Segmentierungslernalgorithmus (z. B.) anwenden und das erlernte Modell auf neue Domänennamen anwenden. Ich bin mir nicht sicher, wie gut es funktionieren würde (aber es wäre interessant).

Answer 11

Ich schaute auf das Problem und dachte vielleicht könnte ich teilen, wie ich es gemacht habe. Es ist ein wenig zu hart, um mein Algorithmus in Worten zu erklären, so könnte ich vielleicht meine optimierte Lösung in Pseudo-Code teilen:

string mainword = "stringintowords"; 
array substrings = get_all_substrings(mainword); 

/** this way, one does not check the dictionary to check for word validity 
* on every substring; It would only be queried once and for all, 
* eliminating multiple travels to the data storage 
*/ 
string query = "select word from dictionary where word in " + substrings; 
array validwords = execute(query).getArray(); 

validwords = validwords.sort(length, desc); 

array segments = []; 
while(mainword != ""){ 
    for(x = 0; x < validwords.length; x++){ 
     if(mainword.startswith(validwords[x])) { 
      segments.push(validwords[x]); 
      mainword = mainword.remove(v); 
      x = 0; 
     } 
    } 

    /** 
    * remove the first character if any of valid words do not match, then start again 
    * you may need to add the first character to the result if you want to 
    */ 
    mainword = mainword.substring(1); 
} 

string result = segments.join(" "); 

Answer 12

Eigentlich mit dem Wörterbuch dieses Problem in O(n) Zeit gelöst werden kann. Genauer gesagt in (k + 1) * n im schlimmsten Fall, wobei n die Anzahl der Zeichen in der Zeichenfolge und k die Länge des längsten Wortes im Wörterbuch ist.

Außerdem ermöglicht der Algorithmus Ihnen, Junk zu überspringen.

Hier ist die Arbeits Umsetzung in Common Lisp ich vor einiger Zeit erstellt haben: https://gist.github.com/3381522

Answer 13

Eine einfache Java-Lösung, die O (n^2) Laufzeit hat.

public class Solution { 
    // should contain the list of all words, or you can use any other data structure (e.g. a Trie) 
    private HashSet<String> dictionary; 

    public String parse(String s) { 
     return parse(s, new HashMap<String, String>()); 
    } 

    public String parse(String s, HashMap<String, String> map) { 
     if (map.containsKey(s)) { 
      return map.get(s); 
     } 
     if (dictionary.contains(s)) { 
      return s; 
     } 
     for (int left = 1; left < s.length(); left++) { 
      String leftSub = s.substring(0, left); 
      if (!dictionary.contains(leftSub)) { 
       continue; 
      } 
      String rightSub = s.substring(left); 
      String rightParsed = parse(rightSub, map); 
      if (rightParsed != null) { 
       String parsed = leftSub + " " + rightParsed; 
       map.put(s, parsed); 
       return parsed; 
      } 
     } 
     map.put(s, null); 
     return null; 
    } 
}