Hlavní navigace

Jehla v kupce sena: ASPSeek

Karel Pánek 6. 3. 2002

ASPSeek patří do kategorie fulltextových strojů s ukládáním dat do SQL databáze. V současné době je využíván na serveru WebSeek.cz, kde zajišťuje vyhledávací služby v doméně .cz. Jedná se o nejlepší bezplatný stroj s implementací P-rank a vah nad termy. Ani tento server však nevydržel jednoduché dotazy a složil se.

Celý softwarový balík obsahuje robota, vyhledávací server a pochopitelně i webové rozhraní na bázi CGI. Na domovské stránce projektu ASPSeek (vytvářeno společností SWsoft) se mimojiné dozvíte, že stroj podporuje indexování několika milionů stránek, vyhledávání frází, využívání pravostranné expanze (populární hvězdička, wildcards) a v neposlední řadě i dotazy v tzv. boolském zápisu.

Z vlastností, které jsou zajímavé pro integrování produktu do dalších projektů (pozor, ASPSeek je vytvářen pod nepříjemným GNU GPL), jmenujme podporu Unicode a stemming (pro češtinu bohužel jen na bázi ispell). Formátování výstupu je na poměrně vysoké úrovni a zahrnuje takové možnosti jako shlukování shodných zásahů do jednoho „koncentrovaného“ nebo vláknovou strukturu výsledků, případně zobrazování cachovaných oindexovaných stránek.

Rychlost

Přestože je stroj realizován v C/C++, tkví hlavní nedostatky ve způsobu uložení dat. To budu dokumentovat později demonstrací toho, jak je možné stroj napadnout tak, aby neodpovídal buď vůbec, nebo aby se jeho odpovědi počítaly i několik desítek sekund. Současně je však nutné podotknout, že jednou vypočítané výsledky jsou poměrně kvalitně cachovány, takže některé dotazy při častém opakování vykazují vysokou rychlost. K tomu, aby se cachování neuplatnilo, však stačí sebemenší modifikace dotazu.

Například když na hlavním serveru vyhledáváte výraz pattern*, tak se výsledek poprvé počítá 23 sekund. To rozhodně nesvědčí o kvalitě použitých algoritmů. Dle mého názoru se dotaz rozkládá na pattern OR patterns, a vyhledávání pouhých dvou slov nad bází šesti milionů dokumentů by nemělo trvat takovou dobu. Pokud ale týž dotaz vyzkoušíte znovu, výpočet trvá už jen několik desetin sekundy.

Pokračujme ale dále. Je cachovací algoritmus natolik dobrý, že by si pamatoval předchozí dotazy a využil je ke konstrukci dotazů nových? Zkusme patter*. Tento dotaz se rozkládá na pattern* OR (…něco…). Stroj by mohl využít předchozí výpočet, protože právě v tomto případě ono (…něco…) bude buď prázdné, nebo velmi malé co do počtu termů. Překvapení se nedočkáte, stroj tento dotaz počítá i bezprostředně po předchozím dotazu celých 31 sekund.

Webové stránky, které nejsou dostupné do šesti sekund, jsou pro většinu uživatelů tzv. „mrtvé“. ASPSeek poměrně nenáročné dotazy na pilotní implementaci zodpovídá 20–30 sekund. Závěr přenechávám čtenáři.

Jak to pracuje

Jak již bylo uvedeno, stroj pracuje s SQL v zádech. Aby zvládal větší zátěže než například UdmSearch (nyní MnogoSearch), jsou slova a jejich výskyty rozloženy do více SQL tabulek. To je pochopitelně do určité míry výhodné (počet vět v jedné tabulce ovlivňuje rychlost), ale při rozkladu na 16 tabulek se nezdá, že by šlo o optimum pro několik milionů stránek.

Jako backend je možné využít MySQL nebo Oracle. Zároveň ale upozorňuji, že kód ASPSeeku neobsahuje žádné výrazné optimalizace, takže se stejně jako v případě UdmSearch můžeme dočkat jen tabulek v režii B-stromů. To je současně pozitivní zpráva, protože to znamená, že lze stroj ještě výrazně urychlit.

Určité části ASPseeku pocházejí ještě z projektu UdmSearch. V čem se ale liší, je vyhodnocování podobnosti. S odvoláním na Kira (jeden z vývojářů) obsahuje kód i implementaci techniky PageRank, kterou jsem popisoval v některém z předchozích dílů. Kromě toho zahrnuje i vyhodnocování na základě vah termů. Přesto se nejedná o klasické implementace, ale o modifikace těchto technik. Přes otevřenost a výbornou čitelnost kódu se mi bohužel nepodařilo zjistit konkrétní implementační techniku, a ani nebylo možné získat patřičnou dokumentaci.

Přesto mohu potvrdit, že stroj techniky na výše uvedené bázi opravdu implementuje a pokračuje v základní podpoře sémantiky, jak ji započal UdmSearch. Z výsledků dotazů je pak patrné, že po této stránce je vskutku schopen kvalitně zpracovat báze o velikosti několik milionů dokumentů.

Jazykové dovednosti

ASPseek využívá při stemmingu program ispell, který stejně jako v případě UdmSearch trpí určitými nemocemi, a to zejména v případě češtiny.

Jedná se o klasický problém s diakritikou, kdy stroj mylně chápe některá podstatná jména jako slovesa (např. stůl oproti stul). V zásadě lze ale jazykové schopnosti při určité obezřetnosti využít k získávání kvalitnějších odpovědí, než nabízejí velké systémy, které stemming neimplementují.

Každý klad má určité negativní aspekty a těmi jsou v případě ASPseek především degradace rychlosti a výkonu při odbavování souběžně řešených dotazů.

Nasazení, závěr

Naprosto ideální je ASPseek pro menší báze (řádově několik set tisíc dokumentů), kde se již začnou projevovat kvalitní techniky jako je P-rank a váhy nad termy, ale ještě se neprojeví rychlostně-kapacitní problémy.

Rozhodnete-li se indexovat opravdu velké báze o rozsahu sedmi milionů dokumentů, jako to činí např. WebSeek.cz, znemožněte kladení pokročilých boolských dotazů – zejména pokud obsahují spojku OR. Dále nezapomeňte omezit nebo úplně zakázat pravostrannou expanzi pomocí hvězdičky. V neposlední řadě raději nepoužívejte stemming.

Nebudete-li se držet těchto pokynů, může útočník naprosto vyřadit váš server. Kromě dotazů, které jsme uplatnili vůči hlavnímu stroji, je na WebSeek.cz velice účinný dotaz web*. Nejen, že se nedočkáte výsledku, ale zároveň zpomalíte celý server. Použijete-li několik browserů, zcela určitě daný stroj zadřete (tohle si prosím vyzkoušejte výhradně na vlastním systému, nikoliv na WebSeek.cz).

Kdo očekává porovnání s UdmSearch (MnogoSearch), nebude zklamán.

MnogoSearch má širší podporu databází a operačních systémů. Má i rozvinutější základnu uživatelů, takže případné problémy můžete úspěšně konzultovat. Jistou výhodou je i to, že frontend je i pro PHP. Zřejmými nevýhodami – které jsem ostatně kritizoval minule – jsou: nevhodné algoritmy, výpočet podobnosti a celková stabilita.

ASPSeek využívá solidních postupů na výpočet podobnosti, je rychlejší a dovoluje podporu Unicode. Mezi jeho nevýhody patří menší uživatelská základna a náročnější modifikace související s webovým rozhraním.

Našli jste v článku chybu?

7. 3. 2002 9:49

kuba (neregistrovaný)
placeni klicoveho vyvojare = parazitovani???

6. 3. 2002 22:06

Michal Illich (neregistrovaný)
No, ono pokud program NEDISTRIBUUJETE (jako binarku) (coz webseek nedela), tak nejste podle GPL nuceni zdrojovy kod uverejnovat... je to takova moucha GPL (proti samotne myslence otevrenosti). GPL (ktera vznikla uz velmi davno) proste nepocita se server-side programy.

Tedy pro vyhledavac neni pro autora GPL moc vyhodna, protoze jini mohou smysluplne vyhledavac pouzivat a rozsirovat a nedat nic nazpet. Zrejme by to chtelo aktualizaci GPL (ted je 2.0, prijde 2.1?).



Vitalia.cz: Analýza letáků: Na co lákají do prodejen?

Analýza letáků: Na co lákají do prodejen?

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

120na80.cz: Rovnátka, která nejsou vidět

Rovnátka, která nejsou vidět

Podnikatel.cz: Změny v daních z příjmů u zaměstnávání

Změny v daních z příjmů u zaměstnávání

120na80.cz: Popraskané rty? Některé balzámy stav zhoršují

Popraskané rty? Některé balzámy stav zhoršují

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Měšec.cz: Platby do zahraničí: pozor na tučné poplatky

Platby do zahraničí: pozor na tučné poplatky

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Lupa.cz: Babiš: E-shopů se EET možná nebude týkat

Babiš: E-shopů se EET možná nebude týkat

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

Vitalia.cz: Manželka je bio, ale na sex moc není

Manželka je bio, ale na sex moc není

DigiZone.cz: Milan Kruml: procházka TV historií

Milan Kruml: procházka TV historií

Podnikatel.cz: Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Podnikatel.cz: Pozor, pojišťovny mění čísla účtů

Pozor, pojišťovny mění čísla účtů

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

DigiZone.cz: Digi CZ výrazně zlevnila balíček HBO

Digi CZ výrazně zlevnila balíček HBO