信息检索四Dictionary.ppt

湖南大学计算机与通信学院刘钰峰，互联网信息搜索四Dictionary，Recapofthepreviouslecture，Bascinvertedindexs : structures : dictionary and postingskeystepinstruction : OrtingBooleanqueryprocessingSimpleoptimizationLineartimeMerging，Recallbasicindexingpipeline，Documentstobeindexed .朋友，罗马人，同胞、解析文档、什么格式？pdf/word/excel/html？什么语言？使用什么字符？每一个问题，我们将在后面的课程中学习，butthesetasksssareoftendoneurism，compliance 3360 format/language，documentsbeingindexedcaninclueddocsfromanydifferentalanguage sasingleindexmayhavetocontaimtosofservingages .有时，sadocumentoritscomponentscancontainmultiplements/formatsfrench emailwithegermanpdfattachment .什么是统一文件？着火了吗？白头翁？（也许是因为).有5个附件的邮件？agropofiles(pptorlateshintml)，标记化，输入：“朋友，罗马人和乡下人”输出： OkensfriendsRomanscountrymentkenization；把字符串变为词串每个suchtokenisnowadidateforindexentry，after processing describebebebebebebelow命令行：对词进行内部结构和形式分析但是whatarevalidtokenstoemit？(1)对一个待分析的字符串（秒)，从左到右进行扫描，读入当前字符(char)到候选词数组（西一)，并将指针（指针)前移，I=I 1；(2)看茶是否为词分隔符（事先可以预定义空格以及一般标点均为词分隔符)；(3)如果茶是词分隔符，并且W不是空格，将W中从起始位置到i-1位置的字符作为一个词汇单位输出，同时将S中的W部分删去，然后清空w、转入(1)，如果茶是词分隔符，且W是空格，将S中的W部分删去，清空w、转入(1)；(4)如果不是词分隔符，看指针是否已经指到字符流尾部；(5)如果指针已经指到字符流尾部，将当前W从起始位置到i-1位置的字符作为一个词汇单位输出，结束(6)如果不是字符流尾部，转入(1)；标记化算法的一般过程，标记化示例、S、指针、字符= .字符流尾部标记，i=2，W=”先生输出：Mr，这时S的格局为：，最后输出：MrWuwasill，要得到先生，需要构造一个词典，收录这一类词苏阿西。tokenization:languageissues,issuesintokenization:finlandscapitalfinland？芬兰？芬兰的？最先进的： breakuphypendented序列。男女同校？拉他回来然后把他拖走的策略？it seeffectivetogethertoputinbassiblinkssandfrancesco : onetokennotwo？你好。策略断字的refixensencourageuserstoenterbellesswhere verthemaypossible over-eagertosearchforover-eagerorovergeoverager .标记化：语言问题，标记化：其他问题，3/12/91Mar.12，199155 b . c . b-52 mygpkey is 324 a3 df 234 CB 23 EEMailAddresses，IPaddress，url，tel100。2 .86 .144 ften，don tindext .butoftenveryusefull 3360 thinkaboutthingslikelookingpercorcodes/stacktracesonwwibwloftenindex .识别分数，日期的正则表达式：0-9 (/0-9)，例如2002年12月215日b .识别百分数的正则表达式：( -)？0-9 ( .)？0-9* %例如-5.9% c识别十进制数字的正则表达式：(0-9，).0-9|0-9)*例如12，345，数字的识别（正则表达式)，表示出现1到无穷次，表示转义什么？表示不出现或只出现1次，*表示出现0到无穷次，表示单个字符，()表示任意个字符，标记化：语言问题，中文和日文姚明现在是休斯顿火箭队的篮球队员。notalwaysguaranteedanonyquitokenization从中文字符串中识别单词：分词；统计结果表明，仅使用正最大匹配的错误率为1/169。反向最大匹配的错误率为1/245。对于通过最大匹配法分割的问题，如果确定最大单词长度(1)如果单词长度太短，长单词将被拼错(“中华人民共和国”)(2)如果单词长度太长， 低效率掩盖了分词的歧义性A .“意见不一致”(正向最大匹配和反向最大匹配的不同结果)意图/意见/不一致/意见/不一致/B .“成分子时间的组合”(正向最大匹配和反向最大匹配的相同结果)组合/成分/子时间/，分词歧义的类型，交集歧义如果AB和BC是字典中的单词，那么如果要分割的字符串包含子字符串“ABC”，则不可避免地会导致两种可能的分割：“AB/C/”和“A/BC/”。 “组合”-“组/合成”和“组合/合成”组合歧义如果AB和A、B是字典中的单词，那么如果要分割的字符串包含子串“AB”，则不可避免地会导致两种可能的分割：“AB/”和“A/B/”。自主，发现歧义，歧义解决的前提是发现歧义。分割算法应该能够检测输入文本中何时出现模糊分割。最小均方误差和最小均方误差方法没有检测模糊度的能力，只能给出一个分割结果。链长：包含在交集歧义字段中的交集字段的数量称为链长。链长为1；尚未链长为2；组合组件链长为3；为人民工作链长为4；中文产品质量链长为6；努力学习语法规则.输入：企业在就业方面拥有真正的自主权。双向最大匹配法可以找到奇数链长的交集模糊度，但不能找到偶数链长的交集模糊度。最大匹配法具有解决切分歧义的能力。对于一些交集型歧义，通过添加回溯机制，可以提高最大匹配法的分割效果。例如，“学习历史知识”的前向扫描结果是：“教育背景/历史/知识/”。查字典后，我们知道“历史”不在字典里，所以我们回去把“教育背景”的结尾词“历史”和后面的“历史”去掉，形成“历史”。然后我们查字典，看看“学习”和“历史”是否在字典里。如果是这样，我们将分割结果调整为“学习/历史/知识/”,并使用最大概率方法来分割单词。其基本思想是：(1)待分割的中文字符串可能包含多种分割结果(2)取概率最高的一个作为字符串的分割结果，路径1: 0-1-3-5路径2: 0-2-3-5，我应该选择哪条路径？此外，也很难找到解决问题的方法。独立性假设，一元语法，分词的最大概率法，P(W1)=P(是)*P(意见)*P(分歧)=1.810-9P(W2)=P(意图)*P(参见)*P(分歧)=110-11P(W1)P(W2)，提高计算效率，达到候选词wi时的累积概率，公式1，如何尽快找到概率最高的词串(路径)？为了提高计算效率(续)，左相邻字假设从左到右扫描字符串，并且几个候选字，例如w1、w2，wi-1，wi，等等。可以获得。如果wi-1的后缀与wi的前缀相邻，则wi-1被称为wi的左邻词。例如，在上面的例子中，候选词“你”是候选词“意见”的左手词，“意见”和“见”是“不同意”的左手词字符串中最左边的单词没有左邻居。最佳左邻词如果候选词wi有几个左邻词wj，wk，等等。具有最大累积概率的候选词被称为wi的最佳左邻词。例如，候选词“意见”只有一个左邻词“你”，所以“你”也是“意见”的最佳左邻词。候选单词“散度”具有两个左相邻单词“意见”和“看见”，其中“意见”的累积概率大于“看见”的累积概率，因此“意见”是“散度”的最佳左相邻单词，最大概率单词分割算法，对于要分割的字符串s，所有候选单词w1，w2，wi，wn按照从左到右的顺序提取；找出字典中每个候选词的概率值P(wi)，并记录每个候选词的所有左邻词；根据公式1计算每个候选词的累积概率，比较得到每个候选词的最佳左邻词；如果当前单词wn是串S的结束单词，并且累积概率P(wn)最大，则wn是串S的结束单词；从wn开始，从右到左依次输出每个词的最佳左邻词，这是S的分割结果.最大概率分词算法的一个例子，(1)从左到右扫描“有不同意见”，得到所有候选词：“是”、“有意”、“意见”、“见”和“不同意”；(2)对于每个候选单词，记录其概率值，并将累积概率的初始值指定为0；(3)依次计算每个候选词的累积概率值，同时记录每个候选词的最佳左邻词：P(是)=P(是)，P(意图)=P(意图)，P(意见)=P(是)P(意见)，(“意见”最佳左邻词为“是”)P(见)=P(意图)P(见)，(“最佳左邻词为“意图”)P(见)(4)“分歧”为最后一个词。“意见”是“不同意”的最佳左邻词。分词过程完成后，输出结果：是/意见/不同意/，最大概率分词问题。它不能解决所有的交集歧义问题“它不能确定”W1=这个/事情/肯定/肯定/不/下/W2=这个/事情/肯定/不/下/不能解决组合歧义问题“做完作业后看电视”W1=做/完成/作业/能力/看/电视/W2=做/完成/作业/能力/看/电视/，P(W1)P(W2)，其他分词困难，中文名字：姚明老张，李，子，中文地名：丁福庄白沟三义约克郡机构名称：方正公司协会集团、国际卫生组织、贸易部品牌名称：特种可乐、乐凯波导、杉山爱、同仁堂、专业术语：万维网主板模态逻辑贝叶斯算法缩写：三个代表五个演讲、四个美女、打假、反色情、计划生育新词：卡拉OK超女、未注册词识别、未注册词识别困难、未注册词无明确界限未注册词的许多成分可以独立成词。 每种类型的未注册单词都需要通过特殊的识别算法来识别。根据内部构词规律(用词规律)和外部环境(语境)，未登录词的识别过程中，中文名称越成熟，中文地名的翻译越困难，商标名称越困难，机构名称越困难，专业术语的缩略语和新词越困难，中文名称的识别越困难，在中文未登录词中，中文名称是最规则、最容易识别的类型。中文姓名一般由以下部分组成：姓：张、王、李、刘、诸葛、西门：张飞、诸葛亮、前缀：老王、小李后缀：王老、中国人的名字经常被认出来。据统计，中国有1000多个姓氏(数量有限)。最常用的姓氏是“王”、“王、陈、李、张、刘”等五大姓氏，覆盖率为32%。姓氏频率表中前14个高频姓氏的覆盖率为50%，前400个姓氏的覆盖率为99%。人名的使用也相对集中。出现频率最高的前6个词的覆盖率达到10.35%，前10个词的覆盖率达到14.936%，前15个词的覆盖率达到19.695%，前400个词的覆盖率达到90%。,令牌化3360种语言，阿拉伯语(orhbaev)