Názory k článku
Nové trendy ve vyhledávání

Nemam zadny odborny komentar; chci jen rici, ze se mi clanek moc libil.

Vyhledávače www stránek existovaly už v tom dávnověku, jen nebyly globální. A globální vyhledávače pro Gopher, myslímže existovaly už tehdy, stejně tak jako distribuované vyhledávání v různých odborných databázích.

Kromě toho mám pocit, že i když to pro nás historicky důležitější než Gagarin ve vesmíru, z tehdejšího pohledu o tak zásadní přelom nešlo. První globální webový prohledávač byl, myslím, Lycos. Lycos jako firma vznikl v 95, ale predtim nejaky rok nebo dva béžel na jakési univerzitě. Cern Httpd v.1 byl vypuštený v 91, než se trochu rozšiřil, trvalo to rok nebo dva. Takže bez globálního vyhledávání byl Internet tak možná 1 rok (a to ještě platil normální ne "internetový" čas ;-)

Predchudci Internetu existuji od 70. let. Rekneme od roku 1983, kdy cela sit presla na TCP/IP, ji myslim muzeme Internet rikat, WWW pak prislo pozdeji.
Pred Lycosem byl myslim jeste WWWWorm, ale ted nejak nemuzu najit informaci o roku jeho spusteni. Samozrejme jsem mel na mysli globalni vyhledavani. Jinak myslim, ze vase tvrzeni s mym nijak v rozporu neni.

Autor článku si posteskl, že žádný český fulltext nepoužívá nějaký inteligentní algoritmus pro posuzování relevance vyhledávaných stránek, myslím si ale, že jej ve skutečnosti nepoužívá ani ten tolik opěvovaný Google. Důvod je prostý: máte-li indexovat jednu miliardu stránek, jste rádi, když se vám takové kvantum dat vůbec podaří nějak použitelně naskládat do počítače. Představa, že by se nad tím daly dělat nějaké složitější výpočty, je velmi naivní. Usuzuji tak na základě zkušeností z vývoje vyhledávače Megatext. Indexuje 3 miliony stránek a téměř 1.5 miliardy slov. Pouhé setřídění těchto slov podle abecedy trvá na běžně vybaveném počítači půl dne. Druhý důležitý argument proti tomu, co Google uvádí, je tento: Na 95% internetových stránek vede jen jeden odkaz. Pokud byste chtěli určovat relevantnost stránek podle "kvality" odkazů, které na ně vedou, mohli byste to věrohodně dělat jen asi u 1% všech dostupných stránek. Na zbývající stránky prostě nevede dost odkazů. Nějakou metodu "PageRank" Google možná používal ve svých začátcích, kdy to byl docela kvalitní PhD projekt indexující nějakých 10-20 milionů stránek (tj. to zmiňované jedno procento). Dnes je ta metoda PageRank spíše marketingová vábnička na nalákání uživatelů a investorů. Je třeba se nějak odlišit:). I když dnes už i Google ví, že mezi fulltexty se nejsnáze odliší tím, že prostě bude největší...

Tohle uz me namichlo - kde se v nekterych Cesich bere ta neodbytna touha, pomazat vsechno zdarile, co jim osobne nepatri, svym lejnem?

Pane Susteku, pokud se vam zda, ze pul dne na serazeni kousku indexu je strasne moc, pak vezte, ze index brokeru se muze sestavovat tydny. U velkych prohledavacu nejede na jednom pocitaci, ale na tisicich. Existuji lidi, kterym se rika matematici, a ti si dokazi s takovymi ulohami poradit. Napr. i s tim, ze osvezuji prubezne jen cast indexu jeho prestavbou adekvatne vybranymi, nejpodstatnejsimi daty.

Naprosto si protirecite v dalsim tvrzeni. Pokud podle vas existuje jen 5% stranek, na ktere vede vice nez jeden odkaz, pak by zpracovani Page Ranks bylo znacne ulehceno a nikde vubec zadny problem. Ono to tak ale neni. Googlovci pouzivaji dalsi metody vazeni stranek. To, ze je nikomu nevysvetluji, je jejich vec. Pouze neco malo nastinuji. To ale neznamena, ze je muzete klidne prohlasovat za lhare.

Kdyz chcete nekoho zpochybnovat a nemate pro to jasne dukazy, pak se nutne ocitate v pozici toho, jehoz ocernovani ma bumerangovy efekt. Technika prohledavani neni nejake ledabyle manazerynkovske politikareni - to zadny index nikdy nesestavi. Rozhoduje to, co Google aj. prohledavace nabizeji lidem.

Jinak receno - ukazte, ze to umite lip nez vsichni ostatni na svete. Takovi lide ale vetsinou byvaji skromnejsiho razeni a nenapadaji nikoho, kdo neco umi.

Tohle uz me namichlo - kde se v nekterych Cesich bere ta neodbytna touha, pomazat vsechno zdarile, co jim osobne nepatri, svym lejnem?

Pane Susteku, pokud se vam zda, ze pul dne na serazeni kousku indexu je strasne moc, pak vezte, ze index brokeru se muze sestavovat tydny. U velkych prohledavacu nejede na jednom pocitaci, ale na tisicich. Existuji lidi, kterym se rika matematici, a ti si dokazi s takovymi ulohami poradit. Napr. i s tim, ze osvezuji prubezne jen cast indexu jeho prestavbou adekvatne vybranymi, nejpodstatnejsimi daty.

Naprosto si protirecite v dalsim tvrzeni. Pokud podle vas existuje jen 5% stranek, na ktere vede vice nez jeden odkaz, pak by zpracovani Page Ranks bylo znacne ulehceno a nikde vubec zadny problem. Ono to tak ale neni. Googlovci pouzivaji dalsi metody vazeni stranek. To, ze je nikomu nevysvetluji, je jejich vec. Pouze neco malo nastinuji. To ale neznamena, ze je muzete klidne prohlasovat za lhare.

Kdyz chcete nekoho zpochybnovat a nemate pro to jasne dukazy, pak se nutne ocitate v pozici toho, jehoz ocernovani ma bumerangovy efekt. Technika prohledavani neni nejake ledabyle manazerynkovske politikareni - to zadny index nikdy nesestavi. Rozhoduje to, co Google aj. prohledavace nabizeji lidem.

Jinak receno - ukazte, ze to umite lip nez vsichni ostatni na svete. Takovi lide ale vetsinou byvaji skromnejsiho razeni a nenapadaji nikoho, kdo neco umi.

Tohle uz me namichlo - kde se v nekterych Cesich bere ta neodbytna touha, pomazat vsechno zdarile, co jim osobne nepatri, svym lejnem?

Pane Susteku, pokud se vam zda, ze pul dne na serazeni kousku indexu je strasne moc, pak vezte, ze index brokeru se muze sestavovat tydny. U velkych prohledavacu nejede na jednom pocitaci, ale na tisicich. Existuji lidi, kterym se rika matematici, a ti si dokazi s takovymi ulohami poradit. Napr. i s tim, ze osvezuji prubezne jen cast indexu jeho prestavbou adekvatne vybranymi, nejpodstatnejsimi daty.

Naprosto si protirecite v dalsim tvrzeni. Pokud podle vas existuje jen 5% stranek, na ktere vede vice nez jeden odkaz, pak by zpracovani Page Ranks bylo znacne ulehceno a nikde vubec zadny problem. Ono to tak ale neni. Googlovci pouzivaji dalsi metody vazeni stranek. To, ze je nikomu nevysvetluji, je jejich vec. Pouze neco malo nastinuji. To ale neznamena, ze je muzete klidne prohlasovat za lhare.

Kdyz chcete nekoho zpochybnovat a nemate pro to jasne dukazy, pak se nutne ocitate v pozici toho, jehoz ocernovani ma bumerangovy efekt. Technika prohledavani neni nejake ledabyle manazerynkovske politikareni - to zadny index nikdy nesestavi. Rozhoduje to, co Google aj. prohledavace nabizeji lidem.

Jinak receno - ukazte, ze to umite lip nez vsichni ostatni na svete. Takovi lide ale vetsinou byvaji skromnejsiho razeni a nenapadaji nikoho, kdo neco umi.

Neverte panu Zajickovy, protoze lze.
Chcete dukaz - zde je:
Tady (http://www.lupa.cz/nazory.phtml?c_id=1222&kk%5B11087%5D=on&show.x=26&show.y=14) se zavazal, ze se uz neucasti diskusi na Lupe, protoze ho obtezuje napadani ostatnich lidi.
Jak je videt podle predchoziho prispevku, byla to jen ucelova lez a hned kdyz se objevila moznost nekoho napadnout (a udelat tak presne to, co sam nesnasi), tak zapomel na vsechny svoje sliby (presne jako nasi politici, kere ma tak rad).
Skutecne mne hodne sklamal a ted uz nemuzu rict, jestli i jeho dalsi argumenty nejsou lzive, proste uz neni duveryhodny.

Bez ohledu na formu páně Zajíčkova příspěvku (a to forma nijak nevybočuje z řady) nemohu než s panem Zajíčkem souhlasit. Vaše argumenty si skutečně protiřečí a příklad s tříděním "na běžně vybaveném počítači" je k smíchu.

K smíchu však už není Vaše odpověď panu Zajíčkovi. Již od dob starověkého Řecka je (všeobecně) známo, že přejít v diskuzi při předkládání argumentů od tématu k diskutérovi je sprosťárna.

To jste se přehlédl, já jsem p. Zajíčkovi nic neodpovídal.

Lituji ze je to offtopic - ale tohle je prave prvni jeho prispevek od te doby co se zavazal nepsat do diskusi (dovolil sem si prehlednout jeho dovysvetlujici komentare k vlastnimu clanku).
Napsal sem to takhle neskutecne otevrene a drsne prave proto, ze on v presne stejnem duchu napadal sve oponenty napr. jste kadrovaci z 50.let, fasisti a podobne nesmyslne urazky a to bez jakyhkoliv dukazu pochopitelne. Ted ovsem on sam slap hodne vedle, kdyz nesplnil svuj vlastni slib.
Je mi to dvakrat lito, protoze sem mu veril, ze to mysli vazne a ze je to i krok k tomu, aby se zbavil sve zavislosti na virtualnim diskutovani (kere pochopitelne popira).
Jeho prispevek tady nebudu hodnotit, ale chci jen aby i ostatni vedeli s kym mluvi.
Jeste jednou se omlouvam za offtopic, ulitlo mi to, protoze sem byl skutecne rozhorcen (necekal sem ze porusi svoje slovo tak brzo).

ADD: Kdyby mel moznost, urcite by Susteka normalne odstrelil z diskuse. Me to udelal v N-O-N-Public. Nebrecim po tom, ale je videt, ze sam necti demokracii a svobodu slova na Netu, kterou neustale tak propaguje v N-O-N. Po pravde receno, me nezklamal. Zachoval se presne jak se od nej dalo cekat.

VmiP.

ADD2:Obecne se par lidi jiz dobre pobavilo, kdyz si precetli moji korespondenci s LZ. Takze pokud mate nekdo zajem ... (It's 100% FREE :-).

Mam zajem. Rad bych si pripomnel, jestli zustavam svuj a mam i nadale odlisny pohled na demokracii:)

Taky mam zajem o tu korespondenci. Zverejnil bych to na NetMagu.

Ale jejej, tak to vam muzu do vaseho kanalu poslat dalsi skvele exemplare. Staci rict, mam toho tady spousty. Treba by se pak vsichni ublizeni mohli schazet u vas, stoupla by vam navstevnost a mozna se bychom se dockali vzniku nove politicke strany. Uz to chce tu starou gardu vymenit... Ale vazne - co bych neudelal pro svou i pro vasi i pro jejich slavu - kdyz tak se ozvete:)

No comment. Got it?

No, on ani MegaText nepracuje právě ideálně. Když zadám např. "Lukáš Mižoch" tak čekám, že mě to hodí na osobní stránky tohoto člověka [alias mě :-)]. Ovšem MegaText vychrlí spoustu úplně jiných odkazů. Zato Google to zpracoval velice hezky, dokonce byl odkaz na mé stránky na prvním místě. :-)

Proč by vás měl hodit zrovna na osobní stránku? Je to textový vyhledávač, hodí vás proto na ty stránky, kde se o Lukáši Mižochovi nejvíc píše. Že to není zrovna vaše osobní stránka, to už je spíš vaše chyba :-) Ale vážně: použil jste pro danou úlohu nesprávný nástroj, hledám-li home page nějakého člověka nebo firmy, najdu ji nejsnáze na Seznamu nebo nějakém podobném katalogu. Fulltextový vyhledávač hledá text, proto se tak jmenuje.

Člověka by ale čekal, že když má stránka jako první slovo v textu "Lukáš Mižoch" a to samé je i v titulku a hlavičce, tak ho to najde jako prvního. Proto to tam taky je, že ano. :-)

Tak to ja byl az na trenim :-((. Ale koukam, na kolika mistech se me jmeno objevuje. To si clovek uvedomi, az kdyz se da vyhledat :-)))

Plne se ztotoznuju s tvrzenim pana Zajicka. Jen bych jeste dodal, ze to, ze Google pagerank skutecne pouziva, je videt uz na vysledcich jeho hledani - zatim jsem nenarazil na jedinej dotaz, kterej by v nejakym vyhledavaci nasel lepsi vysledky nez Google. A to do toho zahrnuju i to, ze cesky stranky uz prohledavam vyhradne Googlem a ne specializovanejma ceskejma prohledavacema.

Pane Sustku, dovolim si s vami nesouhlasit v podstate ve vsem, co rikate. Vezmeme to postupne:

>nepouziva ani ten tolik opevovany Google

Google PageRank pouziva - a napr. ve svem katalogu ho i graficky zobrazuje, takze se muzete podivat, jaky pagerank vybrane stranky maji.

>mate-li indexovat jednu miliardu stranek, jste radi, kdyz se vam takove kvantum dat vubec podari nejak pouzitelne naskladat do pocitace

Autori Googleu o PageRanku s oblibou prohlasuji, ze je to "vyreseni milardy rovnic s miliardou neznamych". To je pravda - je to slozite. Na druhou stranu to neni nic, co by nezvladl pocitac kterehokoliv z ctenaru Lupy pres noc.

>Megatext Indexuje 3 miliony stranek a temer 1.5 miliardy slov. Pouhe setrideni techto slov podle abecedy trva na bezne vybavenem pocitaci pul dne

Z tech 1.5 miliard slov bude ale pouze nekolik malo milionu unikatnich. Ty ma smysl tridit a to zvladne dobry algoritmus za chvilku. Navic neni duvod, proc by fulltextovy hledac potreboval radit slova podle abecedy.

>Na 95% internetovych stranek vede jen jeden odkaz

To ano, to nijak PageRank nevyvraci. Proste ona stranka dostane cast PageRanku materske stranky - tedy i jednotlive, malo zalinkovane stranky, budou pagerankem odliseny - podle toho, v jake strukture se nachazeji.

> Google PageRank pouziva - a napr. ve svem katalogu ho i graficky zobrazuje,

To nepopírám, zobrazuje tam nějaké ohodnocení stránek, které se snaží počítat nějakou smysluplnou metodou. Rozhodně ale ne tak, že by řešil soustavu jedné miliardy rovnic o miliardě neznámých, jak tvrdí. (Tedy rovnic na sobě vzájemně nezávislých - snad si rozumíme).

> Na druhou stranu to neni nic, co by nezvladl pocitac kterehokoliv z ctenaru Lupy pres noc.

Pokud má některý čtenář Lupy počítač, který je schopen pojmout matici o 1E18 koeficientech, ať se ozve.

> Z tech 1.5 miliard slov bude ale pouze nekolik malo milionu unikatnich

Ano, je jich asi 14 milionů, ale jak je chcete najít aniž byste je setřídil? Budete je postupně po jednom vyhledávat v tabulce a nové vkládat? To bude trvat 10x déle. A pokud se vám ta tabulka náhodou nevejde celá do fyzické paměti, bude to trvat 100x déle.

> proc by fulltextovy hledac potreboval radit slova podle abecedy.

Třeba proto, aby z nich sestavil vyhledávací index. Nebo znáte nějaký efektivní algoritmus pro vyhledávání v neseřazených datech?

> materske stranky - tedy i jednotlive, malo zalinkovane stranky, budou pagerankem odliseny

Relevantnost takto získaných hodnot by podle mého názoru byla mizivá.

Celkově k tomu PageRanku: Zdá se mi, že hlavní metoda, kterou Google používá je to, že zadaný výraz nejprve hledá v katalozích stránek, které má k dispozici (interně načtené Yahoo, Seznam...). Pokud jej tam najde v titulku stránky, uvede tuto stránku na prvním místě. Supluje tak nedokonalé schopnosti laických uživatelů, kteří nevědí, že pro hledání frekventovaných pojmů jako jsou např. názvy firem je vhodnější místo fulltextu použít nějaký katalogový seznam.

> Z tech 1.5 miliard slov bude ale pouze nekolik malo milionu unikatnich

Ano, je jich asi 14 milionů, ale jak je chcete najít aniž byste je setřídil? Budete je postupně po jednom vyhledávat v tabulce a nové vkládat? To bude trvat 10x déle. A pokud se vám ta tabulka náhodou nevejde celá do fyzické paměti, bude to trvat 100x déle.

Pokud projdu 1000 stranek, a uplne na kazdy budou slova jako "A", "ALE", "NEBO" (a ostatne vubec vsechny spojky, predlozky, a osobne bych asi automaticky vyrazoval vsechny jednoznakovy slova), tak uz mam pomerne slusnou pravdepodobnost, ze se ty slova budou vyskytovat i vsude jinde a muzu je vyhazet. Takze prvnich X tisic zaindexovani treba bude pomalejsich, ale o to rychlejsi bude zbytek.

> proc by fulltextovy hledac potreboval radit slova podle abecedy.

Třeba proto, aby z nich sestavil vyhledávací index. Nebo znáte nějaký efektivní algoritmus pro vyhledávání v neseřazených datech?

Slysel jste napriklad nekdy o tzv. hashovani?

Relevantnost takto získaných hodnot by podle mého názoru byla mizivá.

Az bude vas prohledavac vracet vysledky relevantnejsi nez Google, tak si o tom muzeme popovidat. Momentalne ovsem jsme v situaci, kdy vy kritizujete Google za neco, co sam udelat nedokazete, ale Google ano.

> Slysel jste napriklad nekdy o tzv. hashovani?

Jistě, nepodceňujte mě.

Jestli znate hashovani, tak proc obhajujete potrebu radit slova podle abecedy vyrokem "Nebo znáte nějaký efektivní algoritmus pro vyhledávání v neseřazených datech?". Me se zda, ze si proste odmitate pripustit, ze by "nejakej blbej Google" mohl bejt lepsi nez vy, a dokazujete to navzajem si odporujicimi tvrzeni podle toho, jak se vam to zrovna hodi. Mozna to tak nemyslite, ale rozhodne to z vasich prispevku vyplyva. Je mi lito.

Tak jsem to rozhodně nemyslel. Google je vynikající, sám jej často používám. Hashování je také vynikající, i Megatext je často používá. Chtěl jsem jen říct, že zpracovat miliardu položek není na dnešních počítačích nic jednoduchého a vyřešit soustavu miliardy lineárních rovnic o miliardě neznámých, jak to Google uvádí, je zcela nemyslitelné.

Dobry den,

docela me pobavila diskuse ohledne Megatextu. Pusobi to me me dojmem, ze autor pred tim, nez zacal psat vlastni program sahl po prvnim algoritmu, ktery ho napadl, misto toho, aby si protudoval nejakou teorii, ktera by praci indexovace znacne zjednodusila. Tezko by pak psal tvrzeni typu "Znate lepsi zpusob, nez vse setridit". Hashovani je rychlejsi jak v sestavovani indexu, tak v samotnem vyhledavani.

So se tyce rovnic o miliarde neznamych, tak je znamo, ze neni rovnice, jako rovnice, ale ze existuji specialni typy rovnic, ktere je mozne resit pomerne jednoduseji.

Doporucuji nastudovat alespon zaklady algebry a teoreticke informatiky.

No konečně jeden fundovaný partner do diskuse! Vidím JS, že máš nejméně jeden semestr lineární algebry, takže se o tom můžeme pobavit na odpovídající úrovni:

Ad soustava rovnic:
Jistě, matice soustavy, kterou Google řeší, bude zcela jistě velmi řídká, takže Google ve skutečnosti neřeší miliardu rovnic, ale pouze milion, možná 10 milionů. Ale to je přesně to, co říkám: vypouští tiskové zprávy s miliardovými ciframi a je rád, že to lidi baští.

Ad hashovaní:
Jistě, pro náš problém s hledáním unikátní podmnožiny řetězců by se dalo s výhodou použít. Ovšem pouze za jednoho předpokladu: a totiž že dopředu víme, že výsledná podmnožina bude mnohem menší než zdrojová množina. Budeme totiž muset řešit hashovací kolize a to buď:
a) tím, že výsledek ještě jednou zkontrolujeme algoritmem, který jsem původně popsal já
b) nebo tím, že použijeme hashovací tabulku s literálními hodnotami
Případ a) by pro velkou množinu znamenal, že hashování bylo zbytečný mezikrok, případ b) by pro velkou množinu znamenal, že se tabulka nevejde do fyzické paměti a algoritmus bude nepoužitelně pomalý.

Jinak samozřejmě přeji hodně úspěchů do dalšího studia ...a nic ve zlém :-). Diskutujeme tu všichni i proto, abychom se pobavili. Třeba se jednou sejdeme u nějakého softwarového projektu.

No konečně jeden fundovaný partner do diskuse! Vidím JS, že máš nejméně jeden semestr lineární algebry, takže se o tom můžeme pobavit na odpovídající úrovni:

Proc ta ironie? Pokud mam bejt uprimnej, tak jestli mam o nekom z diskutujicich dojem, ze nevi, o cem mluvi, tak jste to vy.

Jistě, matice soustavy, kterou Google řeší, bude zcela jistě velmi řídká, takže Google ve skutečnosti neřeší miliardu rovnic, ale pouze milion, možná 10 milionů. Ale to je přesně to, co říkám: vypouští tiskové zprávy s miliardovými ciframi a je rád, že to lidi baští.

1) Jsem presvedcenej o tom, ze obliba Google plyne spis z uzasny kvality vysledku, ktery vraci, nez z poblouzneni lidi "tiskovyma zpravama s miliardovyma ciframa".

2) Pokud uz chcete jit do detailu a ohanet se zaklady matematiky: Chcete mi tvrdit, ze kdyz mam miliardu rovnic o miliarde neznamych, tak vlastne zalezi na tom, jak ridce nebo huste jsou usporadany, aby se dalo o 1Gx1G mluvit? Podle me zalezi na poctu promennych, ne na tom, kolik operaci je pro vyreseni soustavy provyst.

b) nebo tím, že použijeme hashovací tabulku s literálními hodnotami. [...] případ b) by pro velkou množinu znamenal, že se tabulka nevejde do fyzické paměti a algoritmus bude nepoužitelně pomalý.

Jenze tim hashovanim by napred slo roztridit, kterej pocitac ma to dany slovo zpracovavat, a kazdej pocitac by pak mel v pameti jen svou cast dat. Takze pokud bych uvazoval treba jen 1000 pocitacu s jen 32 MB pameti, uz by mohly zpracovavat 32 GB dat v hashovacich tabulkach (samozrejme bude potreba nejaka ta pamet na vykonnej kod, ale to je celkem zanedbatelna polozka). Nepochybuju, ze tehc pocitacu je mnohem vic, nez 1000, ze maj mnohem vic pameti nez 32 MB, a ze si v ty pameti nedrzej uplne vsehcny slova, ale jenom ty nejcastejsi (ze tu pamet pouzivaj spis jako diskovou cache nez na skladovani obrovskych tabulek). I kdyby se mela indexovat miliarda ruznych slov, tech casto pouzivanych muze bejt maximalne par milionu (spis bych rekl par desitek az set tisic, ale to je jen muj odhad - a ja se lingvistikou nezabyvam), a to uz se do pameti pocitacu klidne vejde. Tech 100 slov denne, co vybocujou z normalu, se klidne muze nacist z disku...

Dik za odpoved, studium jedne VS uz mam ukoncene, druhou jeste studuji, takze to neni tak uplne od veci. Osobne si ale myslim, ze titul prilis nevypovida o kvalitach cloveka. V jedom svem rocnikovem projektu jsem se zabyval vicevlaknovym indexovanim textu - a kupodivu zase tak casto ke kolizim nedochazelo. Pokusim se strucne nastinit algoritmus - je velmi trivialni.

Mejme pole o rozumne velikosi (radove 10ky tisic). Mejme hashovaci funkci, ktera pro libovolny retezec vypocita hodnotu, ktera je v intervalu 0..velikost pole. Klic funkce nemusi byt pro vsechny retezce jedinecny, ale funkce by mela data rozume rozvrstvit po celem intervalu (asi nejvetsi problem - najit vhodnou hash. fci). V kazdem prvku pole je odkaz na nejakou datovou strukturu, kam se ukladaji slova s odkazy. Pro nas pripad je jedno, zda je to dalsi hash. tabulka, seznam, nebo nejaka databaze.

No a samotne vlozeni vypada takto:
1. vypocitame hodnotu hash. fce pro retezec
2. zamkne se dat. struktura, ve ktere je ulozen seznam slov pro tuto hodnotu funkce
3. prida se slovo a odkaz do dat. struktury
4. odemknuti

Zindexovani textu je timto algoritmem velmi rychle, pokud to spustite s vice vlakny, tak dochazi sice ke kolizim, ale neni jich prilis (do 1%). Vyhledavani je take velmi rychle - spocita se hodnota has. fce hledaneho retezce a pak uz se jen v pomerne malem seznamu nalezne konkterni hledane slovo (samozrejme lze zase vyuzit has. fce). Nevyhoda - problem hledani podobnych slov.

Celkem by me zajimalo, jaky algoritmus pouziva autor megatextu (pripadne jaky byste doporucili ostatni), opravdu me neni jasne (bez nejake ironie), jakou vyhodu ma trideni vsech slov, pripadne prohledavani seznamu setridenych slov oproti hashovani.

S pozdravem,

Jindrich Sarson

Ano, toto, co popisujete, je klasická hashovací tabulka. Její základní nevýhoda při použití ve fulltextovém vyhledávači spočívá v tom, že objem dat je tak velký, že se celá tabulka nikdy nevejde do paměti. Při jejím plnění musí počítač často swapovat a to celý algoritmus neúnosně zdrží. Megatext používá indexy založené na běžných seřazených tabulkách s binárním vyhledáváním. Nejdůležitější výhodou je, že taková tabulka se dá sestavit jedním lineárním průchodem nad setříděnými vstupními daty. Pokud se nevleze celá do paměti, není to žádný velký problém: sestavování probíhá postupně od začátku do konce a může se to rovnou zapisovat na disk. Na jednou zapsaná data se už nikdy nesahá. U hashovací tabulky se naopak při každé vkládací operaci sahá na nějaké náhodné místo uvnitř dat a jedno a totéž místo se může swapovat z disku do paměti a zpět třeba tisíckrát. Myslím ale, že jsme už dost odbočili od tématu článku... Netušil jsem, že se tu rozpoutá tak vášnivá debata, všem, které jsem snad nějak urazil, se omlouvám ...a dneska končím.

Dobry den,

no asi si uplne nerozumime. Ja jsem netvrdil, ze vsechna data budou v pameti. V pameti je pouze tabulka s odkazy pro kazdou hodnotu fce - ktera ma konstantni velikost, rekneme treba 10 MB. Odkazy pak jsou napr. soubory. Po castech jde samozrejme tridit take, sloucit 2 hash tabulky neni zadny problem. Algoritmus neni samozrejme tak naivni, ze by pri pridani noveho slova do prislusneho seznamu, ktery je urcen hash. fci zvetsoval vzdy - soubor se vzdy zvetsi o urcity nsobek puvodni hodnoty (podobne, jako se to dela u dynamickych poli) - takze nedochazi k prilisne fragmentaci.

Chtel bych se zeptat, jak mate vyresenou situaci, kdy se objevi nova stranka. To sestavujete cely velky index znovu? Pridani noveho slova do hash tabulky je zalezitost okamziku.
Co se tyce vyhledavani, tak pri pouziti binarniho trideni se samozrejme skace po disku vice, to je snad jasne. Pri pouziti hash se skoci jednou - na misto, kam se odkazuje has funkce a zde jiz pak jsou samotna data. Pri binarnim puleni to musi pekne trhat hlavicky (zvlaste u velkeho souboru).

Dobrou noc,

Jindrich Sarson

Vazeny pane Sustek,

> To nepopírám, zobrazuje tam nějaké ohodnocení.

neni to 'nejake ohodnoceni' ziskane 'nejakou smysluplnou metodou'. Je to 'dobre ohodnoceni' ziskane 'dobrou metodou'.

> počítač, který je schopen pojmout matici o 1E18 koeficientech

Neni zcela jasne o ktere z matic hovorite. Mate na mysli nejaky konkretni algoritmus ? Z jakeho duvodu se domnivate, ze se vsechny analyzy musi provadet 'najednou' ?

> znate efektivní algoritmus pro vyhledávání v neseřazených datech?

Kdyby vsechny algoritmy vyhledavani vyzadovaly data pripravena pekne podle abecedy, obavam se, ze by slo skutecne o 'neresitelny problem' (ve smysluplnem case) - k tomuto zaveru vsak pravdepodobne smerujete. Nebo je motivace Vasi polemiky jina?

Pochopitelne si jednotlive algoritmy ruznymi metodami 'pomahaji'; v dusledku se nejedna o nic jineho nez o obycejnou optimalizaci naroku. Jak uvadite v jinem prispevku, o hashovani jste uz slysel - to je dobry priklad.
Pojmy, ktere jste (vyse) zminil: 'pamet', 'vypocetni sila', 'nejake algoritmy' (, ...) ve skutecnosti NEJSOU ARGUMENTY VYLUCUJICI EXISTENCI INTELIGENTNIHO (chapejte funkcniho) VYHLEDAVANI, jak vyplyva z Vaseho nazoru - JSOU NEZBYTNYM PREDMETEM OPTIMALIZACE TAKOVEHO VYHLEDAVANI. Tedy napr. funkcnost/kvalitu Google nesnizuji ale naopak pozvedavaji. Pro dalsi diskusi povazuji za nezbytne si tento rozdil v chapani ujasnit, Vas prvni prispevek dava pak zcela jiny smysl.

Jádrem mého příspěvku bylo toto: Metoda PageRank, kterou Google na svých stránkách popisuje, se snaží přidělit váhy jednotlivým stránkám podle toho, kolik a jakých odkazů obsahujících hledaný text na danou stránku vede. Proti tomu jsem namítal to, že na většinu stránek vede tak málo odkazů, že se z nich dostatečně spolehlivá informace nedá vyzískat. Google dále tvrdí, že potřebné informace získává řešením soustavy jedné miliardy rovnic o miliardě neznámých. Taková soustava se dá popsat maticí obsahující miliardu krát miliardu prvků, což se podle mého názoru s dnešní výpočetní technikou nedá zvládnout. Nepopírám ale, že nějaká metoda PageRank skutečně mohla existovat. Google ji možná používal ve svých začátcích, kdy indexoval pouhý zlomek dnešního množství stránek a oba výše uvedené argumenty neplatily. Myslím si ale, že dnes už Google používá pro přidělování vah podobné techniky, jako jiné vyhledávače (např. upřednostňování stránek s hledaným textem v titulku, v nadpisech, v odkazech vedoucích z Yahoo nebo jiných katalogů) a řeči o miliardové soustavě rovnic jsou pouhou marketingovou vatou. Tím jsem ale nechtěl popřít to, že Google je špičkový vyhledávač, který sám rád používám. Chtěl jsem jen poukázat na to, že šikovně prováděné PR dokáže obloudit i řadu lidí, kteří si jinak myslí, že jsou proti reklamě těžce odolní. (Možná proto někteří tak podrážděně reagují).

The speed you experience can be attributed in part to the efficiency of our search algorithm and partly to the thousands of low cost PC's we've networked together to create a superfast search engine.

Toto je prvni odstavec ze stranky http://www.google.com/technology/index.html.

Takze argument, ze na vasem PC to trva dlouho neobstoji. Na tisicech PC to asi bude o neco rychlejsi.

Veškeré technické popisy Googlu hovoří jasně o tom, že se tam tahle technologie používá, tak nevidím důvod, proč by si vymýšleli.
Žádný originální český vyhledávač tuto technologii zřejmě nevyužívá, ale např. redbox.cz používá vyhledávač Google jako background - mají to licencované. Teď to tam ale nikde nemůžu najít :-)

Takže prostě fakt, že Google funguje, znamená, že používají úžasné mimozemské algoritmy, které fungují na pro pozemšťany nepochopitelných principech... Zajímalo by mě, jak jinak vysvětlíte tak dobré vyhledávací výsledky na Google.

O názor nahoře to zaznělo - využívají toho, že podstatně levnější je mít 4 bazarové počítače v síti než 1 superstroj. Uvědomte si, že stačí mít nějaká Pentia, klidně bez monitoru, klávesnice, myši, jen počítač... to se dneska dává skoro za odvoz. No a pak to propojit po síti a nechat pracovat. Podle mě je to super myšlenka.

Vazeny pane Sustek,

Metod trideni je vskutku mnoho, nekdo jejich studium povazuje za jednu ze zakladnich oblasti algoritmizace. Ujistuji Vas, ze Empyreum Service Develeopment, ale zcela jiste ani Google nevyuzivaji ke trideni ani jinym analyzam Vami citovany "bezne vybaveny pocitac". Nase systemy se od beznych lisi predevsim softwareovym vybavenim (99% vlastni produkty, zasada nepouzivani produktu spolecnosti Microsoft, atp.).

Domnivam se, ze byste mel vyuzit moznosti konzultace v oblasti technologie FullRank nasi spolecnosti. V pripade zajmu kontaktujte, prosim, nase obchodni oddeleni na adrese sales@empyreum.cz.

Těžko jen souhlasit se spojením "dobře spravovaných zdrojů jako je např. Yahoo", Yahoo má podstatně vyšší procento odkazů na dávno neexistující stránky nežli Atlas či Centrum.

Vzhledem k tomu, ze jsem ve svedskych novinach cetl clanek, ktery se obsahem a strukturou velice podobal clanku tomuto (nic proti clanku ci autorovi) a ten clanek byl prevzat z americkeho zdroje tak by mozna neskodilo i zde uvest odkud autor cerpal informace. Jedine co nebylo prevzato je pasaz o tom jak googlove po praci hraji street hokej.
Podotykam - radeji takoveto napul prevzate clanky nez blaboly vycucane z prstu.

Proc by melo jit o prevzatej clanek? Informace, ktery tady byly uvedeny, povazuju takrka za naprosto elementarni zaklady teorie o vyhledavani dokumentu. Cimz chci naznacit, ze v tomhle si samozrejme budou vsechny clanky velmi podrobny - ja znam skoro totez, jen trochu jinejma slovama, z predmetu Metody zpracovani informaci na VSE...

Clanek jsem psal z hlavy a nepouzival k nemu primo zadne materialy. Vychazim z vselijakych whitepaperu, ktere jsem za uplynuly rok, kdy jsem se teto problematice venoval, cetl.

Svedsky neumim, ale kdyz uvedete vas zdroj, rad se na nej mrknu. O hokeji vsak tyto clanky nebudou, i ten Google byl spis jako priklad, me jde predevsim o algoritmy, myslenky a technologie.

Jenom rejpnuti: mozna, ze by neskodilo se zminit o tom, ze jde vlastne o citacni analyzu - tedy vec, ktera se bezne pouziva pri hodnoceni informaci.

Souhlasim, ono by neskodilo o PageRanku uvest jeste spoustu dalsich veci (uz tak jsem to lehce zjednodusil). Text, ktery by jen toto tema plne rozebiral, by byl tak na tri "Lupi" clanky...
Ale nebojte, v pristim dilu se k citacni analyze jeste vratime, dokonce uvedu jeste lepsi algoritmus.

Dovoluji si doporucit napriklad semanticke stromy od Verity a dalsi umele Ynteligentni technologie (neuronove a bayesovske site...).
Nicmene hlavni trend vyhledavacu vidim v presnosti - na Intenetu se da najit vse a to ve spouste zdroju. Presnost tedy jako obrana proti informacnimu zahlceni velmi kriticka. Bohuzel soucasne vyhledavace se orientuji spise na uplnost :-( .
Takze doporucuji se zamerit na vyhledavaci stroje s automatickym profilovanim uzivatelu - ty mohou zjistit, ze pod pojmem 'sit' minim ethernet a ne neco na chytani ryb ;-).
No ale abych jen nepindal - www.autonomy.com - _velmi_ fikany kontextove orientovany vyhledavaci engine s profilovanim uzivatelu...

Citační analýza, jaká se používá např při tvoření citačních indexů podle kteých se hodnotí publikované práce není založena jen na statistice, že někdo něco otisklk a někdo jiný to citoval: roli hraje publikace v renomovaných časopisech,které mají editory, kteří jsou ve svém oboru uznávání, opírá se tady také o autoritu , která ve vědecké komunitě platí. Pro toho, kdo tuto autritu uznává je to tedy do určité míry výpověď o hodnotě obsahu práce. Tady ale jde ale čistě statistický ohlas. Informace tohoto druhu je užitečná pro tvůrce stránek z obchodního hlediska a pro uživatele, kteří hledají orientaci v tom, co v dané oblasti zrovna letí. Je to takový začarovaný kruh, protože tvůci stránek se snaží dosáhnout vysoké známosti a tou se zase řídí uživatelé. Je to jako anketa o zlatého slavíka - zpěvák je populární protože je populární. Pokud hledám specifikou informaci v oblasti, kde se trochu vyznám, je mi tenhle druh informace k ničemu. Pomůže spíš promyšlená fromulace dotazů pomocí fulltextového vyhledače s Booleovským vyhledáváním. Tak mám šanci najít infromace, které jsou skutečně obsahově relevantní a důvěryhodné. Tohle je myslím ohromná vymoženost a na rozdíl od spoléhání se na to, že mu statistická kriteria přihrají ty správné stránky tu nehrozí to, že internet své uživatele dovede k zblbnutí jeko to dělá televize - používáte vlastní hlavu.

No slava! Konecne nekdo uvedl, ze Page Rank neresi vsechno. Jeden priklad za vsechny. Kdyz jsem sveho casu instaloval Sendmail (ale muze to byt cokoli jineho), mel jsem k dispozici obvykle texty manualu, na strankach firmy Sendmail je houstina - rovnez manualovych - popisu.

V ten moment by mi byl mily prehledny "lidsky" popis instalace vcetne zakladnich konfiguraci - neco jako reportaz z instalace. Google ji jednoduchym dotazem nedoda (mozna nekde vzadu). S pouzitim AND OR NOT atd. jsem se propracoval na takovou reportaz nejakeho Japonce. A vsechno bylo hned jasne. To se tyka hledani informaci z jakehokoli oboru ci kategorie lidskych cinnosti.

Page Rank je dobry pro stranky, ktere si vyslouzily zajem odkazy odjinud. Ale chudinky stranecky, ktere "nikdo nema rad" a jsou velmi dobre, Page Rank nevytahne ze tmy. Page Rank bych (i kdyz to neni presne ono) prirovnal ke kamenikum, kteri prezentuji malou cast hudby jejim mlacenim do hlav lidi vsemi kanaly. Lidi se tak odkazuji na jejich cedecka. Jenze na svete jsou mnohem vetsi kvanta perfektni hudby, kterou drtiva vetsina lidi nezna. (Skoro bych Googlu navrhl, aby umoznil zadani "Page Rank = 0" pro vytazeni "nepopularnich" stranek:)

Na Googlu je skvela jedna vec, kterou nikdo nezminil - slucovani stranek ze stejneho zdroje, takze je vypis prehlednejsi (nemusi se poskakovat po spouste vypisu, resp. zadavat vylucovaci NOT). I ono "More pages from..." je parada (stejne tak "Similar Pages" a "Cached").

Krome toho je Google dobry v tom, ze vytahuje i texty z databazi (neignoruje "?" v URL), coz zdaleka vsichni necini, a pokud to cini, ne v takove mire. Well...that's all.

Pokud by se clanek jmenoval "Nove trendy vyhledavacu" dalo by mu tezko neco vytknout. V opacnem pripade nechapu, proc se Autor zabyva takovou starou vestou a nebere potaz vyhledavani v audio a videodatech ...

Vyhledavanim v textu internetovych stranek se zabyvam proto, ze je mi toto tema nejblizsi a protoze takove vyhledavani je nejcastejsi. Toto je prvni clanek ze serie, a budeme se zabyvat i dalsimi typy vyhledavani. Zmenou slov "ve vyhledavani" na "vyhledavacu" se podle me smysl nadpisu nezmeni.
Pokud mate nejake zajimave informace o vyhledavani ve videodatech, velmi by me zajimaly, ja sam nevim o zadnem projektu, ktery by tohoto byl schpny (nemyslim soucasne multimedia searchery, ty hledani pouze v textovych nazvech)

Nez bych zasahoval do rozsahleho threadu nahore (neverte reklame, sustekovi, atd.), napisu jeste par informaci sem.

To, ze je pocitani PageRanku "miliarda rovnic o miliarde neznamych" rozhodne neznamena, ze by se mela resit matici 1E18 prvku, jak navrhuje pan Sustek (a z toho pak spravne vyvozuje, ze by to bylo nemozne). Je to stejne hloupy napad jako radit slova ze stranek podle abecedy (= neoptimalni algoritmus)

Resi se to iterativnim opakovani rovnice (vzpominate na clanek? je tam zjednodusena rekurzivni definice pageranku). Ta po cca 20 iteracich (jedna iterace ma slozitost umernou poctu linku, vsechny operace jsou trivialni) aproximuje vysledky s pozadovanou presnosti.
Na toto staci jediny bezny pocitac (lepe kdyz ma vic pameti) a par minut v pripade indexu ceskeho, nekolik hodin az desitek v pripade celosvetoveho.