download-zdrojaky | download-zdrojaky+binarky

Dokumentace Aho-Corrasic + náhrada novými vzorky

Zadání (Specifikace):

Program má za úkol zpracovat vstupní text, tak že v něm vyhledá množinu zadaných vzorků (algoritmus Aho-Corrasic) a nahradí je vzorky (taktéž definovanými uživatelem). Nahrazení se provádí vždy odleva - vzorek, který začíná v textu nejvíce vlevo se nahradí a to i přesto, že končí později než nějaké jiné vzorky.

Konstanty

V programu nejsou využívány globální konstanty.

Implementace a datové struktury:

Program je napsán v jazyce C++. Použito je v něm několik tříd: GRAPH, STRING a VRCHOL. Metody zde nebudu příliš rozebírat, nejlepší dokumentací je v tomto případě zdrojový kód.

Parametry třídy GRAPH jsou:
VRCHOL* koren - tedy koren vyhledávacího automatu
VRCHOL** vrchol - seznam jednotlivých vrcholů v nějakém pořadí (např BFS)
int vrcholu - počet vrcholů grafu

Parametry třídy VRCHOL:
STRING* string - řetězec uložený ve vrcholu
STRING* novy - řetězec, kterým se má nalezené slovo nahradit, pokud takový vrchol je koncem slova
bool end - řetězec označuje celé slovo (bude se provádět náhrada)
VRCHOL* green, *back - odkazy na zpětné hrany v grafu a další nalezená slova

Třída STRING je prostinkou implementací datové struktury pro práci z řetězci - metody, které jsou pro algoritmus vyžadovány jsou nastavení hodnoty, přidání znaku na konec řetězce, a návratové poslední písmeno a hodnota řetězce. Z toho důvodu jsou parametry této třídy pouze:
char* val - hodnota řetězce
int len - délka řetězce

Algoritmus:

Algoritmus pro vyhledávání pracuje tak, že pro množinu hledaných vzorků sestrojí graf (automat). Automat pak dostává instrukce přímo ze vstupního souboru a podle toho se mění jeho stav. Automat tedy musí mít několik konstrukčních vlastností:

Uživatelská část:

Program bere data z příkazové řádky a to v následujícím pořadí: vstupní_soubor vystupni_soubor vzorek1=nahrazeni1 vzorek2=nahrazeni2 .... Nahrazení určuje čím se má nahradit nalezený vzorek se stejným číslem. Nahrazení je definováno jako neprázdný řetězec.

Nedodělky a chyby:

Program by měl fungovat bez problémů.