Skip to content

jiaaoc/SearchingSystem

Repository files navigation

信息检索系统

利用倒排索引和向量空间模型实现的信息检索系统.

完成工作:

  • 带位置信息的倒排索引 OK
  • 向量空间模型
  • TOP K查询
  • BOOL查询 OK
  • 短语查询
  • 拼写矫正
  • 同义词查询
  • 拼写矫正(短语)

运行

环境要求:python3

在初次运行程序前请下载词干还原依赖的语料库

SearchSystem/main.py中已经注释掉下载语料库的命令

nltk.download("wordnet")
nltk.download("averaged_perceptron_tagger")
nltk.download("punkt")
nltk.download("maxnet_treebank_pos_tagger")

取消注释后运行一次即可,语料库下载完成即可正常运行

windows下如果嫌弃语料库下载比较慢,可以直接将该目录下的nltk_data文件夹替换掉user下的AppData/Roaming/nltk_data文件夹,根目录的nltk_data文件夹是已经下载好的语料库

语料库下载完成后请将相应的下载语注释掉。

SearchSystem目录下运行命令:

python main.py

注意:运行前请不要修改工程文件的名字和相对位置

SearchSystem工程目录是pycharm的工程

实现功能

词干还原

利用python中自然语言处理的库:nltk对文章中的单词进行词干还原。

在词干还原的过程中会去除无用的标点符号。

索引构建

带位置信息的倒排索引:

例子:

{
    "word1":{
        "1":[5,6,10],
        "5":[10,20,30]
    },
    "word2":{
        "2":[5,6,10],
        "33":[15,28,30]
    }
    ···
}

索引事先建立好储存在文件中,每次运行程序时将索引加载到内存中。

向量空间模型

通过查询向量计算出文档的wf-idf评分进行排序。

wf-idf计算方法:

  1. 首先对query中出现的单词对应的文档列表取并集。
  2. 随后对query中出现的单词对文档进行wf-idf计算并评分。
  3. 得到所有文档对该查询的评分后再对所有文档进行排序。

wf-idf 和 tf-idf比较:

  1. 通过log计算削弱词项频率对评分的影响。
  2. 一篇文章中单词出现n次不代表其权重扩大n倍。

TOP K 查询

首先通过向量空间模型得到所有文档的评分。

通过堆排序建好最小堆以后进行K次precDown操作。

堆最后的K个元素即为评分前K大的元素。

短语查询

利用带位置信息的倒排索引。

首先得到包含query中所有单词的文档列表的交集。

从这些文档集中根据位置索引查找是否有匹配的短语。

遍历第一个词项在文档中的位置,依次检测后面的词项位置中是否包含与其匹配的位置。

通配符查询

利用正则表达式找到所有匹配的词项,利用倒排索引检索出词项对应的文档。

支持通配符的短语查询:

首先将检索到的词项存在一个二维数组中,随后对出现的每个短语组合进行短语查询。

同义词查询

同样利用nltk语言处理库获取单个单词的同义词列表(有可能是短语)

随后对每个单词或者短语进行检索,获取文档集。

BOOL查询

  • 将查询表达式转为后序表达式: 如 A OR B AND C 转为 A B C AND OR

  • 用一个栈来计算后序表达式

拼写矫正

c 是 编辑距离为1或者2或者0的词,并且词属于给定的词典.

P(c)是每个词在字典中出现的频率.

P(w)是每一种拼写错误可能出现的概率,这里认为是一个常数

根据贝叶斯理论 计算 P(c|w),即给定词w,纠正到每个c的概率,并且从中选出概率最高的词 这里还需要知道一个项 P(w|c|),即给定c,c就是输入者想要的单词的概率 由于没有错误模型数据,我们简单这么认为

P(W|C0) >> P(W|C1) >> P(W|C2)

C0/1/2 是编辑距离为0/1/2的词,即编辑距离小的有更高的优先级

最后,模型工作如下

  1. 如果输入词在词典里找到了原词,这返回
  2. 从编辑距离为1的词选出频率最高的,返回
  3. 从编辑距离为2的词选出频率最高的返回。

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages