Experimentální systém pro WEB IR Jiří Vraný Školitel: Doc. RNDr. Pavel Satrapa PhD.
Problematika disertační práce velmi stručný úvod
WEB IR – information retrieval from WWW, vyhledávání na webu Vzhledem k množství informací na webu, vrací WWW vyhledávače na běžné dotazy statisíce možných výsledků. Ty je nutno nějak seřadit a předložit uživateli. Výzkum v oblasti získávání informací na webu, postupně vedl k vytvoření celé řady řešení modifikujícíh metody klasického IR, i zcela nových postupů. Nejznámnější publikované algoritmy – PageRank, Hits, Salsa a další. V současnosti snaha o přizpůsobení výsledků konkrétnímu uživateli – personalizace. V ideálním případě tak aby uživatel nemusel dělat nic navíc. Matematika v pozadí – WWW stránky tvoří graf – W. Řadu problémů lze tak převést na problémy z teorie grafů, teorie pravděpodobnosti a další. Většina personalizovaných algoritmů vychází z algorimtu PageRank. Hlavní otázky DP:
Jak jsou tato řešení aplikovatelná na češtinu a česky psané stránky? Lze aplikací jiných přístupů k výpočtu dosáhnout reálné aplikovatelnosti algoritmů odsunutých na pole teorie pro jejich výpočetní náročnost?
Experimentální systém ? Pro testování algoritmů je nutné mít k dispozici vyhledávací stroj a dostatečně velký podgraf grafu W. Požadavky:
Efektivní získání a uložení podgrafu Možnost snadné modifikace řadících a indexačních algoritmů Jednoduché uživatelské rozhraní
Vlastní řešení nebo existující OpenSource?
OS řešení existuje mnoho
Např. Nutch + Lucene, Sherlock Holmes, Isearch, mnoGoSearch. Studium manuálů + implementace + nutnost pochopit cizí kód. Ne vždy je splněn druhý požadavek.
Komplet vlastní řešení
„Proč po desáté vynalézat kolo?“ 100% kontrola nad kódem a algoritmy řada slepých uliček.
Výsledek = kombinace OpenSource:
získání dat – Heritrix http://crawler.archive.org/ úložiště – MySQL http://www.mysql.com/ Python nástroje – BeatifulSoup, Cython a další.
Vlastní řešení:
middleware – zpracování získaných dat do databáze, indexační server, rank server uživatelské rozhraní – řazení výsledků, testování kvality
Schéma systému
Databáze Požadavky:
Rychlé ukládání a vydávání dat Efektivní vyhledávání neúplných informací Možnost vytvářet další podgrafy Škálovatelnost, robustnost řešení
Model databáze
Middleware – zpracování dat
Python WebTextTools
zpracovává WWW stránky uložené na pevném disku rekurzivní prohledávání zadaného adresáře čte data v ARC (Internet Archive) formátu načtená data parsuje a odstraňuje fatální chyby (chybějící titulky, nevalidní url aj.) veškeré texty konvertuje do UTF-8 zpracovaná data ukládá do databáze. z uložených dat ukládá incidenční matice web grafu a podgrafů ve formátech CSR (Numpy) a MPIAIJ (Petsc4py)
Middleware – komunikace
Pro komunikaci klient / server slouží TCP protokol, implementovaný pomocí modulu socket v Pythonu. Pro aplikační vrstvu byl navržen jednoduchý protokol obsahující základní instrukce pro:
ukončení přenosu identifikaci jednotlivých dat – fragmentace, typ
Middleware – index server
Na základě dotazu od klienta najde ID příslušných dokumentů, načte data z databáze a ty vrátí klientovi. Index je uložen v paměti – pro 50 tisíc stránek má cca 100 MB Akutálně používaný index - inverzní index stránek - obsahuje ID dokumentů + váhu slova dle Saltonova vzorce.
Middleware – index server
Zpracování dotazu
Index server používá zjednodušený Booleovský model s absolutní shodou. dotaz je rozdělen na n slov s každé slovo si odpovídá příslušné množině dokumentů Si Výsledná množina dokumentů V je průnikem monžin Si pro i = 1..n
Middleware – rank server
Podobný index serveru, pouze používá jinou datovou strukturu Od klienta obdrží ID stránky na základě kterého vyhledá příslušný rank. Umožňuje hromadné zpracování více ID.
Uživatelské rozhraní
WWW stránka generovaná z Pythonu pomocí Apache + mod_python Přijme dotaz od uživatele, komunikuje s index serverem a rank serverem, sestavuje výsledné pořadí stránek. Vyhodnocení experimentů – umožňuje přepínat hodnotící funkci (utajeně) + vkládat zpětnou vazbu která hodnotící funkce je dle uživatele lepší.
Děkuji za pozornost. Dotazy?
