Anatree

Ett anaträd är en datastruktur utformad för att lösa anagram . Att lösa ett anagram är problemet med att hitta ett ord från en given bokstäverlista. Dessa problem uppstår ofta i ordspel som Scrabble eller i tidningskorsord . Problemet för ordhjulet har också villkoret att den centrala bokstaven förekommer i alla ord som ramas in med den givna uppsättningen. Vissa andra villkor kan införas beträffande frekvensen (antal uppträdanden) för var och en av bokstäverna i den givna inmatningssträngen. Dessa problem klassificeras som Constraint satisfaction problem i datavetenskaplig litteratur.

Ett anaträd representeras som ett riktat träd som innehåller en uppsättning ord (W) kodade som strängar i något alfabet . De inre hörnen är märkta med någon bokstav i alfabetet och bladen innehåller ord. Kanterna är märkta med icke-negativa heltal. Ett anaträd har egenskapen att summan av kantetiketterna från roten till bladet är längden på ordet som lagras vid bladet. Om de interna hörnen är märkta som $\alpha _{1}$ , $\alpha _{2}$ ... $\alpha _{l}$ , och kantetiketter är $n_{1}$ , $n_{2}$ ... $n_{l}$ , sedan vägen från roten till bladet längs dessa hörn och kanter är en lista med ord som innehåller $n_{1}$ $\alpha _{1}$ s, $n_{2}$ $\alpha _{2}$ s och så vidare. Anatrees är avsedda att vara läsbara datastrukturer med alla ord som är tillgängliga vid byggtiden.

Blandat anaträd

Ett blandat anaträd är ett anaträd där de inre hörnen också lagrar ord. Ett blandat anaträd kan ha ord av olika längd, där som i ett vanligt anaträd är alla ord lika långa.

Data struktur

Ett antal datastrukturer har föreslagits för att lösa anagram i konstant tid. Två av de mest använda datastrukturerna är den alfabetiska kartan och frekvenskartan.

Den alfabetiska kartan upprätthåller en hashtabell över alla möjliga ord som kan finnas i språket (detta kallas lexikonet ) . För en given inmatningssträng, sortera bokstäverna i alfabetisk ordning. Denna sorterade sträng mappas till ett ord i hashtabellen. Att hitta anagrammet kräver därför att man sorterar bokstäverna och slår upp ordet i hashtabellen. Sorteringen kan göras i linjär tid med räknande sortering och hashtabellsökningar kan göras i konstant tid. Till exempel, givet ordet ANATREE, skulle den alfabetiska kartan producera en mappning av $\displaystyle \{AAEENRT->\{'' anatree''\}\}}$ .

En frekvenskarta lagrar också listan över alla möjliga ord i lexikonet i en hashtabell. För en given inmatningssträng bibehåller frekvenskartan frekvenserna (antal uppträdanden) för alla bokstäver och använder detta antal för att göra en uppslagning i hashtabellen. Den värsta exekveringstiden visar sig vara linjär i storleken på lexikonet. Till exempel, givet ordet ANATREE, skulle den alfabetiska kartan producera en mappning av $f(A)->2,f(E)->2,f(N)->1,f(R)->1,f(T)->1$ . De ord som inte förekommer i strängen skrivs inte i kartan.

Konstruktion

Konstruktionen av ett anaträd börjar med att välja en etikett för roten och partitionera ord baserat på etiketten som valts för roten. Denna process upprepas rekursivt för alla etiketter i trädet. Anatree-konstruktionen är icke-kanonisk för en given uppsättning ord, beroende på etiketten som väljs för roten, kommer anaträdet att skilja sig åt. Prestandan hos anaträdet påverkas kraftigt av valet av etiketter.

Följande är några heuristik för att välja etiketter:

Börja märka hörn i alfabetisk ordning från roten. Detta tillvägagångssätt minskar byggkostnader
Börja märka hörn baserat på den relativa frekvensen. Ett probabilistiskt tillvägagångssätt används för att tilldela etiketter till hörn. Om $W_{n}^{\alpha }$ är den uppsättning ord som innehåller $n\alpha s$ , då märker vi vertexet med $\alpha$ om det maximerar det förväntade avståndet till bladet. Detta tillvägagångssätt har de vanligast förekommande tecknen (som E) märkta vid roten och de minst ofta förekommande tecknen märkta vid bladen. Följande ekvation är maximerad $D_{\alpha }=\sum _{n}n{\frac {|W_{n}^{\alpha }|}{|W|}}$ . Detta tillvägagångssätt förhindrar långa sekvenser av nollmärkta kanter eftersom de inte bidrar med bokstäver till orden som genereras av anaträdet.

Hitta anagram

För att hitta ett ord i ett anaträd, börja vid roten, beroende på frekvensen av etiketten i den givna inmatningssträngen, följ kanten som har den frekvensen till bladet. Bladet innehåller det önskade ordet. Betrakta till exempel anaträdet i figuren, för att hitta ordet $dog$ , kan den givna strängen vara $ogd$ . Börja vid roten och följ kanten som har $1$ som etikett. Vi följer denna etikett eftersom den givna inmatningssträngen har $1$ $d$ . Passera denna kant tills bladet påträffas. Det ger ordet som krävs.

Utrymme och tidskrav

Ett lexikon som lagrar $w$ ord (varje ord kan vara $l$ tecken långt) i ett alfabet $O$ har följande utrymmeskrav.

Datastruktur	Utrymmeskrav
Alfabetisk karta	$O(wl(log\|O\|)$
Frekvenskarta	$O(w(\|O\|logl+llog\|O\|))$
Anatree	$O(w\|O\|(log\|O\|+l))$

Den värsta exekveringstiden för ett anaträd är $O(|w|(l+w|O|^{2}))$

externa länkar