Array ( [0] => 15514948 [id] => 15514948 [1] => cswiki [site] => cswiki [2] => Trie [uri] => Trie [3] => Trie representation.png [img] => Trie representation.png [4] => [day_avg] => [5] => [day_diff] => [6] => [day_last] => [7] => [day_prev_last] => [8] => [oai] => [9] => [is_good] => [10] => [object_type] => [11] => 1 [has_content] => 1 [12] => Trie, také známý jako prefikový strom, je datová struktura, která se používá především pro efektivní ukládání a vyhledávání řetězců, ať už se jedná o slova, jména nebo jakékoli jiné sekvence znaků. Tato struktura je jako robustní nástroj, který má výjimečnou schopnost zrychlit proces vyhledávání a manipulace s textem. Trie funguje na principu rozdělení textu do jednotlivých znaků, přičemž každý potomek představuje jeden znak ze slova. Tento hierarchický systém umožňuje snadno a rychle vyhledat všechny slova, která začínají na určitý prefix, což je velmi užitečné například v aplikacích pro autokompletaci nebo při vyhledávání v databázích. Jednou z největších výhod trie je efektivita přístupu k datům, která může učinit práci s velkými objemy textu mnohem plynulejší. Dále, díky tomu, že trie ukládá slova na základě jejich prefixů, existuje možnost sdílení společných částí a úspory paměti. I když existují i alternativní datové struktury, jako jsou hašovací tabulky nebo binární stromy, které mohou vykazovat dobré výsledky v určitých scénářích, trie přináší specifické výhody zejména v oblastech vyžadujících rychlé vyhledávání a manipulaci s textovými daty. Celkově lze říci, že trie je mocným nástrojem, který si našel své místo v oblasti informatiky a programování, a jeho použití je stále populární v mnoha moderních aplikacích, přičemž pokračuje v inspiraci díky své jednoduchosti a efektivitě. [oai_cs_optimisticky] => Trie, také známý jako prefikový strom, je datová struktura, která se používá především pro efektivní ukládání a vyhledávání řetězců, ať už se jedná o slova, jména nebo jakékoli jiné sekvence znaků. Tato struktura je jako robustní nástroj, který má výjimečnou schopnost zrychlit proces vyhledávání a manipulace s textem. Trie funguje na principu rozdělení textu do jednotlivých znaků, přičemž každý potomek představuje jeden znak ze slova. Tento hierarchický systém umožňuje snadno a rychle vyhledat všechny slova, která začínají na určitý prefix, což je velmi užitečné například v aplikacích pro autokompletaci nebo při vyhledávání v databázích. Jednou z největších výhod trie je efektivita přístupu k datům, která může učinit práci s velkými objemy textu mnohem plynulejší. Dále, díky tomu, že trie ukládá slova na základě jejich prefixů, existuje možnost sdílení společných částí a úspory paměti. I když existují i alternativní datové struktury, jako jsou hašovací tabulky nebo binární stromy, které mohou vykazovat dobré výsledky v určitých scénářích, trie přináší specifické výhody zejména v oblastech vyžadujících rychlé vyhledávání a manipulaci s textovými daty. Celkově lze říci, že trie je mocným nástrojem, který si našel své místo v oblasti informatiky a programování, a jeho použití je stále populární v mnoha moderních aplikacích, přičemž pokračuje v inspiraci díky své jednoduchosti a efektivitě. ) Array ( [0] => [[Soubor:Trie example.svg|náhled|Trie pro klíče „A“, „to“, „tea“, „ted“, „ten“, „i“, „in“ a „inn“]] [1] => [2] => '''Trie''' nebo '''prefixový strom''' je [[datová struktura]], která se používá pro uchovávání dvojic klíč-hodnota, kde [[index (databáze)|klíči]] jsou obvykle [[textový řetězec|řetězce]]. Na rozdíl od [[binární vyhledávací strom|binárního vyhledávacího stromu]], kde se podle hodnoty [[vrchol (graf)|uzlu]] rozhoduje, do které větve sestoupit, trie v každém uzlu obsahuje všechny podřetězce, kterými může pokračovat řetězec v dosud prohledané cestě. Všichni následníci uzlu mají společný [[prefix]], který je shodný s řetězcem přiřazeným k danému uzlu. [[Kořen (graf)|Kořen]] je asociovaný s prázdným řetězcem. Hodnoty obvykle nejsou asociovány se všemi uzly, ale jen s [[list (graf)|listy]] a některými vnitřními uzly, které odpovídají klíčům. [3] => [4] => Slovo ''trie'' pochází z anglického „re'''trie'''val“ – získávání, vyhledávání. [5] => [6] => V uvedeném příkladu jsou klíče v uzlech a hodnoty pod nimi. Na trie může být nazíráno jako [[konečný automat#Deterministické versus nedeterministické automaty|deterministický]] [[konečný automat]], ačkoli symbol na každé [[hrana (graf)|hraně]] je často implicitní v pořadí větví. [7] => [8] => Přestože je to obvyklé, trie nemusí mít jako klíče textové řetězce. Stejné algoritmy mohou být snadno upraveny, aby sloužily podobným funkcím na seznamech jakékoliv podoby, např. [[permutace]] na seznamu číslic, permutace na seznamu tvarů atd. [9] => [10] => == Výhody a nevýhody trie vzhledem k binárnímu vyhledávacímu stromu == [11] => Výhody oproti [[binární vyhledávací strom|binárnímu vyhledávacímu stromu]]: [12] => [13] => * Nalezení klíče je rychlejší. Nalezení klíče délky ''m'' trvá v nejhorším případě [[Asymptotická složitost|O(m)]]. BVS to trvá O(log n), kde ''n'' je počet prvků ve stromě, protože vyhledávání závisí na hloubce stromu, která je logaritmická v počtu klíčů. Jednoduché operace, které používá trie během vyhledávání, jako je indexování [[pole (datová struktura)|pole]] pomocí znaku, jsou v praxi rychlejší. [14] => * Trie potřebuje méně paměti, pokud obsahuje velký počet krátkých řetězců, protože klíče nejsou uchovávány explicitně, a uzly jsou tak sdíleny klíči se společnými začátky. [15] => * Trie pomáhají při hledání nejdelšího prefixu, kde je úkolem najít klíč sdílející nejdelší možný prefix unikátních znaků. [16] => Konstrukce trie, ať už dávková nebo postupným přidáváním, je implementačně trochu složitější než u binárního vyhledávacího stromu. To platí zvláště při použití optimalizací a optimalizovaných variant. [17] => [18] => == Užití == [19] => [20] => === Jako náhrada jiných datových struktur === [21] => Trie může nahradit [[hašovací tabulka|hašovací tabulku]], oproti které má následující výhody: [22] => [23] => * Vyhledání dat v trie je rychlejší v nejhorším případě, tj. O(m), oproti hašovací tabulce s [[kolize (informatika)|kolizemi]] O(N), typicky však O(1). [24] => * Nenastávají žádné kolize různých klíčů. [25] => * Datová struktura pro uchovávání kolizních klíčů je potřeba pouze v případě, že více hodnot má přiřazeno totožný klíč. [26] => * Není třeba [[hašovací funkce]] nebo její změna při přidávání dalších klíčů. [27] => * Trie může poskytnout abecední řazení záznamů podle klíče. [28] => [29] => Má také ale nevýhody: [30] => * Trie může být v některých případech pomalejší než hašovací tabulka při vyhledávání dat, zejména pokud je k nim přistupováno na [[pevný disk|pevném disku]] nebo podobných zařízeních, kde je doba náhodného přístupu velká vůči hlavní paměti. [31] => * Trie je často méně paměťově efektivní než hašovací tabulka. [32] => [33] => === Reprezentace slovníku === [34] => Častou aplikací trie je uložení [[slovník]]u, např. v [[mobilní telefon|mobilních telefonech]]. To využívá schopnosti trie rychle vyhledávat, vkládat a odstraňovat záznamy. [35] => [36] => Trie je také vhodné pro implementaci algoritmů přibližného matchování, jako jsou ty používané v programech pro kontrolu pravopisu. [37] => [38] => === Algoritmy === [39] => Následující pseudokód ukazuje obecný algoritmus zjišťující, jestli je daný řetězec v trie. Pole ''naslednici'' obsahuje následníky uzlu, koncový uzel je ten, který obsahuje platné slovo. [40] => function jeVTrie(uzel, klic): [41] => if (klic je prazdny retezec): # výchozí případ [42] => return je uzel koncový? [43] => else: #rekurzivní případ [44] => c = prvni znak v klici #funguje, protože klíč není prázdný [45] => sufix = klic minus prvni znak [46] => naslednik = uzel.naslednici[c] [47] => if (naslednik je prazdny): #nelze rekurze, ale klíč je neprázdný [48] => return false [49] => else: [50] => jeVTrie(naslednik, sufix) [51] => [52] => === Řazení === [53] => [[Lexikografické řazení]] skupiny prvků může být provedeno jednoduchým algoritmem založeným na trie: [54] => [55] => * Vlož všechny klíče do trie. [56] => * Vrať všechny klíče v trie [[Strom (datová struktura)#Proch.C3.A1zen.C3.AD stromem do hloubky|průchodem preorder]], který způsobí, že výstup je ve lexikograficky vzestupném pořadí, nebo [[Strom (datová struktura)#Proch.C3.A1zen.C3.AD stromem do hloubky|postorder]], díky němuž bude výstup v sestupném pořadí. Průchod preorder a postorder jsou dva druhy [[prohledávání do hloubky|průchodu do hloubky]]. [57] => [58] => Tento algoritmus je formou [[Číslicové řazení|číslicového řazení]]. [59] => [60] => Trie tvoří základní datovou strukturu [[burstsort]]u, v současné době nejrychlejšího známého [[řadicí algoritmus|algoritmu pro řazení řetězců]] založeném na využití [[cache]]. [61] => [62] => [[Paralelní algoritmus]] pro řazení N klíčů založený na trie je O(1), pokud je N procesorů a klíče mají konstantní horní omezení. Existuje možnost, že klíče mohou kolidovat tím, že mají společné prefixy, nebo jsou identické, což snižuje výhodu rychlosti zpracování více paralelně pracujícími procesory. [63] => [64] => === Fulltextové vyhledávání === [65] => K indexování všech sufixů v textu za účelem rychlého fulltexového vyhledávání může být použit speciální druh trie, [[sufixový strom]]. Dalším využitím může být hledání nejdelšího společného prefixu. [66] => [67] => == Odkazy == [68] => [69] => === Literatura === [70] => * {{Citace sborníku [71] => | jméno = R. [72] => | příjmení = de la Briandais [73] => | titul = File Searching Using Variable Length Keys [74] => | konference = Proceedings of the Western Joint Computer Conference [75] => | rok = 1959 [76] => | strany = 295–298 [77] => | doi = 10.1145/1457838.1457895 [78] => | ref = harv [79] => }} [80] => * {{Citace periodika [81] => | jméno = Edward [82] => | příjmení = Fredkin [83] => | titul = Trie Memory [84] => | periodikum = Communications of The ACM [85] => | ročník = 3 [86] => | číslo = 9 [87] => | strany = 490–499 [88] => | rok = 1960 [89] => | doi = 10.1145/367390.367400 [90] => | ref = harv [91] => }} [92] => * {{Citace monografie [93] => | jméno = Donald [94] => | příjmení = Knuth [95] => | odkaz na autora = Donald Ervin Knuth [96] => | titul = The Art of Computer Programming [97] => | svazek = 3: ''Sorting and Searching'' [98] => | vydání = 3 [99] => | vydavatel = Addison-Wesley [100] => | rok = 1997 [101] => | isbn = 0-201-89685-0 [102] => | kapitola = 6.3 [103] => | název kapitoly = Digital Searching [104] => | strany = 492–512 [105] => | ref = harv [106] => }} [107] => * {{Citace periodika [108] => | jméno = Jun-Ichi [109] => | příjmení = Aoe [110] => | jméno2 = Katsushi [111] => | příjmení2 = Morimoto [112] => | jméno3 = Takashi [113] => | příjmení3 = Sato [114] => | titul = An Efficient Implementation of Trie Structures [115] => | periodikum = Software—practice and experience [116] => | ročník = 22 [117] => | číslo = 9 [118] => | strany = 695–721 [119] => | datum = září 1992 [120] => | rok = 1992 [121] => | url = https://www.co-ding.com/assets/pdf/dat.pdf [122] => | ref = harv [123] => }} [124] => * {{Citace monografie [125] => | jméno = Cai-chun [126] => | příjmení = Gong [127] => | jméno2 = Yang [128] => | příjmení2 = Li [129] => | jméno3 = Shuo [130] => | příjmení3 = Bai [131] => | titul = An Efficient Double-Array Establishing Algorithm Based on Following-set [132] => | rok = 2007 [133] => | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.2699&rep=rep1&type=pdf [134] => | ref = harv [135] => }} [136] => [137] => === Externí odkazy === [138] => * {{Commonscat}} [139] => * [http://ivankuckir.blogspot.com/2010/11/trie-v-as3.html Animace trie ve flashi + implementace] [140] => * [https://web.archive.org/web/20071001002932/http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf Cache-Efficient String Sorting Using Copying] [141] => [142] => {{Stromy Inf}} [143] => {{Autoritní data}} [144] => [145] => [[Kategorie:Stromy (datové struktury)]] [] => )
good wiki

Trie

Trie pro klíče „A“, „to“, „tea“, „ted“, „ten“, „i“, „in“ a „inn“ Trie nebo prefixový strom je datová struktura, která se používá pro uchovávání dvojic klíč-hodnota, kde klíči jsou obvykle řetězce. Na rozdíl od binárního vyhledávacího stromu, kde se podle hodnoty uzlu rozhoduje, do které větve sestoupit, trie v každém uzlu obsahuje všechny podřetězce, kterými může pokračovat řetězec v dosud prohledané cestě.

More about us

About

Tato struktura je jako robustní nástroj, který má výjimečnou schopnost zrychlit proces vyhledávání a manipulace s textem. Trie funguje na principu rozdělení textu do jednotlivých znaků, přičemž každý potomek představuje jeden znak ze slova. Tento hierarchický systém umožňuje snadno a rychle vyhledat všechny slova, která začínají na určitý prefix, což je velmi užitečné například v aplikacích pro autokompletaci nebo při vyhledávání v databázích. Jednou z největších výhod trie je efektivita přístupu k datům, která může učinit práci s velkými objemy textu mnohem plynulejší. Dále, díky tomu, že trie ukládá slova na základě jejich prefixů, existuje možnost sdílení společných částí a úspory paměti. I když existují i alternativní datové struktury, jako jsou hašovací tabulky nebo binární stromy, které mohou vykazovat dobré výsledky v určitých scénářích, trie přináší specifické výhody zejména v oblastech vyžadujících rychlé vyhledávání a manipulaci s textovými daty. Celkově lze říci, že trie je mocným nástrojem, který si našel své místo v oblasti informatiky a programování, a jeho použití je stále populární v mnoha moderních aplikacích, přičemž pokračuje v inspiraci díky své jednoduchosti a efektivitě.

Expert Team

Vivamus eget neque lacus. Pellentesque egauris ex.

Award winning agency

Lorem ipsum, dolor sit amet consectetur elitorceat .

10 Year Exp.

Pellen tesque eget, mauris lorem iupsum neque lacus.

You might be interested in

,'binární vyhledávací strom','Strom (datová struktura)#Proch.C3.A1zen.C3.AD stromem do hloubky','sufixový strom','cache','burstsort','prohledávání do hloubky','Lexikografické řazení','Soubor:Trie example.svg','mobilní telefon','pevný disk','kolize (informatika)','datová struktura'

Cache