Před skoro půl rokem jsem zde publikoval svoje zápisky z přednášky o Seznam fujjtext. Dnes se na naší fakultu její průmyslový partner vrátil a opět nešetřil podrobnostmi.
Tímto chci Štěpánovi poděkovat za pozvání na přednášku i když jsem svoje zápisky z minulé takhle veřejně publikoval. Následující text jsou opět JEN ZÁPISKY. Neberte je moc doslova, seděl jsem vedle Yuhůa (který se na to zašel podívat v rámci svojí dovolené:-) a ten neustále vrtěl hlavou nebo měl bezradně hlavu v dlaních, což jsem si vysvětlil tak, že není zrovna nadšenej, že to Štěpán říká. Poslední půlhodinu jí měl v dlaních pořád. Když viděl osnovu bodu 4, tak uvažoval, že jestli se Štěpán dostane k poslednímu bodu u části c (relevance), tak že to bude asi muset stopnout :-)
Je teoretická šance, že by záznam přednášky byl alespoň pro studenty FI zveřejněnej, ale Dušan nevypadal, že by byl pro. Myslím si, že jednodušší než oficiální cesta bude ta, kterou nedávno zmiňoval ing. Schiller - totiž ta, že všechny přednášky má na svém disku, takže stačí prolomit jen dvoje dveře do jeho pracovny a... ;-) Každopádně ta samá přednáška už pravděpodobně nikde nebude, protože tam byly některé prý příliš citlivé údaje, některé jsem na přání ze zápisku odstranil a nechávám si je jako osobní know-how;-).
Přednáška byla narozdíl od minula myslím hodně přínosná spíš pro programátory (ale SEOisté si v tom své taky našli:-). Bylo na ní vidět, že se v poslední době na fulltextu hodně pracovalo. Osobně mám největší radost z toho, že jsem se zase po delší době (pár měsíců) zase potkal s Dušanem.
Je teoretická šance, že by záznam přednášky byl alespoň pro studenty FI zveřejněnej, ale Dušan nevypadal, že by byl pro. Myslím si, že jednodušší než oficiální cesta bude ta, kterou nedávno zmiňoval ing. Schiller - totiž ta, že všechny přednášky má na svém disku, takže stačí prolomit jen dvoje dveře do jeho pracovny a... ;-) Každopádně ta samá přednáška už pravděpodobně nikde nebude, protože tam byly některé prý příliš citlivé údaje, některé jsem na přání ze zápisku odstranil a nechávám si je jako osobní know-how;-).
Přednáška byla narozdíl od minula myslím hodně přínosná spíš pro programátory (ale SEOisté si v tom své taky našli:-). Bylo na ní vidět, že se v poslední době na fulltextu hodně pracovalo. Osobně mám největší radost z toho, že jsem se zase po delší době (pár měsíců) zase potkal s Dušanem.
Přednáška "Fulltextový vyhledávač", Štěpán Škrob, PV030
Seznámení s anatomií fulltextového vyhledávače.
1. úvod
Všechny vyhledávače jsou stejné, jako auta. Liší se v implementačních detailech (tuším že tam byly obrázky trabantu a ferrari - obě mají 4 kola, volant...).
2. přehled architektury vyhledávače
Původní škálovatelnost 100M dokumentů
Nyní až 1G dokumentů
- Rozdělení databáze do svazků
- Zkrácení odezvy vyhledávače
Současná databáze
- Počet dokumentů 30M
- Datová veliksot 100GB
Výkon robota
- 2 M dokumentů / den
Dvě úzká hrdla
- Výběr dokumentu k reindexaci
- Přeložení URL na url_id
pagerank ovlivnuje jak url server, tak index searchers
3. důležité datové struktury
Lexikon (header, hash table, data area, free space)
- ptr_next (ukazatel na další slovo se stejným hash), id(123), len(4), word(ahoj)
-- ptr_next(null), id(657), len(5), word(nazdar)
slova, která se při reindexaci nenajdou v lexikonu zůstávají, jednou za čas je "ručně" vyhází
- 450MB, 22 miliónů slov, 16 miliónů hashů (využitých 75%), největší kolize 13 slov/hashů, Výkon 100000 slov/sec (zkoušeli lexikon převést na MySQL, které zvládlo cca 15k)
- lexikon je spojený s lemmatizátorem v jednu komponentu
- pro lemmatizovaná slova obsahuje lemmata, pro ostatní termy
Index slov
barrel je soubor ve kterém jsou uloženy záznamy několika slov (slovo s id nějaký a je tam seznam dokumentů, které obsahují to slovo)
barrel: word_id, size (B), doc_count, documents:doc_id(=urlid v robotovi),size, hits:strong (slovo zvýraznění, nejen to, spíš se nepoužívá),word_form (tvar slova jako id, což je nešťastné),para(v jakém odstavci),pos(pozici)
pagerank calculator (pouze odkazy apod., ne slova)
pagerank - zpracování statistických dat z webu
podle pageranku se nedá vyhledávat jen v některých dokumentech
Je potřeba šetřit místem (dekomprimace je rychlejší, než aby se četla nekompr. data).
Index trvale přítomný v paměti, v jakém barrelu slovo leží
50GB, trvale načtené 250MB
Index anchor dat - ze zpětných odkazů
podobné jako u index slov, u každého odkazu se drží rank stránky, ze které odkaz pochází (zřejmě v momentě zaindexování odkazu)
1GB (11odkazů na stránku)
Texty dokumentů
seřazené podle id dokumentu
obsahuje texty všech zaindexovaných stránek včetně balastu
-zachované infromace o odstavcích
- označkované začátky a konce slov
automatický abstrakt dokumentu (site:muni.cz) - hodně dobrý, ale nejde to kromě site: využít
statistické informace, 50GB, průměr 200slov na dokument (7znaků dlouhé slovo)
16b na odstavec + 16b na pozici v odstavci
- ptr_next (ukazatel na další slovo se stejným hash), id(123), len(4), word(ahoj)
-- ptr_next(null), id(657), len(5), word(nazdar)
slova, která se při reindexaci nenajdou v lexikonu zůstávají, jednou za čas je "ručně" vyhází
- 450MB, 22 miliónů slov, 16 miliónů hashů (využitých 75%), největší kolize 13 slov/hashů, Výkon 100000 slov/sec (zkoušeli lexikon převést na MySQL, které zvládlo cca 15k)
- lexikon je spojený s lemmatizátorem v jednu komponentu
- pro lemmatizovaná slova obsahuje lemmata, pro ostatní termy
Index slov
barrel je soubor ve kterém jsou uloženy záznamy několika slov (slovo s id nějaký a je tam seznam dokumentů, které obsahují to slovo)
barrel: word_id, size (B), doc_count, documents:doc_id(=urlid v robotovi),size, hits:strong (slovo zvýraznění, nejen to, spíš se nepoužívá),word_form (tvar slova jako id, což je nešťastné),para(v jakém odstavci),pos(pozici)
pagerank calculator (pouze odkazy apod., ne slova)
pagerank - zpracování statistických dat z webu
podle pageranku se nedá vyhledávat jen v některých dokumentech
Je potřeba šetřit místem (dekomprimace je rychlejší, než aby se četla nekompr. data).
Index trvale přítomný v paměti, v jakém barrelu slovo leží
50GB, trvale načtené 250MB
Index anchor dat - ze zpětných odkazů
podobné jako u index slov, u každého odkazu se drží rank stránky, ze které odkaz pochází (zřejmě v momentě zaindexování odkazu)
1GB (11odkazů na stránku)
Texty dokumentů
seřazené podle id dokumentu
obsahuje texty všech zaindexovaných stránek včetně balastu
-zachované infromace o odstavcích
- označkované začátky a konce slov
automatický abstrakt dokumentu (site:muni.cz) - hodně dobrý, ale nejde to kromě site: využít
statistické informace, 50GB, průměr 200slov na dokument (7znaků dlouhé slovo)
16b na odstavec + 16b na pozici v odstavci
4. použité algoritmy
a, crawlování
- filtrace dokumentů
podle url, http hlavičky, pozor na CGI scripty a URL zakončená lomítkem
- detekce českého jazyka
vyřazení binárních souborů (citilvost na řídící znaky ascii<32 (pozor na UTF16!!!!!!!!!!!!!!!!!!!!!!!!)
hledání tokenů podobných slovům (mezery a délka slova)
vyřazení zcela duplicitních dokuméntů, MD5hash z textového derivátu (bacha, bacha na duplicitní texty - eshopy)
kombinace slovníkové a statistické metody
- slovník ze 100.000 článků novinky.cz
- frekvence slov
- charakterističnost slov pro češtinu (žížala, řeřicha - slovník i jednotlivá písmenka...)
vysoká citrlivost na přítomnost českého jazyka
nutná spolehlivá funkce i pro krátké texty
ruční nastavení vah, neumí se učit
b, indexace
- lemmatizace
od Lingea
zaměření na spisovnou češtinu
více správných možností - dvě lemmata (citron v. citrón)
názvy, jména, příjmení
pouze podle podstatných, číslovky a přídavných jmen
neznámá slova
- indexace termu (nokia, nokii dvě různá slova)
Nejednoznačná slova
-zaindexování ve prospěch všech lemmat
-problémy: "Jana Králová" - vypadne "jan král"
Text bez diakritiky
- doplňuje se pokud je celý odstavec bez diakritiky
- výskyt hlavně v diskuzích
- identifikace podobných dokumentů
zkoumá se podobnost každého dokumentu se všemi ostatním dokumenty
pro každý dokument se spočítá N hashů
výstupem je max (hash) z každé funkce
neplatí tranzitivita (A<>B, B<>C => A<>C)
ze souborů vytvoříme třídy podobných dokumentů jako kdyby podobnost byla transitivní
c, vyhledávání
- doplňování diaktritiky
účel
-stále nezanedbatelné procento dotazů bez diakritiky
-nesprávně psané dlouhé samohlásky (á, é, í, ó) - (Slávia, ale myslí Slavia)
-překlepy (Śkoda místo Škoda)
postup (už se to prý trochu změnilo)
-úplné odstranění diakritiky z dotazu
-doplnění diakritiky do očištěného dotazu
- výběr vhodného lemmatu
pro slovo s více lemmaty se musí hledat pouze jednotlivá (jednak rychlost, druhak kvůli smyslu)
preference lemmat ze znalosti situace
typická podoba dotazů
- podstatná a přídavná jména (dovolená chorvatsko)
- slovesa vyjímečně (běží liška k táboru)
- 1. pád jedn. i mn. čísla (krby)
použití frekvenčního slovníku dvojic lemmat
- kombinace všech možností lemmatizace dotazu
- ohodnocení každé kombinace podle frekvence výskytu
výsledek - rozdílná lemmata pro
- německých tancích (lemma německý, tank)
- německých lidových tancích (lemma německý, lidový, tanec)
- hodnocení relevance
Vyhodnocují se pozice slov (vzdálenost)
- A B vzdálenost 0
- A x B vzdálenost 1
- A x x B vzdálenost 2
- B A vzdálenost 0
v textu musejí být všechna slova
hodnocení slov v
-titulku
-url
-text
url má význam i když není oddělené pomlčkou - viz "jak na web"
dynamická stop slova na základě dotazu
- filtrace dokumentů
podle url, http hlavičky, pozor na CGI scripty a URL zakončená lomítkem
- detekce českého jazyka
vyřazení binárních souborů (citilvost na řídící znaky ascii<32 (pozor na UTF16!!!!!!!!!!!!!!!!!!!!!!!!)
hledání tokenů podobných slovům (mezery a délka slova)
vyřazení zcela duplicitních dokuméntů, MD5hash z textového derivátu (bacha, bacha na duplicitní texty - eshopy)
kombinace slovníkové a statistické metody
- slovník ze 100.000 článků novinky.cz
- frekvence slov
- charakterističnost slov pro češtinu (žížala, řeřicha - slovník i jednotlivá písmenka...)
vysoká citrlivost na přítomnost českého jazyka
nutná spolehlivá funkce i pro krátké texty
ruční nastavení vah, neumí se učit
b, indexace
- lemmatizace
od Lingea
zaměření na spisovnou češtinu
více správných možností - dvě lemmata (citron v. citrón)
názvy, jména, příjmení
pouze podle podstatných, číslovky a přídavných jmen
neznámá slova
- indexace termu (nokia, nokii dvě různá slova)
Nejednoznačná slova
-zaindexování ve prospěch všech lemmat
-problémy: "Jana Králová" - vypadne "jan král"
Text bez diakritiky
- doplňuje se pokud je celý odstavec bez diakritiky
- výskyt hlavně v diskuzích
- identifikace podobných dokumentů
zkoumá se podobnost každého dokumentu se všemi ostatním dokumenty
pro každý dokument se spočítá N hashů
výstupem je max (hash) z každé funkce
neplatí tranzitivita (A<>B, B<>C => A<>C)
ze souborů vytvoříme třídy podobných dokumentů jako kdyby podobnost byla transitivní
c, vyhledávání
- doplňování diaktritiky
účel
-stále nezanedbatelné procento dotazů bez diakritiky
-nesprávně psané dlouhé samohlásky (á, é, í, ó) - (Slávia, ale myslí Slavia)
-překlepy (Śkoda místo Škoda)
postup (už se to prý trochu změnilo)
-úplné odstranění diakritiky z dotazu
-doplnění diakritiky do očištěného dotazu
- výběr vhodného lemmatu
pro slovo s více lemmaty se musí hledat pouze jednotlivá (jednak rychlost, druhak kvůli smyslu)
preference lemmat ze znalosti situace
typická podoba dotazů
- podstatná a přídavná jména (dovolená chorvatsko)
- slovesa vyjímečně (běží liška k táboru)
- 1. pád jedn. i mn. čísla (krby)
použití frekvenčního slovníku dvojic lemmat
- kombinace všech možností lemmatizace dotazu
- ohodnocení každé kombinace podle frekvence výskytu
výsledek - rozdílná lemmata pro
- německých tancích (lemma německý, tank)
- německých lidových tancích (lemma německý, lidový, tanec)
- hodnocení relevance
Vyhodnocují se pozice slov (vzdálenost)
- A B vzdálenost 0
- A x B vzdálenost 1
- A x x B vzdálenost 2
- B A vzdálenost 0
v textu musejí být všechna slova
hodnocení slov v
-titulku
-url
-text
url má význam i když není oddělené pomlčkou - viz "jak na web"
dynamická stop slova na základě dotazu
5. výkonové statistiky
dotazy na web interface
1 ze 3 metasearcherů - kolem 12 60-80/s (asi nepřesné)
kolem 50msc (bez query cache kolem 100)
query cache
nově 60 úspěch 40 neúspěch
odezva indexsearcherů (50-70msc)
content server (do 20msc)
1 ze 3 metasearcherů - kolem 12 60-80/s (asi nepřesné)
kolem 50msc (bez query cache kolem 100)
query cache
nově 60 úspěch 40 neúspěch
odezva indexsearcherů (50-70msc)
content server (do 20msc)
Do budoucna by rádi:
zapojení pokročilých lingvistických metody
zvyšování počtu dokumentů v databázi
zlepšování výpočtu relevance
zvyšování počtu dokumentů v databázi
zlepšování výpočtu relevance
Martin | 25. dubna 2007 v 18:58 | 
Zde hledá
Škoda, že to není jako článek, ale jen poznámky :(. Co takhle nějaký napsat? Za honorář :-D