P3639.第2题-历史的窗口搜索

1000ms

Difficulty: 8

所属公司 : 华为

算法与标签>模拟

题目内容

传统 $TF-IDF$ 方法对突发新闻的敏感度不足，为提高热点词识别效果，某新闻热点追踪平台提出基于历史窗口的TF-IDF方法，具体地，在某个时间点 $t$ 提出一个查询 $q$ 时，系统不应该在整个历史文档库中进行大海捞针式的搜索。

相反，它需要智能地聚焦于查询发生时间点 $t$ 前的一段”历史时间窗口“内的文档，并且只需考虑这个窗口内最新的信息。

您的任务就是实现这个“历史窗口”检索引擎的核心逻辑。

历史窗口：仅计算从查询时间点 $t$ 开始之前的 $K$ 篇文档的词频，而非全部历史文档。

动态权重：为了使该搜索模型更关注短期趋势，窗口内越新(文档编号 $m$ 越大)的文档权重越高，窗口内第 $j$ 篇文档的权重为 $(K-j+1)/K$ (最新文档权重 $=1$ ，最旧文档权重 $=1/K$ )。

筛选与输出：计算查询内容 $q$ 与窗口内每一篇文档向量之间的余弦相似度 $(Cosine Similarity)$ ,返回本次查询中余弦相似度 $>=0.6$ 且余弦相似度最高的文档编号 $m$ ，若未找到满足条件的文档编号(余弦相似度 $<0.6$ )，则本次查询返回 $-1$ ；若存在多个相同最高相似度的文档，返回时间窗口中最早的一篇文档编号。

相似度计算方法：查询 $q$ 向量(向量 $A$ )的第 $i$ 维计算公式为， $q_i = TF(w_i,q)×IDF(w_i)$ ，其中 $TF(w_i,q)$ 表示词 $w_i$ 在所有查询内容 $query$ 中的词频， $IDF(w_i)$ 表示词 $w_i$ 在窗口文档集合中的中逆文档频率。窗口文档集合中第 $n$ 篇文档(向量 $B$ )的第 $i$ 维向量计算公式为: $d_i = TF(w_i,doc) × IDF(w_i) × weight_n$ ,其中 $TF(w_i,doc)$ 表示词 $w_i$ 在查询窗口文档集合中的词频， $IDF(w_i)$ 表示词 $w_i$ 在窗口文档中的中逆文档频率， $weight_n$ 表示第 $n$ 篇文档的动态权重。

提示:向量 $A.B$ 的余弦相似度: $\cos (A, B)=\frac{\mathbf{A} \cdot \mathbf{B}}{\|\mathbf{A}\|\|\mathbf{B}\|}$

输入描述

输入第一行表示文档集合 $corpus$ 总数 $N$

第二行开始每一行为从时间点 $0$ 开始的文档，时间点和文档编号按行递增 (注:文档编号、查询时间点均可理解为数组下标，下标从 $0$ 开始)

之后的一行为查询窗口的大小 $K$

接下来的下一行表示总查询次数 $P$

然后紧跟每个查询，格式为搜索时间点 $t$ 具体查询内容 $q$ ， $t$ 和 $q$ 中间用空格隔开

参数限制

$1.1<=K<=$ 文档总数 $N$

$2.0<$ 文档总数 $N<=100$

$3.0<$ 总查询次数 $P<=100$

在处理完基本题目的 $I/O$ 操作后，你可能需要实现的函数原型

是 $history$ _ $search$ $(corpus,K，query)$ ，参数说明如下:

1. $corpus$ ：从时间点0开始的文档集合， $corpus[i]$ 表示第i篇文档，文档编号 $m$ 和时间点 $t$ 均对应数组下标，下标从 $0$ 开始。

2. $K$ :窗口大小。

3. $query$ ：查询列表。每个查询是一个二元组(查询时间点 $t$ ，查询内容 $q$ )。

输出描述

输出空格分隔的最匹配的文档编号 $m$ ，文档编号和查询顺序一一对应，若两篇文档最高相似度相同，则返回窗口中最早的文档编号

若无匹配则对应位置返回 $-1$

样例1

输入

5
long short term memory
data science
natural language processing
python for data science
a tutorial on python
3
3
2 natural language
4 python data science
4 long short term memory

输出

2 3 -1

说明

第一行 $5$ 表示新闻文档集合 $corpus$ 的总数 $N$

然后紧跟从时间点 $0$ 开始的具体的每篇文档，时间点和文档编号按行递增:

时间点 $0$ 文档编号 $0$ ：" $long$ $short$ $term$ $memory$ "

时间点 $1$ 文档编号 $1$ ：“ $data$ $science$ ”

时间点 $2$ 文档编号 $2$ ：“ $natural$ $language processing$ "

时间点 $3$ 文档编号 $3$ ：“ $python$ $for$ $data$ $science$ "

时间点 $4$ 文档编号 $4$ ：“ $a$ $tutorial$ $on$ $python$ "

下一行的“ $3$ ”为窗口的大小 $K$

接下来的“ $3$ ”表示查询 $query$ 的个数

然后紧跟每个查询，格式为搜索时间点 $t$ 具体查询内容 $q$

第一次查询" $natural$ $language$ "在时间点 $2$ ，我们正好可以看到 $0-2$ 号文档，因为只有2号文档" $natural$ $language$ $processing$ "出现了关键词，因此第一个查询返回 $2$

第二次查询" $python$ $data$ $science$ "在时间点 $4$ ，由于窗口大小是 $3$ ，我们可以看到 $2,3,4$ 号文档我们无法看到 $0,1$ 号文档，本次查询最匹配的是文档编号 $3$

第三次查询“ $long$ $short$ $term$ $memory$ "在时间点 $4$ ，同样的我们只能看到 $2,3,4$ 号文档，无法看到 $0,1$ 号文档，且 $2,3,4$ 号文档中没有与查询相似文档，

所以本次查询返回 $-1$

提示

1. $q$ 可能存在不在窗口文档集合中的查询词，因此在计算逆文档频率的时候你需要进行平滑操作，公式如下 $I D F(x)=\log \left(\frac{N+1}{N(x)+1}\right)+1$ 其中 $N$ 代表窗口文档的总数，而 $N(x)$ 代表包含词 $x$ 的文档总数

2.新闻文档集合 $corpus$ 所包含的文档内容是空格分隔的小写英文文档字符串

输入

预期输出（选填）

解题思路

问题抽象

P3639.第2题-历史的窗口搜索

题目内容

输入描述

输出描述

样例1

提示

Status

Development

Support

About