解题思路

问题抽象

• 给定按时间递增的文档集合 corpus[0…N-1]（下标既是时间点），每次查询给出时间点 t 与查询串 q。

• 窗口：只在 t 及其之前的最近 K 篇文档中检索，即区间 L = max(0, t-K+1), R = min(t, N-1)。

• 打分：使用（窗口内）TF-IDF 与余弦相似度，并加入动态权重强调新文档：

  • 第 j 篇（从新到旧计数，最新 j=1）的权重

题目内容

传统$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$ 所包含的文档内容是空格分隔的小写英文文档字符串