Was ist der effizienteste Weg, den Index eines bestimmten Zeichens in einer Zeichenfolge zu verfolgen?

Question

Nehmen Sie als Beispiel die folgende Zeichenfolge:

"Der schnelle braune Fuchs"

Im Moment befindet sich das q in „quick“ an Index 4 der Zeichenfolge (beginnend bei 0) und das „f“ in „fox“ an Index 16.Nehmen wir nun an, der Benutzer gibt etwas mehr Text in diese Zeichenfolge ein.

„Der sehr schnelle dunkelbraune Fuchs“

Jetzt liegt q bei Index 9 und f bei Index 26.

Was ist die effizienteste Methode, um den Index des Originals q in Quick und f in Fox zu verfolgen, unabhängig davon, wie viele Zeichen vom Benutzer hinzugefügt werden?

Sprache spielt für mich keine Rolle, das ist eher eine theoretische Frage als alles andere. Verwenden Sie also die Sprache, die Sie möchten, und versuchen Sie, sich auf allgemein beliebte und aktuelle Sprachen zu beschränken.

Die Beispielzeichenfolge, die ich angegeben habe, ist kurz, aber ich hoffe auf eine Möglichkeit, mit der Zeichenfolgen jeder Größe effizient verarbeitet werden können.Das Aktualisieren eines Arrays mit dem Offset würde also mit einer kurzen Zeichenfolge funktionieren, würde aber bei zu vielen Zeichen ins Stocken geraten.

Obwohl ich in dem Beispiel nach dem Index eindeutiger Zeichen in der Zeichenfolge gesucht habe, möchte ich auch in der Lage sein, den Index desselben Zeichens an verschiedenen Stellen zu verfolgen, z. B. das o in braun und das o in fox.Suchen kommt also nicht in Frage.

Ich hatte gehofft, dass die Antwort sowohl zeit- als auch speichereffizient wäre, aber wenn ich mich nur für eine entscheiden müsste, wäre mir die Leistungsgeschwindigkeit wichtiger.

Answer 1

Nehmen wir an, Sie haben eine Zeichenfolge und einige ihrer Buchstaben sind interessant.Der Einfachheit halber nehmen wir an, dass der Buchstabe bei Index 0 immer interessant ist und Sie nie etwas davor hinzufügen – einen Wächter.Notieren Sie Paare von (interessanter Buchstabe, Abstand zum vorherigen interessanten Buchstaben).Wenn die Zeichenfolge „+der sehr schnelle dunkelbraune Fuchs“ lautet und Sie an q von „quick“ und f von „fox“ interessiert sind, würden Sie schreiben:(+,0), (q,10), (f,17).(Das Zeichen + ist der Wächter.)

Nun fügen Sie diese in einen ausgeglichenen Binärbaum ein, dessen Durchlauf in der richtigen Reihenfolge die Reihenfolge der Buchstaben in der Reihenfolge ergibt, in der sie in der Zeichenfolge erscheinen.Vielleicht erkennen Sie jetzt das Partialsummenproblem:Sie erweitern den Baum so, dass die Knoten (Buchstaben, Abstand, Summe) enthalten.Die Summe ist die Summe aller Abstände im linken Teilbaum.(Deshalb ist Summe(x)=Abstand(links(x))+Summe(links(x)).)

Sie können diese Datenstruktur nun in logarithmischer Zeit abfragen und aktualisieren.

Um zu sagen, dass Sie hinzugefügt haben N Zeichen links vom Zeichen C Sie sagen „Abstand(c)+=n“ und aktualisieren dann die Summe für alle Eltern von C.

Zu fragen, was der Index ist C Sie berechnen sum(c)+sum(parent(c))+sum(parent(parent(c)))+...

Answer 2

Ihre Frage ist etwas zweideutig: Möchten Sie die ersten Vorkommen jedes Buchstabens im Auge behalten?In diesem Fall ist ein Array mit einer Länge von 26 möglicherweise die beste Option.

Wenn Sie Text an einer Stelle in eine Zeichenfolge einfügen, die niedriger als der Index ist, den Sie haben, berechnen Sie einfach den Versatz basierend auf der Länge der eingefügten Zeichenfolge.

Answer 3

Es wäre auch hilfreich, wenn Sie eine Zielsprache im Kopf hätten, da nicht alle Datenstrukturen und Interaktionen in allen Sprachen gleichermaßen effizient und effektiv sind.

Answer 4

Der Standardtrick, der in ähnlichen Situationen normalerweise hilft, besteht darin, die Zeichen der Zeichenfolge als Blätter in einem ausgeglichenen Binärbaum beizubehalten.Darüber hinaus sollten interne Knoten des Baums Buchstabensätze enthalten (wenn das Alphabet klein und fest ist, könnten es Bitmaps sein), die im Unterbaum vorkommen, der an einem bestimmten Knoten verwurzelt ist.

Das Einfügen oder Löschen eines Buchstabens in diese Struktur erfordert nur O(log(N))-Operationen (Aktualisieren der Bitmaps auf dem Pfad zum Stammverzeichnis) und das Finden des ersten Vorkommens eines Buchstabens erfordert auch O(log(N))-Operationen – Sie kommen von dieser Struktur ab die Wurzel, wobei das am weitesten links stehende untergeordnete Element ausgewählt wird, dessen Bitmap den interessanten Buchstaben enthält.

Bearbeiten:Die internen Knoten sollten auch die Anzahl der Blätter im dargestellten Teilbaum speichern, um den Index des Buchstabens effizient berechnen zu können.