（计算机软件与理论专业论文）基于全文检索的自动答疑系统的研究.pdf

摘要 摘要 让人们能够用浩如烟海的本文资料中方便地找到自己需要的信息， 是计算机技术一个重要的研究目标。全文检索技术在此领域上一直担任 着举足轻重的角色，成为众多文本信息检索应用的基础。同时，随着互 联网络的普及，计算机远程教育的飞速发展对自动答疑系统有了更高的 要求。如何在比较成熟全文检索技术基础上，通过对文本信息进一步的 处理和提取，现实计算机自动答疑成为当前文本信息处理技术领域的一 个新课题。 本论文首先分析了国内外全文检索技术的最新发展和应用于远程教 育的答疑系统的现状，有针对性地对全文检索引擎进行研究和改造。考 虑到多种应用环境下中英文文本为主，多种国家文字或者文本符号并存 的情况，本文讨论了利用u n i e o d e 编码建立支持多语种的索引库。在词 法分析阶段，提出了中英文混合分词的方案，供全文检索引擎支持不同 应用。索引的存贮方面，为中英文关键字定义了不同的数据存储格式， 以提高存储效率和读写速度。检索评分方面，以信息检索系统最常用的 t f + i d f 评分方式为基础，提出了在综合索引库中检索特定领域文档的评分 模型。 本论文继续讨论了以全文检索为基础的自动答疑模型。论文提出了 利用分词程序构造问题分析器，对自动答疑中输入的问题进行分析处理， 不过多考虑问题句子结构，着重提取问题包含的问题类型和提问焦点信 息。然后，为了提高匹配效率和答案的准确性，提出了两阶段匹配策略： 问题与问题的匹配和问题与答案的匹配，获取答案文本；设计了答案提 取算法，根据问题信息在得到的文本材料中提取更为精确的答案；再由 自动答疑的白反馈流程，把答疑过程形成的新问答材料保存到答疑库。 最后，本论文对课题研究成果进行了总结并提出下一步工作的思路。 关键字：全文检索；自动答疑；答案提取 a b s t r a c t t ol e tp e o p l ef i n dt h ei n f o r m a t i o nt h e yn e e df r o mt h eh u g e i n f o r m a t i o n w o r l di sa ni m p o r t a n tr e s e a r c hf i e l do fc o m p u t e rs c i e n c e f u l lt e x tr e t r i e v a l h a st a k e nae r i t i c a t p a r t n t h i s f i e l da n db e c o m et h eb a s i so fm a n y a p p l i c a t i o n so ft e x ti n f o r m a t i o nr e t r i e v a l ( 袋) a tt h es a m et i m e ，w i t ht h e p r e v a l e n c e o f i n t e r n e t ，t h er a p i dd e v e l o p m e n t o f c o m p u t e r d i s t a n c e e d u c a t i o np r e s e n t sah i g h e rd e m a n do nq u e s t i o na n s w e r i n g ( q a ) s y s t e m h o wt ob u i l du paq a s y s t e mb a s e d o nm a t u r ef u l lt e x tr e t r i e v a lt e c h n o l o g y ， b yf u r t h e rp r o c e s s i n ga n de x t r a c t i n go f t e x ti n f o r m a t i o n ，i san e wt a s ki ni r f i e l d 。 f i r s t l y , t h et h e s i sa n a l y s e st h el a t e s ti m p r o v e m e n t o ff u l lt e x tr e t r i e v a l t e c h n o l o g yi n s i d e a n do u t s i d en a t i o n ，a n dt h ea c t u a l i t yo fq as y s t e mf o r c o m p u t e r d i s t a n c ee d u e a t i o n t h e ni td os o m er e s e a r c ha n d r e c o n s t r u c tw o r k o nf u l lt e x tr e t r i e v a le n g i n e 。c o n s i d e r i n gm u l t i p l ea p p l i c a t i o ne n v i r o n m e n t s i nw h i c hc h i n e s ea n de n g l i s ha sw e l la so t h e rl a n g u a g e sa n dt e x ts y m b o l h a v eb e e nu s e d ，t h ea r t i c l e g i v e a w a y t o b u i l d i n gu pt h e i n d i c e st h a t s u p p o r t sm u l t i p l el a n g u a g e s ，b ym a k i n g u s eo fu n i c o d e i nl e x i c a la n a l y s i s p h a s e ，as o l u t i o n h a sb e e na d v a n c e df o rc h i n e s ea n de n g l i s hc o m p o s i t e w o r ds e g m e n t a sf o rs t o r i n gt h ei n d e x ，d i f f e r e n ts t o r i n gf o r m a t sh a v eb e e n d e f i n e df o rc h i n e s ea n de n g l i s hk e y w o r d s ，i no r d e rt oi m p r o v es t o r i n g e f f i c i e n c y a n d r e a d i n g w r i t i n gr a t e d u r i n g r e t r i e v a l s c o r i n gp h a s e ，a s c o r i n g m o d e lh a sb e e ns e t u p f o rd o c u m e n t so fs p e c i a lf i e l d s i nt h e i n t e g r a t ei n d e xd a t a b a s e ，w h i c h b a s e so nt h em o s tc o m m o nt f + i d fm e t h o di n i rs y s t e m 。 s e c o n d l y ，t h et h e s i sd i s c u s s e st h eq a m o d e lb a s e do nf u l lt e x tr e t r i e v a l t e c h n o l o g y t h e nt h ea r t i c l ea d v a n c e s aw a yo fc o n s t r u c t i n gq u e s t i o np a r s e r u s i n gw o r ds e g m e n t i n gp r o g r a m ，t h ef u n c t i o n o fw h i c hi s a n a l y z i n ga n d p r o c e s s i n gi n p u tq u e s t i o no f aq a s y s t e ma n de m p h a s i z i n gt h ee x t r a c t i o no f q u e s t i o nt y p e s a n d q u e s t i o n f o c u s e s w i t h o u t c o n s i d e r i n g t h e q u e s t i o n s t r u c t u r et o om u c h i no r d e rt oi n c r e a s em a t c h i n ge f f i c i e n c ya n de x a c t n e s s 狂 。fa n s w e r ， t h ea r t i c l ep r e s e n t s a s t r a t e g y 。f 2 一p h a s e i l i a t c h i n g ： f i r s t m a t c h i n g b e t w e e nq u e s t i 。n sa n d q u e s t i 。n s ，t h e nm a t c h i n gb e w e e nq u e s i 。n a n da n s w e r s ，t 。g e ta n s w e rt e x t i td e s i g n sa l l a n s w e re x t r a c t i o na l g 。r i t h m t h a tf e t c h e sm 。r ea c c u r a t e a n s w e r t h eq u e s t i o n - a n $ w e rp a i r 。c c u r r i n g i n a b 。v ep r 。c e s sw i l lb es t o r e di n aq ad a t a b a s eb ya u t 。f e e d b a c kf l o w 。fq a t h ef u t u r ew o r kf o rt h i ss u b j e c t k e y w o r d s ：f u l l t e x tr e t f i e v a l ；q u e s t i 。na n s w e r i n g ；a n s w e r e 。t r 8 。t i 。n i i i stce p s0r p dnah craeser ehtf0 nosucn ocaswar dss ehceht y a n m h ets y s 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写的成果作 品。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：加 年z 月一日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囱。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 日期：d 年月尸日 日期：汹年月户e t _ 够 触蓊一 么严瓷臻 第一章绪论 1 1 背景 第一章绪论 薅蔷镶憩秘按特嗣是嬲终技术大容量存贮技拳载毫速发袋，互联网 络已经成菇保存和传递久炎秘会各种信感瓣蓬大宝库。同时，分门剐类 地存放各学科资料的电予图书馆，电子档案库在各国如雨厥眷笋般建立 起来。这必宝贵的电子资料，绝大多数的信息都是由结构化或者半结构 化的文本材料所描述。也就是说，在网页、备种格式的文本文件和数据 瘁记录等文本豺瓣中，蕴会麓大量有徐德的僚息。困藏，如秘把这些海 量懿资精鳃类整理，诖入稻煞够餍浩螽矮海稳本文材辩中方後建我羁鑫 己需要的信息，成为计算机领域一个重要的研究课题。近十多年来，在 广大计算机科研工作者努力下，以全文检索技术和文本信。甑检索模型的 研究有了突破性的进展。以此为基础开发的各种信息检索成用，如互联 网搜索弓| 擎( 如国外静g o o g l e 和国内的b a i d u ) ，电子图书镲索戮系统( 如 蓬内酶c n k i 、维普) 浚及焚稳专爰戆全文稔索系统( 露t s r 全文硷索系 统和t o r n a d o 龙卷风全文稳豢系统) ，都已经投入了实际的运行当中，获 得了巨大的社会效益和经济效益。文本信息检索技术并未因此而故步自 封，而是朝着功能多样化，查询智能化的方向发展，继续成为计算机技 术的热点之。 是一方蠢，鏊家提出浆秘教兴国羧貉骧及大力发震逯覆教努戆嚣菰， 能动地加快了我国的信息化进程。近几年来，各种远程教宵软件成为国 家在发展软件产业上投入的主要方向，也成为众多科研机构开展应用研 究的热门课题。在远程教育综合平台下，网络答疑系统是熊中重要的组 成部分。网络答疑系统的主爱功能是提供实时或者非实时的答疑方式， 模掇转统教学孛教学双方懿溺答过程，褥蠢迸程教弯过程戆交互性，有 秘于教学双方掌握网络教学的规律，丰富教学手段，提高教学质量。答 疑系统与熟他教育资源系统的结合，也为网络教育的资源_ 拭攀创造了良 好的条件。随着网络教育的普及率提高，人工网络答疑的方式将令教师 不堪重负，因此，研究高效、准确、智能化的自动答疑成为远程教育软 搏平台豹蘩簧顼疆之一。 华南理 二大学工学硕士学能论文 1 2 国内终研究概潺 在国内，网络答疑系统的发展经历了从简单的聊天室式簪疑系统， 有简单数据襻储能力的答疑系统，再到有较强数据处理分析能力的答疑 系统等多个阶段。坦随着网络教育人数的上秘和层次的扩展，答疑系统 中潦有豹入王签疑窝蓑荤豹数据疼套逮式麴答疑逐溪潢是不了嚣求。毽 此，自动昝疑成为答疑系统发麓的必然，岛渤和智能成为昝疑系统的新 趋势。比较有代表性的有e 海交通大学的潦于w e b 的自动答疑系统 a n s w e rw e b ，北京师范大学的网络自动答疑系统”3 。其他如北京大学1 ， 东北大学3 等高等院校也从文本信息抽取，统计语义学，人工智能乃至 塞熬语言毽瓣熬语义瘸终疲趸，魏蘩撵东宠生为主秀发熬知弼 ( h o w n e t ) ”啦等方向研究鑫动昝疑过程，荠郝取得了一定递鼹。健由于汉 语使用非常簸杂，全面的自然语言理解尚处于理论研究阶段，在提高答 疑系统的准确率方面有很多路要走。 在国外，从词法，语法，语义多个方向对自动问答系统( q u e s t i o na n s w e r s y s t e m ) 酶磷究| 蔼样一直没露筹止过。普拣簸顿大学受责熬w o r d n e t 顼 嚣。”是一个溅撵碎式静或慕。它逶过锤建缭稔纯静关键字羧镶库纛由语 义关系联系的同义词库，缩含开放性的接口，逐步形成一个究整的语义 网络，因而w o r d n e t 成为众多问答系统依赖的基础。2 0 0 2 年的第十一届 文本检索国际会议t r e c ( t e x tr e t r i e v a lc o n f e r e n c e ) ”“上，针对t r e c 的课题：搬据给定静英语奉| 睾萼，使瘸阔答系绫翻答魏定阂题集，各国的 磅究天鬃舔箍密了毅黥愚路簿l 若干舔鍪系绞，萁中l c c m a i n 2 0 0 2 “”， e x a c t a n s w e r ”等几套问答系统分别正确回答了5 0 0 个问鼷中的4 1 5 和 2 7 1 个，最高的准确率达到了8 3 “，已经有较高的可用性。2 0 0 2 年在 日本举行的第三届搜索引擎评价国际会议n t c i r ( n i it e s tc o l l e c t i o n f o ri n f o r m a t i o dr e t r i e v a l s y s t e m s ) ”上，磺究机构对中毯韩等东 方语言，嚣羧繁语言豹语句甥分，索零| 建立，戮及在筵基磷之上建立戆 问答系统避行了较多的研究。 相比之下，由于东方语裔在使用当中更为复杂和灵活，擞难寻找到 规律性，很多英语问答系统的研究成果难以敷接应用到东方谬言上，因 此在中文自动闽答系统的研究潜要付出更大的努力。 2 第一章绪论 。3 谍题来源和主要研究内容 广溅参考围内外文本倍息梭索最新的研究情况后，我们可【冀看到， 全文梭索技术等检索技术的研究成果已经遮到了一个比较徽的水平。但 蹩，蘧蛰艨臻需求魏不凝扩袋，理论研究憩不鼙接进，遮一赣城傻蒸翔 有广瓣瓣发疑藩豢。各秘缀蹙捻素鼓本瓣纛耱熬会，不鞠谤富之窝绩塞 捡索技术鹃稳置参考，辩东方语言、陲摭馅语害索弓l 技米熬戮究，多语 种统一索弓i 和稳索技术的研究，以及为文本信息检索弓l 入自然语言理解 等成为了主要的发展方向。 捧爻文零镶意检索技术戆主要痤鬟之一鞫答系统豹磺蹇滏楚予 翅级蹬段，特潮是多数巾文越答系统仍然塔哭键字嚣酝豹方斌为主辘戳 蓠荤魏髅患撵联，对予篾杂酶复句提闼粒菇甏精确提取褡索黪阕题显褥 力不驮心。 本论文结合了正在开展的远程教育平台项目，在原有的艇有一定数 据存蘧分瓣处理戆力麴潮络昝袋系统豹繁鹅上爨舅骚究王髂，献全文硷 索为主熬文零绩惠捡索拽寒入手，赞对答疑系撬孛孛英文缝合翡文本为 主熬势熹，黠秘蘧与餐褰穗精迭费籍援势橱，撬逡舂蠡菇符饶懿答案疆 取算法，农不嘲显影噙效率静藩挺下建立越一个院传统关镳字甄配方式 有更高准确率和可用性的自动答疑模型，对中文自动问答系统作有益的 探讨积尝试。 主要磺究斑密： 1 。参考全文羧索技拳最鞭赣突藏采，套审焚定麓主戆痰弱臻凌下，疆突 多逶富绫一索葶| 疼鹣实溅，魄较谣典分橱法耱n g r a m 秘分中荚文文搂 的优劣，并提出相应解决方法。 2 词索引巾英文全文索等| 的模黧分拆，熬点薯寸论不同数据渊的规范哈， 索弓l 颈鹣缀织，中英文鬃警f 壤不同存继方式瓣滋鞍，钤对鑫囊答疑， 提密特定镞域捡索夔糕酝译努模墼。 3 ，臻突逡稷教商答疑过疆鹃闷签文本虢耱靛，提取英主襞偿惑，籍换或 适合建立索引的结构。 4 。自动铸疑模型的研究。焱全文检索引攀的基础上设计自动誉疑模型， 对鑫麓昝疑熬蠲遂努耩、餐怠硷索、僚惑摄取忍个步骤避行分撵设诗， 绘崮耪关算法。 3 华谢理 ：大学工学硕士学能论文 。4 谍题意义 本论文韵耩究内容属予计冀梳软件撩米的个羹要发麟方商。本文 对答疑耶蟪下於文本梭索趱耀避李亍了磷窕，谯全文检索写| 攀鹣支持下建 立秘动磐疑模型，并究成琢凝静设计与实现，其成柒可戳缀接戚霸予国 家娄懿大力笈疑翡诗葵飒逡狴教弯软耱警念串，其鸯较大熊社会竣蘧。 嚣簿，褥壤了令爨簿。魏程文本稳索寝瓣攘忑诗爨魏鑫然谮富骥辩； 推动其避一步发腥趣到抛姆弓l 玉的依用，凝脊很强的理论意义和霆大的 现实意义。 。5 论文匙容安簿 零文献邈疆教育袭鼹避耧孛挺篷酶瓣嚣袋爨笈，藩审蕊交全文捡索 进行有必的分析，研究，辨针对自动答燎环蟪建立横型，张成系统的设 诗彝实魏。本文 第一章婊论羧糕说骥了谍邋瓣骛荣秽戮熬建容。 篓二露夯缓了垒交羧索技零爱其最赫笈蕊。 第三章详细研究了戳谢綮弓l 为基础酾全文检索弓l 擎，镶数据源戴范 纯，索零 缀缀存镰窥疆熬群磐模蘩等方掰溉移转援，菸锌辩串荚文臻壤 下自动铃疑感用提出了改进方案。 第鞠章分辑了鼗鑫麓替疑琴壤下秘昝糖辫浆主要将蔹。 蓁轰鼙孛英文垒文检索弓 擎鸯基醚懿爨幼答聚系统戆建揆箨竣诗， 挺出了髑关然法。 第六帮自动答疑系统的蜜现。 最麟瓣零埝文酌送孪亍憩缝，势挺逡”f 一步工终黧点。 。6 本章小缝 本激分攒了论文盼硪懿鹜荣襁技术璐状，髓要夯缮了本谂文静磷究 内容、途越崽义以殿论文的鬻节安排。 4 第二牵全文捡辩投零麴务缨 繁二耄全文稳素技术蘸套缓 2 。 全文检索概述 全文羧鼗楚攒逶过文零戆冀聚繁爨糍懑褥翼文零餐潍懿赵爨，燕凌 毒爨大懿绩惑援囊模式。“镳瓣索零；”楚聚壤熬蒸叠文戆寨实疆装零，蔟 攘沦愚想蘧据瑷始文秘黪全文分簿残蒸零煞瓣接肇元，淤滚簿一攀元森 文档中出瓒懿次数、鞭鬻，黪瓣这蹙攒攘撼元缀绂褒效黝撼蠹续擒，以 反翔梭窳矮艨在静甄始文襁。 全文检索摭载霹娃，给海褰萼 建囊输黢漱索莓 黉诲黪裁。黎芎l 建立狳 莰赣天鹣楚添魏文整，撩礅戆蘧垒文素譬；，溪鸯索莓l 魏蕊索零；疼；絮零i 蠢谗除段浚入戆蓦奁诲淼令，蠢谗褥黻爨燎建美键字酶文档片凝，凝蔼 班怒麓瓣学逡算缀台，输出豹魑与鸯谗捆镣的文楼。 黧2 - 垒交嫒索瓿戮 2 2 巾文掌索攀l 与谰豢孽l 全文检索技零审，中文义零熬素雩i 方裟鉴婺骞字索葶l n - g r a m ) 拜3 辩 诲裳譬 鼹类。 2 。2 。l 字繁孳 攘零 字索礤l 怒撵越数摆搿巾懿义本耪料，不考虑文字熬懑义，绕开串文 嚣漤锯势戆矮嚣，嚣是羧长寝程寒建立索攀 。逸每寒，辫魂野鲶罄鬻富 夔诗攀懿露瓣壤蓬箍一g r a m 爱瓣予文零疆褰赣壤。簌文謇字蛰滚孛莲襞馥 取n 令字，馁褥鬟该文本瓣个长壤炎n 个字豹字籍察，猕为该文零浆 珏一g r a b 。瓣露一嚣凝为拽令警( 嫒n 誉怒撼文本熬妖霾) 瀚澈袋密强嚣予 5 华南理工人学： 学硕士学位论文 文本上、截取的连续n 个字构成一个n g r a m ，则当窗口从文本的开头以 s 字步长移到文本末尾时，把得到的该文本的所有n g r a m 记作g r a m ( n ， s ) “。 在全文检索中，ng r a m 的概念用于建立不基于词典的字索引。当n = 1 ，s = l 时，字索引就特殊化成常见的单字索引；当n 1 时，多采用覆盖 迭代切分的方法对文本材料建立索引。例如：若n = 2 ，s = l ，中文语句“文 本材料”则被切分为“文本”、“本材”、“材料”3 个语言成分，分别建立 索引。 广西i 再驴 j n 弋夕 图2 - 2n g r a m 方法对字符串切分 现今的字索引汉字全文检索系统多选用n = 1 的单汉字索引。单汉字 索引通常保存在倒排文件中。每个有检索意义的汉字，需要记录以下信 息：出现该字的文档总数，出现该字的文档号列表；在每个文档中该字 出现的位置总数，以及位置列表。检索时，针对检索串中每一个汉字， 在倒排文件中获得其所在文档号以及位置，进行文档号的交集运算并比 较位置差值，最终获得匹配的结果集。 字索引可以避开中文分词，节约了建立和维护词典的工作量，减少 了歧义性对检索的影响。字是汉语中最小的语法单位，因此是最彻底的 后组配式检索模式，可以在检索时达到任意的专指度和泛指度“”。由文 献 1 7 可知，就专指度而言，任何细小专门的事物或概念，只要有其名 称，就可以通过字的组配检索出来，就泛指度而言，单汉字系统具有字 面成族的能力，有较高的查全率。 但是，单汉字索引也有其固有的缺点，首先是存在“过度索引”的 问题，索引量大，占用的空间接近甚至超过原有文本，需要辅助以一定 的压缩算法。其次是检索时要进行位置组配，运算次数增多，效率低， 而且查准率不高。因此，字索引比较适合应用于涉及面广的通用型全文 检索系统中。 2 2 2 词索引技术 词索引是指对文字序列按词典意义上的最小单位进行分解成有意义 的词语。然后，把这些词语作为索引项，建立指向所在文本材料的反向 6 第：章全文检索技术的介绍 素雩l 。辩予中文焉言，运索弓l 营鑫要存关键字库襄蘩臻字辩，蓊耋存羧 需要建立索萼 熬褥语，瑟纛存藏索萼| 过稷巾霹激忽略戆诞浯( 鼹无其髂 意义的助词，叹词等) 。中文词语切分是词索引建立的一项擞键技术。我 国的计算机料学工作者在邋方面已经进行了大量的研究工作，并取得了 一定的成果。前向最大匹嬲，后向最大殴配，双向最大匹配，概率匹配 等分落雾法已经授灭实舔藏躅兰孛。检索辩，走对裣素事按穗霾兹方法 透露努谲处理，获褥谲谬或词语戆集合，蚨索弓l 孛捡素遗篡所在懿交饕， 再进行集合的逻辑运算。褥到匹配检索串的缩果。 词索弓i 优点在于索引胯占用空间小，检索速度快和查准率较高。同 时，词作为有意义的语言单俄，可以允许我们在建立索引的同时建立词 义豹关联，壤辩嚣义司关系，发爻司关系等，璜热捡索翦麓裁牲。著继 续雩l 天谣经等语言擎蕊裰念，菰霹墩在全文羧索之上捧一黧囊然语言理 解方面的探讨，其技术路线祷较好的延续性和可扩展往。 但是渤于汉语使用的戴杂性，词索引技术在词义消歧，涞登录词管 理和词典熊护等方面，还有很多不足之处。对于比词语更大的语言单位， 麴訇、段、篇落麓研究还处予初级酚段。谪索萼 技术适合废朔在专业牲 较强，专照谣汇较多，蜜潍率要求嘉懿全文捡索系统孛。 本文讨论盼全文检索系统采用词索霉l 技米。 2 3 信息检索模型 毽藜全文检索在蠹靛诗算撬文本捡索煞核，是检索挨鍪。捡素模鍪 是怼蕾惠梭索斡数学攮象，蔡建立主要包捺3 个方蟊斡蠢容；文档裙蘑 户查询串的表示，检索和聪黼的策略，结果的排序”“。最常见的几种文 本信息检索模型是布尔模激，向量空间模擞糊概率模型。 2 。3 1 布尔模墼 布尔横激”是一种简单而且常用的严格联配模型。它定义了个二值 变量集合浓袭示文档，这髓变量对应于文档巾的特征项。特 难项是指训 练文档集巾的词条和短语，翔果词条对文档裔贡献，则用l 淡示；对文 饕无贡麸，掰矮0 表示。检索游，鬏蹇臻户提交嚣检素条纬在文舞表示 串静逻辑关系楚否满足将撩索文楼分兔两个集合：匹酝集藕静莲配集。 稚尔横溅实现简单，稔綮速度快，在许多门户网站的榆潦系统中得 到应用。佩n 稚尔模型的文档寝示能力差，并鼠逻辑表达过予严格，可能 7 华南理工人学工学硕士学位论文 强菇一令黪铤戆不满是露怨鼹了其建特缝，麓法表这不弱麴溺条对文撞 贡献静差雾，往往会造成大整酶漏裣。p 一藏数模型h 1 是对布尔模型静扩 展，它克服了简单布尔模型贩配函数过于严格而导致漏捡率商的缺陷。 2 3 2 向量空间模型 向量空阗模型”1 褥文秘器佟由稆互猿立麓谗条缝鞫成溺条稳量( t ， t 2 - - ，t 。) ，对于每一词条t 。，都根据其在文档中的重要程度赋以一定的 权值w i 。谯样文档就映射成为以各个词条组成的n 维空间中的一个点， 对于所有文档和用户查询都w 映射到此文本向量空间。用户焱询和被检 索文档疆尝巍冬稳钕程度可嗣离量之闻鹣夹角寒度量，夹角越少穗强度越 离。设存愆户查谗请求，浚囱蠢q ( 谨。，疆。：，雾。) 表示，被稔索文搂竣 向量d ( w 。w 。，w 。) 表示，贝i j 两者之间楣似度的余弦计算公式为： 。k 一一 c o s ( q ，d ) 2 w d i + w q i 、( 聊f + w q i ) 、e ( w a i + g d i ) ( 2 1 ) i = 1 y l = fv ，* 这种表示模型考虑到了文档的内容特征，部分地克服了传统毒尔捡 索夔袋麓，滚避震户多徉弦骏及检索多样鬟：瓣嚣要，瑗毒一黧w e b 上翡检 索系统采用了这种检索模羹，并取得了较好的效果。向量空问模型的关 键在于特征掇取，当前对自然语言理解的研究还没能达到实用的阶段， 因此多数系统会使用基于统计学的机械方法提取文本特征。向量模型的 缺点是相似发计算量大，关键字的权重估计赡发大。 2 3 3 概率模型 同以上两种模型相比，概率模型“引是基于提问词在相关和非相关文 献中的分布檄率的，其基本恩怨就是根据关键字在相关文档中蹬现豹概 率窝无关文撼中密理豹壤枣寒裁錾该关键字熬双重。其诗葵公裁懿下： w i j 2l 0 9 2 【( f ，( r * f ) ) ，( ( n r ) l ( n - n - r + r ) ) 】( 2 2 ) 其中，w i j 是关键字i 在检索串j 中的权重，r 怒检索串i 所得到的相关文 档中包含关键字i 的文档数嫩，r 是与提问j 相关的文档总数，n 是用于 检索的所有文档中包含关键字i 的文档数薰，n 是系统包含的文档总数。 壤搴模型戆霞点采薅严掺熬数学理论为蒎攥，采矮穗关爱绩琢理， 可开发出瑗论上更为坚实斡方法。它酶主要缺点是增热存储和计算资源 的开销而且，参数估计难度较大。 3 第二章全文检索技术的介绍 2 4u n i c o d e 对中英文索引的影响 2 4 1 文本的编码 在对各种文本奉孝料建立索弓| 和检索蘧配的过程中，难免会逐舞不同 国家的文字和符号。英语，法谣等语言，以字母为基本单元组成词汇， 其字母秘簿合瓣数嚣缓少，一般只有死卡令到土嚣个，建萃字繁编玛是 以应付，例如麓名的h s c i i 编码。但是，中，e 1 ，韩等东方语京不以字 母为基本单元，而是拥有几千个甚至几万个不网的方块字，单字节编码 显然不足瑷应付。因魏缀多编确体系裁采翔了肇澉字节混合编褥，铡絮 g b k 编码，就采用了英文单字节，中日韩文字双字节的编码方式，可以表 示3 万多令字符。世界上语言文字耱类非鬻多，狳了控丁文字秘零方文 字之矫，还有阿拉伯文字，蒙古文字等等。这梯的一些单独编码方式往 往只能针对一种或者几种文字，很难涵蘸全世界所有语言的字符。 攀竣字节滠会编码熬使爰，增攘了壤程实瑷鼹疫。l 羹予编鹚不定长， 我们在程序中必须注意分清字符边界；在双字节或者多字节编码中，更 要考虑字符重鼗的闯题。例如：我们要在字符串a 中查找字符串b 。其中 a 力双字节编码的字符串，长发为8 个字节，8 。8 a 8 搏。a 。a 。a ，8 。，其中 a 。a ：，a 。a 。，a 。a 。，a ，a 。分别组成4 个文字。b 为另一双字节编码字符串，长度 是4 字慧，a 。a 。熊；码蕊涮中，8 。a 。，8 疆。也是合滚黟文字。若不在疆亭中 加以控制，则很可能得到字符串a 中含有字符串b 的错误结论。 a 陌a l a 2 1 a 3 a 4 , a 5 a 6 i a 7 a 司8 是| 。l j b 医a 2 a 五38 4a 翮5bi ! 图2 3 字符串的诶匹配 2 。4 。2u n i c o d e 的特点 为巍服这些不剩因素，1 9 9 1 年多家计冀扭公司设立嚣营剩的u n i c o d e 拄术委员会( u n ic o d et e c h n i c a lc o m m i t t e e ) ，目的在于推广一个全世 界通行的编码体制，把世界上所有的语言文字都涵盏进去。起初， u n i c o d e “”是一秘楚攀戆、霾定长度豹1 6 位编璐，可袭示6 5 5 3 6 今字 符。随着u n ic o d e 的发展，它和国际标准化组织i s o - 1 0 6 4 6 标准” 9 蔓扭辩瑗工大学工学硕士学髓论文 ( u n i v e f s a lc h a r a c t e rs e t 标准，u c s ) 逐步走囊一致。 u n i c o d e 熬2 。巷舔壤灏勰与u c s 使疆耀褥瓣字痒蠢字避。i s o 一1 0 6 4 6 字符码的谶蕊形式”4 1 ( 爵简称为u c s 一4 ) 淹3 2 个位，麓分戒4 个，位， 由左而右命名为群八位( g o c t e t ) 、面八傲( p o c t e t ) 、列八位( r - o c t e t ) 霸穆a 撼 = m ，则转步骤 3 ； 如果从被处理文本的尾部向前处理，匹配不成功时去除前面一个字， 就是逆向最大匹配检索法。如果同时使用两种最大匹配检索法，就构成 1 5 华南理工大学工学硕士学位论文 了双向最大匹配检索法。 3 2 2 1 最大概率法 最大概率法是噪声信道模型的分词方法。噪声信道模型是指信号序 列i 通过有干扰的信道之后变为信号序列0 ，且序列0 不等于序列i 。序 列0 代表分词前的文本，序列i 代表分词后的文本。 这个方法需要首先利用大量的文本材料生成语料库，并用统计的方 式得出同一词以不同的词性出现的生成概率和同一词不同词性概率的之 间的组合概率矩阵1 。这里应用连续隐马尔可夫模型( h m m ) “4 ”1 构造连 续概率密度函数，把一个具有词性词串中所有词的生成概率p g ( ) 的积乘 以所有连续词的词性转移概率p ( x ；，x 。十1 ) 的积作为词串的生成概率p ， 即： p ( i ) = 兀蹭丰兀p ( f ，f + 1 ) ( 3 1 ) 表3 1 最大概率法分词词库 词语词性概率 分外 b0 1 2 5 0 0 0 分外 d0 6 2 5 0 0 0 分外夺目 i1 0 0 0 0 0 0 分外事 n1 0 0 0 0 0 0 分为 v0 9 3 1 0 3 4 分委会j1 0 0 0 0 0 0 然后，列举己知序列i 的所有可能情况i 。，i 。，i 。，在已知每 种可能情况下出现0 的概率i 。( x = l n ) ，即己知p ( 0li 。) ，根据贝叶 斯公式求出当输出序列0 时，序列i 的所有可能情况i x 的概p ( i ，io ) 。 p ( i ；l0 ) = p ( i ；) p ( o ii ，) p ( 1 1 ) p ( o i ，1 )( 3 2 ) j i 而其中有最大值p ( i 。10 ) 的i n 是可能性最大的i ，也就是最后的分词 结果。 最大概率法的优点在于分词准确率较高，结合统计语料库能标注词 的词性，为进一步的语义理解和处理做好准备。 1 6 第三章全文检索引擎的研究 3 3 索引结构 3 3 1 数据源的结构化 全文检索的数据来自文本材料，但具体的来源就多种多样，可以是 t x t 文本文件，d o c 文档，p d f 文档，也可以是h t m l 文件和x m l 文件，甚 至还有可能数据库关系表的记录。为适应这些不同的格式，增强使用灵 活性，全文检索引擎规定了通用的数据源格式。在处理不同格式的文本 资料前，应该先将其转化为通用格式，再按统一的方式做建立索引处理。 我们的全文检索引擎中，对要建立索引的文本数据源以“文档一域 一关键字”3 个层次进行抽象。 文档( d o c u m e n t ) ：文档对应一个完整的数据源，例如一个t x t 文件， 在建立索引之后有其id 作为索引库的内部标识，也作为检索返回的结果： 域( f i e l d ) ：一个文档可以包含多个域，域包括域名和文本内容， 按内容特性对要建立索引的文本材料分类；检索的时候对指定的域进行 检索。按内容特性的不同，域可以对所包含的内容作建索引，整体保存 域内容等不同的处理。 关键字( t e r m ) ：域的内容包含个关键字。关键字包括内容，开始位 置，结束位置等信息。关键字对应索引项，在关键字层次上建立倒排索 引，指向所在文档。 图3 1 索引数据源格式 例如，我们要对文本文件a t x t 建立全文索引。则其结构化转换过 程为： 1 文件a t x t 对应一个文档，由其i d 标识： 2 文件的路径，标题，作者，内容对应各对应一个域，域名分别是p a t h ， t i t l e ，a u t h o r ，c o n t e n t ，这几个域所包含的内容都需要建立索引供检 索。而且，对于p a t h 域，其内容还需要做整体保存以便在检索到该文档 1 7 牮南理工丈学：i = 学硕士学位论文 是能够取得其存放路径谶而访问这一文件： 3 文件麴标题，作者和内容的文本经过分词等处理后，得到的词语序列 组成关键字链；鬣终在关键字屡次上爻a t x t 建立索弓l 。 3 3 。2 索雩| 瑗缝构 要建立索引的各类烈文本材料转换为通用的数据源格式，并对进行 分词预簸理螽，接下来全文检索孳l 擎就鼗对关键字建立镯舞 索孳 ，将关 键字指向所在文档。由于通用数据源结构中，文档与关键字之间存在域。 捡索在攘定的域中执行，因此，辑在域名不同豹楗同关键字我们将其看 作不同的关键字，建立不同的反向索引。索引项的结构如图3 2 所示。 n = d o c f r e q i = f r e q l j = f r e q 2 k = f r e q 3 圈3 2 索；l 顶络构 图3 - 2 中，索引项备个属性的含义分别为： t e r m t e x t 表示关键字内容； f i e l d n a m e 液示关键字所在的域名： d o c f r e q 表示该含有该关键字的文档数目； f r e q p o i n t e r 是频率籀锌，攥淘一令不定长戆“文毯一频率”结穗， 该结构袋示关键字在某个特定的文档中出现的次数。其中d 。( x = 1 n ) 为文档号，按从小到大的顺序排列，f r e q ；( x = 1 n ) 为关键字在文档d ， 中出现的次数； p o s t i o n p o i n t e i - 是位置指针，指向一个不定长的“文档一位置结构”， 该续梅表示关键字在菜令特定瓣文整孛爨现熬具髂整萋。文毽号_ j 整文毯 中关键字的位髯个数按“文档一频率”缁构列出的顺序隐含给出，p o s ； ( x = 1 i ) 表示狂关键字在文档中出现的位置值。 每个索弓l 壤已经蘩本包含了关键字在全文索雩| 库鬃静所有信怠。 利用关键字的索引项，可以检索出关键字所在的文档，缩合位嚣信息， l s 第三章全文检索引擎的研究 更可以作更高级的词组检索和范围检索。关键字的几个频率信息则可以 作为检索时计算权重，对匹配结果评分的依据。索引项的频率信息和位 置信息使用链接方式存储，有利于减少数据移动量，降低索引项的修改 代价。 3 3 3 索引项的组织 每个索引项对应着域内的一个关键字。文本材料的全文索引就由许 许多多的索引项组成，并且随着索引的文本材料增多，索引项的数目会 不断增长，索引项包含的信息也相应会发生变化。如何科学地组织索引 项，加快其查询和更新速度，成为影响全文检索引擎工作效率的关键因 素之一。 我们知道，全文检索中索引库空间占用量比较大的，不可能完全存 放在计算机的主存空间中，只能以文件或者数据库记录的形式保存在磁 盘存贮器。磁盘的i 0 操作，往往是检索速度的瓶颈所在。所以，为了 打破这一瓶颈，需要在尽量少磁盘i 0 的操作中准确地把相关索引项读 入主存处理。多数情况下，索引以文件形式保存会获得更高的效率，减 少i o 操作提高效率的就可以通过对索引文件采取直接访问的方式和合 理的预读入策略来实现。为此，我们在首先为索引项排序，然后对其建 立二级索引。 索引项以域名和关键字标识。排序的时候先按域名的字母序升序排 列，域名相同的按关键字的字母序升序排列。有序的索引项构成一个线 性列表。索引项的数量很多，如果以顺序方式查找索引项，评价需要查 找一半的索引项，必然效率很低。解决的办法是采用多级索引，为索引 项列表建立“索引的索引”。 1 9 华鸯理工大学工学颈士学位论文 二缀索弓 图3 3 索引项的组织 如图3 3 掰示，在列表中，每隔若予个索引斌抽取一个，构戏一级 索引，原有的索弓l 项列淡就相应变为二级索弓l 。一级索弓l 酶每个索弓l 项 后增加一个指针域，指向二级索引中相同的项。一级索引占用的空间较 ，l 、，套翁将冀颈瓷敖入烹存或者纛存孛，并可敬缝缓残适合快速囊技豹 数据结构，如h a s h 表，b + 树，多b 树“引等。在我们系统中采用h a s h 表 对应一级非稠密索引，劳预读二级索引傲顺序存储结合的方式。一级索 葶| 读入构造成h a s h 表，然后检索时首走扶h a s h 表中我翔指示索弓f 所在 区域的索引项，把该区域整块读入内存。如图3 3 ，若需骥取得2 0 0 号索 辱l 颈，罄先通过键值毙较褥鲡该索弓l 顼在级索辱| 孛1 2 8 号索弓| 颈豢示 的区域中，根据指针在二级索引文件中把1 2 8 号索引之厨的12 8 个索弓l 项读入内存查找。 3 4 索弓i 的存储 索弓l 最终要以文件的形式保存在磁掇中。为实现多语言统一索弓l ， 索引库中文件以u t f 8 编码格式保存。为了提高压缩率和读取速度，我们 会在索零| 瑗存耱之蔻箨数据疆式懿转换。 3 。4 1 几种数据类型 索引文件使用到几种基本数据类型，下面简单做介绍。 第三章全文检索引擎的研究 b y t e ：包含8 个二进制位，是最基本的数据类型，所有其他的数据 类型郝可以由b y t e 组成。 u i n t 3 2 u i n t 6 4 ：定长静无符号整数，前者包含4 个b y t e ，稀者包含 8 个b y t e 。写入和读取时先读写高位。 v i n t ”：交长正整数掺式。簿一字蕊戆最态位为l 辩表示下一字节 是否仍属于该整数，其余7 位表示整数假。 表3 - 2v i n t 类黧数值表 数值第一字节第二字节第三字节 o0 0 0 0 0 0 0 0 10 0 0 0 0 0 01 1 2 71 l l l l l l l 1 2 8l0 0 0 0 0 0 0 0 0 0 0 0 e ol 1 2 91 0 0 0 0 0 0 1o o o o o o o1 1 3 01 0 0 0 0 0 1 0o o o o o o ol 1 6 3 8 3l l l l l l l lo l l l l l l l 13 6 8 410 0 0 0 0 0 010 0 0 0 0 0 0 0 0 0 0 0 0 01 | 1 6 3 8 51 0 0 0 0 0 0 ll0 0 0 0 0 0 0 o 0 0 0 0 0 0l c h a r s ：字镣类型，使用u 1 、f 8 编码。 s t r i l a g ：字符串类怒，在索弓l 文件中，字符串类型由 组成，前者表明字符串的长度，后者是字符串内铎。”引 3 4 2 索引项的存储格式 疆筒读写速度和节省存储空闻是索弓 顼存储簸主要黪嚣标。褥且这 两方面的目标也是相辅相成的。单个索弓i 量占用的