Præfiks træ

Præfikstræ (også bore [1] , ray [2] , loaded tree [3] , engelsk  trie [4] ) er en datastruktur, der giver dig mulighed for at gemme et associativt array , hvis nøgler er strenge. Det er et rodfæstet træ , hvor hver kant er mærket med et eller andet symbol, så for enhver node er alle kanter, der forbinder denne node med dens sønner, mærket med forskellige symboler. Nogle noder i præfikstræet er valgt (de er fortegnet med tal i figuren), og det anses for, at præfikstræet indeholder en given streng-nøgle, hvis og kun hvis denne streng kan læses på stien fra roden til nogle ( den eneste for denne streng) valgte node. I nogle applikationer er det praktisk at betragte alle noder i et træ som udvalgte.

I modsætning til binære søgetræer er nøglen, der identificerer en bestemt knude i træet, ikke eksplicit gemt i den knude, men er givet af den pågældende knudes position i træet. Du kan få nøglen ved at skrive tegn i en række, der markerer kanterne på stien fra roden til noden. Trærodnøglen er en tom streng. Ofte gemmer dedikerede noder yderligere information knyttet til en nøgle, og typisk er kun blade og muligvis nogle interne noder dedikerede.

Handlinger på et præfikstræ

Der er tre hovedoperationer på et præfikstræ: at kontrollere om der findes en nøgle i træet, at slette en nøgle fra træet og indsætte en ny nøgle (måske med nogle yderligere relateret information). Hver af disse operationer implementeres ved at gå ned af træet fra roden, men effektiviteten af ​​en sådan operation afhænger direkte af organiseringen af ​​navigation gennem noderne. For den efterfølgende analyse af forskellige tilgange til dette problem, lad os angive længden af ​​den streng, der anmodes om/slettes/indsættes, og angive størrelsen af ​​alfabetet , det vil sige antallet af forskellige tegn på kanterne af det givne præfikstræ. . Lad denne node få sønner (med ). Betegn med henvisningerne til disse sønner og med symbolerne, der markerer kanterne, der forbinder med de tilsvarende sønner.

1. Den nemmeste måde at organisere navigation på er at gemme en dynamisk række . Med denne tilgang udføres alle tre operationer i . Hvis indsættelse og sletning ikke bruges, er det bedre at sortere parrene efter nøglen , og så kan operationen med at kontrollere tilstedeværelsen af ​​en nøgle i præfikstræet udføres ved hjælp af binær søgning i noderne.
2. Det er muligt at opnå udførelsestider for alle tre operationer ved at gemme par sorteret efter nøgle i et eller andet balanceret binært søgetræ , såsom et rød-sort træ eller et AVL-træ . I de fleste programmeringssprog er en implementering af en slags balanceret søgetræ inkluderet i standardbiblioteket i form af et associativt array .
3. En anden populær måde at organisere navigation på er at gemme par efter nøgle i en hash-tabel . Med denne tilgang afsluttes alle tre operationer inden for den forventede tid (mens de to foregående muligheder har en garanteret udførelsestid). I mange programmeringssprog er hashtabeller inkluderet i standardbiblioteket. Du kan yderligere forbedre timing-garantierne ved at erstatte hash-tabellen med en cuckoo-hash eller en lignende struktur: en sådan hash tillader, at nøgler kan forespørges og slettes inden for garanteret tid, og kun indsættelse finder sted inden for det forventede tidspunkt .

Komprimeret præfikstræ

Overvej et præfikstræ, der indeholder alle suffikser af en streng af længde . Dette træ har mindst noder og optager dermed hukommelse. I dette eksempel er dette spildende hukommelsesforbrug forårsaget af at have et stort antal noder med kun ét barn. For at bekæmpe dette problem udviklede Donald Morrison [5] en modifikation af præfikstræet, kaldet det komprimerede præfikstræ (der er også muligheder kompakt præfikstræ, basistræ , komprimeret boring , kompakt boring , komprimeret stråle , komprimeret belastet træ ; Morrison selv [5] kaldte dets struktur "PATRICIA-træ", og dette navn findes stadig nogle gange).

Definition og lagringsmetoder

Et komprimeret præfikstræ, der indeholder de givne strenge , er minimumstræet i form af antallet af noder, hvor hver kant er mærket med en ikke-tom streng (og ikke et symbol, som i et almindeligt præfikstræ), så enhver streng kan læses på stien fra roden til en (valgt) node, og for enhver node er de første tegn på alle etiketter på kanterne af den underordnede node forskellige. For eksempel indeholder det komprimerede præfikstræ vist i figuren otte ord i det russiske sprog, og kun blade er udvalgte noder i det.

Et komprimeret præfikstræ opnås fra et almindeligt præfikstræ, der indeholder nøgler , ved sekventielt at slette hver node (undtagen roden), der kun har én søn og ikke er valgt, mens far og søn til den node, der slettes, er forbundet, og den resulterende kant er mærket med en streng opnået ved at forbinde etiketter på forældre-node og node-søn-kanter (selvom denne metode til at bygge et komprimeret præfikstræ ikke anbefales[ af hvem? ] ).

Effektiviteten af ​​det komprimerede præfikstræ kommer fra den måde, kantetiketter er repræsenteret på. Da hver etiket er en understreng af en streng , kan den repræsenteres ved hjælp af en triplet af tal , hvor ( betegner her en understreng af strengen, der starter ved position og slutter ved position ). Hvis alle strenge er understrenge af en enkelt given streng , kan etiketter repræsenteres af talpar svarende til understrenge . Navigation i noderne er organiseret på samme måde som i det sædvanlige præfikstræ, men de første tegn i etiketterne på node-son-kanterne fungerer som referencetegn: for eksempel i det komprimerede præfikstræ i figuren, den tilsvarende node til strengen har "vest" tre sønner, og referencesymbolerne i denne node er "i", "n", "b", som er de første tegn i etiketterne "ib", "nick", "b" på kanter af knude-sønnen. Det kan vises, at et komprimeret præfikstræ for et sæt strenge ikke har mere end noder i alt og dermed optager hukommelse, bortset fra den nødvendige hukommelse til at gemme strengene selv .

Operationer på et komprimeret præfikstræ

Forespørgsel, slet og indsæt operationer på et komprimeret præfikstræ kan udføres på samme måde som på et almindeligt præfikstræ ved at gå ned fra roden. I dette tilfælde bliver algoritmen noget mere kompliceret på grund af behovet for at læse indholdet af etiketten fra den tilsvarende understreng af en af ​​strengene, når man går ned langs kanterne, der er markeret med strenge med længde to eller flere . Teoretisk set kan køretiden for en sådan algoritme estimeres på samme måde som for et almindeligt præfikstræ (det vil sige, som , , afhængigt af organisationen af ​​navigation i noder), men i praksis udføres operationer på et komprimeret præfikstræ ofte viser sig at være hurtigere på grund af det faktum, at det meste af stien fra roden til noden går langs kanterne, og der er ingen grund til ofte at henvise til datastrukturerne i noderne.

Hvis længderne af alle linjer er relativt små (f.eks. inden for længden af ​​en cachelinje , hvilket er 64 bytes på mange moderne processorer), så kan cache-misser forårsaget af hyppige spring mellem forskellige etiketter undgås ved at bruge en anden trænedstigningsmetode ( netop denne metode blev beskrevet i Morrisons papir [5] ). Overvej for eksempel en algoritme til at finde det længste præfiks for en given streng , der kan læses på stien fra roden til en knude i det givne komprimerede præfikstræ; andre operationer kan implementeres analogt.

Algoritmen består i den første omgang kun at udspørge træets noder, springe kanterne over, og dermed, så lavt som muligt i træet, finde den streng fra sættet , der har det længste fælles præfiks med strengen . Så skal du beregne det fælles præfiks og den sædvanlige naive algoritme og returnere resultatet. I den C -lignende pseudokode nedenfor angiver s[i] en streng , root angiver træets rod, og hver node x indeholder følgende felter/metoder: x->len er længden af ​​etiketten på kanten fra x til x's far; x->child(c) er en reference til barnet af node x forbundet til x med en kant med en etiket, der starter med c, eller nullptr, hvis der ikke er en sådan søn; x->src er et tal, således at strengen på stien fra roden til x er strengpræfikset .