Die meisten effizienten Datenstruktur zum hinzufügen von Stilen auf text
Ich bin auf der Suche nach der besten Datenstruktur fügen Sie Stile hinzu, um einen text (sagen wir in einem text-editor). Die Struktur sollte ermöglichen die folgenden Operationen:
- Schnellen nachschlagen aller Stilrichtungen, an absolute position X
- Schnelles einfügen von text an einer beliebigen position (Stile nach, die position verschoben werden muss).
- Jeder position des Textes muss die Unterstützung einer beliebigen Anzahl von Stilen (überlappung).
Habe ich mir überlegt Listen/arrays, die text enthalten, reicht aber nicht erlauben schnelles einfügen ohne Neuberechnung der Positionen aller Stilrichtungen nach der insert-Punkt.
Einer Baum-Struktur mit den relativen offsets unterstützt die #2, aber der Baum entarten schnell, wenn ich viele Formatvorlagen auf den text an.
Andere Optionen?
- Haben Sie sich entschieden, wie ist der text selbst gespeichert? Was auch immer die Struktur der text verwendet hat, um effizient zu handhaben Insertionen/Deletionen, so dass es möglich sein könnte, zu erweitern, durch den text, zeigen Sie auf die Stile, die eher als die andere Weise herum. So etwas wie begleitende jedes Zeichen mit einem Zeiger auf ein array/Liste der anwendbaren Stile. Sie sollten in der Lage sein zu teilen, die Stile und das array unter den Zeichen, und Sie könnten der Veranstaltung in der Lage sein zu teilen, der Zeiger selbst.
- Bitte poste das als Antwort, damit kann ich kommentieren.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Habe ich nie entwickelt einen editor, aber wie wäre es damit:
Ich glaube, es wäre möglich, erweitern Sie das Schema, das verwendet wird zum speichern der text-Zeichen themeselves, selbstverständlich abhängig von den details der Implementierung (Sprache, toolkits etc) und Ihre Leistung und Ressourcen-Nutzung Anforderungen.
Eher als eine separate Datenstruktur für die Stile, ich würde lieber mit einem Verweis, dass würde begleiten jedes Zeichen und zeigen auf ein array oder eine Liste mit den gültigen Zeichen. Charaktere mit der gleichen Menge von Stilen könnte auf das gleiche array oder eine Liste, so dass man gemeinsam genutzt werden.
Charakter Einfügungen und Löschungen würden sich nicht auf die Stile, die themeselves, abgesehen von der änderung der Anzahl der Verweise auf Sie, das könnte behandelt werden, mit ein bisschen reference counting.
Abhängig von der Programmiersprache könnte man noch komprimieren, Dinge, die ein bisschen mehr mit dem Hinweis auf halbem Weg in einer Liste, obwohl die zusätzliche Buchführung für diese könnte in der Tat machen es eher ineffizient.
Das Hauptproblem bei diesem Vorschlag ist die Speicherauslastung. In einem ASCII-editor, geschrieben in C, Bündelung ein Zeiger mit jedem char erheben würde seine effektive Speichernutzung von 1 byte 12 Byte auf einem 64 bit-system ist, aufgrund der Struktur-alignment-Polsterung.
Ich Aussehen würde, zu brechen den text in kleine Blöcke variabler Größe, die es Ihnen ermöglichen, effizient komprimieren den Zeiger. E. g. ein 32-Zeichen-block könnte so Aussehen: C:
Der interessante Teil ist die Metadaten-Verarbeitung auf der variable Teil der Struktur, die enthält sowohl den gespeicherten text und jede Formatvorlage, die Zeiger. Die Größe der element geben würde, die Anzahl der Zeichen. Die Stile integer (daher die 32-Zeichen-limit) gesehen werden, als eine Reihe von 32 1-bit-Felder, von denen jedes angibt, ob ein Charakter hat seinen eigenen Stil Zeiger, oder ob es den gleichen Stil wie die vorherigen Charakter. Diese Weise ist eine 32-char-block mit einem einzigen Stil würde nur der zusätzliche overhead der Größe von char, die Stile, die Maske und einen einzelnen Zeiger, zusammen mit padding-bytes. Einfügen und löschen von Zeichen in ein kleines array wie dieses sollte Recht schnell.
Als für den text, den Speicher selbst, ein Baum klingt wie eine gute Idee. Vielleicht ein binärer Baum, in dem jeder Knoten mit dem Wert würde die Summe der Kinder Werte, die mit der Blatt-Knoten schließlich zeigt auf text-Blöcke mit Ihrer Größe wie Ihrer Knoten mit dem Wert? Der root-Knoten wäre Wert die Gesamtgröße des Textes, wobei jeder Teilbaum im Idealfall halten die Hälfte des Textes. Sie würden immer noch, um auto-balance es aber manchmal zu verschmelzen halb-leere Textblöcke.
Und in falls Sie es verpasst, ich bin kein Experte in den Bäumen 🙂
EDIT:
Anscheinend was ich vorgeschlagen ist eine modifizierte version von dieser Daten-Struktur:
http://en.wikipedia.org/wiki/Rope_%28computer_science%29
als verwiesen wird in diesem Beitrag:
Datenstruktur für text-editor
EDIT 2:
Löschung in der vorgeschlagenen Datenstruktur sollte relativ schnell sein, wie es kommen würde, auf byte-Verschiebung in einem array und ein paar bitweise Operationen auf die Stile, die Maske. Insertion ist so ziemlich das gleiche, es sei denn, ein block füllt sich. Ist es sinnvoll zu reservieren, Platz (z.B. einige bits im Stile Maske) in jedem block, dass zukünftige Einfügungen direkt in die Blöcke, ohne änderung der Struktur selbst für relativ kleine Mengen von neuen text.
Ein weiterer Vorteil der Bündelung von Zeichen und Stile in Blöcken wie diesen ist, dass Ihre inhärente Daten Lokalität sollte die Möglichkeit für mehr effiziente Nutzung der CPU-cache als die anderen alternativen, also die Verbesserung der Verarbeitungsgeschwindigkeit zu einem gewissen Grad.
Viel wie jede komplexe Datenstruktur, allerdings würden Sie wahrscheinlich brauchen, entweder profiling mit repräsentativen Testfälle oder ein adaptiver Algorithmus zur Bestimmung der optimalen Parameter für den Betrieb (block-Größe, keine reservierten Raum etc).