搜索引擎与信息检索

搜索引擎与信息检索。

References

awesome-information-retrieval

授课老师:徐君

Course PDF: PDF(慕尼黑,Website

Introduction to Information Retrieval

Modern Information Retrieval

类似课程信息:现代信息检索(Modern Information Retrieval)

一个垃圾短信识别系统——国科大网络数据挖掘(徐君)课程设计 - GitHub

EasyML

Intelligent Information Retrieval 信息检索IR

[搜索引擎]搜索引擎索引数据结构和算法 - hoohack

搜索引擎索引之索引基础- 张俊林的博客- CSDN博客

用Golang写一个搜索引擎(0x02)—- 倒排索引技术- 吴说- SegmentFault

先讲稍微底层一点的东西。

人民大学的研究生课程。书:《Introduction to Information Retrieval》,《Modern Information Retrieval》。

Slides from:Schitze(德国慕尼黑大学?)

(研究生一年级/保送生可选课)

信息检索:从非结构、大规模数据中根据需求寻找信息。

  • 寻找信息
  • 非结构化数据(关系型数据库对非结构数据的处理很弱,说明性(非浮点、布尔)的数据很难处理)
  • 信息需求
  • 大规模数据

只做信息的搬运工,不创造新的信息。

基本假设

  • 静态文档集合
    • 工程上一般会使用爬取、搜索(两个系统)两个服务。
  • 检索目的
    • 检索——相关信息

Ranking:相关性、权威性等。

搜索引擎的发展

  • (1990)Archie FAQ精确FTP文件名搜索
  • (1993)WWW Wanderer网络爬虫,网站主动检索信息;Excite分析字词关系(概念搜索,不同表达同一概念)
  • (1994)Yahoo提供简单目录搜索(黄页);WebCrawler全文搜索引擎(开始关注于文本文件的内容,对空间消耗要求高);Lycos网页自动摘要(早期文本摘要);Infoseek网页自动摘要、同时提供网页目录等其它服务
  • (1995)自然语言搜索和高级搜索语法;爬取索引,存储用户搜索喜好
  • (1996)自然语言问答,优先提供答案(命中率很低)
  • (1997)天网搜索,第一个中文搜索引擎
  • (1998)Google
  • (1999)Fast利用ODP自动分类改善搜索
  • (2000)搜索结果自动聚类;Baidu出现

第一代:基于语法的查询-内容匹配

第二代:考虑链接分析、用户点击路径(PageRank对搜索的意义并不大)

第三代:结果页面不仅仅显示网页的链接

第四代:移动,信息流,个性化(搜索+推荐+广告

  • 下一代搜索引擎?

Boolean Retrieval 逻辑过滤器

问题(Query)是一个布尔表达式。(图书馆在用)

作为现代搜索引擎的一部分。(过滤器

正则表达式(grep):慢,按行,很难回答Not,相似度判断

对BR构建一个类似与word2vec的向量。(向量化

  • 出现了词,对应为1,否则为0(布尔向量

  • 110100&110111&!010000

  • 如果词库很大时,向量会过大(存储空间爆炸),稀疏矩阵$\longrightarrow$索引化
    • 只记录1
    • index(数据结构)
      • 字典:每一个单词指向一个文档列表(还可以对其排序),这些文档中包含这个单词
        • 快速查找(Hash,红黑树,二分查找……)
      • 按内容进行寻址相联存储器

操作过程:

  • 对每个文档拆散为单词
  • 按单词字典序排序(或者其它的序,反正要排序)
  • 对单词向量进行唯一化(把相同单词搞成一个串)

需要再看看:MapReduce

如何搜索呢?

  • 按照布尔Query找出多个文档列表
  • 对这些文档列表求交:类似LCS(最大公共字串)算法?因为已经排序了,可以达到线性的时间复杂度

优点:简单、可信。

Optimization

多于两个AND运算?:

  • 按文档长度排序(搞个优先队列?或者直接排序也行),最短的先求交,类似Huffman编码。这样可以降低期望运行时间

Summary

  • 输入:BR

  • 输出:一个文档集合

  • 建立Inverted index
  • 算出文档?……

Skip pointers 跳跃表

跳跃表— Redis 设计与实现

../_images/skiplist.png

在posting list上加一些额外的指针(空间前穿)。

  • 在位移的过程面临选择
    • 挪到下一个位置
    • 跳到下一个位置(如果还满足关系的话)

可以节省常数的时间复杂度(消耗常数的空间复杂度)。

必须考虑跳跃的命中率和跳跃距离的权衡。

  • 用$\sqrt P$的常数的跳跃表

考虑多层次的跳跃表?(在牺牲一定空间后,可以达到对数期望复杂度)

Phrase queries

下次课讲。

检索模型

经典信息检索模型(无结构文本):

  • 布尔
  • 向量
  • 概率

半结构文本:

  • 邻近节点
  • 其它基于XML

Today:

  • Ranking
  • Term Frequency
  • Tf-idf ranking
  • Vector space model

排序

排序的根本原因是因为适应大多数非专业的查询

人群的意识具有潮流性和随机性。

因此,最终的查询非常依赖于系统。

布尔查询的缺点就是没有排序,会导致检索出太少或太多的文档。(并且,对大部分用户而言,编写布尔查询是繁琐的)

Ranking造成了一种假象——排在前面的结果质量更好。

打分

独立相关假设、位置无关假设。

Jaccard系数

停用词问题(词语重要性的衡量)。

量纲分析原则。(单位一致性?)

Log TF

词袋模型

Binary matrix$\longrightarrow​$Count matrix。

Log TF

TF(项频)是一个线性函数,对数化以后则比较能反映事实。

TF-IDF

信息熵:$-plogp​$。

Note: 信息量信息熵。(维度)

乘法原理有点像那个什么F1。

经验上,DF(文档频率)比CF(总频率)更有效。

TF-IDF有许多变体。

Exercise: DF、TF、CF。

向量模型

非二值权重。

余弦相似度

q: query; d: document.

0%