スタイルをテキストに追加するのに最適なデータ構造を探しています (テキスト エディターなど)。構造は、次の操作を許可する必要があります。
テキスト範囲を含むリスト/配列を検討しましたが、挿入ポイントの後のすべてのスタイルの位置を再計算しないと、すばやく挿入できません。
相対オフセットを持つツリー構造は #2 をサポートしますが、テキストに多くのスタイルを追加すると、ツリーが急速に劣化します。
他のオプションはありますか？
私はエディターを開発したことがありませんが、これはどうですか？
もちろん、実装の詳細（言語、ツールキットなど）やパフォーマンス、リソースの使用要件によっては、テキスト文字のテーマ自体を格納するために使用されるスキームを拡張できると思います。
スタイルに個別のデータ構造を使用するのではなく、各文字に付随し、該当する文字を含む配列またはリストを指す参照を使用することをお勧めします。同じスタイルのセットを持つ文字は、同じ配列またはリストを指すことができるため、1つを共有できます。
文字の挿入と削除は、それらへの参照の数を変更することを除いて、スタイルのテーマ自体には影響しません。これは、少しの参照カウントで処理できます。
プログラミング言語によっては、リストの途中を指すことで、物事をもう少し圧縮することもできますが、これに対する追加の簿記は、実際には非効率になる可能性があります。
この提案の主な問題は、メモリ使用量です。Cで記述されたASCIIエディターでは、ポインターを各文字にバンドルすると、構造アライメントのパディングにより、64ビットシステムでの実効メモリ使用量が1バイトから12バイトに増加します。
テキストを小さな可変サイズのブロックに分割して、ポインターを効率的に圧縮できるようにすることを検討します。たとえば、32文字のブロックはCでは次のようになります。
struct _BLK_ {
unsigned char size;
unsigned int styles;
char content[];
}
興味深い部分は、構造体の変数部分でのメタデータ処理です。これには、格納されたテキストと任意のスタイルポインターの両方が含まれます。size要素は、文字数を示します。スタイル整数（したがって32文字の制限）は、32個の1ビットフィールドのセットと見なされ、各フィールドは、文字に独自のスタイルポインターがあるかどうか、または前の文字と同じスタイルを使用する必要があるかどうかを示します。このように、単一のスタイルを持つ32文字のブロックには、サイズchar、スタイルマスク、単一のポインター、およびパディングバイトの追加のオーバーヘッドのみがあります。このような小さな配列への文字の挿入と削除は非常に高速です。
テキストストレージ自体に関しては、ツリーは良い考えのように聞こえます。おそらく、各ノード値が子の値の合計であり、リーフノードが最終的にノード値としてサイズを持つテキストブロックを指すバイナリツリーですか？ルートノードの値はテキストの合計サイズになり、各サブツリーは理想的にはテキストの半分を保持します。ただし、半分空のテキストブロックをマージする必要がある場合もありますが、それでも自動バランスを取る必要があります。
そして、あなたがそれを逃した場合に備えて、私は木の専門家ではありません:-)
編集：
どうやら私が提案したのは、このデータ構造の修正バージョンです。
http://en.wikipedia.org/wiki/Rope_%28computer_science%29
この投稿で参照されているように：
編集2：
提案されたデータ構造の削除は、配列内のバイトシフトと、スタイルマスクに対するいくつかのビット演算に帰着するため、比較的高速である必要があります。ブロックがいっぱいにならない限り、挿入はほとんど同じです。比較的少量の新しいテキストのためにツリー自体を変更することなく、ブロックに直接挿入できるように、各ブロック内にスペース（つまり、スタイルマスクのビット）を予約することは理にかなっています。
このようなブロックに文字とスタイルをバンドルすることのもう1つの利点は、その固有のデータ局所性により、他の方法よりもCPUキャッシュをより効率的に使用できるため、処理速度がある程度向上することです。
ただし、他の複雑なデータ構造と同様に、その操作に最適なパラメーター（ブロックサイズ、予約済みスペースなど）を決定するには、代表的なテストケースを使用したプロファイリングまたは適応アルゴリズムが必要になる可能性があります。