Leerzeichen zwischen Wörtern in raumlosen Zeichenfolgen hinzufügen

Question

Ich bin auf OS X, und in Objective-C versuche ich zu konvertieren

zum Beispiel, "Bobateagreenapple"

in "Bob hat einen grünen Apfel gegessen"

Gibt es eine Möglichkeit, dies effizient zu tun? Würde etwas mit einer Rechtschreibprüfung funktionieren?

EDIT: Nur einige zusätzliche Informationen: Ich versuche, etwas zu erstellen, das falsch formatierten Text verarbeitet (z. B. Text, der aus alten PDFs kopiert wurde, die ohne Leerzeichen enden, insbesondere aus Internetarchiven wie JSTOR). Da der falsch formatierte Text wahrscheinlich lang sein wird... nun, ich versuche nur herauszufinden, ob dies machbar ist, bevor ich tatsächlich versuche, ein System zu schreiben, nur um herauszufinden, dass es 2 Stunden dauert, einen Textabsatz zu korrigieren.

Answer 1

Eine Möglichkeit, die ich in einer nicht-OS-spezifischen Weise beschreiben werde, besteht darin, alle möglichen Wörter zu durchsuchen, aus denen sich die Buchstabensammlung zusammensetzt.

Im Grunde genommen schneiden Sie den ersten Buchstaben Ihrer Buchstabensammlung ab und fügen ihn dem aktuellen Wort hinzu, das Sie gerade bilden. Wenn es ein Wort ergibt (z. B. nachschlagen im Wörterbuch), fügen Sie es dem aktuellen Satz hinzu. Wenn du es schaffst, alle Buchstaben in deiner Sammlung zu verbrauchen und aus allen ein Wort zu bilden, hast du einen vollständigen Satz. Aber Sie müssen hier nicht aufhören. Stattdessen machen Sie weiter, und schließlich werden Sie alle möglichen Sätze bilden.

Ein Pseudocode würde etwa so aussehen:

FindWords(vector<Sentence> sentences, Sentence s, Word w, Letters l)
{
    if (l.empty() and w.empty())
        add s to sentences;
        return;
    if (l.empty())
        return;
    add first letter from l to w;
    if w in dictionary
    {
        add w to s;
        FindWords(sentences, s, empty word, l)
        remove w from s
    }
    FindWords(sentences, s, w, l)
    put last letter from w back onto l
}

Es gibt natürlich eine Reihe von Optimierungen, die Sie vornehmen können, um das Programm zu beschleunigen. Zum Beispiel könnte man prüfen, ob das Wort der Stamm eines beliebigen Wortes im Wörterbuch ist. Aber dies ist der grundlegende Ansatz, der Ihnen alle möglichen Sätze liefert.

Answer 2

Die Lösung dieses Problems ist viel schwieriger als alles, was Sie in einem Framework finden werden. Beachten Sie, dass es auch in Ihrem Beispiel andere "Lösungen" gibt: Zum Beispiel "Bob ein grüner Tee-Apfel".

Eine sehr naive (und nicht sehr funktionale) Herangehensweise wäre es, mit einer Rechtschreibprüfung zu versuchen, jeweils ein "richtiges Wort" in der Zeichenkette zu isolieren; in diesem Beispiel würde das natürlich nur funktionieren, weil "Bob" zufällig ein englisches Wort ist.

Das soll nicht heißen, dass es keine Möglichkeit gibt, das zu erreichen, was Sie wollen, aber die Art und Weise, wie Sie diese Frage formulieren, deutet für mich darauf hin, dass es viel komplizierter sein könnte, als Sie es sich vorstellen. Vielleicht kann Ihnen jemand eine annehmbare Lösung anbieten, aber ich wette, derjenige müsste viel mehr darüber wissen, was genau Sie zu tun versuchen.

Edit: als Antwort auf Ihren Edit, es würde wahrscheinlich weniger Aufwand bedeuten, eine Art OCR-Tool auf einem PDF laufen zu lassen und dessen Ausgabe zu korrigieren, als das zu korrigieren, was dieses System ausgibt, geschweige denn es zu programmieren

Answer 3

Ich habe eine Lösung implementiert, der Code ist im Code-Projekt verfügbar:

http://www.codeproject.com/Tips/704003/How-to-add-spaces-between-spaceless-strings

Meine Idee war es, die Ergebnisse zu bevorzugen, die die meisten Zeichen verwenden (am besten alle), und dann die mit den längsten Wörtern zu bevorzugen, da lange Wörter mit 2, 3 oder 4 Zeichen oft zufällig aus ausgelassenen Zeichen entstehen können. In den meisten Fällen führt dies zur richtigen Lösung.

Um alle möglichen Permutationen zu finden, habe ich die Rekursion benutzt. Der Code ist auch bei großen Wörterbüchern recht schnell (getestet mit 50 000 Wörtern).