Názory k článku Jehla v kupce sena: rozšířený boolský model

Proč se na teoretiky dívají někteří lidé s opovržením? Protože se zabývají neadekvátními problémy.
Konkrétně tedy si představme dokument, ve kterém bude uvedeno český vyhledávač, česká diakritika a také české řazení. Zadám-li nějakému vyhledávači termín český, má onen dokument tři přístupové termíny (jak by neznalý člověk předpokládal) anebo jen jeden přístup "český"? A to se prosím nezminuji o dalších pádech natož pak o "češtině".
A ted teprve se bavme, jaké budou mít váhy hodnoty a jak se budou počítat vzdálenosti. - Jistě každý nahlédne, že v angličtině teorie platí!
Otázka tedy zní, o jakém českém vyhledávači máme hlasovat. Pokud má vyhledávat v anglických textech uložených na českých WWW-serverech, tak to chápu. Ale jinak se mi zdá, že autor klade otázku, aniž detailně tuší, na co se ptá.

To co zadate, si vynucuje neprimo i vyuziti modulu pro zpracovani prirozeneho jazyka, a to jsme pravdepodobne zcela nad moznostmi ceskych firem, ktere malokdy implemetovaly i zakladni stemming (z tech komercne aktivnich dokonce zadna).

Otazka, kterou zvolila redakce, neni uplne bezpredmetna. Podle volby p-normy muzete dotaz ladit mezi vektorovym pres boolsky (WebFast, Kompas) az po fuzzy, prip. ruzne michat.

Tim muzete ziskat z textu siroky prehled informaci. Nehlede na to, ze kazdy uzivatel si muze prednastavit ono jedine *p* (treba jen 4 byte) a s nim fungovat nad tymz indexem jako ostatni a pritom bude dostavat jine hit result listy.

Nemyslite, ze takovy stroj by nemel chybu? Kdyz hledam neco o HP 6L, je nejlepsi vyuzit boolsky model, pri hledani software zase vektorovy s PageRank, pri hledani obecnych informaci vektorovy riznuty fuzzy. To vse by slo...

Já nežádám, aby to někdo měl. Já bych jenom chtěl, kdyby bylo alespon nekde poznamenáno:
vše je "anglicky" na českých znacích, vyřešili jsem alespon diakritická znaménka pro různé kody, nerozlišujeme koncovky na dvě či tři písmena, máme už český modul který pozná "pes" a psí, dokonce podle kontextu rozlišíme "působení sil" a "sil jsem proso",
Ale totéž musím říci, než začnu psát vzorce. Uvažuji o všem "anglicky" i v českém textu?
Samozřejmě je nutno začít i uvažovat odjinud. Není "český modul" tak složitý, že je programově jednodušší vše pro indexování angličtiny zahodit a začít úplně odjinud. A tady začíná teorie, a ne ve formalizmu intuitivně nadefinovaných koeficientů.

Nejsem v teto oblasti zadny odbornik - ale mel jsem moznost zahlednout pri praci ASPI, coz je pomerne rozsahla databaze pravnich textu (pravda, v porovnani s internetovymi databazemi ji lze povazovat za malou) a jeji schopnost full-textove vyhledavat podle ceske fraze mi pripadala znacna, prestoze se obcas u nektereho slova zeptal, jestli se jedna o to ci ono (konkretni pripad si nepamatuji, ale neco ve smyslu, jestli slovem "sudba" myslim "vestbu" nebo sloveso od "soudit") - a pak vracel az necekantne relevantni texty, prestoze pozadovana slova byla nakonec ve zcela jinych tvarech. Dokonce ma jakousi povedomost i o synonymech.

Tak na pul ucha jsem poslouchal pred cca rokem na jednom z EurOpen prednasku o teto problematice, specialne s ohledem na "ceska specifika" - a odnesl jsem si z ni dojem, ze se nejedna ani o problem neresitelny, ani o problem, ktery je mimo dosah schopnosti ceske firmy.

Takze, pusobi to na me dojmem (protoze jine vysvetleni me z mych chudych informaci nenapada), ze nejde ani tak o schopnosti, jako proste o to, ze implementovat takovy mechanismus v ceskych vyhledavacich je proste nevyhodne ekonomicky. Ale samozrejme se mohu mylit.

> ze nejde ani tak o schopnosti, jako proste o to, ze
> implementovat takovy mechanismus v ceskych vyhledavacich je
> proste nevyhodne ekonomicky. Ale samozrejme se mohu mylit.

Podarilo se vam natuknout jadro problemu.

Pokud ma fulltext implementovat ohybani slov, znamena to, ze namisto jednoho slova "pes", coz znamena jednou sahnout na disk (1 seek, tedy 10ms), musi vyhledat rekneme 2*7 padu, coz znamena sahnout na disk (nebo do databaze) 14krat. To vede k vyrazne degradaci vykonu, tedy pri stovkach tisic dotazu za den k nutnosti koupi dalsich serveru, tedy vydajum.

Jinym zpusobem reseni je stemovat slova jiz pri indexaci, coz ale vede k cca dvakrat vetsim reverznim databazim, coz negativne ovlivni dobu jejich vytvareni i praci s nimi.

To jsou ciste "ekonomicke" argumenty, pak tu jsou jeste problemy mnohem vetsi:
- kde ziskat vhodny slovnik? (vetsinou se pouziva ispell)
- co stejne psana slova? (zminovane "sil jsem proso" a "pusobeni sil")
- maji se take implementovat synonyma? (napr. najdi.to vyhledava pri zadani "seznam" take "registr", "rejstrik", "soupis", coz je pekne, ale zrovna u tohoto slova casteji kontraproduktivni).
atd.

Pane Illichu, pokusim se nektere Vase otazky zodpovedet. Protoze budu muset byt strucny, nevysvetlujte si prosim kratke a strohe odpovedi jakymkoliv druhem averze.

- zadny slovnik neni potreba, stemming lze delat i bez slovniku a to dokonce pro libovolny jazyk v prutokove rychlosti (slozitost 2n, kde n je delka vstupu)

- se stejne psanymi slovy mate potize i nyni a reseni je ve sledovani okoli slov. Tyto techniky zadny cesky fulltext neimplementuje, nechapu proc je zminujete az nyni.

- synonyma se mohou pochopitelne povolit na zadost uzivatele

Vase kritika spojena s "naklady" je neadekvatni. Nebo snad ceske fulltexty omezuji delku dotazu na 2 slova, aby s dalsimi slovy nemusely tyto sekundy taktez ztracet?

Stemming se pochopitelne dela vetsinou pred indexaci a neni ani pravda, ze by dochazelo k vetsim bazim (asi jste ale myslel delku jednoho inversniho listu).Baze je spise mensi, protoze misto mnoha slov mate jen jejich stemy (tj. daleko mene rozdilnych slov) - ale vse zavisi na technice nakladani s daty.

Fulltextove algoritmy jsou v nejhorsim pripade linearni, takze o narocnosti kvuli padum nebo synonymum se nema cenu prakticky bavit.

Take nevim jakou techniku pouzivate pro inverzni seznamy, ze je stemming tak negativne ovlivni. Rozhodne Vam mohu doporucit Golomb kody urovne 3 a vrstvene inverzni seznamy. Predpokladdam, ze ani tyto techniky zadny cesky fulltext neimplementuje. Mylim se? :-)

Souhlasim, ze jde o ekonomicky problem, ale v te rovine, ze ceske firmy neciti potrebu zaplatit opravdu kvalitni teoreticky rozbor. I vynikajici programator tezko zvladne napsat efektivni a dobry fulltext. Proste proto, ze nezna teoreticke poznatky a neumi aktualni chyby stroje vyresit pouzitim spravne techniky (nikoliv hardwarove, ale algoritmicke).

> Pane Illichu, pokusim se nektere Vase otazky zodpovedet.
> Protoze budu muset byt strucny, nevysvetlujte si prosim
> kratke a strohe odpovedi jakymkoliv druhem averze.

Zadnou otazku jsem nepolozil a na vase vyjadrovani jsem uz zvykly ;) - pojdme tedy k veci:

> zadny slovnik neni potreba, stemming lze delat i bez

Zadny slovnik neni treba v 95% pripadu. Ale jine pripady (mezi nimiz pes/psa/psovi patri mezi ty nejjednodussi, o neco horsi jsou ruzne nepravidelnosti na konci korene, napr. b/p, velkym problemem jsou historicky vnikle veci jako kun/kone/konovi) je nutne resit pomoci slovniku. Spravne reseni (a kazde jine nez spravne podle mne zpusobi vic zmatku nez uzitku) vyzaduje jak slovnik tak i automat pro slova, ktera nebyla ve slovniku nalezena.

O sklonovani se v Cechach pokousi Megatext i Aspseek, oba s pouzitim slovniku (prvni ma vlastni, druhy pouziva ispell) a vysledky jsou nevalne.

> slovniku a to dokonce pro libovolny jazyk v prutokove
> rychlosti (slozitost 2n, kde n je delka vstupu)

To je velmi odvazne tvrzeni! (cti: zjevne nepravdive). Vite, existuji i jine jazyky nez ty indoevropskeho typu. Zkuste dokazat sve tvrzeni ("libovolny jazyk", "bez slovniku") treba pro cinstinu. Tesim se ;)

ad naklady a odsekavani: od urciteho poctu klicovych slov se skutecne uzivatelsky dotaz osekava (napr. google po 10tem slove), taktez je obvykle zcela vynechat tzv. stopslova -- to vse samozrejme kvuli snizeni nakladu.

ad velikost inverzni baze: ta je vetsi, protoze musite udrzovat informaci jak o stemovanych formach, tak o normalnich, protoze musite uzivateli ponechat volbu.

V otazce pouziti slovniku se mylite. Existuje zpusob, dokonce ceskeho autora - meho byvaleho spoluzaka, ktery nepotrebuje zadny slovnik (zadny znamena naprosto zadny a presto si poradi se vsemi tzv. vyjimkami). Tato metoda pracuje v O(n), presneji 2n (jeden pruchod cteni, druhy pruchod zapis vysledku).
V otazce cinstiny nejsem zbehly, ale jak jsem zbezne vyse zmineneou metodu precetl, nehraje jazyk a jeho konstrukce roli.

V otazce velikosti inverzi baze se take mylite, protoze u nekterych hodnot dochazi ke kumulovani do jiz existujicich. Kdyby se nechal jeden stroj fungovat nad stemovanymi a druhy nad nestemovanymi formami, tak mate pravdu. V realu to ale tak strasne neni. Naopak napr. prave s Golomb kody si jeste vice pomuzete pri narustajici delce inverzniho listu, protoze delty mezi idecky budou reprezentovany kratsim kodem. S vrstvenim takovych i-listu si zachovate i rychlost.

Ze dochazi k vynechani stopslov (pro neznale: slov, ktera se neindexuji) z dotazu je pochopitelne. Ze google odsekava po 10-tem slove je zajimava informace, ale velikost jeho baze a baze *.CZ je diametralne nekde jinde, nehlede na navstevnost Googlu. Ale prosim, muzeme srovnavat Trabant a Volvo, kdyz na to prijde.

ad cinstina> predstavujete si to prilis jednoduse; otazce indexovani cinskych textu jsem se ze zajmu venoval a tam narazite uz na zakladni problem, ze nerozeznate od sebe jednotliva SLOVA :) - uz to je pomerne obtizny problem (resitelny), takze na nejaky obecny a jednoduchy recept, ktery plati pro vsechny jazyky zapomente ;)

ad golomb> pouziti jakehokoliv kodovani je trade-off mezi rychlosti a velikosti databaze; v soucasnosti je cena disku tak mala, ze se golomb nevyplati. A mimochodem, golomb neni ani prilis dobrou volbou, pomoci jinych algoritmu (napr. aritmeticke kodovani) dosahnete mnohem lepsich kompresi.

ad vrstvene inverzni listy> muzete mi poslat citaci nejakych materialu, ktere se efektivitou tohoto reseni zabyvaji? o totez prosim ohledne te "zazracne" metody vaseho byvaleho spoluzaka (prilis v jeji existenci neverim ;) ).

Zrejme bude lepsi v diskusi pokracovat e-mailem, zde jsme se jiz vzdalili tematu clanku.

---
(a jako vzdy: veskere vyse uvedene nazory jsou soukrome a nevyjadruji stanovisko zadne firmy, vyhledavace, nabozenstvi, rasy, pohlavi, politickeho lobby ani university)

Asi se vam vmisim do hovoru. Jestli ma pan Panek na mysli stejnou metodu, jako znam ja, tak ta funguje tak, ze se NAUCI potrebne prevody ke stemovani sama. Pak opravdu muze fungovat i na cinstinu, ale asi by to chtelo zkusit, sam tomu ale moc sanci nedavam. Narozdil od pana Illicha ale mam ponekud mene vyhroceny nazor na metodu, kterou neznam dopodrobna a nevidel jsem potrebne testy. Galileovi take neverili, ze je Zeme kulata a vime jak to nakonec dopadlo :-))).

Golomb je opravdu vhodnejsi nez aritmeticke kodovani, protoze ho lze cist sekvencne i pri vrstvenych i-listech a hlavne bylo dokazano, ze potrebne CPU se ziska tahanim kratsich bloku z disku. Ten clanek byl v ACM, ale rocnik uz nevim. Najdete si to sam, nebo se mam trapit s nejakym fulltextem (po pravde mi uz u ACM vyprsel account...)? :-))

No, nedokazu si predstavit, jak se algoritmus v linearnim case muze naucit, ze druhy pad od "kun" je "kone", natoz pak, ze od "ja" je to "mne". Tu metodu opravdu neznam (jak rikate), proto mne zajima nejaky dokument, ktery ji popisuje -- zatim k.p. sva tvrzeni nicim nepodlozil.

Aritmeticke kodovani lze take cist sekvencne. Navic pokud usilujete o nejlepsi kompresi, je pro pravdepodobnosti aritmeticke kodovani _optimalni_, tedy lepsi nez Golomb nebo Huffman.

Ona metoda byla na SOFSEM 2001 a v zasade asi pracuje tak jak napsal Stano - sbornik mi jeste neprisel, takze operuji jen s tim co jsem se doslechl od duveryhodnych lidi.

V ostatnim jste se stal obeti vlastniho omylu, protoze Golomb nelze porovnavat s kompresnimi algoritmy jakymi je napr. aritmeticke ci huffmanovo. Jde ve sve podstate jen o formu zapisu integer cisel a vase vyroky jsou v teto oblasti pravdepodobne staveny jen na nejake nepresne shode s pojmy s nimiz tu nyni operujeme. Golomb neni v zadnem pripade kompresni metoda, jak se mylne domnivate a lze ji tedy dokonce predradit jako primarni onem zminenym (skutecne) kompresnim algoritmum.

> V ostatnim jste se stal obeti vlastniho omylu, protoze Golomb nelze porovnavat s kompresnimi algoritmy jakymi je napr. aritmeticke ci huffmanovo. Jde ve sve podstate jen o formu zapisu integer cisel a vase vyroky jsou v teto oblasti

Vzdyt huffmanovo kodovani i aritmeticke kodovani je take jen "forma zapisu integer cisel"... rozdil mezi Golombem a zminenymi algoritmy je v tom, ze ty, o kterych mluvim ja, jsou daleko obecnejsi, Golomb je v podstate pravidelny Huffman pro geometricke rady.

Golomb oproti aritmetickemu kodovani ztraci jak svou neobecnosti (musite se rozhodnout pro presne rozdeleni bitu) tak i nepresnosti (narust delky kodu je skokovy a nikoliv pozvolny). Aritmeticke kodovani se spravne spocitanymi pravdepodobnostmi vam da vzdy lepsi vysledek.

Tedy nemam duvod menit cokoliv z toho, co jsem rekl.

Prosim, vratme se na zacatek, nebot se vzdalujeme nejen sami sobe, ale i od podstatneho. Oboji je dle meho nazoru chybou.

Zacal jste srovnavat kod a kompresni algoritmus. Musim trvat na tom, ze srovnavate neporovnatelne hodnoty z rozlicnych definicnich oboru, a v tomto kontextu byste mel svuj vyrok upravit nebo zpresnit.

pozn.: podle vyzkumu Moffata a Zobela je vhodnejsi implementovat Golomb kody, protoze zlepseni spojene s jinymi kody je nad invertovanymi seznamy zanedbatelne.

Puvodne jsme se ale bavili o nakladech. Dosli jsme tedy k tomuto:

- cpu i disk je nyni levny (bud akceptujeme vas vyrok k tomu, ze komprese je prepych pri stavajicich cenach; nebo akceptujeme fakt, ze si misto kompresemi vyrobime - v pripade Golomb kodu existuji studie, kdy cas pridany cpu usetrime adekvatne na praci disku)

Tim jsme ale popreli vas puvodni vyrok, ze ceske firmy celi vysokym nakladum v pripade, ze budou implementovat urcite "features".

Zustava tedy otazka pro vas: Proc kalkulujete seek-y pro zduvodneni vysokych nakladu, kdyz muzete mit levne diskove pole, ktere tyto seeky paralelizuje?

(tento text je pouze souhrn predeslych myslenek, doufam, ze jsem zustal maximalne objektivni k prednesenym nazorum)

Zdravim, dobry clanek. Diskuze nakousla spoustu temat - nechteli byste napsat serial o vyhledavacich a vyhledavani textu?