Sling (datová struktura)

Sling (lano, šňůra) je datová struktura, která umožňuje efektivně ukládat a zpracovávat dlouhé řetězce, například text. Poskytuje uložení dlouhého řetězce jako stromu sestávajícího z malých podřetězců. Je vhodný pro ukládání a zpracování textových souborů a poskytuje efektivní provádění operací typických pro textový editor: vkládání, mazání, obrácení (náhodný přístup) [1] .

Popis

Závěs je binární strom, kde každý list (uzel bez potomků) obsahuje řetězec (podřetězec textu) a délku (váhu) a každý nelistový uzel stromu obsahuje délku listů svého levého potomka podstromu. . Uzel se dvěma dětmi rozdělí celý řetězec na dvě části, kde první část je uložena u levého podstromu, druhá - u pravého, váha samotného uzlu je rovna délce první části. Pro základní operace se předpokládá, že řetězce nejsou upravovány nedestruktivním způsobem, což umožňuje kopírování při zápisu. Listové uzly jsou obvykle implementovány jako řetězce konstantní délky s referenčním počtem, při resetování se uvolní paměť. Lze také použít pokročilé techniky sběru odpadu.

Operace

V následujících definicích je N délka závěsu.

Vložit

Definice: Insert(i, S’) : vloží řetězec S' začínající na pozici i do řetězce s , čímž vznikne nový řetězec C 1 , …, C i , S' , C i + 1 , …, C m . Složitost: O(log N) .

Tuto operaci lze provést pomocí Split()a dvou operací Concat().

Odvolání

Definice: Index(i) : vrátí znak na pozici i Složitost: O (log N)

Abychom se podívali na i -tý znak, zahájíme rekurzivní vyhledávání počínaje kořenem:

index funkce ( uzel RopeNode , celé číslo i ) if node . váha <= i a existuje ( node . right ) pak návrat index ( node . right , i - node . weight ) end if existuje ( node . left ) then return index ( node . left , i ) end návratový uzel . řetězec [ i ] konec

Podívejte se například na obrázek 2.1 a najděte znak na pozici i=10, začínáme od kořene (A), máme, že jeho váha 22 je větší než 10, takže jdeme dolů doleva (B). Zde máme, že 9 je menší než 10, odečtěte 9 od 10 (získání i=1) a přejděte ke správnému podřízenému uzlu (D). Máme 6 větších než 1 a přejdeme k levému dítěti (G). Zde 2 je větší než 1 jdeme dolů doleva (J). A konečně, 2 je větší než 1, ale protože se jedná o listový uzel, nemá žádné potomky a my se jednoduše odkážeme na index 1 uložený v uzlu řetězce "na" (tedy "a"), který být odpovědí.

Závěs

Definice: Concat(S1, S2) : Spojuje dvě vedení, S 1 a S 2 , do jednoho celku. Složitost: O(1) (nebo O(log N) při výpočtu hmotnosti kořene)

Řetězení se provádí vytvořením nového kořene s dětmi vlevo = S1 a vpravo = S2 , v konstantním čase. Váha nadřazeného uzlu je nastavena na délku levého potomka S 1 , který může mít O(log N) , pokud je strom vyvážený.

Většina vázacích operací vyžaduje, aby byl strom vyvážen, po zavěšení může být nutné strom vyvážit.

Členění

Definice: Split (i, S) : rozdělí řetězec S na dvě nové S 1 a S 2 , kde S 1 = C 1 , …, C i a S 2 = C i + 1 , …, C m . Složitost: O (log N)

Jsou možné dva případy:

  1. Bod přerušení je na konci řádku (tj. za posledním znakem listového uzlu)
  2. Bod přerušení je uprostřed řádku.

Druhý případ je zredukován na první tak, že se řetězec přeruší v bodě přerušení a vytvoří se dva nové koncové uzly a poté se pro ně vytvoří nový nadřazený uzel.

Chcete-li například rozdělit smyčku o 22 znacích na obrázku 2.3 na dvě složky o délce 11, požádáme o 12. znak pro určení uzlu K na spodní úrovni. Odstraňte spojení mezi K a G . Přejděte na rodič G a odečtěte váhu K od hmotnosti D . Vylezte po stromu nahoru a odstraňte všechny pravé odkazy podstromu obsahující znaky za 11. znakem odečtením váhy K od jejich nadřazených uzlů (v našem případě pouze D a A ). Nakonec seřadíme nedávno osiřelé uzly K a H tak, že pro ně vytvoříme nového rodiče P s váhou rovnou délce levého dceřiného uzlu K .

Většina operací vázání vyžaduje, aby byl strom vyvážen, po vytyčení může být nutné strom vyvážit.

Odstranění

Definice: Delete(i, j) : odstraňte podřetězec C i , …, C i + j − 1 , z s a vytvořte nový řetězec C 1 , …, C i − 1 , C i + j , …, C m . Složitost: O(log N) .

Dá se to udělat dvěma Split()a jedním Concat(). Pro začátek vydělíme řetězec třemi, oddělenými i -tým a i + j -tým znakem, řádek, který se má smazat, bude přidělen samostatnému (střednímu) uzlu. Poté propojíme další dva uzly.

Žádost

Definice: Report(i, j) : vrací řetězec C i , …, C i + j − 1 . Složitost: O(j + log N)

Chcete-li se dotázat na řetězec C i , …, C i + j − 1 , najděte uzel u obsahující C i c a poté navštivte T počínaje uzlem u . Odvozujeme C i , …, C i + j − 1 navštěvující T v pořadí počínaje uzlem u . weight(u) >= j

Porovnání s hustými poli

Výkon
Úkon Sling pole
odvolání [1] O(log n) O(1)
Rozdělení [1] O(log n) O(1)
Zapřáhnout (zničit) O(log n) nevyvážený / O(n) nejhorší případ Na)
Spojka (nedestruktivní) Na) Na)
Průchod postavy [1] Na) Na)
Vložit [2] O(log n) nevyvážený / O(n) nejhorší případ Na)
Dodatek [2] O(log n) nevyvážený / O(n) nejhorší případ O(1) odpružené, O(n) nevyvážené
Odstranění O(log n) Na)
Žádost O(j + log n) O(j)
Stvoření Na) Na)

výhody:

  • Slingy umožňují rychlejší vkládání a mazání textu (ve srovnání s hustými řetězci, které mají O(n) časovou složitost).
  • Slingy nevyžadují O(n) extra paměť při provádění operací (pole ji potřebují při kopírování).
  • Slingy nevyžadují velké husté paměťové prostory.
  • Při použití pouze nedestruktivních verzí operací je sling trvalou datovou strukturou . To usnadňuje organizaci více úrovní úprav (jako jsou operace zpět) v textovém editoru.

nedostatky:

  • Více celkového využitého prostoru, který je potřeba pouze při provádění operací (k ukládání nadřazených uzlů). Musíme najít kompromis mezi tím, kolik paměti navíc budeme ukládat a jak dlouhé mohou být podřetězce v uzlech. Řádky ve výše uvedených příkladech byly zjevně příliš krátké. Nadměrná složitost bude vždy O(n), ale konstantu lze snížit.
  • Zvýšená doba práce s další pamětí
  • Zvýšená složitost kódu; větší pravděpodobnost chyb

Tato tabulka porovnává algoritmické vlastnosti implementací řetězců a závěsů, nikoli jejich hrubou rychlost . Řetězce na polích jsou méně režijní, takže například zřetězení a dělení bude pro malé řetězce mnohem rychlejší. Při použití polí pro dlouhé řetězce však již bude časová složitost a náklady na paměť nepřijatelně velké (protože počet kopií se značně zvýší). Naproti tomu výkon je nezávislý na délce dat. Kromě toho se paměťová složitost v obou reprezentacích odhaduje na O(n). Abych to shrnul, smyčky jsou preferovány, když jsou šňůry velmi dlouhé a často se mění.

Také

  • Softwarové prostředí Cedar , které používá závěsy „téměř od jejich počátku“ [1]
  • Model T enfilade , podobná datová struktura z počátku 70. let.
  • Buffer window , datová struktura používaná v textových editorech, která umožňuje efektivní vkládání a mazání blízko umístěných dat.
  • Piecewise table , další datová struktura používaná v textových editorech.

Poznámky

  1. ↑ 1 2 3 4 5 Boehm, Hans-J; Atkinson, Russ; Plass, Michael (prosinec 1995). Lana: Alternativa k strunám . Software – praxe a zkušenosti . New York, NY, USA: John Wiley & Sons, Inc. 25 (12): 1315-1330. DOI : 10.1002/spe.4380251203 . Archivováno z originálu ( PDF ) dne 2020-03-08. Použitý zastaralý parametr |url-status=( nápověda )
  2. ↑ 1 2 Přehled implementace lana . www.sgi.com . Získáno 1. března 2017. Archivováno z originálu 19. prosince 2017.

Odkazy