倒排索引设计公开课PPT.pptx

信息源\网页集合
Query
检索
候选信息\
页面
相关性排序
结果
关键词\Query
基本思路
关键字匹配
好文档至少要包含query中的所有词
分词
清华大学邮编
分词
清华大学
邮编
+
最初的思路
索引查询、归并
Term:
清华大学
倒排
索引
doc1
doc2
doc3
…
Doc list A
…
…
…
…
Doc list B
……
索引归并
候选集
目标
生存
能够实现简单的倒排索引建立和检索
发展
针对高性能索引加载的设计
针对高性能索引归并的设计
针对索引压缩的设计
生存篇
第一步:建立词到文档&位置的映射关系
…
for (my $i = 0; $i < $documentCount; ++$i)
{
my $document = &ReadDocument($i);
my $words = &WordBreak($document); #分词
my $wordCount = $#$words + 1;
for (my $j = 0; $j < $wordCount; ++$j)
{
printf “%s\t%d\t%d\n”, $words->[$j], $i, $j; #建立映射
}
}
…
生存篇
第二步:按照词排序
LC_ALL=C sort -k1,1 -k2,2n -k3,3n
相同词的映射记录被调整到邻近行
相同词的记录,按照文档号从小到大排序
相同词对应的相同文档的记录,按照出现位置从小到大排序
Why?
a 3 5
b 3 1
b 3 2
b 3 5
b 5 0
b 5 1
b 6 3
d 3 4
a 3 5
b 3 1
b 3 2
b 3 5
b 5 0
b 5 1
b 6 3
d 3 4
生存篇
第三步:归并
a 3 5
b 3 1
b 3 2
b 3 5
b 5 0
b 5 1
b 6 3
d 3 4
a 3:5
b 3:1,2,5 5:0,1 6:3
d 3:4
生存篇
第四步:加载索引&检索
while (my $line = <STDIN>)
{
chomp($line);
next unless (length($line) > 0);
my ***@fields = split(/\t/, $line);
my ***@docs;
for (my $i = 1; $i <= $#fields; ++$i)
{
my %doc;
my ***@cols = split(/:/, $fields[$i]);
my ***@pos = split(/,/, $cols[1]);
$doc{"docId"} = $cols[0];
$doc{"pos"} = \***@pos;
push(***@docs, \%doc);
}
$index{$fields[0]} = \***@docs;
}
my $info = $index{$term};
加载
检索
生存篇
第四步:加载索引&检索
$VAR1 = {
'a' => [
{
'docId' => '3',
'pos' => ['5' ]
}
],
'b' => [
{
'docId' => '3',
'pos' => ['1', '2', '5']
},
{
'docId' => '5',
'pos' => ['0', '1']
},
(续)
{
'docId' => '6',
'pos' => ['3']
}
],
'd' => [
{
'docId' => '3',
'pos' => ['4']
}
]
};
生存篇
回顾
索引建立
映射关系建立
排序
归并
索引加载&检索
Hash表
二分查找