基于搜索引擎的中文关键字纠错系统引言在当今社会，信息的重要性日益凸显，如何有效的收集和传播成为了一项重要的技术。
作为信息收集的有效手段之一，搜索引擎越来越多的得到人们的关注，例如Google，百度等大型搜索引擎迅速成为IT产业中最炙手可热的公司。
搜索引擎面向社会各个阶层的大众用户，为了具有更好的交互性和可操作性，有必要为用户输入关键字提供纠错。
一个搜索引擎的关键字纠错能力，可以人性化的指导用户尽可能的搜索到需的信息，这在一定程度影响着搜索引擎服务质量的好坏。
基于搜索引擎的中文关键字纠错系统（以下简称作“纠错系统”）尝试纠正用户输入的中文关键字中可能存在的错误，并把可能的正确输入推荐给用户。
该系统能够发现用户输入中出现的选字错误，注音错误，字形错误以及其他的一些错误，并向用户推荐用户可能希望输入的正确关键字。
该系统能够有效的为用户输入关键字提供指导，并能纠正一些现有的搜索引擎不能纠正但是在使用中经常出现关键字错误。
1. 应用背景：进入信息时代，人类社会信息化进程加快，信息的重要性日益凸显，信息不仅成为与物质、能源同等重要的战略资源，而且获取信息也成了竞争角逐的重要手段。
在这样的背景下，Google[2]，百度[3]（图1）等大型搜索引擎为广大用户提供了一个搜索和交流信息的平台，并且迅速的崛起。
根据05年8月的统计数据，Google的月访问量为8040万人，位居全美网站第四位，而排名第一的是另一著名搜索引擎Yahoo（但Yahoo同时也提供其它服务）。
而在中国，百度以37%的市场份额成为全球最大的中文搜索引擎[1]。
图1：Google和百度作一个好的搜索引擎，不但需要有迅捷的搜索速度和全面的搜索内容，人性化的操作和指导也是搜索引擎服务质量好坏的重要标准。
因此，大多搜索引擎都提供了高级搜索的功能以及一些人性化的附加功能，自动纠错就是其中的一种（图2，图3）。
图2：百度的自动纠错功能图3：Google的自动纠错功能由于中文是一种表意文字，它在词的切分以及词义方面的复杂性使得很多中文系统的处理比其他拼音文字要复杂的多。
对于中文关键字的纠错也不例外，不考虑语义层次的信息（在语义层次上英文的规范化程度比中文要高很多，因此中文处理也要远远难于英文），英文纠错往往上只有简单的拼写错误，且不存在复杂的分词问题；而一个中文纠错系统需要面临的第一个问题就是中文分词问题。
在中文中，单字往往都会有它自身的意义，而任意几个中文汉字组合在一起可能都会有某种含义，而交集型歧义和组合型歧义更是会经常出现。
例如中文中“米兰球星”，在系统不考虑语义的情况下既可以正确的分词为“米兰/球星”，又可以分词为“米/兰球/星”（“兰球”是“篮球”的一种常见的不规范的使用方法，事实上，汉字使用的不规范也是中文纠错处理所面临的一大障碍）。
而在假设输入关键字有错误的前提下，分词的难度就更大了。
即便解决了分词问题，中文输入所可能出现的错误也是五花八门多种多样，例如拼音输入时的选字错误（将“篮球”误为“蓝球”），由发音的不规范而导致的注音错误（将“邹韬奋”误为“周韬奋”），由于形近字造成的字形错误（将“彬彬有礼”误为“杉杉有礼”）等。
因此，处理基于搜索引擎的中文关键字纠错，是一项很复杂的工作，虽然现有的很多搜索引擎（百度，Google等）都提供中文关键字纠错的功能，但是大部分还都停留在纠正简单错误的基础上，因此，为了能够提供更加人性化的服务，搜索引擎的中文关键字纠错功能还是有很大的改进空间的。
本文所介绍的基于搜索引擎的中文关键字纠错系统，采用将分词和纠错并行处理的方法，利用搜索引擎关键字的长度一般比较短的特点，尽可能全面地考虑用户可能需要查询的内容，并尝试纠正用户输入中可能存在的错误。
在报告的一下部分，首先介绍了纠错系统的概要设计，然后分模块介绍了系统的实现，以及工作成果，最后是对所做工作的总结和讨论。
2. 系统概要设计：纠错系统主要由训练模块，纠错模块和学习模块三个部分组成，如图4所示。
图4：纠错系统设计示意图训练模块使用一个语料库，训练成字符树的存储结构，供纠错模块查询。
并为保证字符树能够完整地读入内存，首先使用hash的方法将语料库中的词条分类。
纠错模块通过分词，纠错和查找字符树，对用户的输入进行处理，并对可能有错误的用户输入，给出系统的推荐词条。
学习模块通过记录并学习用户的输入，自动的为系统添加用户经常查询但系统中没有的词条，以增强系统的功能。
3. 系统实现：在这一部分将详细介绍纠错系统中各个功能模块的实现。
首先介绍一下系统的界面和使用方法。
纠错系统界面采用如图5所示的网页形式。
图5：纠错系统界面用户在对话框中输入想要查询的关键字，系统将分析用户输入的关键字，如果没有发现错误，则输出“关键字准确”；如果系统发现在用户输入的关键字中可能出现错误，则输出“您要查找的是不是：”+系统推荐词条。
3.1. 训练模块实现：训练模块的主要任务是使用语料库中的词条训练纠错模块可用的简单，快速的查找结构。
在纠错系统中，选用了字符树作为词条的查找结构。
图6：字符树纠错系统使用了课程提供的“人民日报语料库”[4]的一部分以及一些自己手工加入的词条。
训练模块首先对语料库进行必要的清理和处理，由于语料库是以分词的，因此系统直接去除其中的单字，并从中提取词条，形成一张词表。
这张词表一方面作为字符树的训练语料，另一方面也作为在纠错模块中对用户输入关键字进行分词时使用的分词词表。
在得到词表之后，使用一个汉字拼音对照表对词表中的每一个词条注音。
对于多音字，则需要另一个多音字对照词表，在系统中，对于在注音过程中发现的每一个多音字使用手工的方法注音，从而得到了多音字对照词表。
这个词表在纠错模块中为用户输入的关键字注音时也会用到。
然后，训练模块使用已注音的词表训练如图6所示的字符树。
注意到当语料库中的词条很多时，整棵字符树可能会很庞大，有可能不能直接读入内存。
因此系统使用hash的方法把词条分类，对每一类的词条训练一棵字符树。
在纠错模块需要在字符树中进行查找时，只需利用hash函数找到对应的字符树，并将其读入内存之后进行查找。
在纠错系统的实现过程中，使用简单的首字母的方式来最为hash函数，即首字母不同的词条在不同的字符树中。
对于hash函数可能的改进，将在最后的讨论中提及。
并且，由于选用的词库很小，为了方便起见，实际系统并没有把训练好的字符树写入磁盘，而是全部保留在内存中。
在对词表中的所有词条处理完毕之后，系统就得到了一组字符树。
在用户输入关键字并进行查询时，纠错模块可以通过对应的字符树快速准确的找到匹配的词条。
3.2. 纠错模块实现：纠错模块主要由分词，字符树查找，纠错三部分组成。
用户输入查询关键字后，纠错模块首先对关键字进行分词，并对每个非单字的词条在对应的字符树中查找匹配的词条，如果没有找到匹配的词条，则认为该词条可能出现错误，对该词条进行错误纠正之后重新在对应的字符树中查找。
最后，系统输出“关键字准确”或者输出系统推荐词条。
3.2.1. 分词在纠错系统中，分词是一个很重要，但也很难处理的步骤。
由于会产生交集型歧义（“网球/场”和“网/球场”）和组合型歧义（“（我）个人”和“三”个/人）等歧义，中文的分词问题本身就没有非常有效的解决方法。
而在纠错系统中，我们假设用户输入的关键字中可能带有错误，这样就更加大了分词的难度。
例如一个用户可能希望在搜索引擎中搜索“米兰球星”，但在输入关键字时误为“米篮球星”，那么分词系统就很难正确的处理这条输入。
事实上，在Google和百度上搜索“米篮球星”，更多的搜索到的是“篮球”相关的网页，但Google可以纠正该输入错误：“您是不是要找‘米兰球星’？”。
但大多数用户在使用搜索引擎时一般不会输入很长的关键字，并且用户常常会直接输入一个关键词条，或者分别输入多个词条；即使用户输入的是短语或句子，一般也只会包含很少的几个词。
针对这样的特点，在纠错系统中将分词与查找纠错合并在一起处理，使用递归的分词策略（图7）：1.如果字串是一个单字，则终止对它的分词；2.对于长度不超过系统分词词库中单个词条最大长度的字串，首先将整个字串当作一个词条，在对应的字符树中查找匹配，并尝试进行纠错；3.如果没有找到合适的匹配，则对字串中所有长度为2和3的子串在分词词库中查找匹配，如果找到匹配，则子串前面的部分和子串后面的部分（如果有）分别作为一个新的字串，回到第一步进行搜索。
匹配成功纠错匹配成功图7：递归的分词方法例如对“米篮球迷”这样一个输入字串，首先在系统中把整个字串作为一个词条进行查找，没有得到结果，而“米篮”在分词词库中找不到匹配的词条，而“篮球”和“球星”分别都能找到对应匹配的词条；而对“球星”前面的部分“米篮”纠正选字错误之后纠正为“米兰”。
因此，系统给出两种分词方案：“米/篮球/迷”和“米篮（米兰）/球星”。
3.2.2. 字符树查找字符树查找就是对于一个词条，使用注音字库，对其进行注音，然后根据在训练模块训练出的字符树中根据hash函数（按照系统的实现，即根据首字母）找到对应的字符树，沿注音所对应路径查找是否有匹配的词条。
在注音的过程中需要对多音字进行特别的处理。
当词条中遇到多音字时，使用训练模块中注音所使用的同样的多音字对应词表来对多音字进行注音。
3.3.3. 纠错纠错功能是纠错系统的核心功能，它将用户输入中可能存在的错误分为选字错误，注音错误和字形错误，并分别进行纠正。
3.3.3.1. 纠正选字错误选字错误是指用户输时输入了正确的拼音，但在选择拼音对应的汉字时发生了错误，例如将“澳大利亚”误为“奥大利亚”，将“炼钢”误为“练钢”。
产生选字错误的主要原因是用户在输入时的不留意（“练钢”）以及某些外来语及专有名词在音译时的多样性（“奥大利亚”）。
由于系统的训练模块是按照语料库中的词条的注音来训练字符树的，因此，系统在对应的字符树中寻找到注音匹配的路径后，如果找不到汉字匹配的词条，则寻找注音匹配但汉字不匹配的词条，作为纠正选字错误后的推荐词条。
例如“练钢”的注音为l-i-a-n-g-a-n-g，根据hash函数，在[L]对应的字符树中找到注音匹配的路径，但在这条路径对应的词条中找不到“练钢”这一词条，这时，系统认为用户的输入可能发生了选字错误，并将路径l-i-a-n-g-a-n-g对应的词条“炼钢”。
图8是在系统中输入“练钢”后，系统给出的结果：图8：纠错系统对“练钢”的纠错结果对于同样的错误，Google，没有给出推荐的纠错方案。
而百度对的纠错结果如图9所示：图9：百度对“练钢”的纠错结果其中涟钢是“涟源钢铁集团有限公司”的简写，在纠错系统的词库中没有这个词条。
图10是在系统中输入“米篮球星”后，系统给出的结果：图10：纠错系统对“米篮球星”的纠错结果对于同样的输入错误，百度没有给出推荐的纠错方案，而Google则可以正确的纠正（图11）：图11：Google对“米篮球星”的纠错结果3.3.3.2. 纠正注音错误由于我国地方方言的多样性和复杂性，某些方言的发音与标准普通话相差很大，一些使用方言较多的人群很难分清某些汉字的正确注音，如把“篮球”读作n-a-n-q-i-u，把“飞机”读成h-u-i-j-i。