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.

2 komentářů:

  1. Petr Neudek ... (3. května 2018 0:14)

    Hezky zpracované - ostatně jako asi všechno, ale zatím jsem všechno neprošel. Hodím spíš téma co zpracovat problematiku Aho-Corasic metody pomocí sofistikovanější metody BruteForce.
    Zde je konečná enumerace n! krát p(n). Raději slovy faktoriál krát partition "n". Faktoriál i partition (správně Partition Numerorum - PN) jsou sice neúměrně rostoucí, ale lze při generování využít existence jednotlivých dvojic, takže buď Combin(n,2), nebo ekvivalent (n^2 - n)/2 pro test existence dvojic podle které vyloučíme už při generování faktoriálu řádek - vylučujeme ale variaci - těch je 2x více. Názorně vyloučení dvojice 12 :
    3!.....PN(3,1).......PN(3,2).....PN(3,1)...Existuje
    123....[12]3.........12-3........1-2-3.....NE (12)
    132....132...........13-2........1-3-2
    213....[21]3.........21-3........2-1-3.....NE (21)
    231....231...........23-1........2-3-1
    312....3[12].........31-2........3-1-2.....NE (12)
    321....3[21].........32-1........3-2-1.....NE (21)
    Zůstanou 2 ze 6-ti možností. Je to návod podobný s problémem obchodního cestujícího ve všech variantách. Například se změří existující vzdálenost a doplní do modelu ořezaného faktoriálu :
    1231 [12]+[23]+[31]
    1321 [13]+[32]+[21]
    2132 [21]+[13]+[32]
    2312 [23]+[31]+[12]
    3123 [31]+[12]+[23]
    3213 [32]+[21]+[13]
    Vidíme že jde o start i cíl ve stejném bodě a stačí sečíst vzdálenosti mezi body - variace dvojice AB - BA reprezentuje dvousměrnou průchodnost (jednosměrku) která možnosti vylučuje stejně jako neexistence vazby AB v řádu kombinací. Stačí generovat faktoriál a hned sčítat s podmínkou menšího součtu.
    Samozřejmě generujeme čísla a provádíme substituci vzdáleností. Problém je v algoritmu pro množinu faktoriál - to se dá vyřešit celkem pohodlně (i když třeba běžný komp nedá ani pouhý počet pro 100!). Když se do toho zamontuje ještě PN tak je dvojnásobná složitost. Při tom například PN(100) je více než 190 milionů, ale řeší se reálně většinou jen jedna třída z "n" tříd ("k"). PN(100) je zajímavé pro statistiku protože 100 reprezentuje procenta - a tím také určitou možnost aproximace. Ale dá se tak řešit například rozvržení jízdních řádů (tras a časů) místní dopravy, nebo rajóny pošťovních doručovatelů .....

  2. Petr Neudek ... (3. května 2018 0:27)

    Utekla mi chybička. V nadpisech příkladu PN(3)*3! má být poslední nadpis sloupce PN(3,3) místo PN(3,1). U těch tříd PN(n) jde o můj výraz "třída". Takže správně zápis PN(n,k=n). Raději zase názorně PN(4):
    PN(4,1)....4
    PN(4,2)....3+1, 2+2
    PN(4,3)....2+1+1
    PN(4,4)....1+1+1+1

Okomentovat