Předponový strom

Prefix tree (také bore [1] , ray [2] , loadovaný strom [3] , anglicky trie [4] ) je datová struktura , která umožňuje uložit asociativní pole , jehož klíče jsou řetězce. Je to zakořeněný strom , jehož každá hrana je označena nějakým symbolem, takže pro jakýkoli uzel jsou všechny hrany spojující tento uzel s jeho syny označeny různými symboly. Jsou vybrány některé uzly stromu prefixů (na obrázku jsou podepsány čísly) a má se za to, že strom prefixů obsahuje daný řetězec-klíč tehdy a jen tehdy, pokud lze tento řetězec číst na cestě od kořene k nějaké ( jediný pro tento řetězec) vybraný uzel. V některých aplikacích je vhodné považovat všechny uzly stromu za vybrané.

Na rozdíl od binárních vyhledávacích stromů tedy klíč, který identifikuje konkrétní uzel ve stromu, není explicitně uložen v tomto uzlu, ale je dán pozicí tohoto uzlu ve stromu. Klíč získáte vypsáním znaků v řadě, které označují hrany na cestě od kořene k uzlu. Kořenový klíč stromu je prázdný řetězec. Vyhrazené uzly často ukládají dodatečné informace spojené s klíčem a obvykle jsou vyhrazeny pouze listy a možná některé interní uzly.

Operace se stromem předpon

Ve stromu předpon jsou tři hlavní operace: kontrola, zda klíč ve stromu existuje, odstranění klíče ze stromu a vložení nového klíče (možná s dalšími souvisejícími informacemi). Každá z těchto operací je implementována sestupem stromu z kořene, ale účinnost takové operace přímo závisí na organizaci navigace přes uzly. Pro následnou analýzu různých přístupů k tomuto problému si označme délku řetězce, který je požadován/mazán/vkládán, a označme velikost abecedy , tedy počet různých znaků na okrajích daného stromu prefixů. . Nechť má tento uzel syny (s ). Označte odkazy na tyto syny a symboly, které označují hrany spojující s odpovídajícími syny. $n$ $\sigma$ $X$ $k$ $k\leq \sigma$ ${\displaystyle x_{1},x_{2},\ldots ,x_{k))$ ${\displaystyle a_{1},a_{2},\ldots ,a_{k))$ $X$

Nejjednodušší způsob, jak uspořádat navigaci, je uložit dynamické pole . S tímto přístupem jsou všechny tři operace prováděny v . Pokud se nepoužívá vkládání a mazání, je lepší seřadit páry podle klíče a poté lze operaci kontroly přítomnosti klíče ve stromu prefixů provést pomocí binárního vyhledávání v uzlech. $X$ $(a_{i},x_{i})$ $O(n\sigma )$ $a_{i}$ $O(n\log \sigma )$
Je možné dosáhnout doby provádění pro všechny tři operace uložením dvojic seřazených podle klíče v nějakém vyváženém binárním vyhledávacím stromu , jako je červeno-černý strom nebo AVL strom . Ve většině programovacích jazyků je implementace jakéhosi vyváženého vyhledávacího stromu součástí standardní knihovny ve formě asociativního pole . $O(n\log \sigma )$ $(a_{i},x_{i})$ $a_{i}$
Dalším oblíbeným způsobem, jak organizovat navigaci, je ukládat páry podle klíče do hashovací tabulky . S tímto přístupem jsou všechny tři operace dokončeny v očekávaném čase (zatímco dvě předchozí možnosti mají garantovanou dobu provedení). V mnoha programovacích jazycích jsou hashovací tabulky součástí standardní knihovny. Záruky načasování můžete dále zlepšit nahrazením hashovací tabulky kukaččím hashem nebo podobnou strukturou: takový hash umožňuje dotazování a mazání klíčů v garantovaném čase a pouze vložení proběhne v očekávaném čase . $X$ $(a_{i},x_{i})$ $a_{i}$ $Na)$ $Na)$ $Na)$

Komprimovaný strom předpon

Zvažte strom předpon obsahující všechny přípony řetězce délky . Tento strom má alespoň uzlů a zabírá tak paměť. V tomto příkladu je tato nehospodárná spotřeba paměti způsobena velkým počtem uzlů pouze s jedním potomkem. Pro boj s tímto problémem vyvinul Donald Morrison [5] modifikaci stromu prefixů, nazvanou komprimovaný strom prefixů (existují také možnosti kompaktní strom předpon, základní strom , stlačený otvor , kompaktní otvor , stlačený nosník , stlačený zatížený strom ; Morrison sám [5] nazval jeho strukturu "strom PATRICIA" a tento název se stále někdy vyskytuje). ${\textstyle \underbrace {aa\cdots a} _{k{\text{ times}}}b\underbrace {aa\cdots a} _{k{\text{ times}}}b}$ $n=2k+2$ $k^{2}=\Theta (n^{2})$ $\Theta (n^{2})$

Definice a způsoby ukládání

Komprimovaný strom prefixů obsahující dané řetězce je minimální strom z hlediska počtu uzlů, jehož každá hrana je označena neprázdným řetězcem (a nikoli symbolem, jako v běžném stromu prefixů), takže jakýkoli řetězec může být načten na cestě od kořene k některému (vybranému) uzlu a pro jakýkoli uzel jsou první znaky na všech štítcích na okrajích podřízeného uzlu různé. Například komprimovaný strom předpon zobrazený na obrázku obsahuje osm slov ruského jazyka a pouze listy jsou v něm vybrané uzly. ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $s_{i}$

Komprimovaný strom prefixů se získá z běžného stromu prefixů obsahujícího klíče postupným mazáním každého uzlu (kromě kořene), který má pouze jednoho syna a není vybrán, zatímco otec a syn mazaného uzlu jsou spojeni a výsledná hrana je označené řetězcem získaným spojením štítků na hranách nadřazeného uzlu a uzlového syna (ačkoli tato metoda vytváření komprimovaného stromu prefixů se nedoporučuje ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ [ kým? ] ).

Efektivita komprimovaného stromu prefixů vychází ze způsobu, jakým jsou reprezentovány popisky hran. Protože každý štítek je podřetězcem nějakého řetězce , lze jej reprezentovat pomocí trojice čísel , kde (zde označuje podřetězec řetězce začínající na pozici a končící na pozici ). Pokud jsou všechny řetězce podřetězci jednoho daného řetězce , pak mohou být štítky reprezentovány dvojicemi čísel odpovídajících podřetězcům . Navigace v uzlech je organizována stejným způsobem jako v obvyklém stromu prefixů, ale první znaky v popiscích na hranách uzlu-son slouží jako referenční znaky: například v komprimovaném stromu prefixů na obrázku uzel odpovídající k řetězci "west" má tři syny a referenční symboly v tomto uzlu jsou "i", "n", "b", což jsou první znaky ve štítcích "ib", "nick", "b" na okraje uzlu-son. Lze ukázat, že komprimovaný strom prefixů pro sadu řetězců nemá celkem více než uzlů a zabírá tedy paměť, kromě paměti potřebné k uložení samotných řetězců . $t$ ${\displaystyle s_{h))$ $t$ $(h,i,j)$ $s_{h}[i..j]=t$ $s_{h}[i..j]$ ${\displaystyle s_{h))$ $i$ $j$ ${\displaystyle s_{h))$ $s$ $(i,j)$ $s[i..j]$ ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $2k$ $OK)$ ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$

Operace na komprimovaném stromu předpon

Operace dotazování, mazání a vkládání na komprimovaném stromu předpon lze provádět stejným způsobem jako na běžném stromu předpon sestupem z kořene. V tomto případě se algoritmus poněkud zkomplikuje kvůli nutnosti číst obsah štítku z odpovídajícího podřetězce jednoho z řetězců při sestupu podél okrajů označených řetězci o délce dva nebo více . Teoreticky lze dobu běhu takového algoritmu odhadnout stejným způsobem jako u běžného stromu prefixů (tedy jako , , v závislosti na organizaci navigace v uzlech), ale v praxi se často operace na komprimovaném stromu prefixů se ukázaly být rychlejší díky skutečnosti, že většina cesty z kořene do uzlu vede podél okrajů a není potřeba často odkazovat na datové struktury v uzlech. ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $O(n\sigma )$ $O(n\log \sigma )$ $Na)$

Pokud jsou délky všech řádků relativně malé (například v rámci délky jednoho řádku mezipaměti , což je u mnoha moderních procesorů 64 bajtů), lze se vyhnout chybám mezipaměti způsobeným častými skoky mezi různými štítky pomocí jiné metody sestupu stromu ( právě tato metoda byla popsána v Morrisonově článku [5] ). Zvažte například algoritmus pro nalezení nejdelšího prefixu daného řetězce , který lze číst na cestě od kořene k některému uzlu v daném komprimovaném stromu prefixů; ostatní operace mohou být implementovány analogicky. $s_{i}$ $t$

Algoritmus spočívá v prvním průchodu dotazem pouze na uzly stromu, přeskočením hran, a tak sestupem co nejníže ve stromu najít řetězec z množiny , který má nejdelší společnou předponu s řetězcem . Poté musíte vypočítat společnou předponu a obvyklý naivní algoritmus a vrátit výsledek. V níže uvedeném pseudokódu podobném C znamená s[i] řetězec , kořen kořen stromu a každý uzel x obsahuje následující pole/metody: x->len je délka štítku na okraji od x k otci x; x->child(c) je odkaz na potomka uzlu x spojeného s x hranou se štítkem začínajícím na c, nebo nullptr, pokud takový syn neexistuje; x->src je takové číslo, že řetězec na cestě od kořene k x je předponou řetězce . $s_{i}$ ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $t$ $t$ $s_{i}$ $s_{i}$ ${\displaystyle s_{x{-}{>}src))$

size_t find_longest_prefix ( string t ) { struct node_t * x = root ; for ( size_t i = 0 ; i < t . length (); i += x -> len ) if ( x -> dítě ( t [ i ]) != nullptr ) x = x -> dítě ( t [ i ]); jinak zlomit ; návratová délka společné předpony t a s [ x -> src ]; }

Aplikace

Struktura je široce používána ve vyhledávacích algoritmech a dalších aplikacích.

Strom prefixů se používá v algoritmu Aho-Korasik k hledání více řetězců v daném řetězci.
Strom prefixů se také používá v algoritmu Lempel-Ziv-Welch .
Komprimovaný strom předpon obsahující všechny přípony daného řetězce se nazývá strom přípon a hraje klíčovou roli ve vyhledávacích algoritmech.
Komprimovaný strom předpon se používá zejména pro analýzu přirozených jazyků [6] .
Komprimovaný strom předpon je jednou z datových struktur linuxového jádra [7] .

Poznámky

↑ V prvním překladu Knuthovy monografie.
↑ V dalších překladech Knuthovy monografie.
↑ Aho, Hopcroft, Ulman, 2003 , str. 152.
↑ Fredkin, 1960 .
↑ 1 2 3 Morrison, 1968 .
↑ Pymorphy 2 https://habrahabr.ru/post/176575/ Archivovaná kopie z 24. srpna 2017 na Wayback Machine
↑ Robert Love. Vývoj jádra Linuxu. třetí edice. 2010.

Literatura

Knut D. E. Umění programování. Svazek 3. Třídění a vyhledávání = The Art of Computer Programming. Svazek 3. Třídění a vyhledávání / ed. V. T. Tertyshny (5. kap.) a I. V. Krasikov (6. kap.). - 2. vyd. - Moskva: Williams, 2007. - T. 3. - 832 s. — ISBN 5-8459-0082-1 .
Aho A. V. , Hopcroft J. E. , Ulman J. D. Datové struktury a algoritmy = Data Structures and Algorithms / ed. S. N. Triguba ; za. z angličtiny. A. A. Minko . - M. : Williams, 2003. - 384 s. — ISBN 5-8459-0122-7 .
Crochemore M. , Rytter W. Klenoty stringologie. Singapur: World Publishing Scientific Co. Pte. Ltd., 2002. - 306 s. — ISBN 981-02-4782-6 .
Fredkin E. Trie Memory // Komunikace ACM . - 1960. - V. 3 , č. 9 . — S. 490–499 . - doi : 10.1145/367390.367400 .
Praktický algoritmus Morrison DR pro získávání informací kódovaných v alfanumerickém // Journal of the ACM . - 1968. - T. 15 , č. 4 . — S. 514–534 . - doi : 10.1145/321479.321481 .

Odkazy

Bentley, John; Sedgewick, Robert (1998-04-01). "Ternární vyhledávací stromy" . Dr. Dobb's Journal (Dr Dobb's). Archivováno z originálu 2008-06-23.
Algoritmy a datové struktury Výzkum a referenční materiál: Tries Archivováno 6. března 2013 na Wayback Machine , Lloyd Allison, Monash University.
Algoritmy a datové struktury Výzkum a referenční materiál: PATRICIA Archivováno 22. května 2018 na Wayback Machine , Lloyd Allison, Monash University.
Patricia Tree archivována 30. prosince 2017 na Wayback Machine , NIST Dictionary of Algorithms and Data Structures.
Crit-bit trees Archivováno 31. prosince 2007 na Wayback Machine , Daniel J. Bernstein.
Radix Tree API v linuxovém jádře Archivováno 8. listopadu 2020 na Wayback Machine od Jonathana Corbeta.
Kart (key alteration radix tree) Archivováno 7. srpna 2008 na Wayback Machine , Paul Jarc .

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree

Struny
Míry podobnosti řetězců	Vzdálenost Damerau - Loewenstein Levenshteinská vzdálenost Hammingova vzdálenost Podobnost Jaro-Winkler
Hledání podřetězců	Boyer-Mooreův algoritmus Algoritmus Boyer-Moore-Horspool Knuth-Morris-Prattův algoritmus Rabin-Karpův algoritmus funkce předpony Z-funkce Algoritmus Aho - Korasik
palindromy	palindromový strom Manažerův algoritmus
Sekvenční zarovnání	Algoritmus Needleman-Wunsha Smith-Watermanův algoritmus
Struktury přípon	Pole přípon Přípona automat příponový strom předponový strom
jiný	rozebrat Shoda vzorů Největší společná podsekvence Největší společný podřetězec