信息检索与 Web 搜索 第 3 讲 词项词典及倒排记录表 The term vocabulary and postings lists 授课人:高曙明 * 改编自 “ 现代信息检索 ” 网上公开课件( )

Slides:



Advertisements
Similar presentations
DOC 推廣活動 月餅星光大道. 中秋  農曆八月十五日,是中國傳統的中秋節。 古人將一年分成春夏秋冬四季,而一季又 分為孟、仲、季三月,八月是仲秋之月, 而十五又是這個月中間的一天,正處在秋 季的正中,所以把八月十五稱為「中秋」 或「仲秋」。  中秋夜,月亮最圓,月色最美,因此人們 把月圓看成是團圓的象徵,同時也稱八月.
Advertisements

中南區兒教組教員進修會 宗教教育的危機與轉機 - 巫鐘琳. 在開始之前 … 關手機 … 打開心 … 「學」「思」「達」 學習共同體 你是學習的主體,決定收穫多少.
中 五 級中 五 級 戰後國共關係 與 中華人民共和國成立 中國歷史科 1 )認識國共政治協商的概況 2 )認識國共內戰的概略經過及結果 3 )中華人民共和國成立.
不吃早餐的影響: 體內的葡萄糖無法 足夠供應給大腦與 肌肉,會感覺疲勞, 注意力無法集中。。 營養的早餐:乳品 + 全榖類食品 + 蛋白質 + 水果 早餐你吃了嗎?
北京师范大学生命科学学院 北京师范大学生命科学学院 余跃强 章腾勋 王航 余跃强 章腾勋 王航 2 目 录目 录目 录目 录  前言 前言  概述 概述  形态和生活史 形态和生活史  寄生适应特征 寄生适应特征  致病机制与症状 致病机制与症状  诊断 诊断  流行情况 流行情况.
103年度統一入學測驗 報名作業說明會 時 間:102年12月16日(星期一) A.M.9:40~10:30 地 點:行政七樓講堂
河北衡水中学 康新江 高效课堂与激情教育 河北衡水中学 康新江
第5讲 索引构建 Index construction 授课人:高曙明
人文地理專題研究 王志明.
凱琪的包裹 這個故事是發生在第二次世界大戰後的歐洲。故事 藉由美國及荷蘭的兩位小女孩,因書信的往來而發
绝经后骨质疏松症的防治.
2014年爱婴医院复核方案解读 省卫生计生委妇幼处 邱灵.
從產地到餐桌--- 談美食、食材與食育 社團法人微風市集志業協會 總幹事 林憲輝.
导言 第四 单元 凡尔赛—华盛顿体系与第二次世界大战
自动化专业介绍 廖家平.
104年度統一入學測驗 報名作業說明會 時 間:103年12月15日(星期一) A.M.10:00~11:50 地 點:行政七樓講堂
劳动关系法务-实操篇 规章制度修审与员工手册撰写.
社團經費申請 及核銷相關規定 製作:世新大學會計室.
102年度統一入學測驗 報名作業說明會 時 間:101年12月14日(星期五) A.M.9:00~10:20 地 點:行政七樓講堂
会计实验.
2014届毕业生毕业论文与毕业实习动员 一、郑州航院毕业论文工作规定 二、法律系毕业论文工作安排 三、法律系毕业论文格式要求
信息检索中效率问题的研究 报告人:赵江华 北京大学计算机科学与技术系 网络与分布式系统实验室 2002年4月21日.
高一年级过渡性学习 活动汇报 高一年级组 教科研室 汉滨高中.
何处安放 我们的青春? 透视 大学毕业生 “族化”生存现象.
“卓越工程师”培养的质量保障体系构建探索
土地出让转让的政策与实务 岳晓武 国土资源部利用司.
第十九课 旅行.
Teaching the Chinese Copula 是 for CSL Purposes
老師:鍾郁芬 老師 指導 組長:陳欣怡 組員:曾郁雯 倪敏富 王宣化 簡宏倫 黃郁涵
题目回顾 泉水在地下蓄积,一旦有机会,它便骄傲地涌出地面,成为众人瞩目的喷泉,继而汇成溪流,奔向远方。但人们对地下的泉水鲜有关注,其实,正是因为有地下那些默默不语的泉水的不断聚集,才有地上那一股股清泉的不停喷涌。 请根据你对材料的理解和感悟,自选一个角度,写一篇不少于800字的文章,文体自定,标题自拟。要求:立意明确,不要套作,不得抄袭。
第十三章 有效资本市场 有效资本市场(efficient capital market)是一个证券价格能根据新信息的出现迅速调整的市场,即现行的证券价格能够反映有关证券的全部信息。 研究意义:第一,对投资者有重要的现实意义;第二,观点相差很大,有很多未知问题需要研究。
广 东 技 术 师 范 学 院 美术学院 装潢专业 2012级(3)班 郑可珊
張曼娟 12523王勻庭 12524陳宥蓉.
第十九章 散文 教学要求: 了解散文的含义、分类、特点,学习写作抒情散文。 重点: 散文的特点,散文的写作。 难点: 散文的写作训练。
行政作用法 行政命令.
技师专业论文与答辩 技师专业论文与答辩辅导 2016年3月.
主持人 張校長榮輝 導讀者 彭吉梅 中華民國95年11月3日
模块4 授导型教学的设计 陈冬.
农机化项目管理培训会 柳州市农机局 郑崇宁
一二·九运动                                                                    0712班.
只有一个词,它不会争,争到了也不受用,只让它静静安踞在并不明亮的高位上,留给那座唯一的城市。 这个词叫伟大,这座城市叫罗马。
中小学教育科研课题的选择 王典伟.
Hosted by Andrew Ferrell(范宪儒) 和 James Packman(潘杰士)
出口农产品风险管理 企业分类及监督管理表格
心靈補給站 你可以「活」的「更好」 輔導主任 陳正馨老師.
● 四 (2)班 家 长 网络交 流 会 ● 快乐成长 与您 共享 家庭 学校 社会.
学科科研工作与科研 奖励政策解读讲座 朱文斌 博士 教授 2015年9月8日.
第9章 金融监管.
首都师范大学.
Unit 2 Topic 2 What does she look like? Section D 龙岩初级中学 余军.
Unit 1 Making New Friends
社會學(一) 空中大學花蓮中心 鍾燕菁
Lecture 5 : Sequence Tagging and Language Processing
關心今天的老人, 就是關心明天的自己 作者:周儀.
现代信息检索 Modern Information Retrieval
机器学习与数据挖掘 样本准备(2).
陕西省教育科学研究所 张雪莲 初中英语教学与2011年中考命题趋势思考 陕西省教育科学研究所 张雪莲
Chapter 3 Nationality Objectives:
Making Connection Sound with Symbol
A an的区别和联系。 a 和 an 均用在单数名词之前,表示一类人或事物中的“一个”,相当于汉语中的“一”,但不强调数目概念。
《郑伯克段于鄢》 黎兰老师制作.
疑問句的形成.
香港道教聯合會圓玄學院石圍角小學 中國清朝衣服 By:蔡思敏.梁嘉敏.杭依澄.
全球化與在地化: 台商在大陸的投資及發展 張家銘〈東吳大學社會學系〉 台商在大陸投資的反思 2019/5/9 全球化下的台商在蘇州.
钱炘祺 一种面向实体浏览中属性融合的人机交互的设计与实现 Designing Human-Computer Interaction of Property Consolidation for Entity Browsing 钱炘祺
世界无烟日主题班队会.
仲裁处理细则及常见问题解析.
嘉義縣立溪口國民中學 辦理96年度推動自由軟體學校資訊融入教學
我是神的朋友 I Am A Friend of God
O W E L C M E.
Presentation transcript:

信息检索与 Web 搜索 第 3 讲 词项词典及倒排记录表 The term vocabulary and postings lists 授课人:高曙明 * 改编自 “ 现代信息检索 ” 网上公开课件( )

Tokenizer 词条流 Friends RomansCountrymen 回顾:倒排索引构建 Linguistic modules 与词项对应的词条 friend romancountryman Indexer 倒排索引 friend roman countryman 待索引文档 Friends, Romans, countrymen. 词条化工具 语言分析工具

文档预处理  任务目标: 将文档转化成词项集合,支持倒排 索引,支持基于词项比对的文本检索  主要内容 文档编码转换 文档单位选择 文本分析: 词条化、词条归一化、词形归并、词干还原等  主要方法: 自然语言处理、语言学

文档编码转换  任务:将字节序列转换成线性的字符序列  难点:多格式、多语言并存  方法:采用启发式方法进行文档语言识别、 文档编码识别,再分类转换

文档单位选择  任务:确定被索引文档的合理粒度  粒度过大:正确率低 粒度过小:召回率低  方法:提供不同文档粒度,由用户根据实际需 要选择合理的文档粒度

词条化 (Tokenization)  任务: 将字符序列分割成一系列有意义的子序列  例子: 输入 : “Friends, Romans and Countrymen” 输出 : Friends Romans Countrymen  词条: 一个字符串实例,具有语义,适合作为索引单元  作用: 词条化工作是构建倒排索引的基础,并影响检索 效果  难点: 如何有效地确定词条

词条化面对的问题  “’” 如何处理 O’Neill 、 boys’ 、 Chile’s 、 aren’t Finland’s capital  Finland? Finlands? Finland’s?  “-” 如何处理 Hewlett-Packard  看成 Hewlett 和 Packard 两个词条 ?  空格如何处理 San Francisco 到底是一个还是两个词条?  如何判断是一个词条?  特殊词条如何识别 C ++ 、 C # 、 B-52 、 M*A*S*H 、 电话号码、网址 … …

中文分词 (Chinese Word Segmentation)  难点: 没有空格符,字也可能有语义  例子: “ 和尚 ” 、 “ 和 ” 、 “ 尚 ”  方法: 词典、统计学习、启发式规则、字词混合方式 /k-gram ( K 字符序列)  例子: 李明天天都准时上班 李 明 天 天 都 准 时 上 班  一般原则: 没把握的情况下细粒度优先  一个策略: 查询和文档采用一致的分词方法 8

停用词去除  停用词: 在进行文档和查询匹配时作用不大的常见词 一般不包含语义信息的词: the 、 a 、 and 、 to 、 be 这些词都是高频词 : 前 30 个词就占了 ~30% 的倒排记录表空间  停用词去除的作用 压缩索引空间 提高检索响应速度  停用词确定方法 高文档频率且与文档主题关系不大的词 应用领域相关: “click” 作为锚文本的停用词 在处理查询时决定哪些词不用

停用词去除  现代信息检索系统中倾向于不去掉停用词 在保留停用词的情况下,采用良好的压缩技术后,停 用词所占用的空间可以大大压缩,最终它们在整个倒 排记录表中所占的空间比例很小 采用良好的查询优化技术,基本不会增加查询处理的 开销 所谓的停用词并不一定没用,比如:短语查询 : “King of Denmark” 、 歌曲名或者台词等等 : “Let it be”, “To be or not to be” 、 “ 关系型 ” 查询 “flights to London”

词条归一化 (Normalization)  任务: 将本质上等价但形式上不完全一致的多个词 条归纳成一个等价类,即词项  作用: 提高检索效果,缩小索引空间  两类方法: 规则法,关联关系法  规则法: 采用隐式规则在处理文档和查询时将多个 词条映射成同一词项,比如: 剔除句点规则: U.S.A., USA USA 剔除连接符规则: anti-discriminatory, antidiscriminatory antidiscriminatory

词条归一化 (Normalization)  关联关系法: 通过维护等价的非归一化词条之间 的关联关系,显式地建立并应用等价类,如建立并 应用同义词词典( Thesauri, WordNet ) 每一不重复的词条都作为索引单元 处理查询时对每一词项基于等价类进行扩展,并将 扩展后得到的多个词所对应的倒排表合到一起 在索引构建时就对词进行扩展,如对于包含 car 的文 档也放入 automobile 的倒排表中  方法比较: 规则法效率高,关联关系法更灵活

归一化相关问题及其处理  重音符问题: 如法语中 résumé vs. resume 处理方法:常常归一化成不带重音符号的形式  Tuebingen, Tübingen, Tubingen --  Tubingen  大小写问题: Automobile vs. automobile 处理方法:将句首词转换成小写形式,将标题中大 写或首字母大写的全部单词转换成小写形式  时间格式问题: 3/12/91, Mar. 12, 1991 (美式), 12/3/91 (欧式) 处理方法:启发式规则 + 语言识别

词形归并 (Lemmatization)  任务: 将单词的不同语法形态还原为原形  例子: am, are, is  be ; car, cars, car's, cars'  car the boy's cars are different colors  the boy car be different color  作用: 提高检索效果,减少索引单元  方法: 词典 + 相关词列表  问题: 如: found  find? found? 上下文语义理解 ?

词干还原 ( Stemming )  任务: 将词项归约 (reduce) 成其词干 (stem) 比如,将 automate(s), automatic, automation 都 还原成 automat  作用: 提高检索效果,减少索引单元 ( 5-10% for English , 50% in Arabie , 30% 芬兰语 )  方法: 基于规则截除词缀 for example compressed and compression are both accepted as equivalent to compress. for exampl compress and compress ar both accept as equival to compress

Porter 算法  英语词干还原中最常用的算法,开始于 70 年代  一些规则 + 5 步骤的归约过程

Porter 算法  Porter 算法问题举例 [Note] false positive: pairs of different words have the same stem; false negative: pairs of words have different stem when they should have the same.

其他词干还原工具 (stemmer)  Lovins research/stemming/general/lovins.htm 单遍扫描,最长词缀剔除 ( 大概 250 条规则 )  Paice/Husk  基于词形分析对于检索只能提供一定的帮助  未来:基于词用分析? 18

回顾:基本合并算法  两个指针,同步扫描,线性时间 Brutus Caesar 2 8 两个表长度为 m 和 n 的话,上述合并时间复杂度为 O(m+n) 能否做得更好?

带跳表指针的倒排表  跳表 (skip list) :  作用: 支持在遍历倒排表时跳过那些不可能出现在 检索结果中的记录项,以提高合并操作的效率  需要解决的问题: 在什么地方加跳表指针?如何 利用跳表指针支持倒排表的快速合并?

基于跳表的倒排表快速合并  假定匹配到上下的指针都指向 8 ,接下来两个指针都向下移动一位  比较 41 和 11 ,这里 11 小且有跳表指针(指向 31 ),则直接比较 41 和 31 ,由于 31 仍然比 41 小,于是下指针直接指向 31 ,这样就跳过了 12 、 21 两项; 跳表法

基于跳表的倒排表快速合并 跳表法

跳表指针的位置选择  均衡性 : 指针数目过多过少都不合适 指针越多  跳步越短  更容易跳转,但是需要更多的与跳 表指针指向记录的比较 指针越少  比较次数越少,但是跳步越长  成功跳转的次 数少  简单的启发式策略: 对于长度为 L 的倒排记录表,每 L 处放一个跳表指针,即均匀放置。均匀放置方法忽 略了查询词项的分布情况

短语查询  短语查询:以一个短语整体作为查询的查询方 式,比如 “stanford university” “ 浙江 大学 ”  是一种符合人们需要的查询方式  基于关键词的查询难以达到短语查询的效果  原因何在?  问题:如何改造索引 ? 如何识别文档中的短语?

双词 (Biword) 索引  目的: 将文档中每两个连续的词组成词对,作为索 引单元  例子: 对文本 片段 “Friends, Romans, Countrymen” , 产生两个词对 friends romans romans countrymen  方法: 索引构建时,将每个词对看成一个词项放到 词典中  问题: 大大增加词汇表的规模和索引的规模

更长的短语查询处理  方法: 将其拆分成基于双词的布尔查询式,拆分采 用 K-gram 策略  例子: 对于 stanford university palo alto , 将 其拆分成 stanford university AND university palo AND palo alto 进行查询处理  满足上述布尔表达式只是满足短语查询的必要条件 很难避免伪正例的出现!

双词扩展 ( Extended Biword )  目的: 有效支持名词短语查询  扩展方法: 对文档进行词性标注,将词项进行组块,每个组块包含名词 (N) 和冠词 / 介词 (X) 称具有 NX*N 形式的词项序列为扩展双词,放入词典  例子 : catcher in the rye N X X N  查询处理: 将查询也分析成 N 和 X 序列 将查询切分成扩展双词 在索引中查找 : catcher rye

位置索引 (Positional indexes)  是指带词项位置信息的倒排索引,即在倒排记 录表中,对每个词项在每篇文档中的每个位置 ( 单词序号 ) 进行存储  目的:一般性地支持短语查询和邻近查询 <term, 出现 term 的文档 篇数; doc1: 位置 1, 位置 2 … ; doc2: 位置 1, 位置 2 … ; 等等 > <be: ; 1: 7, 18, 33, 72, 86, 231; 2: 3, 149; 4: 17, 191, 291, 430, 434; 5: 363, 367, …>

基于位置索引的短语查询处理  短语查询: “to be or not to be”  对每个词项,抽出其对应的倒排记录表 : to, be, or, not  合并倒排记录表, 考虑位置匹配(保持位置关系一致) to:  2:1,17,74,222,551; 4:8,16,190,429,433; 7:13,23,191;... be:  1:17,19; 4:17,191,291,430,434; 5:14,19,101;...  K 邻近搜索中的搜索策略与此类似,不同的是此时考 虑前后位置之间的距离不大于 K

基于位置索引的合并算法

位置索引分析  位置索引目前是实际检索系统的标配,这是因为实 际中需要处理短语和邻近式查询  位置索引需要更大的存储空间,因为增加了位置信 息,但是可以采用索引压缩技术进行处理  位置索引的大小大概是无位置信息索引的 2-4 倍  位置索引大概是原始文本容量的 35-50%  提高了倒排记录表合并操作的复杂性

混合索引  混合索引: 将双词索引和位置索引合并形成的索引, 其中双词为用户查询中的高频双词  目的: 提高检索效率 对某些特定的短语 ( 如 “Michael Jackson”, “Britney Spears”) , 如果采用位置索引的方式那么效率不高 对于 “The Who” (英国一著名摇滚乐队),采用位置索引, 效率更低  Williams et al. (2004) 的评估结果 采用混合机制,那么对于典型的 Web 查询 ( 比例 ) 来说, 相对于只使用位置索引而言,仅需要其 ¼ 的时间 相对于只使用位置索引,空间开销只增加了 26%

参考资料  《信息检索导论》第 2 章  MG 3.6, 4.3; MIR 7.2  Porter’s stemmer:  跳表理论 : Pugh (1990) Multilevel skip lists give same O(log n) efficiency as trees  H.E. Williams, J. Zobel, and D. Bahle “Fast Phrase Querying with Combined Indexes”, ACM Transactions on Information Systems.  php?author=4 php?author=4  D. Bahle, H. Williams, and J. Zobel. Efficient phrase querying with an auxiliary index. SIGIR 2002, pp

课后作业  见课程网页 : 34