利用倒排文档和平衡树基于QT实现的简易搜索引擎

Benjamin

发布日期: 2019-02-26 10:05:36 浏览量: 301
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、实验目标

本此实验包含两个部分,一部分是构建平衡树与构建倒排文档,对于 query.txt 文档的关键词进行分析,将结果输到 result.txt 中。另一部分是 创建图形化界面,进行用户操作。本文档将先介绍第一部分,然后再详细介 绍第二部分与如何对界面进行操作。

特殊说明:本程序应在 Release 条件下运行,用 Debug 模式特别缓慢。

二、实验环境

  • 系统环境:Windows 10 64 位

  • IDE:Visual Studio 2012

三、抽象数据结构的说明

特殊说明:本实验二是在实验一的基础上来编写的,字符串类、栈、字符串 链表类在实验一说明文档中都详细的介绍了,这里不再 重复介绍了。但是这 里的一些数据结构在实验二中添加了一些新的函数,我在程序的注释中已详 细的介绍了,文档中不再介绍。

3.1 hashtable(哈希表类)

  • 功能

    • 实现一个链式哈希表
  • 类说明

    • 成员变量
      • StringLink *elem;以字符串链表为元素 的哈希表
      • int size;哈希表长度
    • 成员函数
      • void insert_ptr(CharString &aim);往哈希表中插入元素
      • bool search(CharString &aim);哈希表搜索元素,如果找到就返回TRUE反之返回FALSE
      • unsigned int hash_value(CharString & s);哈希函数
  • 功能

    • 实现倒排文档
  • 类说明

    • 结构体file(文档)
      • filename;文档名
      • rank;文档地址
      • fre;词频
      • next;下一个文档节点
    • class fileLink
      • file*head;文档链表头结点
      • file*tail;文档链表尾节点
      • int size;文档链表长度
    • 成员函数
      • Add;文档链表添加节点
      • Remove;文档链表删除节点
      • Search;文档链表搜索节点
      • Edit;编辑文档链表

3.3 AVL平衡树

  • 功能

    • 构建平衡树
  • TreeNode类

    • 成员说明
      • data;节点储存的字符串
      • height;节点的高度
      • frequent;词的频率
      • left;左孩子
      • right;右孩子
      • fileSet;节点的倒排文档
  • AVLTree类
    • 成员说明
      • root;根节点
    • 成员函数
      • Insert_ptr; 添加节点
      • Search_ptr;查找节点
      • Remove_ptr;删除节点
      • height;求节点高度
      • SingleRotateLeft;单左旋
      • SingleRotateRight;单右旋
      • DoubleRotateLR;双旋转从左到右
      • DoubleRotateRL;双旋转从右到左
      • Max;求最大值
      • Insert;总体的插入节点
      • Search;总体的搜索
      • Remove;总体的删除
      • Destroy;析构整个平衡树

四、核心算法说明

主要是在分词过程中将新分出的词插入到平衡树中,在平衡树中构 建倒排文档,记录每个网页含有该词的个数。网页分析分词完以后,读取 query中的关键词进行分词,将分词结果存到一个字符串链表中。对该链表进行从表头到表尾的遍历,在平衡树中搜索到链表节点所代表的词的倒排 文档,将这些关键词的倒排文档进行整合,得出每个含有这些关键词的网 页含有这些关键词的个数,然后按要求对节点排序后将结果输出到 result.txt中。

五、流程概述

  • 加载字典

  • 遍历并且记录 input 文件夹下所有的 HTML 格式的文件 的文件名

  • 分析网页内容

  • 中文分词建立平衡树与倒排文档

  • 对query.txt进行处理将结果输出到result.txt中

  • 析构平衡树与哈 希表

六、输入与输出以及操作的相关说明

将带解析的网页文件存放在 input 文件夹中,在程序目录下添加 query.txt文件,将词典文件放在可执行程序目录执行即可。输出时需要耐心等待19或20秒钟,便可在result.txt中的到结果。

七、实验结果

result.txt会显示符合实验要求的结果,每行的实验结果按照关键词出现 次数从大到小排序。

八、UI设计与怎么使用此UI检索关键字

此实验的gui是用QT编写,界面开始出现时会出现一个进度条,只有进度条 进度到百分之百时界面才可以使用。如图:

该 UI 除了相应的水平与垂直布局外,主要有这四个部分,搜索框 QLineEdit, 文 件显示框 QListWidget,搜索按钮 QPushButton 和显示文章内容的 textBrowser。

操作的特别说明

在搜索框输入关键词时,看以往搜索框中输入一整段话,系统会对这段话进行分 词,然后根据分词分出的关键字,在左边的框中显示出含有这些分出的关键词的 文档名。在输入关键词以后,点击搜索按钮便会在界面左边的窗口显示包含这些 关键词的文件的文件名。注意双击这些文件的文件名便可在右边的矿中的到文章 的信息,由于没有加载图片资源所以文章内容不会出现图片。文章内容中用户所 搜的关键字会显示红色显示出关键词所在的位置。如果想搜其他的关键词清空搜 索框再输入关键字点击搜索即可,再次点击新的文件之前右边框会显示上个打开 的文章的文章内容。特殊说明:文章内容的网页链接无法被打开。当输入为空或 者词没有出现在已载入的网页中会弹出一个对话框进行提示,此时点是或否对话 框就会消失然后在搜索框中重新输入即可,如图 :

九、实验亮点

  • 独特的 UI 设计:程序加载会出现进度条显示程序的进度进程,文章 内容中的关键词会变红提示关键词位置

  • 实验加载 520 个网页的速度比较快,只用了 18 秒(虽然可以在优化)

  • 分词算法中可以有效的过滤掉不是中文的单字

  • 如果在 gui 中搜索词不在已知网页中出现,会有对话框提醒

十、实验体会

通过这次实验我了解到了搜索引擎的原理,也复习了 C++相应的知识与 QT 的 使用,学习了 AVL 平衡树与倒排文档的使用,更认识到内存管理的重要性, 提高了编程能力。

上传的附件 cloud_download 利用倒排文档和平衡树基于QT实现的简易搜索引擎.7z ( 12.93mb, 2次下载 )
error_outline 下载需要13点积分

发送私信

你愿苦其自身,必将掌声雷动

8
文章数
11
评论数
最近文章
eject