第一次作业

题目1：考虑以下文档

文档名	内容
文档1	new home sales top forecasts
文档2	home prices rise in june
文档3	increase in home sales in june
文档4	july new home sales rise

1、画出文档集对应的词项-文档矩阵

	文档1	文档2	文档3	文档4
forecasts	1	0	0	0
home	1	1	1	1
in	0	1	1	0
increase	0	0	1	0
july	0	0	0	1
June	0	1	1	0
new	1	0	0	1
prices	0	1	0	0
rise	0	1	0	1
sales	1	0	1	1
top	1	0	0	0

2、参考以下图例，画出该文档集的倒排索引（需要按照字典序排列）

3、给定如下查询，返回的结果是什么？

• rise AND new
  • 0101 and 1001 = 0001
  • rise->2,4 new->1,4（参考）
  • 文档4
• sales AND NOT (forecasts OR july)
  • forecasts OR july = 1000 or 0001 = 1001
  • NOT(forecasts OR july) = 0110
  • 1011 and 0110 = 0010
  • 文档3

题目2、VB编码与γ编码

​ 写出倒排记录表(777，17743，294068，31251336)的VB编码以及 $\gamma$ 编码，在可能的情况下对间距而不是文档ID编码。请以8进制串的方式写出这些编码。（$\gamma$ 编码不考虑对0编码的问题，仅对原始文档ID以及间隔进行编码）

VB编码计算：

1. 计算相邻数的间距（后一个减前一个）
2. 将间距转换为二进制
3. 将结果写入有效编码区间，每个字节的后7位是字节有效编码区间，每个字节的高8位置0（如果是最后一个字节置1）。

777的二进制编码，7个一组进行拆分：110 0001001

然后在最后一个字节的专用位（高位）c置为1。

得到777的VB编码为：0000,0110,1000,1001

然后每个文档ID计算与前一个的间距，使用同样的方式计算VB编码。

γ编码计算：

1. 计算相邻数的间距（后一个减前一个）
2. 将间距转换为二进制
3. 将间距的二进制形式首部的1去除，作为偏移，偏移的位数作为长度
4. 将长度转换为一元编码
5. 将长度和偏移拼接

将间隔G表示成长度和偏移两部分。

偏移对应G的二进制编码，去除首部1；

长度部分表示偏移的位数，采用一元编码（将n表示n个1和末位补0）。

777的二进制编码去除高位1得到偏移部分：100001001

偏移部分位数为7，因此长度部分编码为：11111110

文档ID	777	17743	294068	31251336
间距	0	16966	276325	30957268
VB编码	0000,0110,1000,1001	0000,0001,0000,0100,1100,0110	0001,0000,0110,1110,1110,0101	0000,1110,0110,0001,0011,1101,1101,0100
γ编码	1,1111,1101,0000,1001	1,1111,1111,1111,1000,0010,0100,0110	1,1111,1111,1111,1111,1000,0011,0111,0110,0101	1,1111,1111,1111,1111,1111,1110,1101,1000,0101,1110,1101,0100

题目3：K-gram索引

1、计算查询 “bord” 与图中每个包含 2-gram “or” 的词项之间的 2-gram Jaccard 系数，并写出计算过程。

“bord”与图中包含2-gram ”or”的词项，2-gram集合：

包含or的词项	2-gram
bord	$b, bo, or, rd, d$
border	$b, bo, or, rd, de, er, r$
lord	$l, lo, or, rd, d$
morbid	$m, mo, or, rb, bi, id, d$
sordid	$s, so, or, rd, di, id, d$

Jaccard系数计算公式
$$Jaccard(a,b)=\frac{|a\cap b|}{|a\cup b|}$$
不考虑首尾标志符：

bord与border：

• bord ∩ border = {bo, or, rd}
• bord ∪ border = {bo, or, rd, de, er}
• Jaccard(bord, border) = 3/5

bord与lord：

• bord ∩ lord = {or, rd}
• bord ∪ lord = {bo, lo, or, rd}
• Jaccard(bord, lord) = 2/4 = 1/2

bord与morbid：

• bord ∩ morbid = {or}
• bord ∪ morbid = {bo, mo, or, rb, rd, bi, id}
• Jaccard(bord, morbid) = 1/7

bord与sordid：

• bord ∩ sordid = {or, rd}
• bord ∪ sordid = {bo, so, or, rd, di, id}
• Jaccard(bord, sordid) = 2/6 = 1/3

考虑首尾标志符：

bord与border：

• bord ∩ border = {$b, bo, or, rd}
• bord ∪ border = {$b, bo, or, rd, d$, de, er, r$}
• Jaccard(bord, border) = 4/8 = 1/2

bord与lord：

• bord ∩ lord= {or, rd, d$}
• bord ∪ lord= {$b, bo, or, rd, d$, $l, lo}
• Jaccard(bord, lord) = 3/7

bord与morbid：

• bord ∩ morbid= {or, d$}
• bord ∪ morbid= {$b, bo, or, rd, d$, $m, mo, rb, bi, id}
• Jaccard(bord, morbid) = 2/10 = 1/5

bord与sordid：

• bord ∩ sordid= {or, rd, d$}
• bord ∪ sordid= {$b, bo, or, rd, d$, $s, so, di, id}
• Jaccard(bord, sordid) = 3/9 = 1/3

2、k>2时，如何添加首尾标志符？

类似的，在词项的前部的第 i 个位置，在词项开头加 k-i 个<BOS>符；在词项后部的第j个位置，在词项后头加 k-j 个<EOS>符。

比如bord计算3-gram集合：{$$b, $bo, bor, ord, rd$, d$$}

bord计算4-gram集合：{$$$b, $$bo, $bor, bord, ord$, rd$$, d$$$}

……

题目4：考虑表1中的3篇文档Doc1、Doc2、Doc3中几个词项的tf情况，表2为词项在所有文档中的idf值

表一：tf值	Doc1	Doc2	Doc3
car	27	4	24
auto	3	33	0
insurance	0	33	29
best	14	0	17

表二：idf值	${df}_t$	${idf}_t$
car	18165	1.65
auto	6723	2.08
insurance	19241	1.62
best	25235	1.5

$tf$是指词项频率，一种替代原始tf的计算方式是对数词频：

$$w_{t,d}=\{\begin{array}{ll}1+{\log }_{10}{\mathrm{tf}}_{t,d}& {\text{if tf}}_{t,d}>0\\ 0& \text{otherwise}\end{array}$$

${df}_t$是指文档频率，出现词项 $t$ 的文档数目。

$idf$权重是指逆文档权重，$N$ 是文档集中文档的数目。

$${\mathrm{idf}}_t={\log }_{10}\frac{N}{{\mathrm{df}}_t}$$

$tf-idf$权重是 $tf$ 权重和 $idf$ 权重的乘积

$$w_{t,d}=(1+\log {\mathrm{tf}}_{t,d})\cdot \log \frac{N}{{\mathrm{df}}_t}$$

1、计算所有词项car、auto、insurance、best的tf-idf值。

对于词项”car”，计算Doc1中的tf-idf值，如下所示：

$$w_{car,doc1}=(1+{\log }_{10}27)\times 1.65=4.01$$

tf-idf权重计算	Doc1	Doc2	Doc3
car	4.01	2.64	3.93
auto	3.07	5.24	0
insurance	0	4.08	3.99
best	3.22	0	3.35

参考答案：为了计算方便，采用原始的 tf 值，则 $w_{car,doc1}=27\times 1.65=44.55$

tf-idf(原始tf值)	Doc1	Doc2	Doc3
car	44.55	6.6	39.6
auto	6.24	68.64	0
insurance	0	53.46	46.98
best	21	0	25.5

2、试计算采用欧氏归一化方式处理后的文档向量，其中每个向量有4维，每维对应一个词项。
$$||V||=\sqrt{x_1^2+x_2^2+x_3^2+x_4^2}$$

对向量进行归一化：

$$\text{normalized value}=\frac{x_i}{||V||}$$

Normalized	Doc1	Doc2	Doc3
car	0.67	0.37	0.60
auto	0.51	0.73	0
insurance	0	0.57	0.61
best	0.54	0	0.51

参考答案：
$$\begin{gathered} \Vert {Vec}_1\Vert =\sqrt{{44.55}^2+{6.24}^2+0^2+{21}^2}\approx 49.65 \\ {Vec}_{Nor{m}_1}=[\frac{44.55}{49.65},\frac{6.24}{49.65},\frac{0}{49.65},\frac{21}{49.65}]\approx [0.879,0.125,0,0.423] \end{gathered}$$

3、对于查询car insurance计算3篇文档的得分并进行排序。查询词项的权重计算采用：查询
中出现的词项权重为1，否则为0。

查询词项的权重如下，

word	weight	Doc1	Doc2	Doc3
car	1	0.67	0.37	0.60
auto	0	0.51	0.73	0
insurance	1	0	0.57	0.61
best	0	0.54	0	0.51

$$\mathrm{score}=\mathrm{query}\mathrm{weight}\times {\mathrm{Doc}\mathrm{normalized}}^T$$

查询向量为：$\text{Query weight vector}=(1,0,1,0)$

计算文档1的得分：

$$\text{Doc1 normalized vector}=(0.67,0.51,0,0.54)$$

$${\mathrm{score}}_{\mathrm{Doc}1}=(1\times 0.67)+(0\times 0.51)+(1\times 0)+(0\times 0.54)=0.67$$

类似的，可以计算出：

$${\mathrm{score}}_{Doc2}=0.37+0+0.57+0=0.94$$

$${\mathrm{score}}_{Doc3}=0.60+0+0.61+0=1.21$$

根据得分计算结果，文档得分从高到低排序为：

• 文档3：1.21
• 文档2：0.94
• 文档1：0.67

参考答案：