Ich suche nach der besten Datenstruktur, um einem Text Stile hinzuzufügen (etwa in einem Texteditor). Die Struktur sollte die folgenden Operationen ermöglichen:
Ich habe Listen / Arrays betrachtet, die Textbereiche enthalten, aber sie erlauben kein schnelles Einfügen, ohne die Positionen aller Stile nach dem Einfügepunkt neu zu berechnen.
Eine Baumstruktur mit relativen Offsets unterstützt # 2, aber der Baum wird schnell degenerieren, wenn ich dem Text viele Stile hinzufüge.
Andere Optionen?
Ich habe noch nie einen Editor entwickelt, aber wie wäre es damit:
Ich glaube, es wäre möglich, das Schema, das zum Speichern der Textzeichen verwendet wird, zu erweitern, natürlich abhängig von den Einzelheiten Ihrer Implementierung (Sprache, Toolkits usw.) und Ihren Anforderungen an die Performance und Ressourcennutzung.
Anstatt eine separate Datenstruktur für die Stile zu verwenden, würde ich eine Referenz bevorzugen, die jedes Zeichen begleiten und auf ein Array oder eine Liste mit den entsprechenden Zeichen zeigen würde. Zeichen mit demselben Satz von Stilen können auf dasselbe Array oder dieselbe Liste verweisen, sodass einer geteilt werden kann.
Das Einfügen und Löschen von Zeichen würde sich nicht auf die Stile selbst auswirken, abgesehen von der Änderung der Anzahl der Verweise auf diese, die mit ein wenig Referenzzählung behandelt werden könnten.
Abhängig von Ihrer Programmiersprache könnten Sie die Dinge sogar ein bisschen mehr komprimieren, indem Sie halbwegs auf eine Liste zeigen, obwohl die zusätzliche Buchhaltung dafür ineffizient sein könnte.
Das Hauptproblem bei diesem Vorschlag ist die Speichernutzung. In einem ASCII-Editor, der in C geschrieben ist, würde das Bündeln eines Zeigers mit jedem Zeichen die effektive Speicherbelegung von 1 Byte auf 12 Byte in einem 64-Bit-System erhöhen, da die Struktur auf die Ausrichtung ausgerichtet ist.
Ich würde versuchen, den Text in kleine Blöcke variabler Größe zu zerlegen, die es Ihnen erlauben würden, die Zeiger effizient zu komprimieren. Z.B. Ein 32-stelliger Block könnte in C wie folgt aussehen:
%Vor%Der interessante Teil ist die Metadatenverarbeitung für den variablen Teil der Struktur, die sowohl den gespeicherten Text als auch beliebige Stilzeiger enthält. Das Größenelement würde die Anzahl der Zeichen anzeigen. Die Ganzzahl der Stile (also die 32-Zeichen-Grenze) würde als eine Menge von 32 1-Bit-Feldern angesehen werden, wobei jedes angibt, ob ein Zeichen seinen eigenen Stilzeiger hat oder ob es den gleichen Stil wie das vorherige Zeichen verwenden soll. Auf diese Weise hätte ein 32-char-Block mit einem einzigen Stil nur den zusätzlichen Overhead des Size-Zeichens, der Styles-Maske und eines einzelnen Zeigers sowie etwaiger Füllbytes. Das Einfügen und Löschen von Zeichen in ein kleines Array wie dieses sollte ziemlich schnell sein.
Wie für den Textspeicher selbst klingt ein Baum wie eine gute Idee. Vielleicht ein binärer Baum, bei dem jeder Knotenwert die Summe der Kinderwerte wäre, wobei die Blattknoten schließlich auf Textblöcke mit ihrer Größe als Knotenwert zeigen würden? Der Wert des Stammknotens wäre die Gesamtgröße des Textes, wobei jeder Teilbaum idealerweise die Hälfte des Textes enthält. Sie müssen es jedoch immer noch automatisch ausgleichen, da Sie manchmal halb leere Textblöcke zusammenführen müssen.
Und falls Sie es verpasst haben, bin ich kein Experte für Bäume: -)
BEARBEITEN:
Anscheinend habe ich eine modifizierte Version dieser Datenstruktur vorgeschlagen:
wie in diesem Beitrag erwähnt:
Datenstruktur für den Texteditor
EDIT 2:
Das Löschen in der vorgeschlagenen Datenstruktur sollte relativ schnell sein, da es sich um eine Byteverschiebung in einem Array und einige bitweise Operationen in der Stilmaske handeln würde. Die Einfügung ist ziemlich gleich, es sei denn, ein Block füllt sich. Es könnte sinnvoll sein, in jedem Block etwas Platz (d. H. Einige Bits in der Stilmaske) zu reservieren, um zukünftige Einfügungen direkt in den Blöcken zu ermöglichen, ohne den Baum selbst für relativ kleine Mengen neuen Textes ändern zu müssen.
Ein weiterer Vorteil der Bündelung von Zeichen und Stilen in solchen Blöcken ist, dass die inhärente Datenlokalität eine effizientere Nutzung des CPU-Cache als andere Alternativen ermöglichen sollte, wodurch sich die Verarbeitungsgeschwindigkeit etwas verbessert.
Wie bei jeder komplexen Datenstruktur benötigen Sie wahrscheinlich entweder ein Profiling mit repräsentativen Testfällen oder einen adaptiven Algorithmus, um die optimalen Parameter für die Operation zu bestimmen (Blockgröße, reservierter Speicherplatz usw.).
Tags und Links data-structures text text-editor styling styledtext