Trie v AS3

Dnes se ve flashi pokusíme implementovat datovou strukturu Trie. Kromě samotné trie ji navíc nějak hezky vykreslíme, abychom dostali přehledné znázornění této struktury.

Něco o Trii

Řekněme, že náš program dostane tisíc slov, která musíme uložit do nějaké struktury. Poté nám budou chodit dotazy, zda naše struktura obsahuje konkrétní slovo. Uložení prvku do lineárního pole by bylo paměťově náročné, zároveň při hledání slova bychom museli projít všechny prvky. Trie je na tom o mnoho lépe. Sice přidání slova není tak rychlé jako u pole, ale hledání je výrazně rychlejší. Pokud v každém uzlu uchováváme pole o velikosti celé abecedy, jdeme od kořene přímo k listu, složitost je rovná délce slova. Více ve článku na Wikipedii.

Třída TNode

Co od trie chci

Chci si trii snadno vytvářet (var trie = new ...), snadno přidávat slova (trie.AddWord("ahoj");). Chci snadno zjišťovat, zda obsahuje nějaké slovo (if(trie.Contains("ahoj")) ...).

Jak ukládat potomky uzlu

Každý uzel ve trii může mít potomků od 0 až do velikosti abecedy. Abecedy jsou často velké (26 - písmena ang. abecedy, 256 - ASCII znaky, $2^{16}, 2^{24}, 2^{32}$ - znaky Unicode atd.). Avšak uzel většinou neobsahuje všechny tyto potomky. Paměťově efektivnější použít nějaké menší pole pevné velikosti, do kterého budeme prvky hešovat. Níže ukládám prvek na pozici (kód znaku) modulo 4. Kolize řeším vytvářením spojového seznamu.

Základní třída

package
{
   public class TNode
   {
      // pole 4 potomků tohoto uzlu
      public var cn:Vector. = new Vector.(4, true);
      public var c:String;   // znak uložený v uzlu
      public var next:TNode; // ukazatel na další prvek na stejné úrovni
      public var isEnd:Boolean = false; // zda je uzel koncem slova
  
      public function TNode(c:String):void
      {
         this.c = c; // přiřadím znak do "c"
      }
   }
}

Vyhledání potomka pro daný znak

Jelikož potomky máme v poli pevné velikosti a navíc ve spojových seznamech, není jejich vyhledání úplně triviální, proto si raději napíšeme metodu.

public function GetChild(s:String):TNode
{
   // nejdříve se podíváme do pole
   var n:TNode = cn[ s.charCodeAt(0)% 4 ];
   if ( n == null) return null; // nebyl v poli
   else    // byl v poli, hledáme ve spojáku
      while (n.next != null)  
      {
         if (n.c == s) return n;
         n = n.next;
      }
   if (n.c == s) return n; // byl na konci spojáku
   return null; // nebyl nikde
}

Přidání slova do trie

Nejdříve si přečteme první znak slova. Buď pro tento znak už máme potomka, nebo ne (potom ho vytvoříme). Tomuto potomku sdělíme mu, aby si přidal zbytek slova.

public function AddWord(s:String):void
{
   // podíváme se, zda nemáme potřebného potomka
   var n:TNode = GetChild(s.charAt(0));
   if(n==null) // nemáme
   {
      n = new TNode(s.charAt(0)); // vytvoříme ho
      var pos:int = s.charCodeAt(0)% 4; // kam ho dáme
      if(cn[pos] == null) cn[pos] = n;  // místo je volné
      else // není volné - dáme do spojáku
      {
         var no:TNode = cn[ pos ];
         while(no.next != null) no = no.next;
         no.next = n;
      }
   }
   // když není konec slova, přidáme zbytek do "n"
   if(s.length>1) n.AddWord(s.substring(1,s.length));
   else n.isEnd = true; // konec slova
}

Zda trie obsahuje slovo

public function Contains(s:String):Boolean
{
   // když jsme na dně rekurze, vrátíme "isEnd"
   if(s.length == 0) return isEnd;
   // podíváme se na potomka s daným znakem
   var n:TNode = GetChild(s.charAt(0));
   if(n==null) return false; // potomek není
   else return n.Contains(s.substring(1,s.length)); // potomek je
}

Vykreslení trie

Trii vykreslujeme podobným způsobem, jako Binární vyhledávací strom.

function vykresli(n:TNode, x:int, y:int, w:int, place:Sprite)
{
   var i:int;
   // potomky uzlu si dám do nového pole
   var nodes:Array = new Array();
   for(i = 0; i<4; i++)
   {
      var no:TNode = n.cn[i]; if(no == null) continue;
      while(no != null){ nodes.push(no); no = no.next;}
   }
   var sW:int = w/nodes.length; // místo pro každý uzel
   for (i = 0; i < nodes.length; i++)
   {
      with(place.graphics)  // čára k potomkovi
      {
         lineStyle(3,0x00E1FF);
         moveTo(x, y);
         lineTo(x-w/2 + i*sW + sW/2, y+60);
      }
      // a vykreslení potomka
      vykresli(nodes[i], x-w/2 + i*sW + sW/2, y+60, sW, place); 
   }

   // nakreslíme kroužek pro daný uzel
   with(place.graphics)
   {
      if(n.isEnd) lineStyle(4, 0x000000); // když je koncový
      else lineStyle(2, 0x333333);  // když není - tenčí okraj
      beginFill(0x6D00D9);
      drawEllipse(x-14, y-14, 28, 28);
      endFill();
   }
 
   // přidáme textové pole s písmenkem
   var tf:TextField = new TextField();
   tf.text = n.c; tf.x = x-tf.textWidth; tf.y = y-14;
   place.addChild(tf);
}