数据结构与算法 第九次上机作业讲评 助教：钟威 邮箱： 第一部分 文本的向量空间模型 下载搜狗新闻分类语料环境，搜狗分类语料。该语料一共有九个 类，每个类在一个文件夹下，内容分别是： C000008 财经 C000010 IT C000013 健康 C000014.

Presentation on theme: "数据结构与算法 第九次上机作业讲评 助教：钟威 邮箱： 第一部分 文本的向量空间模型 下载搜狗新闻分类语料环境，搜狗分类语料。该语料一共有九个 类，每个类在一个文件夹下，内容分别是： C000008 财经 C000010 IT C000013 健康 C000014."— Presentation transcript:

1 数据结构与算法 第九次上机作业讲评 助教：钟威 邮箱： zhongwei@pku.edu.cn

2 第一部分 文本的向量空间模型 下载搜狗新闻分类语料环境，搜狗分类语料。该语料一共有九个 类，每个类在一个文件夹下，内容分别是： C000008 财经 C000010 IT C000013 健康 C000014 体育 C000016 旅游 C000020 教育 C000022 招聘 C000023 文化 C000024 军事 做过的预处理包括：去掉多余的空行和空格，丢弃一些无法解码 的字符以及控制字符，正则过滤掉一些网页标签（如 >[1]; 下一页 等），以及分词和词性标注。 后缀为.seg 的文件是经过分词的语料（由一个个空格分隔开的 token 组成，每个 token 格式为 / ）

3 任务 1 请大家给出一个全局的词频统计（建议采用 Trie 树，每个汉字是 由两个字节组成，每个字节的编码空间为 0-255 ）；同时统计每 个词的 IDF 和 ICF （ ICF 与 IDF 类似，是词对于类的分布包含的信 息量）。结果输出为文件，每个词条占一行。 文件读取 构建 Trie 树遍历 Trie 树 处理流程：

4 文件读取 采用循环逐个读入所有文件 sprintf 用来生成文件路径， fopen 用来打开文件（在 vs2012 以上版本默认用 fopen_s ，设置后可用 fopen ） 一次读取一个字符串，可以根据词性标注等去除无用字符

5 构建 Trie 树 Trie 树节点 Node 一个中文字符占两个 char 把 char 型转成 unsigned char 型 统计这个词在多少篇文章中出现 过，用于后面计算 IDF 统计这个词在多少个类别中出现 过，用于后面计算 ICF

6 遍历 Trie 树 递归遍历 Trie ，如果找到某个节点的词频大于 0 ，说明这里 存在一个词，那么计算这个词的 idf 和 icf ，并且输出到文件； 否则递归调用下一层。 str 用来存放当前的词

7 任务 2 统计每篇文章的词频（ TF ）向量。实现按 TF*IDF 的文档相似度 检索（建议先直接生成按 TF*IDF 向量夹角余弦值构成的文档相似 矩阵），即输入一篇文档的 ID （类 ID+ 文章名），输出所检索的 目标文章内容，然后再输出前 3 篇跟这篇文章最相似的文章（ ID+ 内容）。可以支持循环输入响应， esc 退出系统。 计算 TF- IDF 构建 TF- IDF 矩阵 计算相似 度 处理流程：

8 计算 TF-IDF Tf-idf=tf*idf 前面任务一已经计算过 idf ，现在只需计算 tf 。 计算 tf 时，我们需要统计一个词在一篇文章中出现的总次数和这 篇文章的总词数，这时需要纪录每个词在出现过的文章中的词频。 部分同学在 Node 里面开 17910 个元素的数组，用来存 这个单词在各篇文章中的 tf 值，显然一个单词不会在所 有 17910 篇文章中都出现，而且这样内存空间会不够用 改进方法： 因为一个单词不会在所有文件中出现，所以 可以在 Node 里面构建一个链表来代替 tf 数组， 用来存出现了这个单词的文章的 id 和 tf 值。

9 在读取完一篇文章内容并加入 Trie 树后调用 calculate_tf 函数，计算这篇文章的 tf 向量，然后 在 dfs 遍历 Trie 树的时候计算 tf-idf 。 13 级杨炎锦同学的部分程序

10 TF-IDF 矩阵的存储 矩阵大小： 17910* 几十万，用一个二维数组显然存不下。 因为一篇文章一般只有几百个词，而矩阵行的维度为几十万，所 以这个矩阵有很多 0 元素，为稀疏矩阵。这样我们可以采用稀疏 矩阵的形式来存储。 稀疏矩阵有三元组、十字链表等存储形式，但在这里我们只需要 存词的 id 和 tf-idf 值，所以我们对篇文章建立一个二元结构体数组 用来存这篇文章的词的 id 和 tf-idf 值。

11 14 级白珂同学的部分程序

12 相似度计算 由 tf-idf 矩阵计算所有文章两两之间的相似度运算量会特别大（有 同学计算相似度矩阵花费 3 个多小时），很多同学采用的方法是 输入一篇文章，然后去计算这篇文章和其他所有文章的相似度， 再找出相似度最高的三篇文章，然后输出。

13 第二部分 矩阵特征值的计算 在上一步工作生成的文档相似矩阵及文档相似检索功能的基础上， 实现关键词检索。及输入一个或多个关键词，匹配所有包含这个 关键词的文档，然后按文档内容与该关键词的相关度排降序，输 出前 5 篇文档的内容。 该功能实现的基本流程是： 1 、按关键词检索到所有匹配上的文档，比如有 m 篇。得到这 m 篇 文档的 TF*IDF 向量构成的 m*n 的矩阵（ n 为词向量的长度） 2 、求出该矩阵最大特征值对应的特征向量，按照与该特征向量的 夹角的余弦值排降序，输出前 5 篇文档的内容。（选做，参考 HITs 算法）。

14 按关键词检索文档 方法 1 ：遍历所有文档去找出包含该词的文章。有同学采用读取 所有.seg 的分词文件来做匹配，从而找出包含该词的文章。 方法 2 ：像前面存储 tf-idf 矩阵那样，前面我们是构建一个每篇文 章到该文章所有词的映射；这里可以对每个词构建一个该词到包 含该词的所有文章 id 的映射，这样输入一个词我们可以很快找到 包含该词的所有文章。

15 特征值方法找相关度最高 5 篇文章

16 谢谢！