Dokumentace k zápočtovému programu v C yaaho Ondřej Bojar obo@cuni.cz 8.9.99 Obsah Zadání Informace pro provozovatele systému Struktura systému yaaho Podrobný popis chování systému Konfigurace systému Vzorový formulář pro použití yaaho Programátorská dokumentace Společné prvky Dokumentace yaaho Dokumentace searcheru Dokumentace plotteru ---- Zadání Cílem zápočtového příkladu je vytvořit systém pro prohledávání stránek WWW uložených lokálně, tj. na stejném počítači, kde je tento systém provozován. Pro uživatele systému je připraveno obdobné ovládání (zadávání požadavku, prohlížení výsledků) jako u většiny vyhledávacích systémů, např. http://www.altavista.com/. Vytvořený systém nese název yaaho jako zkratku za Yet Another AHO-Corasick-based searching machine a jako parafrázi známého katalogu a vyhledávací služby http://www.yahoo.com/. Cílovou platformou unix, systém bude konkrétně provozován jako služba na serveru http://www.cestina.cz/. Podrobný popis chování systému Uživateli systému je předložena stránka WWW s formulářem pro zadání hledaných slov nebo slovních spojení. Výstup z tohoto formuláře je běžným mechanismem CGI (Common Gateway Interface) předán do systému yaaho. Systém podle požadavku prohledá server a výstup předá v podobě upravené stránky jazyka HTML serveru WWW a ten ji odešle uživateli. Struktura systému yaaho Přestože celý úkol systému yaaho lze splnit jediným jednoprůchodovým programem, rozhodl jsem se systém realizovat trojicí samostatných programů spojených v konečné podobě pomocí systémové "roury". Výhody tohoto rozdělení jsou především následující: + snadné programování a ladění samostatných menších celků (možnost pro účely ladění zapojit "falešné" vstupy s ručně připravenými vstupními daty do jednotlivých částí) + snadné začlenění hotových systémových nástrojů do systému, konkrétně se jedná o program find pro získání seznamu všech souborů, které je třeba prohledat + samostatné programy jsou díky multiprocessingu rovnou spouštěny souběžně, takže se systém jako celek chová "vícevláknově", aniž by bylo nutné jej takto programovat; na počítači s více procesory mohou být dokonce procesy prováděny na různých procesorech, a to bez jakékoli úpravy systému yaaho Systém yaaho je tedy rozčleněn do navazujících částí s následujícími úkoly: - yaaho Program yaaho představuje vstupní bránu do systému. Jeho úkolem je zpracovat požadavek uživatele, tj. vyplněný formulář, do interní podoby a spolu se seznamem všech souborů, které bude třeba prohledat, jej předat vyhledávací části. Název yaaho označuje jednak celý vyhledávací systém, jednak jeho první článek -- CGI bránu. - searcher Program searcher na standardním vstupu očekavá požadavky hledání a seznam souborů, které má prohledat. Soubory postupně prohledává a jakmile nějaký soubor splňuje alespoň částečně požadavek, je základní popis souboru předán další části. - plotter Program plotter je poslední částí systému yaaho. Jeho úkolem je načíst ze vstupu přehled všech úspěšných nálezů (tj. seznam souborů a stručných informací o nich), tento seznam uspořádat a v podobě stránky WWW předat na výstup. Celý systém se aktivuje ve chvíli, kdy server WWW běžným mechanismem CGI spustí program yaaho. Každá část systému pak provede svůj úkol a sama spustí navazující program. Celkovým výstupem systému je výstup programu plotter. Konfigurace systému Jednotlivé programy systému yaaho mají do určité míry oddělenou a do určité míry společnou konfiguraci. Stručně lze princip konfigurování popsat takto: každý program vyhledává vlastní konfigurační soubor, implicitně se jménem ".conf", nebo podle parametru "-c ". Kromě pokynů z tohoto souboru se však každý program řídí i pokyny předanými od předcházejícího článku systému, a těmto pokynům dává navíc přednost. Nejjednodušší a nejméně redundantní postup pro konfigurování je tento: nastavení volby proveďte pouze v konfiguračním souboru prvního programu v rámci řetězu, který toto nastavení potřebuje znát. Například implicitně očekávanou znakovou sadu ze sítě potřebuje znát hned yaaho, řádek charset network input = iso-8859-2 tedy patří hned do souboru yaaho.conf. Naproti tomu implicitní výstupní znakovou sadu potřebuje znát až plotter, a řádek charset network output = iso-8859-2 tedy patří do souboru plotter.conf. Následuje přehled všech předvoleb, písmena v pravém sloupci říkají, které z programů systému yaaho volbu potřebují znát, první z těchto písmen tedy udává, do kterého konfiguračního souboru volba patří. charset saved default název sady, v níž jsou uloženy soubory na disku S charset meta can override 0 nebo 1, má-li searcher respektovat příkaz udávající sadu souborů na disku S charset network output název výchozí výstupní znakové sady, nepožádá-li klient jinak YP charset network input název implicitně očekávané vstupní znakové sady, neudá-li klient jinak Y charset add to content type 0 nebo 1, má-li plotter do hlavičky HTTP připisovat určení znakové sady P root url plná URL odpovídající plné cestě P root dir plná cesta k adresáři, v němž je uloženo hnízdo stránek P dir delimiter jeden znak, oddělovat adresářů na disku (např. v DOSu "\", bez uvozovek) P yaaho cgi url plná URL k vstupní bráně do systému yaaho P layout error page vzhled stránky informující o chybě P layout answer page header vzhled úvodní částí odpovědní stránky P layout answer page item vzhled jedné položky v seznamu nalezených souborů P layout answer page footer vzhled závěrečné části odpovědní stránky P Dosud nepodporované volby: request count limit omezení počtu nalezených souborů, které se mají zobrazit na jedné stránce P plotter pathname plná cesta a argumenty k plotteru YS searcher pathname plná cesta a argumenty k searcheru Y find command plná cesta a argumenty k příkazu find, který vypíše seznam všech souborů k prohledání Y Při vytváření vzorů výstupních stránek ("layouts" v konfiguraci plotteru) je možné užívat ve stránkách následující "proměnné", které jsou při odesílání stránky automaticky nahrazeny odpovídajícím obsahem. Ve jménech proměnných je nutné užívat velká písmena. Proměnné ve stránce ohlašující chybu (layout error page): __ERR_NO__ číslo chyby (podle interního číslování v systému yaaho) __ERR_STR__ text popisující chybu Proměnné ve hlavičce nebo patičce stránky seznamu nálezů (layout answer page header, resp. footer): __YAAHO_CGI__ bude nahrazeno URL na vstupní bránu do systému yaaho, tj. uvedeného ve stejnojmenné volbě v konfiguraci __ORIGINAL_REQUEST__ řetězec původního dotazu uživatele __PAGES__ automaticky generovaný seznam všech stránek odpovědí (nebo nic, pokud se všechny nálezy vešly na jedinou stránku); dosud není podporováno Proměnné v položce seznamu nálezů (layout answer page item): __URL__ odkaz na nalezenou stránku __TITLE__ titulek nalezené stránky __DESCRIPTION__ popisek nalezené stránky, jak je uveden v jejím META DESCRIPTION __MATCHES__ číslo udávající celkový pocoet úspěšných nálezů __CONTEXT__ výsek textu stránky z okolí prvního nálezu __DATE__ datum a čas poslední změny stránky __CHARSET_MIME__ znaková sada, v níž je stránka uložena (název podle MIME) __CHARSET_SHORT__ znaková sada, v níž je stránka uložena (krátký český název sady) Vzorová konfigurace všech programů systému yaaho je součástí balíku. Vzorový formulář pro použití yaaho
Programátorská dokumentace Následující část textu popisuje koncepci stavby systému yaaho a algoritmicky zajímavější části programů yaaho, searcher a plotter. Detailní poznámky lze nalézt v komentářích zdrojového kódu. Společné prvky Komunikační kanál Termínem "komunikační kanál" systému yaaho označuji jednosměrnou rouru z programů balíku. Standardní výstup yaaho je přesměrován na standardní vstup searcher a výstup searcheru na vstup plotteru. Pro dobrou komunikaci na tomto kanálu modul cross.c shrnuje komunikační konvence. Kanálem proudí řádky s následujícími informacemi (v tomto pořadí): -příkazy konfigurace -seznam vzorků -seznam souborů -případná chybová hláška Mezi jednotlivými bloky řádek jsou dohodnuté oddělovače. Ošetření a propadávání chyb Správa chyb je pro všechny tři programy sjednocena rovněž v modulu cross.c. Zde se zavádějí jednak konstanty chyb, vysvětlující řetězce a rovněž několik užitečných funkcí, z nichž klíčovou roli hraje funkce fatal. Úkolem funkce fatal, již lze zavolat z kterékoli funkce systému yaaho, je ohlásit chybu a ukončit běh programu. Hlášení chyby však neprobíhá ve všech případech stejně: pokud selže např. program yaaho dříve, než se mu podaří otevřít komukační kanál, musí zahlásit chybu sám. Pokud ovšem selže např. searcher během načítání vzorků a na plotter už napojen je, je vhodnější nechat hlášení chyby až na plotteru, který umí hlášku odevzdat čtenáři stránek v podobě HTML stránky. Z tohoto důvodu je funkce fatal je deklarována v modulu cross.h, její implementace je však ponechána na jednotlivých programech. Toto rozvržení umožňuje volat funkci fatal i ze společných částí programu, a její chování přitom určit v každém programu zvlášť. Samostatné hlášení chyb je jasné, jak ale probíhá "propadávání chyb" až k plotteru? Pro tento účel je v modulu cross.c zřízena proměnná prefatal_state, která udává, které z povinných bloků informací se na komunikační kanál už podařilo odeslat (konfigurace odeslána, vzorky odeslány...). Pokud dojde během dalšího zpracování k nějaké chybě, tj. je zavolána funkce fatal, je ještě před samotným ohlášením chyby uzavřena komunikace v kanálu, tj. jsou odeslány chybějící oddělovače, aby přijímající program v pevně daném pořadí obdržel všechny požadované bloky (samozřejmě s prázným obsahem). Pak je do komunikačního kanálu ohlášena chyba. Závěrečný program plotter je na toto chování připraven a chybu zabalí do pěkné stránky. Práce s diakritikou Systém yaaho podporuje různá kódování češtiny. Pro převod mezi kódováními je užit modul charconv.c Martina Mareše. K modulu charconv jsem vyrobil vlastní "kliku", modul charset.c, která navíc obsahuje rutiny pro správu názvů znakových sad. Pro práci s diakritikou jsem si stanovil následující pravidlo: v komunikačním kanálu bude vždy "interní znaková sada". Interní znakovou sadou je v tomto případě ISO-8859-2. Všechno ostatní se musí interní znakové sadě přizpůsobit. Ke konverzi textů tedy dochází: V yaaho: Při zpracování požadavku ze sítě V searcheru: Při čtení souboru z disku (pokud je soubor uložen v jiné sadě, než je interní) V plotteru: Při poskytování výstupu do sítě Požadavek hledání bez ohledu na diakritiku si vynutil připojit k programu ještě tabulku ekvivalencí mezi znaky. Tato tabulka je skryta v modulu cross.c. Přirozeně je tato tabulka vázana na určitou znakovou sadu, a proto je volba interní znakové sady ještě na programátorovi (a ne až na správci systému yaaho), jehož povinností je dodat i vlastní tabulku ekvivalencí. Systém konfigurace Systém konfigurace je významnou částí kódu společnou všem programům. Důvody, jež mne ke sjednocení systému konfigurace vedly, byly především následující: - všechny složky systému určitou konfigurovatelnost vyžadovaly - některé volby byly pro všechny složky společné, jisté sdílení konfigurace by tedy bylo tak jako tak nutné realizovat - snadnější programování -- jedenkrát napsaná funkce read_config pracuje ve všech programech a lze ji užít i v programech dalších - snadnější úpravy užívané sady voleb -- viz níže Zobecnění mechanismu načítání konfigurace si vynutilo přesun informací o jménech voleb a typech jejich dat z kódu do datové části programů. Nyní stačí přidat novou konstantu označující novou volbu v programu a o řádek rozšířit tabulku přiřazující k volbě jméno a datový typ, aby byla volba v konfiguračním souboru odpříště rozpoznána. Správa vzorků Pro zjednodušení manipulace se vzorky (načtení vzorků ze vstupu, sklad vzorků v paměti, počítaní výskytů vzorků, výstup vzorků a jejich počtů) byly tyto funkce shrnuty do modulu samples.c. Modul je opět využíván všemi programy systému yaaho. Dokumentace yaaho Úkolem yaaho je načíst vstupní požadavek uživatele, převést jeho součásti do interní znakové sady a pomocí příkazu find získat seznam souborů k prohledání. Všechny tyto informace je třeba předat na standardní vstup programu searcher. V současném stavu balíku yaaho sám neumí searcher ani find spustit. Z tohoto důvodu je na konstrukci řetězce procesů užit skript loader, který programy doslova prodrátuje, tak, jak bylo celkovým úkolem. #!/bin/csh ( yaaho; find /www/cestina -name "*.html" -print ) |\ searcher | plotter Další dokumentace yaaho mi připadá poměrně zbytečná, yaaho se odvolává na společné části balíku (config, samples) pro ukládání získaných informací. Zpracování požadavku v query_stringu je rovnež poměrně přímočaré, jedinou kličku představuje nutnost odhalit vstupní znakovou sadu dříve, než budou načítány vzorky, aby byly hned převedeny do interní znakové sady. Dokumentace searcheru Úkolem searcheru je prohledat seznam souborů na hledané vzorky. Ústředním algoritmem je dobře známý vyhledávací stroj navržený autory Aho a Corasic, jehož popis i formální důkaz lze nalézt ve skriptech Algoritmy (Peterka). Modul machine.c je právě implementací tohoto algoritmu. Modul je využíván prostřednictvím několika základních funkcí: - init_machine vytvoří prázdnou strukturu hledaciho stroje *add_sample rozšíří strukturu stroje tak, aby vyhledával i daný vzorek, vzorek je označen identifikačním číslem *finish_machine dokončí strukturu stroje po přidání všech vzorků *reset_machine inicializuje stroj před započetím vyhledávání *scan_machine zpracuje další písmeno (ze vstupního souboru) a oznámí identifikační číslo vzorku, byl-li nějaký nalezen; v tomto případě je nutné funkci volat opakovaně, protože vzorků mohlo být nalezeno v jeden okamžik víc (např. "len" a "volen" ve slově "Zvolen") Celý modul je napsán nad abstraktním typem "letter" a pro porovnávání písmen je nutné funkcím poskytnout odkaz na porovnávací funkci int comparator(letter, letter), takže je modul snadno použitelný i v jiných situacích. Searcher sám variabilitu vyhledávací stroje používá pro odlišné vyhledávání v dokumentech s diakritikou a bez ní. Pro dobrou funkci však nestačí zaměnit porovnávací funkci pro vyhledávání, je nutné postavit dva odlišné vyhledávací stroje, jeden se vzorky v plné diakritice (dia_mach), jeden se vzorky redukované do ASCII (asc_mach). Celkové chování searcheru k diakritice shrnuje následující tabulka: na vstupu vzorky s diakritikou na vstupu vzorky bez diakritiky soubor s diakritikou vyhledávání podle dia_mach soubor redukován do ASCII, vyhledávání podle asc_mach soubor bez diakritiky vyhledávání podle asc_mach vyhledávání podle asc_mach Searcher tedy prochází jeden soubor za druhým a pomocí vyhledávacího stroje zjistí, kolik vzorků se v souboru vyskytlo. Jakmile soubor splňuje minimální požadavky (byl v něm nalezen alespoň jeden vzorek a všechny vyžadované vzorky), je po dokončení hledání oznámen na výstup, tj. do plotteru. Součástí informací o každém nalezeném souboru není jen jméno souboru a počet vzorků, ale též informace z obsahu souboru: - titulek tj. text mezi příkazy a - popis tj. text v příkazu - kontext tj. citace z obsahu stránky v okolí prvního nalezeného vzorku Aby se pro vyhledání potřebných informací dokument zbytečně nepročítal vícekrát, jsou lineární vyhledávací stroje rozšířeny o speciální řídící vzorky (např. "DESCRIPTION", identifikační čísla jsou označena MI_něco). Jakmile je některý z řídících vzorků nalezen, funkce get_more_file_info z okolí aktuální pozice v bufferu zkopíruje požadovanou informaci. Jakmile je celý vstupní soubor zpracován, je jeho popiska odeslána komunikačním kanálem plotteru. Přesný tvar popisky souboru (musí být samozřejmě shodně stanoven pro searcher i plotter) lze ovlivnit volbami ve společném modulu cross.c. Dokumentace plotteru Úkolem plotteru je sesbírat všechny dosavadní výsledky hledání searcheru a utřízené je oznámit na výstup. Plotter proto musí vyčkat, až bude celé hledání dokončeno. Během tohoto času si ukládá informace o nálezech do struktury implementované v modulu items.c. Součástí funkcí tohoto modulu je i utřízení všech položek (algoritmem quicksort) podle počtu nálezů. Až jsou informace sesbírány (a je ověřeno, že v komunikačním kanálu není uvedena žádná chybová hláška) a utřízeny, je přehled souborů zabalen do HTML a odeslán na výstup. Klíčovou roli zde hraje funkce flush_buffer, která v daném řetězci (typicky je jím předloha stránky uvedená v konfiguračním souboru) provede náhradu __PROMĚNNÝCH__ skutečnými informacemi a takto upravený text vypíše. Funkce flush_buffer je parametrizována funkcí xxx_replacator, která je podle situace připravena nahrazovat různé skupiny proměnných. (Viz výše, v hlavičce odpovědní stránky je totiž možné užívat jinou škálu proměnných, než v položce nálezu nebo na chybové stránce ap.)