Struktura danych wstęga: edycja gigantycznych ciągów bez kopiowania ich

Z płaskich tablic do drzewek odcinków

Tekst prosty, czyli ciąg znaków w języku poziomowym jako tablica charakterów lub w języku wyższego poziomu jako niezmienialna sekwencja, jest przechowywany w kontynuowanej bloku pamięci. Czytanie znaku na danej pozycji jest natychmiastowe, ponieważ komputer może skoczyć bezpośrednio do odpowiedniego adresu pamięci. Ale edytowanie jest drogie: wstawienie lub usunięcie znaku w środku oznacza, że każdy znak po tym punkcie musi zostać przesunięty, co wymaga operacji proporcjonalnej do długości ciągu. Dla krótkiego ciągu to nie ma znaczenia. Dla dokumentu z milionami znaków staje się poważnym brzegiem, szczególnie kiedy edycje występują ponownie podczas pisania. Rope podejmuje inny podkład. Tekst dzieli na wiele małych odcinków, często tylko kilkanaście lub kilka setek znaków każdego i przechowuje każdy odcinek w liściu drzewa binarnego. Liście, czytane od lewej do prawej, rekonstruuują pełny dokument w odpowiedniej kolejności. Węzły wewnętrzne drzewa nie przechowują żadnych znaków; ich jedynym zadaniem jest opisanie organizacji drzewa, głównie zapisując wagę swojego dziecka lewego, co oznacza całkowitą liczbę znaków znajdujących się w każdym liści pod tym poddrzewem lewym. Ta reorganizacja zmienia profil kosztu na całkowicie inny. Ponieważ dokument jest rozłożony na wiele niezależnych odcinków połączone drzewem, edycja w początku tekstu już nie wymaga dotykania odcinków w końcowej części. Wytyczna tylko ścieżka od zatroskanej liścia do korzenia potrzebuje nowych lub zmodyfikowanych węzłów, a w odpowiednio równie zbalansowanym drzewie ta ścieżka ma długość proporcjonalną do logarytmu liczby odcinków, a nie liczby znaków. W zamian za to znalezienie dowolnego znaku teraz wymaga krótkiej wędrówki po drzewie zamiast pojedynczego przeszukiwania pamięci, ale ta wędrówka jest ekonomiczna, a zwrot w szybkości edycji dla dużych dokumentów jest ogromny. To jest podstawowa idea za każdym operacją, która wspiera rope.

Indeksowanie: Przechodzenie w dół z wagami akumulowanymi

Nawet jeśli łańcuch tekstowy rozrzuca swoje znaki po wielu liściach, nadal musi szybko odpowiadać na bardzo proste pytanie: jaki znak znajduje się na pozycji n w dokumencie, czy równoznacznie, który liść i jakie offsety w tym liście odpowiadają danemu indeksowi. To jest tam, gdzie waga przechowywana w każdym wewnętrzny węzeł sprawdza swoją wartość. Szukanie zaczyna się od korzenia, mając na starczyku docelowy indeks. W każdym wewnętrznym węźle algorytm porównuje docelowy indeks do wagi tego węzła, która jest liczbą znaków wszystkiego znajdującego się w jego lewym poddrzewie. Jeśli indeks jest mniejszy niż waga, to szukany znak musi być gdzieś w lewym poddrzewie, więc wyszukiwanie przechodzi w lewo i indeks pozostaje niezmieniony, ponieważ lewe poddrzewo nadal zaczyna liczyć od pozycji zero. Jeśli indeks jest większe lub równe wagie, szukany znak znajduje się w prawym poddrzewie, więc wyszukiwanie przechodzi w prawo, ale najpierw odejmuje wagę lewego poddrzewa od indeksu, ponieważ własne liczenie pozycji w prawym poddrzewie zaczyna się od nowa od zero i znaki z lewej strony muszą być pomijane pojęciowo. Ten proces powtarza się, liść za liściem, aż wyszukiwanie dotrze do liścia. Wtedy pozostająca wartość indeksu jest prosto offsetem w krótkim fragmentu znaków tego liścia, a znak jest odczytywany bezpośrednio. Ponieważ każda krotność przesuwa się o poziom drzewa, którego wysokość proporcjonalna jest do logarytmu liczby liści, całe wyszukiwanie zajmuje około czasu logarytmicznego zamiast stałego czasu dla płaskiego tablicy, ale pozostaje szybkie nawet dla ogromnych dokumentów, a nigdy nie wymaga skanowania niespokojonego fragmentu tekstu. Taka sama przechodząca w dół ścieżka, monitorująca wagę akumulowaną, jest ponownie wykorzystywana jako podstawowy element budowy dla podziału łańcucha na konkretnej pozycji.

Podział i konkatenacja: dwie operacje, które robią wszystko

Practiquement każda edytorska akcja, której wspornik obsługuje wstęgę, może być zbudowana tylko z dwóch niższych operacji: podziału jednej wstęgi na dwie na danym indeksie i konkatenacji, czyli łączenia, dwóch wstęg w jedną. Zrozumienie tych dwóch operacji jest kluczem do zrozumienia całości struktury. Podział wykorzystuje taką samą opadanie pod kierunkiem masy jak indeksowanie. Podczas gdy algorytm idzie w dół ku punktowi podziału, odłączając części drzewa, które całkowicie leżą do lewej strony tego punktu i osobno zbierając części, które całkowicie leżą po prawej stronie, czasami musi rozbić pojedyncze liście na dwa krótsze fragmenty, jeśli punkt podziału znajduje się dokładnie w środku tekstu tej listy. Wynikiem jest dwie niezależne, dobrze sformowane wstęgi: jedna reprezentująca wszystko przed punktem podziału, a druga reprezentująca wszystko od tego punktu dalej. Ponieważ tylko węzły po drodze od korzenia do lokalizacji podziału muszą być sprawdzone i przestawione, ta operacja kosztuje czas proporcjonalny do wysokości drzewa, ponownie około logarytmicznego względem liczby fragmentów. Konkatenacja idzie w przeciwnym kierunku: dana dwie wstęgi tworzy nową jedyną wstęgę reprezentującą tekst ich łączonego końcem z końcem. Najprostsze podejście tworzy nowy korzeń, którego dzieckiem lewym jest pierwsza wstęga, a prawym druga wstęga, z wagą nowego korzenia ustawioną na całkowitą liczbę znaków w pierwszej wstępie. Jest to ekonomiczna operacja, niemal stała czasu, ponieważ nie musi dotykać ani kopiować znaków wewnątrz żadnej z wstęg; wystarczy alokować jedno nowe węzeł. Z tych dwóch narzędzi wstawianie na pozycji n staje się: podział wstęgi na pozycję n, konkatenacja części lewej z nową małą wstęgą zbudowaną z wstawionego tekstu, a następnie konkatenacja tego wyniku z części prawej. Usunięcie zakresu staje się dwoma podziałami, nastepującymi przez konkatenację przetrwujących zewnętrznich części. Wyodrębnianie podciągu staje się dwoma podziałami izolującymi pożądany środkowy fragment. Nikt z operacji nigdy nie musi kopiować lub przesuwać większości oryginalnego dokumentu.

Dlaczego to przewyższa kopiowanie całego tablicy

Pomogłoby to dodać konkretne intuicję założenia, że wstęgi są szybsze podczas edycji. Wyobraźmy sobie dokument zawierający milion znaków przechowywany jako płaski tabliczka, a następnie wyobraźmy sobie wstawianie jednego znaku blisko początku. Implementacja musi przesunąć około miliona znaków o jedną pozycję lub w wielu zarządzanych językach programowania alokować nową tablicę o rozmiarze milion-plus-jeden znaków i kopiować wszystko na nowo. W każdym przypadku koszt jest proporcjonalny do rozmiaru całego dokumentu, a ponownie zostaje zapłacony za kolejne wstawiania, niezależnie od miejsca edycji. Teraz wyobraźmy sobie ten sam dokument jako wstęgę zbudowaną z liści przechowujących około sto znaków każdego, co daje około tysiąca setek liści ułożonych w drzewie o wysokości tylko około czternaście poziomów, ponieważ wysokość równoległego drzewa binarnego rośnie ze wzrostem logarytmu liczby liści. Wstawianie znaku wymaga przejścia dookoła czternaście poziomów, aby podzielić wstęgę, alokacji małego nowego liścia dla wstawionych tekstu i powrotu na górę do ponownego budowania około czternaście przodków, tylko ich numery kalkulacyjne, a nie zawartość znaków. Innych około tysiąca setek liści, przechowujących większość rzeczywistego tekstu dokumentu, nigdy nie są dotykać, nigdy nie są kopii i często dzielą się odniesieniem między starym i nowym wersją wstęgi. Ta różnica rosnie, gdy dokumenty rosną. Podwójne rozmiar dokumentu roughly podwójnie zwiększa koszt wstawiania w tabliczce płaskiej, ale dodaje tylko jeden dodatkowy poziom wysokości drzewa równoległego, zmieniając już mały koszt logarytmiczny na niewielkie znaczenie. To dokładnie dlaczego oprogramowanie, które musi obsługiwać bardzo duże lub często edytowane teksty, w tym profesjonalne procesory tekstu, edytory źródeł języków programowania i systemy zarządzania edycją collaborative, przewyższa struktury podobne do wstęgi nad proste ciągi kontynuowane, gdy dokumenty rosną ponad pewien mały rozmiar. Taka sama logika wyjaśnia dlaczego niektóre systemy zastępują reprezentację wstęgi tylko po przekroczeniu pewnego próg rozmiaru, ponieważ dla naprawdę małych ciągów prosta i przyjazna buforom pamięci tabliczka płaska nadal może wygrać w praktyce.

Zachowanie drzewa w równowadze

Logarytmiczne wydajność zapewniana przez wstęgę zależy całkowicie od utrzymania drzewa w odpowiednio równoważnym stanie, co oznacza, że żaden ścieżka od korzenia do liścia nie jest znacznie dłuższa niż inna. Jeśli wstęga jest budowana zbyt słabo, na przykład dodając pojedyncze znaki jedno po drugim na prawy koniec bez żadnej reequilibracji, drzewo może stanie się podobne do długiej łańcuchowej struktury, gdzie każdy węzeł ma właściwie tylko jednego istotnego potomka. W tej zdegenerowanej formie operacje, które powinny trwać czas logarytmiczny, wracają ku kosztowi liniowemu, który wstęgi były zaprojektowane do uniknięcia, ponieważ przegladanie długiej i cienkiej łańcuchowej struktury odwiedza prawie tyle węzłów, ile jest znaków. Aby uniknąć tego, implementacje wstęg wykorzystują strategie reequilibracji. Niektóre reequilibrują się zdecydowanie, sprawdzając po każdym podziału lub łączeniu, czy kształt wynikającego drzewa odchylił się za bardzo od równowagi i, jeśli tak, przeprowadzają jego restructurację, często używając technik podobnych do tych stosowanych w samoreequilibrujących drzewach binarnych wyszukiwania (takich jak rotacje, które przesuwają poddrzewa zachowując porządek lewo-prawo liści). Inne reequilibrują się łagodnie, pozwalając na akumulację pewnej nierównowagi podczas burzy edycji i potem wykonując pojedynczy proces czyszczenia, czasami przez zbieranie wszystkich liści w porządku i powtórne budowanie nowego, doskonale równoważnego drzewa z nich, co jest samodzielnie szybkim operacją, ponieważ musi przetworzyć tylko liście raz. Użyteczny mentalny standard można znaleźć w liczbach Fibonacciego: wstęga jest rozważana za bardzo nierównoważna i potrzebująca uwagi, jeśli jej całkowita liczba znaków jest mniejsza od liczby Fibonacciego odpowiadającej wysokości drzewa, próg, który gwarantuje minimalną gęstość drzewa i zachowuje logarytmiczną gwarancję wysokości. dobrze zaprojektowane biblioteki wstęg również łączą bliskie małe liście z powrotem razem i dzielą nadmiernie duże liście, utrzymując rozmiar fragmentów w odpowiednim zakresie, tak aby drzewo ani nie rosnęło zbyt wieloma węzłów, co hamuje przegladanie, ani zbyt mało, co ryzykuje dużych kopii na poziomie liści. Zachowanie równowagi jest to, co umożliwia wstęgach utrzymywanie szybkiej wydajności przez długą sesję edycji, a nie tylko podczas pierwszych kilku operacji.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Rope: The Data Structure Behind Big Text Editors i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.