Jak funguje fulltextové vyhledávání
Tomáš Hlucháň
Obsah
• Vyhledávání
• Komponenty
– Crawler
– Indexace
– Výdej
– Přepis dotazu
– Čeština
– Řazení
• Seznam.cz Vyhledávání
Typy vyhledávání
• Sekvenční
• Hierarchie
• Index
Rušení
Strom
Uzlu
Vložení
Vyhledání
4
1
2,3,4
3
2
Obsah vs. Rejstřík
1. Strom
2. Vyhledání uzlu
3. Vložení uzlu
4. Rušení uzlu
1
2
3
4
Rušení
Strom
Uzlu
Vložení
Vyhledání
4
1
2,3,4
3
2
Obsah vs. Rejstřík
1. Strom
2. Vyhledání uzlu
3. Vložení uzlu
4. Rušení uzlu
1
2
3
4
Hledání dotazu
• jednoslovný dotaz
• dvouslovný dotaz
• negativní operátor
Crawler VýdejIndexace
Hlavní komponenty
Crawler VýdejIndexace
Hlavní komponenty
xxx
xxx
xxx
xxx
xxx
xxx
Crawler VýdejIndexace
Hlavní komponenty
xxx
xxx
xxx
xxx
xxx
xxx
Crawler VýdejIndexace
Hlavní komponenty
xxx
xxx
xxx
xxx
xxx
xxx
DB
Crawler VýdejIndexace
Hlavní komponenty
xxx
xxx
xxx
xxx
xxx
xxx
DB
Crawler VýdejIndexace
Hlavní komponenty
xxx
xxx
xxx
xxx
xxx
xxx
DB
Strom
-1,1,...
invertované indexy
Uzlu
-2,2,...
-3,2,...
-4,2,....
Crawler VýdejIndexace
Hlavní komponenty
xxx
xxx
xxx
xxx
xxx
xxx
DB
Strom
-1,1,...
invertované indexy
Uzlu
-2,2,...
-3,2,...
-4,2,....
dokumenty
-1, rank, jazyk
-2, rank, jazyk
-3...
Crawler VýdejIndexace
Hlavní komponenty
• analýza dotazu
xxx
xxx
xxx
xxx
xxx
xxx
DB
Strom
-1,1,...
invertované indexy
Uzlu
-2,2,...
-3,2,...
-4,2,....
dokumenty
-1, rank, jazyk
-2, rank, jazyk
-3...
Crawler VýdejIndexace
Hlavní komponenty
• analýza dotazu
• vyhledání
xxx
xxx
xxx
xxx
xxx
xxx
DB
Strom
-1,1,...
invertované indexy
Uzlu
-2,2,...
-3,2,...
-4,2,....
dokumenty
-1, rank, jazyk
-2, rank, jazyk
-3...
Crawler VýdejIndexace
Hlavní komponenty
• analýza dotazu
• vyhledání
• řazení dle relevance
xxx
xxx
xxx
xxx
xxx
xxx
DB
Strom
-1,1,...
invertované indexy
Uzlu
-2,2,...
-3,2,...
-4,2,....
dokumenty
-1, rank, jazyk
-2, rank, jazyk
-3...
Crawler VýdejIndexace
Hlavní komponenty
• analýza dotazu
• vyhledání
• řazení dle relevance
• snipety
xxx
xxx
xxx
xxx
xxx
xxx
DB
Strom
-1,1,...
invertované indexy
Uzlu
-2,2,...
-3,2,...
-4,2,....
dokumenty
-1, rank, jazyk
-2, rank, jazyk
-3...
Crawler VýdejIndexace
Hlavní komponenty
• analýza dotazu
• vyhledání
• řazení dle relevance
• snipety
xxx
xxx
xxx
xxx
xxx
xxx
DB
Strom
-1,1,...
invertované indexy
Uzlu
-2,2,...
-3,2,...
-4,2,....
dokumenty
-1, rank, jazyk
-2, rank, jazyk
-3...
texty
-1, text stránky
-2, text ..
Crawler
DB
xxx
xxx
xxx
xxx
xxx
xxx
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
301
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
xxx
xxx
200
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
404
500
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Chyby
– 404
– 500
– zahlcení sítě
xxx
xxx
Crawler
• Co vybrat?
DB
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
301
404
xxx
xxx
xxx
xxx
• Přesměrování
– 301
– javascript
• Duplicita
• Chyby
– 404
– 500
– zahlcení sítě
xxx
xxx
Crawler - duplicita
• Co je to duplicita?
• Úplná a částečná duplicita
• Přirozená duplicita
– http://www.seznam.cz/ http://www.seznam.cz/index.html
– test.php?x=1&y=2 test.php?y=2&x=1
– Kanonizace
• Nepřirozené duplicity
Crawler - aktualizace
• Frekvence změny
– detekce
– predikce změny
• Důležitost
– ranky
• RSS
• Technické limity
Crawler - DB
Crawler - DB
• Obsah
– “texty”
– metadata
• jazyk
• ranky
• odkazy
• ....
Crawler - DB
• Obsah
– “texty”
– metadata
• jazyk
• ranky
• odkazy
• ....
• NoSQL
Crawler - DB
• Obsah
– “texty”
– metadata
• jazyk
• ranky
• odkazy
• ....
• NoSQL
• Map-Reduce
Crawler - DB
• Obsah
– “texty”
– metadata
• jazyk
• ranky
• odkazy
• ....
• NoSQL
• Map-Reduce
Crawler - dodatky
• robots.txt
Crawler - dodatky
• robots.txt
• sitemapy
Crawler - dodatky
• robots.txt
• sitemapy
• ignorované parametry
Crawler - dodatky
• robots.txt
• sitemapy
• ignorované parametry
• výběrové funkce
– založit
– smazat
– indexovat
Crawler - dodatky
• robots.txt
• sitemapy
• ignorované parametry
• výběrové funkce
– založit
– smazat
– indexovat
Crawler - dodatky
xxx
xxx
xxx
xxx
xxx
xxx
DB
• robots.txt
• sitemapy
• ignorované parametry
• výběrové funkce
– založit
– smazat
– indexovat
Crawler - dodatky
xxx
xxx
xxx
xxx
xxx
xxx
DB
• robots.txt
• sitemapy
• ignorované parametry
• výběrové funkce
– založit
– smazat
– indexovat
Crawler - dodatky
xxx
xxx
xxx
xxx
xxx
xxx
DB
• robots.txt
• sitemapy
• ignorované parametry
• výběrové funkce
– založit
– smazat
– indexovat
Crawler - dodatky
xxx
xxx
xxx
xxx
xxx
xxx
DB
indexace
Indexace
• Získání stránky
• Převedení na “prostý” text
• Extrakce odkazů a metadat
• Výpočty metadat
• Budování rejstříku
• Aktualizace indexu
– přírůstkové
– najednou
• Uložení odkazů a metadat
Indexace - merge & split
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
index
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
index
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
index
index
index
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
index
index
index
?
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
index
index
?
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
index
index
?
Indexace - merge & split
xxx
xxx
xxx
xxx
xxx
xxx
xxx
xxx
index
index
index
index
index
index
?
Výdej
index dotaz
Výdej
Doc
1
3
21
34
67
Pos
34,23
12
45,67
1
4
auto
index dotaz
Výdej
Doc
1
3
21
34
67
Pos
34,23
12
45,67
1
4
auto
index dotaz
[auto]
Výdej
Doc
1
3
21
34
67
Pos
34,23
12
45,67
1
4
auto
index dotaz
[auto]
[bílé auto]
Výdej
Doc
1
3
21
34
67
Pos
34,23
12
45,67
1
4
auto
Doc
2
3
13
34
89
Pos
15
6,17
34
6
71,89
bílé
index dotaz
[auto]
[bílé auto]
Výdej
Doc
1
3
21
34
67
Pos
34,23
12
45,67
1
4
auto
Doc
2
3
13
34
89
Pos
15
6,17
34
6
71,89
bílé
index dotaz
[auto]
[bílé auto]
&
Výdej
Doc
1
3
21
34
67
Pos
34,23
12
45,67
1
4
auto
Doc
2
3
13
34
89
Pos
15
6,17
34
6
71,89
bílé
index dotaz
[auto]
[bílé auto]
&
Doc: 3,34
Výdej
• Pochopit
• Najít
• Relevance
• Seřadit
Doc
1
3
21
34
67
Pos
34,23
12
45,67
1
4
auto
Doc
2
3
13
34
89
Pos
15
6,17
34
6
71,89
bílé
index dotaz
[auto]
[bílé auto]
&
Doc: 3,34
Výdej - architektura
Hledání
I
Výdej - architektura
Webovka
?
Hledání
I
Výdej - architektura
Webovka
?
Hledání
I
Výdej - architektura
Webovka
?
Hledání
I
Výdej - architektura
Webovka
?
Hledání
I
Agregátor
Výdej - architektura
Webovka
?
Hledání
I
Agregátor
H
I
Výdej - architektura
Webovka
?
Hledání
I
Agregátor
I
HH
I
Výdej - architektura
Webovka
?
Hledání
I
Agregátor
H
II
HH
I
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
II
HH
I
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
II
HH
I
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
I
MetaSearch
I
HH
I
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
I
MetaSearch
I
HH
I
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
I
MetaSearch
I
HH
I
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
I
MetaSearch
I
HH
I
pochopení
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
I
MetaSearch
I
HH
I
pochopení
hledání
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
I
MetaSearch
I
HH
I
pochopení
hledání
relevance
Výdej - architektura
Cache
Webovka
?
Hledání
I
Agregátor
H
I
MetaSearch
I
HH
I
pochopení
hledání
relevance
řazení
Přepis dotazu
• Tokenizace
– “Firefox, Opera?” - [Firefox, Opera]
– “seznam.cz” - [seznam.cz]
– “C/C++” - [C/C++]
Přepis dotazu
• Tokenizace
– “Firefox, Opera?” - [Firefox, Opera]
– “seznam.cz” - [seznam.cz]
– “C/C++” - [C/C++]
• Oháčkování
Přepis dotazu
• Tokenizace
– “Firefox, Opera?” - [Firefox, Opera]
– “seznam.cz” - [seznam.cz]
– “C/C++” - [C/C++]
• Oháčkování
• Stop slova
– “bar v Brně” - [bar, Brně]
– “jak vyloupit banku” - [vyloupit, banku]
Přepis dotazu
• Tokenizace
– “Firefox, Opera?” - [Firefox, Opera]
– “seznam.cz” - [seznam.cz]
– “C/C++” - [C/C++]
• Oháčkování
• Stop slova
– “bar v Brně” - [bar, Brně]
– “jak vyloupit banku” - [vyloupit, banku]
• Operátory
– “+jak”, “recept -brokolice”, “site: .cz”
Přepis dotazu
• Kolokace
– “vlakové nádraží Brno” - [ [vlakové, nádraží], Brno]
Přepis dotazu
• Kolokace
– “vlakové nádraží Brno” - [ [vlakové, nádraží], Brno]
• Zkratky
– “ČT” - [ČT or [Česká televize]]
– “Česká televize” - [[Česká televize] or ČT]
– “vše o Praze” vs. “vše v Praze” ?
Přepis dotazu
• Kolokace
– “vlakové nádraží Brno” - [ [vlakové, nádraží], Brno]
• Zkratky
– “ČT” - [ČT or [Česká televize]]
– “Česká televize” - [[Česká televize] or ČT]
– “vše o Praze” vs. “vše v Praze” ?
• Spojování a rozdělení slov
– “babybox” - [ babybox or [baby, box]]
– “baby box” - [ [baby, box] or babybox]
Přepis dotazu
• Kolokace
– “vlakové nádraží Brno” - [ [vlakové, nádraží], Brno]
• Zkratky
– “ČT” - [ČT or [Česká televize]]
– “Česká televize” - [[Česká televize] or ČT]
– “vše o Praze” vs. “vše v Praze” ?
• Spojování a rozdělení slov
– “babybox” - [ babybox or [baby, box]]
– “baby box” - [ [baby, box] or babybox]
• Čísla
– “2. světová válka”
Strom dotazu
• AND, OR uzly
• váha, proximita
• další atributy
Strom dotazu
• AND, OR uzly
• váha, proximita
• další atributy
“ČT v Brně”
Strom dotazu
• AND, OR uzly
• váha, proximita
• další atributy
“ČT v Brně”
ČT
Česká televize
Brně
AND
OR
AND
Strom dotazu
• AND, OR uzly
• váha, proximita
• další atributy
“ČT v Brně”
ČT
Česká televize
Brně
AND
OR
AND
Hledání
I
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
rybou
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
rybou
rybám
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybou
rybám
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybou
rybám
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybo
rybou
rybám
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
• Lemmatizace
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
• Lemmatizace
– term → lemma
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
• Lemmatizace
– term → lemma
– lemma → termy
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
• Lemmatizace
– term → lemma
– lemma → termy
– desambiguace
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
• Lemmatizace
– term → lemma
– lemma → termy
– desambiguace tancích
tank tance
?
Přepis dotazu - čeština
• základní pojmy
– term
– lexém
– lemma ryba
ryby
rybě
rybu
rybo
rybou
rybám
miska
• Lemmatizace
– term → lemma
– lemma → termy
– desambiguace tancích
tank tance
?
hrách
hrách hra
?
Čeština a indexace
• Indexace lemmat
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
– lemmata do indexu
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
– lemmata do indexu
– dotaz se převádí na lemmata
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
– lemmata do indexu
– dotaz se převádí na lemmata
– problémy
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
– lemmata do indexu
– dotaz se převádí na lemmata
– problémy
• velké indexy
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
– lemmata do indexu
– dotaz se převádí na lemmata
– problémy
• velké indexy
• nejednoznačnost
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
– lemmata do indexu
– dotaz se převádí na lemmata
– problémy
• velké indexy
• nejednoznačnost
• různé jazyky
Čeština a indexace
• Indexace lemmat
– termy dokumentů převést na lemmata
– lemmata do indexu
– dotaz se převádí na lemmata
– problémy
• velké indexy
• nejednoznačnost
• různé jazyky
• přesné znění
Čeština a indexace
• Indexace termů
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
• menší indexy
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
• menší indexy
• částečné řešení desambiguace
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
• menší indexy
• částečné řešení desambiguace
• cizojazyčné expanze
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
• menší indexy
• částečné řešení desambiguace
• cizojazyčné expanze
• přesné znění
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
• menší indexy
• částečné řešení desambiguace
• cizojazyčné expanze
• přesné znění
• operativní možnosti
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
• menší indexy
• částečné řešení desambiguace
• cizojazyčné expanze
• přesné znění
• operativní možnosti
– co to neřeší
Čeština a indexace
• Indexace termů
– termy dokumentů přímo do indexu
– “vyskloňuji” při přepisování dotazu
– “OR” uzel s tvary (+váhy)
– výhody
• menší indexy
• částečné řešení desambiguace
• cizojazyčné expanze
• přesné znění
• operativní možnosti
– co to neřeší
• “kniha o německých tancích”, “ženu holí stroj”
Řazení výsledků
• Vstup: signály
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
doc
v
textu
v
titulku
PR
slov
dotazu
pořadí
A
B
C
D
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
doc
v
textu
v
titulku
PR
slov
dotazu
pořadí
A
B
C
D
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
doc
v
textu
v
titulku
PR
slov
dotazu
pořadí
A
B
C
D
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
doc
v
textu
v
titulku
PR
slov
dotazu
pořadí
A
B
C
D
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
doc
v
textu
v
titulku
PR
slov
dotazu
pořadí
A
B
C
D
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
• Lineární kombinace
doc
v
textu
v
titulku
PR
slov
dotazu
pořadí
A
B
C
D
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Řazení výsledků
• Vstup: signály
• Lineární kombinace
• Regresní rozhodovací stromy
doc
v
textu
v
titulku
PR
slov
dotazu
pořadí
A
B
C
D
Dotaz: “auto”
2 1 6 1
1 2 2 1
3 0 5 1
4 1 3 1
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+-
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+-
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+-
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+-
A
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+-
AB
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+C
AB
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+C
AB D
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D A
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D A B
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D CA B
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 3 1 4 1 3
1
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 3 1 4 1 3
1
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 3 1 4 1 3
1
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 3 1 4 1 3
1
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 3 1 4 1 3
1
5
2
4
6
Rozhodovací stromy
doc text hf PR slov pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 3 1 4 1 3
1
5
2
4
6
1. D
2. A
3. C
4. B
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 5 2 4 2.5 3.5
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 5 2 4 2.5 3.5
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 5 2 4 2.5 3.5
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 5 2 4 2.5 3.5
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 5 2 4 2.5 3.5
6.5
3.5
5.5
8.5
4
1
2
5
Stavění stromů
doc text hf PR slov ruční pořadí
A 2 1 6 1
B 1 2 2 1
C 3 0 5 1
D 4 1 3 1
PR > 4
- +
text > 1
+hf
> 1
+slov
> 2
- +
text > 2+C
AB D C DA B
1 5 2 4 2.5 3.5
6.5
3.5
5.5
8.5
E 2 0 7 1 4.5
4
1
2
5
Dodatky
• Překlepy
• Související dotazy
• Zpětná vazba
• Oháčkování 4x jinak
• Rozhodovací stromy
– spam, porno
Seznam.cz Vyhledávání
• Jak to začalo
• Co máme
• Co používáme
• Co řesíme
Jak to začalo
• Rok = 2005
• Stroje = 11
• Lidé = 4
Co máme
• Celkem 70 lidí
• 32 programátorů
• 16 produkt manažerů
• 12 výzkumníků
• 6 administrátorů
• 100 brigádníků
Co máme
• Celkem 500 strojů
• 300 vyhledávání
• 150 robot
• 50 vývoj a výzkum
• 2 serverovny
Co máme
• 500TB dat
• 50M dokumentů denně
• Rychlostí několik GBit/s
• Hledáme v 800M dokumentech
• 350 až 500 dotazů za sekundu
Co používáme
Co řesíme
• “kniha o německých tancích” ?
• Relevance
• Relevance
• Relevance
• Relevance
• …
Děkuji za pozornost…