Aho-Corasick, kód v AS3

Ve dnešním díle si ukážeme způsob implementace algoritmu Aho-Corasickové. Používá se pro vyhledávání slov v textu a je velmi rychlý oproti ostatním běžným metodám. Podobně se dá implementovat jazycích C, C++, C#, Java a dalších.

Algoritmus Aho-Corasick

Tento algoritmus lze rozdělit do 2 kroků:

1. stavba konečného automatu
   • výstavba trie z hledaných slov
   • konstrukce zpětné hrany pro každý uzel
2. průchod automatem - čtení textu po znacích, ukládání výsledků

V příkladu výše máme ve trii slova "depo", "sedět", "posed", "seno", "se". Prohledávaný text je v políčku dole. Pokud v nějakém kroku najdu hledaná slova (v jednom místě může končit více slov), rozsvítí se jejich koncová písmena.

Implementace

Trie

Stavbu trie jsme si již ukázali v předchozím článku o Trii. Pro náš účel si do ní přidáme 5 dalších položek:

   // ukazatel na předka a zpětná hrana
   public var parent:TNode;
   public var fall:TNode;
   // nějaké údaje pro snazší kreslení
   public var x:Number;
   public var y:Number;
   public var width:Number;

Konstrukce zpětných hran

Pro konstrukci zpětných hran (pointer "fall") musíme prohledávat trii do šířky a potřebujeme frontu. Já jsem použil frontu z balíčku AS3DS od PolygonLabs (proměnná "q").

function MakeFallFunctions():void
{
   trie.fall = trie; // zpětná hrana z kořene je kořen
   q.enqueue(trie);  // přidám do fronty kořen
   while (q.size != 0) // prohledávám do šířky
   {
      var n:TNode = q.dequeue();
      var no:TNode;
      var i:int;
      for (i = 0; i < 4; i++) // naházím potomky do fronty
      {
         no = n.cn[i];
         if (no == null) continue;
         while (no.next != null) { q.enqueue(no); no = no.next; }
         q.enqueue(no);
      }
      if (n == trie) continue; // kořen už má zpětnou hranu
      // od předka jdu po zpětných hranách než najdu pokračování
      // nebo dojdu do kořene
      var fall:TNode = n.parent.fall;
      while (fall.GetChild(n.c) == null && fall != trie) fall = fall.fall;
      // když najdu pokračování, do nastavím do fall
      n.fall = fall.GetChild(n.c);
      if (n.fall == null) n.fall = trie; // není pokračování
      if (n.fall == n) n.fall = trie;
   }
}

Prohledávání - průchod automatem

function Prohledávej(e:MouseEvent):void
{
   var text:String = "V tomhle textu budu prohledávat.";
   var cState = trie; // aktuální stav
   var n:TNode;       // pomocné uzly
   var no:TNode;
   var b:String;      // písmeno, které čteme
   for(var i:int=0; i < text.length; i++)
   {
      n = cState;
      b = text.charAt(i);
      
      // jedu po zp. hranách, než najdu pokračování
        while (n.GetChild(b) == null && n != trie) n = n.fall;
      
      // když jsem se dostal do kořene
        if (n == trie)
        {
            n = n.GetChild(b);
            if (n == null) n = trie;
        }
        else n = n.GetChild(b); // našel jsem pokračování
      
      no = n; // jedu po fallech do kořene, tím projdu všechny přípony
      while(no!= trie)
      {
         if(no.isEnd){/* právě jsem našel slovo, co končí v "no"*/}
         no=no.fall;
      }
      cState = n;
   }
}

Lineární složitost algoritmu

Při vysvětlování nebudu uvažovat složitost hlášení nalezených slov. Jen dodám, že jde vyřešit v konstantním čase.

Nechť prohledávaný text má $n$ znaků. Při hledání děláme buď pohyby "dolů" - na další písmeno, nebo "nahoru" - po zpětné hraně. S každým písmenem se pohneme max. jednou dolů. Počet pohybů "dolů" je max. $n$.

Abychom mohli udělat několik pohybů nahoru (po zpětných hranách), musíme nejdříve udělat aspoň stejně tolik pohybů dolů (abychom byli v patřičné "hloubce"). Počet pohybů nahoru tedy nikdy nepřekročí počet pohybů dolů. Celkový počet pohybů (nahoru i dolů) během celého výpočtu nikdy nepřekročí $2n$, algoritmus tedy má lineární složitost $O(n)$.

Závěr

Aho-Corasickovou jsem původně programoval v C#, teď jsem ten kód jen přepsal do AS3. Tento algoritmus se v AS3 nikdy neprogramuje, jelikož když hledáme málo prvků v krátkém textu, vystačíme si se String.indexOf("..."). Pokud hledáme hodně prvků ve velkém textu, nepoužijeme Flash, ale efektivnější nástroj, např. unixový program grep. Tento článek má spíše sloužit jako ilustrace a nástřel k implementaci Aho-Corasickové v jiných jazycích.