Najbardziej wydajna struktura danych do dodawania stylów do tekstu

Question

Poszukuję najlepszej struktury danych, aby dodać style do tekstu (np. W edytorze tekstu). Struktura powinna umożliwić następujące operacje:

1. Szybkie wyszukiwanie wszystkich stylów na pozycji absolutnego X
2. Krótki wkładka tekstu w dowolnej pozycji (style po tej pozycji musi być przeniesiony).
3. Każda pozycja tekstu musi obsługiwać dowolną liczbę stylów (nakładanie się).

Rozważałem listy/tablice, które zawierają zakresy tekstowe, ale nie pozwalają na szybkie wstawianie bez ponownego obliczania pozycji wszystkich stylów po punkcie wstawienia.

Struktura drzewa ze względnymi przesunięciami obsługuje # 2, ale drzewo zwinie się szybko, gdy dodaję wiele stylów do tekstu.

Jakieś inne opcje?

Answer 1

nigdy nie rozwinął edytor, ale jak o tym:

wierzę, że byłoby to możliwe, aby rozwinąć program, który jest używany do przechowywania znaków tekstowych themeselves, w zależności oczywiście od szczegółów implementacji (język, zestawy narzędzi itp.) oraz wymagania dotyczące wydajności i wykorzystania zasobów.

Zamiast używać osobnej struktury danych dla stylów, wolałbym mieć odniesienie, które towarzyszyłoby każdemu znakowi i wskazywać na tablicę lub listę z odpowiednimi znakami. Znaki z tym samym zestawem stylów mogą wskazywać na tę samą tablicę lub listę, aby można było dzielić się nimi.

Wprowadzanie i usuwanie znaków nie wpłynęłoby na styl samych kompozycji, poza zmianą liczby odniesień do nich, które można obsłużyć niewielkim licznikiem odwołań.

W zależności od języka programowania można nawet nieco skompresować elementy, wskazując w połowie listy, chociaż dodatkowe księgowanie może w rzeczywistości sprawić, że będzie on bardziej nieefektywny.

Głównym problemem związanym z tą sugestią jest użycie pamięci. W edytorze ASCII napisanym w C łączenie wskaźnika za pomocą każdego znaku zwiększyłoby jego efektywne wykorzystanie pamięci z 1 bajta na 12 bajtów w systemie 64-bitowym z powodu dopełnienia wyrównania strukturalnego.

Chciałbym rozejrzeć się za rozbijanie tekstu na małe bloki o zmiennej wielkości, które pozwoliłoby skutecznie skompresować wskaźniki. Na przykład. blok 32-znakowy może wyglądać tak: C:

struct _BLK_ { 
    unsigned char size; 
    unsigned int styles; 
    char content[]; 
} 

Interesującą częścią jest przetwarzanie metadanych na zmiennej części struktury, która zawiera zarówno zapisany tekst i żadnych wskazówek stylu. Element size wskazywałby liczbę znaków. Styl liczba całkowita (stąd limit 32 znaków) byłby postrzegany jako zestaw 32 1-bitowych pól, z których każdy wskazuje, czy znak ma swój własny wskaźnik stylu, czy też powinien używać tego samego stylu, co poprzedni znak. W ten sposób 32-znakowy blok z pojedynczym stylem będzie miał tylko dodatkowy narzut rozmiaru char, maskowanie stylów i pojedynczy wskaźnik, wraz z dowolnymi bajtami dopełnienia. Wstawianie i usuwanie znaków w tak małej tablicy powinno być dość szybkie.

Co do samego magazynu tekstów, drzewo brzmi jak dobry pomysł.Być może drzewo binarne, w którym każda wartość węzła byłaby sumą wartości podrzędnych, a węzły liści ostatecznie wskazywałyby na bloki tekstowe z ich rozmiarem jako wartością węzła? Wartość węzła głównego będzie całkowitym rozmiarem tekstu, a każde poddrzewo będzie zawierać połowę tekstu. Nadal musiałbyś jednak wyrównać wagę, niekiedy trzeba scalać w połowie puste bloki tekstu.

A w przypadku, gdy go brakowało, Nie jestem ekspertem w drzewach :-)

EDIT:

Podobno co zasugerowałem to zmodyfikowana wersja tej struktury danych:

http://en.wikipedia.org/wiki/Rope_%28computer_science%29

wymieniony w tym poście:

Data structure for text editor

EDYTUJ 2:

Usunięcie w proponowanej strukturze danych powinno być względnie szybkie, ponieważ sprowadzałoby się do przesunięcia bajtu w tablicy i kilku operacji bitowych na masce stylów. Wstawianie jest prawie takie samo, chyba że blok wypełnia się. Może być sens zarezerwowanie pewnej przestrzeni (tj. Niektórych bitów w masce stylów) w każdym bloku, aby umożliwić przyszłe wstawianie bezpośrednio w blokach, bez konieczności zmiany samego drzewa dla stosunkowo małych ilości nowego tekstu.

Inną zaletą łączenia znaków i stylów w blokach, takich jak ta, jest to, że lokalna lokalizacja danych powinna umożliwiać bardziej efektywne wykorzystanie pamięci podręcznej procesora niż inne alternatywy, co w pewnym stopniu poprawia szybkość przetwarzania.

Podobnie jak w przypadku dowolnej złożonej struktury danych, prawdopodobnie potrzebne będzie profilowanie z reprezentatywnymi przypadkami testowymi lub algorytm adaptacyjny w celu określenia optymalnych parametrów jego działania (wielkość bloku, zarezerwowana przestrzeń itd.).