中国科学技术大学：《信息检索与数据挖掘》课程教学资源（课件讲稿）第3章 词项词典和倒排记录表

信息检索与数据挖掘 2019/3/4 1 信息检索与数据挖掘 第3章词项词典和倒排记录表

信息检索与数据挖掘 2019/3/4 1 信息检索与数据挖掘 第3章 词项词典和倒排记录表

信息检索与数据挖掘 2019/3/4 3 第3章词典查找及扩展的倒排索引 l.如何建立词项词典(term vocabulary)? ① 文档集 ② 文本词条化(Tokenization) 语言学预处理 建立索引 2.如何实现倒排记录表？ ① 快速合并算法：带跳表的倒排记录表(skip lists) ② 包含位置信息的倒排记录表以及短语查询 3

信息检索与数据挖掘 2019/3/4 3 第3章 词典查找及扩展的倒排索引 1. 如何建立词项词典（ term vocabulary ）？ ① 文档集 ② 文本词条化（ Tokenization ） ③ 语言学预处理 ④ 建立索引 2. 如何实现倒排记录表？ ① 快速合并算法：带跳表的倒排记录表(skip lists) ② 包含位置信息的倒排记录表以及短语查询 3

信息检索与数据挖掘 2019/3/4 4 建立词项(Term)词典过程 量h西 待建索引文档集合 词条化模块 Tokenizer 词条化 Friends Romans Countrymen 语言学预处理模块 Linguistic modules friend roman countryman 语言学预处理 索引器 Indexer friend 000 0 倒排记录表 roman countryman 13 16 4

信息检索与数据挖掘 2019/3/4 4 建立词项(Term)词典过程 词条化模块 Tokenizer 词条化 Friends Romans Countrymen 语言学预处理模块 Linguistic modules 语言学预处理 friend roman countryman 索引器 Indexer 倒排记录表 friend roman countryman 2 4 2 13 16 1 待建索引文档集合 4

信息检索与数据挖掘 2019/3/4 5 第3章词典查找及扩展的倒排索引 ●第一部分：如何建立词项词典？ ●文档解析(Parsing a document) ●词条化 ●停用词 ●词项归一化 ●词形归并 ●词还原 ●第二部分：如何实现倒排记录表？ ●快速合并算法：带跳表的倒排记录表 ●包含位置信息的倒排记录表以及短语查询 5

信息检索与数据挖掘 2019/3/4 5 第3章 词典查找及扩展的倒排索引 第一部分：如何建立词项词典？ 文档解析（Parsing a document） 词条化 停用词 词项归一化 词形归并 词干还原 第二部分：如何实现倒排记录表？ 快速合并算法：带跳表的倒排记录表 包含位置信息的倒排记录表以及短语查询 5

信息检索与数据挖掘 2019/3/4 6 文档解析 ●文档包含哪些格式？ pdf/word/excel/html? ●文档中包含的语言？ ●文档使用何种编码方式？ 上述问题都可以看成是机器学习中的分类问题，但 在实际中往往采用启发式方法来实现。（后面章节 讨论) 6

信息检索与数据挖掘 2019/3/4 6 文档解析 文档包含哪些格式？ • pdf/word/excel/html？ 文档中包含的语言？ 文档使用何种编码方式？ 上述问题都可以看成是机器学习中的分类问题，但 在实际中往往采用启发式方法来实现。（后面章节 讨论） 6

信息检索与数据挖掘 2019/3/4 7 不同文档格式的识别 ☑EditPlus-[o:teach2.01i信息检索教程nlp.stanford.edu01 Lintrol01 introl01 intro..te 白EditPlus-【o: File Edit View Search Document Project ools Window Help ☑File Edit 3日量台"回品围凫X口始自+AW=勰图▣国国回？8 时3日 Directory Cliptext --- ----2--4--3------4--4--5--4---6-4---7-----8---4---9--4---0--1- 49 Directory Cliptext [C:]OS_WIN7 50 begin(frame)[label=takeaway] [C:]OS_WIN7 C 51 %\begin(frame) 包Windows 52 frametitle(Take-away明 白C 53 包Windows 白system32 白system32 ☒0409 54 beginfitemize】 ☐0409 ☐2052 55 56 Ipause[2] ▣2052 AdCache 57 AdCache ~temp 58 litem Administrativa 12520437.cpx 59 ~temp 12520850.cpw 12520437.cpx 60 \pause[3] 360SoftMgr.cpl 12520850.cpx 61 5U875.ax 360SoftMgr.cpl 62 5U875.d litem Boolean Retrieval:Design and data structures of a 5U875.ax 7B296FB0-376B-497e-BC 63 simple information retrieval system 5U875.dW 7B296FB0-376B-497e-BC 64 7B296FB0-376B-49 aaclient.dll 65 Ipause[4] 7B296FB0-376B-49 accessibilitycpldll 66 aaclient dil ACCTRES.dll 67 litem What topics will be covered in this class? accessibilitycpldll acledit.dll ACCTRES.dll 68 aclui dll acledit dll 69 acppage.dll \enditemize) aclui.dil acproxy.dil 70 acppage.dll ActionCenter.dil 71 end frame) acproxy.dll ActionCenterCPL.dll 72 ActionCenter.dll ActionQueue.dll 73 ActionCenterCPL.dl -1 ActionQueue.dll All Files[",〕 All Files ("" 01intro.tex ☐◆informatic For Help,press F1 In 65 col 10 141200 UNIX REC INS READ For Help,press 7

信息检索与数据挖掘 2019/3/4 7 不同文档格式的识别 7

信息检索与数据挖掘 2019/3/4 8 语言的自动检测 ·你好 ·我爱你 。乙h记古太 ·私体西尔龙左愛( 。Hallo 。Ich liebe dich ·处5￡. ·LH告量L叶 ·AII0 ·AIo60Te6a .j .4i 】Google超译 ←→ 能成入N网数 但☆≡☑鱼 函过远程女或得入你的收意夹来添加到收藏实兰 翻译 G四 英语中文日语检测后神语， 中文英语日语一 Hallo 你好 0 ☆里五的< 另请象阅 8 Hallo!.Hallo?.Hallo,wie gehrs? 关同时标碑 关于Co0g翻译移动社区私反和使用条敏帮助发送反德

信息检索与数据挖掘 2019/3/4 8 语言的自动检测 • 你好 • こんにちは • Hallo • 안녕하세요. • Алло • أهال و سهال. 8 • 我爱你 • 私はあなたを愛して • Ich liebe dich • 나는 당신을 사랑합니다 • Я люблю тебя • أحبك

信息检索与数据挖掘 2019/3/4 9 文档中的语言 上加字 元音 991 别5558aN夏5！ 前加字 第二後加字 欢迎您到西藏来！ 下加字 第一後加字 到风到N5'1 您好！早上好！下午好！晚上好！ 四N宁a利刚 ZHONGGUO RENMIN YINHANG 吉祥如意 5折N到到 对不起 回 w专 1999年 影像网 谢谢 市上的五种文字：汉文、蒙古文字、藏文字、维吾尔文字、壮文

信息检索与数据挖掘 2019/3/4 9 文档中的语言 9 人民币上的五种文字：汉文、蒙古文字、藏族文字、维吾尔文字、壮文

信息检索与数据挖掘 2019/3/4 10 文档中的编码方式 ·7 bit ASCII? ·UNICODE? ·UTF-8、UTF-16、UTF-32 ·Email对二进制附件的编码 Content-Type:text/html; charset="gb2312" Content-Transfer-Encoding:base64 10

信息检索与数据挖掘 2019/3/4 10 文档中的编码方式 • 7bit ASCII？ • UNICODE？ • UTF-8、UTF-16、UTF-32 • Email对二进制附件的编码 • Content-Type: text/html; • charset="gb2312" • Content-Transfer-Encoding: base64 10

信息检索与数据挖掘 2019/3/4 11 复杂因素：格式/语言 ●待索引文档集中包含不同语言的文档 ·单独的一个索引应该包含不同语言的文档 ●一个文档或者其附件中包含多种语言或格式 ·例子：一封法语的邮件中包含德语的pdf ●文档单位的选择？ ·一个文件？ 。一封email? ·一封带有5个附件的email? 。一组文件？ 11

信息检索与数据挖掘 2019/3/4 11 复杂因素：格式/语言 待索引文档集中包含不同语言的文档 • 单独的一个索引应该包含不同语言的文档 一个文档或者其附件中包含多种语言或格式 • 例子：一封法语的邮件中包含德语的pdf 文档单位的选择？ • 一个文件？ • 一封email？ • 一封带有5个附件的email？ • 一组文件？ 11