分类： C/C++
2008-04-23 21:49:57
全文信息检索介绍及算法分析
作者：
一、摘要
本文主要介绍了全文信息检索的概念、应用领域、算法分类、技术难点和算法比较。及一款实现全文检索的数据结构和算法。
二、什么是全文数据库和全文信息检索
保存在数据库中的记录数据，从类型上可以分为两种。其一是结构化数据，象字符、日期、数值、货币等，这些数据都是具有有限长度或固定格式的数据；其二是非结构化数据，也叫全文数据，象简历、简介、论文等，这些数据都是以不定长、非固定格式保存的字符型数据。
现有的数据库系统，都是以结构化数据为检索的主要目标，因为实现相对简单。比如数值检索，可以建立一张排序好的索引表，以二分法实现查找，速度很快。但对于非结构化数据，即全文数据，要想实现检索，相对难度要大的很多了。
当然，你也许会说：“这个多简单呀，把全文数据读到内存，然后进行比较查找不就可以了？”。不错，的确是一个很朴素想法。不过最严重的问题是，如果数据库中有1万条，10万条，100万条记录的话，可以想象一下检索所消耗的时间了吧？！如果一个全文数据库系统，对一条检索命令的响应时间超过了半分钟，那么没有用户是能够容忍的了。
因此，全文检索的主要目的，就是实现对大容量的非结构化数据的快速查找。
三、应用领域
现在，随着计算机使用的越来越普及，数据的积累越来越多，全文检索的要求也就越来越迫切了。目前，主要的应用领域是：图书馆数据库、情报数据库、专利数据库、医药数据库、办公自动化、历史资料库、电子出版系统、等等。
四、算法和算法比较
目前，实现全文信息检索的算法有两大基本方案，词索引和字索引。
词索引，以单词为索引单位的检索算法。这个技术是全文检索技术的鼻祖（60年代，就已经有产品问世）。道理很简单，计算机是适合于英语语言环境的，而英语又是以单词为语言要素。说的更通俗一些，就是每个英文单词之间都有一个空格。因此，在对全文数据库建立索引的时候，按照单词划分建立索引，是即简单又自然的。我们国家最开始引入全文检索技术的时候，是汉化英文的数据库系统，因此也就自然使用了词索引技术。但由于中英文环境中语素的不同特点，使得中文必须要解决分词的问题。比如对一句话“我是中国人”，那么必须要切分出“我
是 中国 人”这样的单词形式。如果是人的大脑来进行分词判断，那真是太简单了，只要有小学二年级的中文水平，就足够了。但是，如果想让计算机能够进行分词，却非常困难。计算机分词的大致算法是：由文章切分出段落，由段落切分出句子，由句子切分出短语，然后查找词库，根据动词、连词、形容词再进行切分得到所有的单词。在某些情况下，计算机是根本无法正确进行分词的。下面是计算机自动分词所闹的笑话：
(1)我们要积极地主动作好计划生育工作
计算机愚蠢的分词结果：我们 要 积极 地主 动作 好
计划 生育 工作
评论：我胡汉三又回来啦
后果：检索“地主”的时候，产生误查结果
(2)吉林省长春市的人民
计算机愚蠢的分词结果：吉林 省长 春市 的 人民
评论：我知道了，吉林有个省长叫“春市”
后果：检索“吉林省”的时候，产生漏查结果
因此，词索引的技术难点是分词算法。Oracle
和 Notes
等汉化的数据库系统，虽然也都提供了部分全文检索功能，但都出现了这样或那样的问题。分词算法的提升空间还是有的，需要加入人工智能分析、上下文判断等技术。但还有一个致命的弱点，那就是对地名，人名的判断。
字索引，以汉语单字为索引单位的检索算法。这个也是我推荐的算法，较词索引更适合于中文环境。这也就是为什么英文汉化版的全文检索软件没有占领中国市场的主要原因。（目前，本土民族化的软件，比如手写板，汉字扫描识别，中文全文信息检索......还是比国外的同类产品领先很多的。）但字索引也不是没有缺点，最主要的问题是：
(1)、检索“华人”，会误查出“中华人民共和国”
(2)、检索中药“大黄”，会误查出“大黄缄”，“大黄麻”等完全不同概念的药品。而这些单词在英文中是不会出现错误的，因为根本就是不同的拼写。
字索引的多查错误，也是可以更正的。比如检索“大黄”的同时，也检索“大黄缄”，然后排除“大黄缄”的检索命中点，但这需要付出检索时间的代价。下表，是字、词索引方案各项性能的比较：
|
索引方式 给主人留下些什么吧！~~
|
