信息检索技术 第四章 文本操作技术 (2).pdf

第四章 文本操作技术第四章 文本操作技术 拼写检查 1 概述1 概述 当用户输入的查询中存在拼写错误时系统的 当用户输入的查询中存在拼写错误时 IR系统的 鲁棒性处理技术 文本编辑软件 Word WPS 中的拼写检查功 能 IR系统中的拼写检查 举例 举 输入查询 Mircosoft Google会提示 您是不是要找 Microsoft Google会提示您是不是要找 Microsoft 2011 11 132 1 概述1 概述 拼写错误的两种类型 拼写错误的两种类型 上下文无关的错误 isolated word error 也叫 非词错误 即输入的词是一个无效词 在字典中不 存在 例如 the 错为teh reluctant 错为reluctent 上下文有关的错误 context dependent word p error 也叫真词错误 即输入的词是和原词相似 的另一个有效词 例如 I have a peace of cake peace piece 撼祖国强盛 卫京都泰安 撼 捍 强 2011 11 133 1 概述1 概述 拼写错误的两种类型 拼写错误的两种类型 上下文无关的错误 上下文有关的错误 由于字形和读音的相似而导致的输入错误 形和读相似致输错误 例如 hear 错为 here it s错为its 再接再励 励 厉 再接再励 励 厉 年轻有为 轻 青 由于用法上的相似而导致的错误 由于用法上的相似而导致的错误 例如 between 错为 among 在文化建设方面 北京市首当其冲 在文化建设方面 北京市首当其冲 2011 11 134 1 概述1 概述 拼写错误的任务 拼写错误的任务 查错 即判断目标词是否正确 纠错 即对错误的单词给出修改建议 纠错 即对错误的单词给出修改建议 2011 11 135 1 概述1 概述 拼写错误的任务 拼写错误的任务 查错 即判断目标词是否正确 词表查找 形态还原 相似度计算 纠错 即对错误的单词给出修改建议 2011 11 136 1 概述1 概述 拼写错误的任务 拼写错误的任务 查错 即判断目标词是否正确 纠错 即对错误的单词给出修改建议 对于拼写错误的查询 在其可能的正确拼写中 选拼错误 其确拼中 择距离 最近 的那一个 当两个正确拼写查询的距离相等时 选择更常见的 那一个 1 统计文档集频率 2 统计其他用户常用的搜索查询用词 邹结论 周杰伦 or 周结论 2011 11 137 1 概述1 概述 在中拼写检查的功能通过以几种方式将搜 在IR中 拼写检查的功能通过以下几种方式将搜 索结果返回给用户 输入查询 李艳红 IR系统往往在返回包含 李艳红 的文档的同时 也返回包含 李艳红 多 种能的拼校结的文档种可能的拼写校正结果的文档 当查询不在词典时 采用编辑距离寻找最近邻词 当原始的查询返回的文档结果数目少于预定值 比如少于5篇文档 时 采用编辑距离计算最近邻 词或者给出拼写建议 您是在找 吗 2011 11 138 2 动态规划算法2 动态规划算法 适合采用动态规划方法的最优化问题的两个基本 适合采用动态规划方法的最优化问题的两个基本 要素 最优子结构 如果一个问题的最优解中包含子问 题的最优解 则该问题具有最优子结构 重叠子问题 当一个算法不断的调用同一个问题 时 我们说该最有问题包含重叠子问题 举例 Fibonacci 函数 Fn Fn 1 Fn 2举例函数 nn 1n 2 F1 F2 1 2011 11 139 2 动态规划算法2 动态规划算法 动态规划算法设计的个步骤 动态规划算法设计的四个步骤 描述最优解的结构 递归定义最优解的值 按照自底向上的方式计算最优解 按照自底向上的方式计算最优解 构造最优解 2011 11 1310 2 动态规划算法2 动态规划算法 问题描述 问题描述 两条装配线 每条装配线上有n个装配站 在两条 装配线上相同位置的装配站完成相同的功能 但装 配时间不同 在同一条装配线的装配站之间移动底 盘不需花费额外的时间但是移到另外条装配线盘不需花费额外的时间 但是移到另外一条装配线 上则需额外的时间 求从底盘进入到底盘离开的最 短的时间短的时间 2011 11 1311 2 动态规划算法2 动态规划算法 S1 6S1 5S1 4 S1 3 S1 2S1 1 装配线1装配线1 934847 2 2 3 3134 完成退出完成退出 底盘进入底盘进入 4 2 2 2 3 1 1 2 3 2 4 1 装配线2装配线2 S2 6S2 5S2 4 S2 3 S2 2S2 1 564578 2011 11 1312 2 动态规划算法2 动态规划算法 最优子结构 最优子结构 通过装配站S1 j的最快路线只能是以下两者之一 j 通过装配站S1 j 1 然后直接通过装配站S1 j 通过装配站S2 j 1 从装配站S2 j 1移走底盘 然后通 2 j 12 j 1 过装配站S1 j 通过装配站S2 j的最快路线只能是以下两者之一 通过装配站S1 j 1 从装配站S1 j 1移走底盘 然后通通装配站 1 j 1 从装配站1 j 1移走底 然后通 过装配站S2 j 通过装配站S2 j 1 然后直接通过装配站S2 j j j 2011 11 1313 2 动态规划算法2 动态规划算法 个递归解 一个递归解 令fi j 表示一个底盘从起点到装配站Si j的最快时 j 间 ei进入装配线的时间 xi离开装配线的时间 ai j 在装配站si j的装配时间 ti j从装配站si j移除的时间 求解 f min f1 n x1 f2 n x2 递归解 11 1 1 e a j 1 f j min f j 1 af j 1 t a j 1 11 j22 j 11 j min f j 1 a f j 1 t a j 1 22 1 2 e a j 1 f j i f j 1 f j 1 j1 2011 11 1314 2 11 j 12 j22 j f j min f j 1 t a f j 1 a j 1 2 动态规划算法2 动态规划算法 计算最优解 计算最优解 j123456j123456 f1 j 9 f2 j 12 f 38 j23456 l l1 j l2 j 2011 11 1315 l 1 2 动态规划算法2 动态规划算法 计算最优解 计算最优解 j123456j123456 f1 j 918 f2 j 1216 f 38 j23456 l l1 j 1 l2 j 1 2011 11 1316 l 1 2 动态规划算法2 动态规划算法 计算最优解 计算最优解 j123456j123456 f1 j 91820 f2 j 121622 f 38 j23456 l l1 j 12 l2 j 12 2011 11 1317 l 1 2 动态规划算法2 动态规划算法 计算最优解 计算最优解 j123456j123456 f1 j 9182024 f2 j 12162225 f 38 j23456 l l1 j 121 l2 j 121 2011 11 1318 l 1 2 动态规划算法2 动态规划算法 计算最优解 计算最优解 j123456j123456 f1 j 918202432 f2 j 1216222530 f 38 j23456 l l1 j 1211 l2 j 1212 2011 11 1319 l 1 2 动态规划算法2 动态规划算法 计算最优解 计算最优解 j123456j123456 f1 j 91820243235 f2 j 121622253037 f 38 j23456 l l1 j 12112 l2 j 12122 2011 11 1320 l 1 2 动态规划算法2 动态规划算法 ASSA FASTEST WAY a t e x n 1 f1 1 e1 a1 1 2 f2 1 e2 a2 1 3 for j 2 to n3 for j 2 to n 4 do if f1 j 1 a1 j f2 j 1 t2 j 1 a1 j 5 then f1 j f1 j 1 a1 j 6 l1 j 1 7 else f1 j f2 j 1 t2 j 1 a1 j 8l1 j 2 9 if f2 j 1 a2 j f1 j 1 t1 j 1 a2 j 10then f j f j 1 a10 then f2 j f2 j 1 a2 j 11 l2 j 2 12 else f2 j f1 j 1 t1 j 1 a2 j 13 l2 j 1 14 if f1 n x1 f2 n x2 15 then f f1 n x1 16l 1 17else f f n x 2011 11 1321 17else f f2 n x2 18l 2 2 动态规划算法2 动态规划算法 构造最优解 构造最优解 j23456 l j 12112l1 j 12112 l2 j 12122 l 1 2011 11 1322 2 动态规划算法2 动态规划算法 构造最优解 构造最优解 j23456 l j 12112l1 j 12112 l2 j 12122 l 1 2011 11 1323 2 动态规划算法2 动态规划算法 构造最优解 构造最优解 j23456 l j 12112l1 j 12112 l2 j 12122 l 1 2011 11 1324 2 动态规划算法2 动态规划算法 构造最优解 构造最优解 j23456 l j 12112l1 j 12112 l2 j 12122 l 1 2011 11 1325 2 动态规划算法2 动态规划算法 构造最优解 构造最优解 j23456 l j 12112l1 j 12112 l2 j 12122 l 1 2011 11 1326 2 动态规划算法2 动态规划算法 PRINT STATIONS l l n PRINT STATIONS l l n 1 i l 2 print line i station n 3 for j n downto 2 4do i li j 5i t li i t ti j 15 print line i station j 1 2011 11 1327 2 动态规划算法2 动态规划算法 算法复杂度 算法复杂度 Brute force 2n Dynamic Programming ygg 2 n 2011 11 1328 词语相似度计算词语相似度计算 当检查用户输入的字符串是个错 当检查用户输入的字符串X x1x2 xn 是一个错 误的单词时 需要从词表中找出与X相似的词Y 作为改的候选提供给用户 y1y2 ym 作为改正的候选提供给用户 计算两个字符串X和Y的相似度 可以通过计算出 两个串之间的距离d X Y 得到 d X Y 0 串X等于串Y 串 等于串 d X Y max X Y 串X与串Y完全不匹配 0 d X Y max X Y 串X与串Y在一定程度 0 xi 即在位置i处插入字符xi you your 删除 xi 即在位置i处删除字符xi 删除 i 即在位置 处删除字符 i your you 替换xi yi即将位置i处字符xi用字符yi替换 替换 xi yi 即将位置i处字符xi 用字符yi替换 me my 2011 11 1330 词语相似度计算词语相似度计算 计算两个字符串之间的相似度时以采用以 计算两个字符串之间的相似度时 可以采用以下 几种距离 编辑距离 允许插入 删除和替换操作 海明距离 只允许替换操作 Episode距离 只允许插入操作 最长公共子串距离 允许插入和删除操作 最长公共子串距离 允许插入和删除操作 替换 1次删除 1词插入 相当于2个代价 进一步推广不同的编辑操作具有不同的权重 进一步推广 不同的编辑操作具有不同的权重 考虑键盘输入 输入将字符s替换为字符a的代价 可能会比替换为字符p的代价小可能会比替换为字符p的代价小 2011 11 1331 词语相似度计算词语相似度计算 使用动态规划算法求解编辑距离 使用动态规划算法求解编辑距离 问题定义 在将字符串x1x2 xn 转换成y1y2 ym 的过程中 最少的字符插入 删除和替换操作的次数 2011 11 1332 词语相似度计算词语相似度计算 最优子问题 最优子问题 xn ym d x1x2 xn y1y2 ym d x1x2 xn 1 y1y2 ym 1 xn ym 插入x1x2x x1x2x y 插入 x1x2 xn x1x2 xnym d x1x2 xn y1y2 ym d x xxy yy 1d x1x2 xn y1y2 ym 1 1 2011 11 1333 词语相似度计算词语相似度计算 最优子问题 最优子问题 xn ym xn ym 删除 x1x2 xn x1x2 xn 1 删除 1 2n1 2n 1 d x1x2 xn y1y2 ym d x1x2x 1 y1y2y 1d x1x2 xn 1 y1y2 ym 1 2011 11 1334 词语相似度计算词语相似度计算 最优子问题 最优子问题 xn ym xn ym 替换 x1x2 xn x1x2 xn 1ym 替换 1 2n1 2n 1 ym d x1x2 xn y1y2 ym d x1x2x 1 y1y2y 1 1d x1x2 xn 1 y1y2 ym 1 1 2011 11 1335 词语相似度计算词语相似度计算 个递归解 一个递归解 定义 M i j d x1x2 xi y1y2 yj j M i j M i 1 j 1 当i j 0且xi yj min M i j 1 1 M i 1 j 1 M i 1 j 1 1 当i j 0且xi yjM i 1 j 1 1 当i j 0且xi yj j 当i0 j 0 j 当i 0 j 0 当 i 当i 0 j 0 2011 11 1336 词语相似度计算词语相似度计算 递推 初始化 递推 初始化 babb babb 01234 a1 a2 b3 a4a4 b5 2011 11 1337 词语相似度计算词语相似度计算 递推 递推 babb babb 01234 a11123 a2 b3 a4a4 b5 2011 11 1338 词语相似度计算词语相似度计算 递推 递推 babb babb 01234 a11123 a22123 b3 a4a4 b5 2011 11 1339 词语相似度计算词语相似度计算 递推 递推 babb babb 01234 a11123 a22123 b32212 a4a4 b5 2011 11 1340 词语相似度计算词语相似度计算 递推 递推 babb babb 01234 a11123 a22123 b32212 a43222a43222 b5 2011 11 1341 词语相似度计算词语相似度计算 递推 递推 babb babb 01234 a11123 a22123 b32212 a43222a43222 b54322 2011 11 1342 词语相似度计算词语相似度计算 递推算法 递推算法 2011 11 1343 词语相似度计算词语相似度计算 回溯 回溯 babb babb 01234 a11123 a22123 b32212 a43222a43222 b54322 2011 11 1344 词语相似度计算词语相似度计算 回溯 回溯 babb babb 01234 a11123 a22123 b32212 a43222a43222 b54322 2011 11 1345 词语相似度计算词语相似度计算 回溯 回溯 babb babb 01234 a11123 a22123 b32212 a43222