2024年8月26日发(作者：鄞泽)
２０１０年第９期
计算机与现代化
ＪＩＳＵＡＮＪＩ ＹＵ ＸＩＡＮＤＡＩＨＵＡ 总第１８１期
文章编号：１００６－２４７５（２０１０）０９－００８５￣３
基于ｎ—ｇｒａｍ的字符串分割技术的算法实现
李文，洪亲，滕忠坚，石兆英，胡小丹，刘海博
（福建师范大学仓山校区物理与光电信息科技学院，福建福州３５０００７）
摘要：相似字符串的模糊查询一直是人们致力研究的方向，目前基于关键字的查询技术都是前缀匹配，无法查找到与搜
索字符串相似的结果。本文提出一种基于ｎ—ｇｒａｍ的字符串分割技术的算法，该技术是实现基于关键字的模糊查询技术
的基础，通过对数据集以及搜索关键字的字符串进行分割，利用编辑距离实现相似字符串的模糊查询，该技术在数据挖
掘以及论文抄袭等方面都有很重要的应用。
关键词：模糊查询；编辑距离；ｎ ｇｒａｍ；字符串分割
中图分类号：ＴＶ３９１．１ 文献标识码：Ａ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６－２４７５．２０１０．０９．０２４
Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ ｎ－ｇｒａｍ Ｓｔｒｉｎｇ Ｓｅｇｍｅｎｔａｔｉｏｎ
ＬＩ Ｗｅｎ，ＨＯＮＧ Ｑｉｎ，ＴＥＮＧ Ｚｈｏｎｇ￣ｉａｎ，ＳＨＩ Ｚｈａｏ—ｙｉｎｇ，ＨＵ Ｘｉａｏ—ｄａｎ，ＬＩＵ Ｈａｌ—ｂｏ
（Ｓｃｈｏｏｌ ｏｆ Ｐｈｙｓｉｃｓ ａｎｄ Ｏｐｔｏｅｌｅｃｔｍｎｉｃｓ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｆｕｊｉａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｍｉ￣Ｃａｎｇｓｈａｎ Ｃａｍｐｕｓ，Ｆｕｚｈｏｕ ３５０００７，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｒｅｃｅｎｔｌｙ，ｓｉｍｉｌａｒ ｓｔｒｉｎｇｓ ｏｆ ｆｕｚｚｙ ｑｕｅｒｉｅｓ ｈａｖｅ ｂｅｅｎ ｉｎｖｏｌｖｅｄ ｉｎ ｒｅｓｅａｒｃｈ，ａｎｄ ｍａｎｙ ｐｅｏｐｌｅ ａｒｅ ｗｏｒｋｉｎｇ ｏｎ ｉｔ ａｃｔｉｖｅｌｙ．
Ｔｈｅ ｃｕｒｒｅｎｔ ｋｅｙｗｏｒｄ—ｂａｓｅｄ ｑｕｅｒｙ ｔｅｃｈｎｉｑｕｅｓ ａｒｅ ｍｏｓｔｌｙ ｐｒｅｆｉｘ ｍａｔｃｈ．ｗｈｉｃｈ ｃｏｕｌｄ ｎｏｔ ｆｉｎｄ ｒｅｓｕｌｔｓ ｔｈａｔ ａｒｅ ｓｉｍｉｌａｒ ｗ ｔｈ ｔｈｅ ｑｕｅｒｙ
ｓｔｒｉｎｇｓ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｎ—ｇｒａｍ ｓｔｉｒｎｇ ｓｅｇｍｅｎｔａｔｉｏｎ，ｗｈｉｃｈ ｉｓ ｔｈｅ ｆｏｕｎｄａｔｉｏｎ ｆｏｒ ｆｕｚｚｙ ｑｕｅｒｙ．Ｄａｔａ ｓｅｔｓ，ａｓ
ｗｅｌｌ ａｓ ｔｈｅ ｋｅｙｗｏｒｄ ｓｔｒｉｎｇｓ ａｒｅ ｓｅｇｍｅｎｔｅｄ ｂｙ ｉｔ，ａｎｄ ｔｈｅｎ ｔｈｅ ｓｔｒｉｎｇ ｅｄｉｔ ｄｉｓｔａｎｃｅ ｉｓ ｕｓｅｄ ｔｏ ａｃｈｉｅｖｅ ｓｉｍｉｌａｒｆｕｚｚｙ ｑｕｅｒｙ，ｗｈｉｃｈ ｈａｓ
ｖｅｒｙ ｉｍｐｏｒｔａｎｔ印ｐＨｃａｔｉｏｎｓ ｉｎ ｄａｔａ ｃｌｅａｎｉｎｇ ａｎｄ ｃｌｏｎｉｎｇ ｐａｐｅｍ．
Ｋｅｙ ｗｏｒｄｓ：ｆｕｚｚｙ ｑｕｅｒｙ；ｅｄｉｔ ｄｉｓｔａｎｃｅ；ｎ—ｇｒａｍ；ｓｔｒｉｎｇ ｓｅｇｍｅｎｔａｔｉｏｎ
０ 引 言
其检索结果是“错误的输入，错误的输出”，对于用户
因记忆不清或误操作单词中的个别字母，甚至在有的
在信息膨胀的互联网时代，如何从海量的数据中
数据库中也有可能存在不正确的数据即“脏数据”。
快捷有效地管理和检索信息成为当前一项紧迫的研
在这些情况下，就可能无法得到想要的检索结果。原
究任务 ¨。
来对关键字的索引无法满足这种检索要求，为此本文
目前随着信息的增多，人们迫切地要求信息系统
提出一种全新的解决方法，首先对关键字进行分割处
能够支持相似字符串的模糊查询－２ Ｊ，传统的查询技
理，再对分割的片段字符串创建索引，然后通过对片
术，用户在进行查询的时候，有可能输人错误的单词，
段字符串进行检索实现模糊检索。为此本文提出一
中文里也经常出现模糊音、模糊字的现象。在这些情
种基于ｎ—ｇｒａｍ的字符串分割技术为实现基于关键字
况下，可能就无法得到想要的检索结果。尽管目前有
模糊检索提供基础。
些搜索引擎中加入了“您是否要找 书”这种功
能，也依然无法满足人们的检索要求。因此，怎样从
１基于关键字的查询
海量的数据中搜索出与查询字符串相类似的查询结
１．１传统的查询方法
果，是本文努力研究的方向 。
搜索引擎是一种典型的利用信息检索技术实现
基于关键字的查询技术是实现各种查询的基础，
的搜索平台，随着网络与通信技术的迅速发展，Ｗｅｂ
但目前基于关键字查询一般都是前缀精确匹配 Ｊ，
信息爆炸性的增长，已经成为一个巨大的海量信息空
收稿日期：２０１０－０５－２６ 。
作者简介：李文（１９８６一），女，山东济宁人，福建师范大学硕士研究生，研究方向：数据库；洪亲，女，高工，研究方向：数据库；
滕中坚，男，教授，研究方向：计算机图形图像处理及应用；石兆英，女，讲师，研究方向：数据结构；胡小丹，助教，硕士，研究
方向：计算机图形图像处理及应用；刘海博，女，助教，硕士，研究方向：嵌入式系统。
计算机与现代化 ２０１０年第９期
间，搜索引擎成为网络必不可少的工具 Ｊ。本文就
用户在输入一个错误的查询字符串，或者在数据库中
存在的一个有错误的记录，也都可以作为查询结果返
回给用户，而这些记录很有可能就是用户所需要的。
以搜索引擎为例来说明传统的查询方法。目前，互联
网上的大部分搜索引擎都是采用基于关键字的查询
技术，典型代表为Ｇｏｏｇｌｅ和百度 Ｊ。这些传统的基
于关键字的搜索引擎，往往都是对整个关键字创建索
引 ¨，这种查询方法往往只能做到完全前缀匹配 Ｊ，
在用户输入有误或者数据库中存在“脏数据”等情况
因此，这种新的检索技术将更加人性化、方便、灵活、
有效地满足人们实际的检索需求。
表１为在设定编辑距离为１的情况下，所能实现
的查询范围，其中Ｙ表示可以查询的情况，Ｎ表示不
下，可能就无法搜索到用户需要的信息。如图１所
可以。
示，为搜索引擎进行信息检索时的流程图 Ｊ，从图１
表１不同情况下可以实现的查询
中可以清晰地看出，传统的搜索技术，将用户输入的
查询字符串进行切词处理，而本文所研究的技术是对
条件 ＥＤ＝０ ＥＤ＝Ｉ ＥＤ＞ｌ
词再进行分割。
输入正确，无“脏数据” Ｙ Ｙ Ｎ
输人正确，有“脏数据” Ｙ Ｙ Ｎ
输入错误，无“脏数据” Ｙ Ｙ Ｎ
输入错误，有“脏数据” Ｎ Ｎ Ｎ
要实现上述这种相似字符串的模糊查询，首先将
整个数据集进行字符串分割，根据所得到的倒排列表
创建索引，然后将用户输人的查询字符串进行字符串
分割，再与索引结构中的字符串片段进行模糊匹配，
将查询结果按照匹配程度反馈给用户。
图１搜索引擎的查询过程流程图
综上所述，字符串的分割技术是本文创建索引，
１．２基于ｎ－ｇｒａｍ的字符串分割技术的查询方法
以及实现相似字符串的模糊查询技术的重要前提。
本文所研究的字符串分割技术，解决了传统的基
于关键字的查询技术的完全前缀匹配的问题。能够
２基于ｎ－ｇｒａｍ的字符串分割技术
在用户输入有误或数据库中存在“脏数据”的情况
２．１ ｎ－ｇｒａｍ技术
下，依然查找到用户需要的查询信息¨引。如图２所
示为采用基于ｎ—ｇｒａｍ的字符串分割技术的查询方法
ｎ—ｇｒａｍ的定义：设∑为一个字母表，Ｓ是一个由
的流程图。
中的字母组成的一个字符串。ＩＳｌ表示Ｓ的长度，Ｓ
［ｉ］是Ｓ中第ｉ个字母（ｉ从１开始），ｓ［ｉ，ｊ］是ｓ中从
第ｉ个到第ｊ个字母，ｎ是一个整数。
Ｓ中的一个ｎ—ｇｒａｍ的定义为一个（ｉ，ｇ）对，其中
ｇ表示Ｓ中从第ｉ个字母开始的一个ｎ—ｇｒａｍ，如Ｓ［ｉ，
ｉ＋ｎ一１］，Ｇ（Ｓ，ｎ）表示字符串ｓ中所有的ｎ—ｇｒａｍ的
集合，如Ｓ＝ｓｍｉｔｈ，ｎ＝３，则ｃ（ｓ，ｎ）＝｛（１，ｓｍｉ），（２，
ｍｉｔ），（３，ｉｔ｝１）｝¨ 。
综上所述，ｎ—ｇｒａｍ其实就是以一定的长度并按一
定的规律将一个字符串进行分割，分割成的每个ｎ－
图２基于ｎ—ｇｒａｍ的查询技术的查询流程图
ｇｒａｍｓ都是这个字符串的一个子串 引。在本文中，对
将两个串ｓ１和ｓ２之间编辑距离ＥＤ（ｓ１，ｓ２）定
多个字符串进行分割时，将空格以及其他特殊字符也
义为将串ｓ１转换成ｓ２，所需要的字符编辑操作（删
作为一般的字符进行处理。
除、插入、替换）的次数 ¨。该技术采用编辑距离来
２．２字符串分割算法实现
限定字符串的相似程度。如输入查找字串ｃｅｔ且限
该算法可以根据用户输入的分割字符串的长度
定检索出的内容与输人查找字串允许一个字符不同
来对数据集或查询字符串进行分割。算法的实现主
（即编辑距离ＥＤ＝１）时，如果数据库内容存在，那么
要采用两个结构体。一个是分割字符串的结构体。
可能检索出的结果是￥ｃｅｔ、，Ｉ：ｅｔ、ｃ ｔ、ｃｅ 、ｅｔ ，其
这个结构体主要的功能是，程序从源文件中读取到一
中 表示可以是空或任意一个字符。这样一来，即使
行数据，然后程序根据分割字符长度来分割该行数
２０１０年第９期 李文等：基于ｎ－ｇｒａｍ的字符串分割技术的算法实现
据，最后存放在这个结构体中。另一个是目标文件的
结构体，也就是说，将最终分割好的字符串以这个结
构体为单位进行存储。之所以采用结构体的方式进
行存储，是因为如果采用字符串的存储方式 那么每
次添加一个字符串都要重新再从头到尾读写一下目
标文件，这样会很浪费时间。
该算法包括４个主要函数：
（１）Ｉｎｓｅｒｔ Ｓｅｇｍｅｎｔａｔｉｏｎ Ｓｔｉｒｎｇ（参量ｃＤｅｓｔＦｉｌｅ、参
量ｃＰｔｒ、参量ｉｎｄｅｘ、参量ｉＳｅｑＬｅｎ）。该函数用来将一
个字符串ｃＰｔｒ分割好，转化为ｓｅｑＳｔｉｆｎｇ，并在目标文
件中查找是否已经存在这个字符串片段，如果有，则
删除；如果没有，则存人到目标文件中。
（２）Ｄｅａｌ Ｗｉｔｈ Ｉｎｓｅｒｔ Ｓｔｒｉｎｇ（参量ｃＤｅｓｔＦｉｌｅ、参量
ｓｅｑＳｔｒｉｎｇ、参量ｉＳｅｑＬｅｎ）。该函数调用函数（１），将
ｓｅｑＳｔｒｉｎｇ参数中的相关信息存人到目标文件中。
（３）Ｄｅａｌ Ｗｉｔｈ Ｓｅｇｍｅｎｔａｔｉｏｎ Ｓｔｒｉｎｇ（参量ｃＰｔｒ、参
量ｐＳｅｑＳｔｒｉｎｇ、参量ｉＳｅｑＬｅｎ、参量ｉｎｄｅｘ）。该函数是
将字符串ｃＳｔｒ，根据ｉＳｅｑＬｅｎ来分割，并将分割好的字
符串存入到ｐＳｅｑＳｔｒｉｎｇ中。
（４）Ｄｅａｌ Ｗｉｔｈ Ｐｒｏｃｅｓｓ（参量ｃＤｅｓｔＦｉｌｅ、参量ｃＳｒｃ—
Ｆｉｌｅ、参量ｉＳｅｑＬｅｎ）。该函数分是割字符串的主函数，
调用函数（３）和函数（２），从源文件ｃＳｒｃＦｉｌｅ中读取记
录，按照ｉＳｅｑＬｅｎ的值，即用户输人的子串长度进行
分割，最后将分割好的结果放入目标文件
ｃＤｅｓｔＦｉｌｅ中。
本算法使用ｃ语言编写，该算法主要实现过程
描述如下：
Ⅱ源文件存在
记录字符数＞０
目标文件若不存在，则新建一个
ＬＯＯＰ
Ｉｆ可以从源文件中读取一行数据
从源文件读取一行数据
Ｄｅａｌ Ｗｉｔｈ ｒｒｏｃｅｓｓ（目标文件名，源文件名，分割长度）
ｅｌｓｅ
ｂｒｅａｋ
ｅｌｓｅ打印结果，退出程序
如图３所示，为该算法的主要流程图，其中Ｓｅｑ—
Ｓｔｒｉｎｇ为声明的分割字符串的结构体。
２．３实验结果与分析
该算法的时间复杂度为Ｏ（ｎ／２），其中ｎ表示记
录数。该算法呈线性增长趋势，有较高的效率。表２
为利用该算法对包含不同记录数的ＴＸＴ文件，采用
不同ｎ—ｇｒａｍ进行分割时所用的时间比较，单位为ｍｓ，
运行环境为Ｐｅｎｔｉｕｍ（Ｒ）４，ＣＰＵ ３．ＯＯＧＨｚ，１Ｇ内存的
Ｗｉｎｄｏｗｓ ＸＰ系统。
图３字符串分割算法流程图
表２对不同记录数文件分割所使用的时间
记录数 ２－ｇｒａｍｓ ３－ｇｒａｍｓ ４一ｇｒａｍｓ
５ ｌｌＯｍｓ ８８ｍｓ ７２ｍｓ
ｌＯ ２６６ｍｓ ２３８ｍｓ ２Ｏ９ｍｓ
５０ ８８２ｍｓ ７２７ｍｓ ５８０ｍｓ
３ 结束语
相似字符串的模糊查询一直是人们努力研究的方
向，本文所提出的这种基于ｎ—ｇｒａｍ的字符串分割技
术，是实现相似字符串模糊查询的一项关键技术。本
文创新点在于可以通过字符串的分割，查找到与输人
字符串相似的查询结果，而非完全前缀匹配。而且，这
种技术的实现，对将来在数据挖掘、数据清洗、拼写检
查以及论文抄袭等方面都有很重要的应用ｌ】 。
参考文献：
［１］刘兴字．基于倒排索引的全文检索技术研究［Ｄ］．武汉：
华中科技大学硕士学位论文，２００４．
［２］崔维梅，范荣鹏．搜索引擎技术的现状和热点［Ｊ］．青年
记者，２００６（１６）：１１６．１ｌ７．
［３］ Ｍｏｔｏｄａ Ｈ，Ｙｏｓｈｉｄａ Ｋ．Ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｔｅｃｈｎｉｑｕｅｓ ｔＯ ｍａｋｅ
ｃｏｍｐｕｔｅｒｓ ｅａｓｉｅｒ ｔＯ ｕｓｅ［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒ－
ｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ．１９９７：１６２２－１６３１．
［４］ Ｋｕｋｉｃｈ Ｋ．Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ａｕｔｏｍａｔｉｃａｌｌｙ ｃｏｒｒｅｃｔｉｎｇ ｗｏｒｄｓ ｉｎ
ｔｅｘｔ［Ｊ］．ＡＣＭ Ｃｏｍｐｕｔ．Ｓｕｒｖ．，１９９２，２４（４）：３７７－４３９．
［５］ 冯冰洁，杨天奇．后缀树聚类算法在元搜索引擎中的应
用［Ｊ］．微计算机信息，２０１０（３）：２０４－２０６．
［６］ Ｂｅｈｍ Ａｌｅｘａｎｄｅｒ，ｊｉ Ｓｈｅｎｇｙｕｅ，Ｌｉ Ｃｈｅｎ，ｅｔ ａ１．Ｓｐａｃｅ－ｃｏｎｓｔｒａｉｎ．
ｅｄ ｇｒａｍ－ｂａｓｅｄ ｉｎｄｅ￣ｎｇ ｆｏｒ ｅｆｆｉｃｉｅｎｔ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｓｅａｒｃｈ
［Ｃ］／／ＩＣＤＥ．２００９：６０４－－６１５． （下转第９１页 ）
２０１０年第９期
靳建彬等：基于遗传算法的！！ 兰里兰竺 兰！ 查———————————
钟凛
－／－－－
鬈
蓑
藁量
示
神经网络收敛速度得到明显提商，
嚣
１ｃ【匕明
；
月
，
文献：
［１］ａＰ ｇｅｌｌｏ Ｅ，Ａｎｇｅｌ。Ａ ’
。Ａ Ｄ．ｃｏｏｐｅ碍ｔｉ
＿Ｃ唧咖 ＆
ｖｅ
ｂｔｅｉ０ｈ
ａｖ
ｉｏｒｓ ｉ
‘
ｎ ｍ
ｕ
…
ｍ－
ｒｏ
ｏｏｔ
－＿－‘
ｓｙｓｔｅｍｓ ｔｈｒｏｕｇｈ ｉｍｐｌｉｃｉｔ ｃｏｌｎｍｕｎｌｃ ‘ ‘
ｎ
‘Ｌ
［Ｊ］．
‘……
Ｒ０
ｂｏ
ｆｉ
。
ｃ
ｓ
龃ｄ
图３优化网络训
ＴＩ１ＡＩＮＬｒｄ，Ｅ ２８／５０，ＭＳＥ０．０００９８４８３５／０・００ｌ，ｂ龇哪
２．删
厶
。
ＴＲＡＩＮＬＭ，ｐｅｒｆｏｒｍａｎｃｅ ｇｏａｌ ｍｅｔ・
ｆ］４ 阎平凡，奎 张长水．人工神经网篁络与模拟进化算法【备与俣似堪 异 “Ｍ］ ～ ．ｊ匕
统在２８步之内就能够找到最优 缩 ，ｌＩ又似埋发 业
‘
ｆ １５
、
弓｝∈钤
．
张钹．神经网络中
ＢＰ
鼻 刚万 ｌ
算法的分析［ｊ］．模式识别
Ｌ ＪＪ’佚 ～
（３）：
１９１－
１９５．
耋 底腐蚀管道极限承载力的研冤Ｌ鬣 金
飞．Ｇ
Ａ－Ｂ
Ｐ
人
工神经网络应用于海 Ｊ Ｊ‘ 目博汗‘‘ ’
ｒ
『
１
９］
８
。
Ｎｔ！ｔ兴．ｇ 篓嚣
．北京：电子工业出版 ｏｏ４．
李钟侠．神经网络结构及兵秘但 化 堪 开
，
菇 算
Ⅲ
…
茹机器人协作中的
ｂ－
图４ １０ ４一＂，ｆｆ￣ ’
…
譬
快
１
５０ －１５８ ．
路径
’
ｍ阜
； 鬣 暑
达到期望目
［
…
１３
］李姚张蒂 ＰＩＤ￣Ｎ］［Ｊ Ｎ新Ｎ￣凇Ｎ， ２１１７，
和遗传算法的智能
计算
１５嚣（１５ ） ：６１０－０ １２．
差大小的隋熏 况下用节点删除法和扩张ｉ丢调讽佣疋。 噘
ｒ
ｒ
］丛爽．面向
１４
杰而向
Ｍａｔｌａｂ 工具箱的柙绘
箱的神经网络理论与应用
矬 司 门ｎ
．
［１１］Ｌｉ Ｃ，Ｌｕ Ｊ，Ｌｕ Ｙ・Ｅ
ｆ
ｉｆ
ｃ
ｉ
ｅｎｔ
ｍ
ｅｒ
ｇ
ｉｎ
ｇ ａ
ｎｄ
ｉｆ
ｈ
ｅ
ｒ
ｉ
ｎｇ
ａ１
ｇｏ
ｒｉ
ｔｈｍ
ｓ
接第８７页）
．
ｆ ｏｒ ａｐｐｒｏｘｉｍａｔｅ ｓｔｎｎｇ ８ｅａＩ ‘Ｉ
ｓ
ｔ
ｒｉ
ｎ
ｇ
８
ｅａｒ
ｃ
ｈｅ
ｃ
８
［
Ｌ ｕ …
ｃ
］
／
／
Ｉ
ｃ
ＤＥ２
—
０ｏ
８
：
Ｌｉ Ｇｕｏｌｉａｎｇ ，Ｆｅｎ
ｇ Ｊｉ
ａｎｈ ｕａ，
ｗａｎｇ Ｊｉ
ｉ
ａｎ￣
ａｎｙ
ｏｎｇ，ｅｔ ａ
’・
ｌ Ａｎ
ｅｎｅ
一
ｃ－
．
—
…
…
ｔ ｉｖｅ ａ ｎｄ
ｖ ｅｒｓａｔ
ｉ
ｌｅｋ
ｋ
ｅｖｗ
眦 ｅ
ｎ
ｇｉｎ
ｅ
ｏｎｎｅｔ
ｅｒｏ
ｇｃｎ
ｕｕ
￣
．
［１２］Ｘｉａｏ Ｃｈｕａｎ，Ｗａｎｇ Ｗｅｊ
Ｌ
ｉｎ Ｘ ｕｅｍ
ｉｎ ．Ｅ
ｄ
－
Ｊｏ
ｉ
ｎ：Ａ
ｎ
ｅｆｆ ｉｃｉｅ
ｎ
ｔ
，
ｄａｔａ ｓ０ｕ脚
，ｍ
［Ｃ］
ｃ
／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈ
ｅ
。
ｖＬＤ
Ｂ
Ｅ
ｎ
ｄ
。
ｗｍ
“～…
ｅｎ
ｔ．
．
．
ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｉｍｉｌａｒｉｔｙ ｊｏｍｓ ｗｌｔｎ ｅｑ Ⅱ
ｅ
ｄ
ｉ
ｓｔ
ａ
ｎｃｅ
ｎ
ｃ。ＩＩｓ
ｗ¨……‘
ｎｔ
ｓ
２）：１４
５２
－索１４
５５
术．
『Ｃ１／／ＶＬＤＢ．２００８：１３１－１４０．
ｆ］
８
．
ｒ １
陆宜梅．
Ｗｅｂ
搜索技术现状分析Ｌ
搜
技
现状分析［Ｊ］．沈阳大学学报，
Ｊ Ｊ・ ｐ曙人手子 ’
ｍ１ ＲＡ，ＦｉｓｅｈｅｒＭ Ｊ，Ｔｈｅ ｓｔｉｒｎｇ－ｔｏ。ｓｔｒｉｎｇ ｃｏ 帆ｐ
［９］ 之关键字查询［ＥＢ／ＯＬ］ＥＢ／ＯＬ］．一
．
ｈｔｔｐ：／。。／ｗｗｗ．
咿 ‘
， 删４
＿一一
．‘
：［１ ４：Ｙ］ｌⅪｅｍ ｕ［Ｊｒ］ｈ．ｌＡ】ａＣｎＭ，ｗ‰ “，１９ａ７ｎｇ４，ｗ２１ｅ（ｉ１，）“： ｎ１６ｘ８－ｕ１ｅ７ｆ３ｒＩｉ．ｎ，昌ｅｔ ａ１．雎ｃｉｅｎｔ ｓｉｍｃｉｌｓ
．
三
ｉｔｖ ｊｏｉｎｓ ｆｏｒ ｎｅａｒ ｄｕｐｌｉｃａｔｅ ｄｅｔｅｃ【 ｕ Ｌ Ｊ川………”。
。
Ｇｕｏｌｉｎａ
ｇ 一ｅｔ
ａｔ．Ｅｔｈｅｌ
ｅｎ
ｔ ｌｎｔ
ｅ
ｒａｃ
ｕ
ｖｅ
…
…
Ｊ
ｆ
ｉ Ｓｈｅｎ
ｇｙｕｅ，Ｌｉ
ｃ，
ｕｚｚｙ ｋｅｙｗｏｒｄ ｓｅａｒｃｈ【ｃ］
『ｃ
／／Ｉｎｔｅｍａｔｉ
０ｎ
０ｎａ１
ａｌ
ｗ０ｎｕ ｗ儿Ｊ
Ｗ０ｄ
ｄＷｉｄ
ｅ
…
ｗ
ｅｂ
2024年8月26日发(作者：鄞泽)
２０１０年第９期
计算机与现代化
ＪＩＳＵＡＮＪＩ ＹＵ ＸＩＡＮＤＡＩＨＵＡ 总第１８１期
文章编号：１００６－２４７５（２０１０）０９－００８５￣３
基于ｎ—ｇｒａｍ的字符串分割技术的算法实现
李文，洪亲，滕忠坚，石兆英，胡小丹，刘海博
（福建师范大学仓山校区物理与光电信息科技学院，福建福州３５０００７）
摘要：相似字符串的模糊查询一直是人们致力研究的方向，目前基于关键字的查询技术都是前缀匹配，无法查找到与搜
索字符串相似的结果。本文提出一种基于ｎ—ｇｒａｍ的字符串分割技术的算法，该技术是实现基于关键字的模糊查询技术
的基础，通过对数据集以及搜索关键字的字符串进行分割，利用编辑距离实现相似字符串的模糊查询，该技术在数据挖
掘以及论文抄袭等方面都有很重要的应用。
关键词：模糊查询；编辑距离；ｎ ｇｒａｍ；字符串分割
中图分类号：ＴＶ３９１．１ 文献标识码：Ａ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６－２４７５．２０１０．０９．０２４
Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ ｎ－ｇｒａｍ Ｓｔｒｉｎｇ Ｓｅｇｍｅｎｔａｔｉｏｎ
ＬＩ Ｗｅｎ，ＨＯＮＧ Ｑｉｎ，ＴＥＮＧ Ｚｈｏｎｇ￣ｉａｎ，ＳＨＩ Ｚｈａｏ—ｙｉｎｇ，ＨＵ Ｘｉａｏ—ｄａｎ，ＬＩＵ Ｈａｌ—ｂｏ
（Ｓｃｈｏｏｌ ｏｆ Ｐｈｙｓｉｃｓ ａｎｄ Ｏｐｔｏｅｌｅｃｔｍｎｉｃｓ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｆｕｊｉａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｍｉ￣Ｃａｎｇｓｈａｎ Ｃａｍｐｕｓ，Ｆｕｚｈｏｕ ３５０００７，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｒｅｃｅｎｔｌｙ，ｓｉｍｉｌａｒ ｓｔｒｉｎｇｓ ｏｆ ｆｕｚｚｙ ｑｕｅｒｉｅｓ ｈａｖｅ ｂｅｅｎ ｉｎｖｏｌｖｅｄ ｉｎ ｒｅｓｅａｒｃｈ，ａｎｄ ｍａｎｙ ｐｅｏｐｌｅ ａｒｅ ｗｏｒｋｉｎｇ ｏｎ ｉｔ ａｃｔｉｖｅｌｙ．
Ｔｈｅ ｃｕｒｒｅｎｔ ｋｅｙｗｏｒｄ—ｂａｓｅｄ ｑｕｅｒｙ ｔｅｃｈｎｉｑｕｅｓ ａｒｅ ｍｏｓｔｌｙ ｐｒｅｆｉｘ ｍａｔｃｈ．ｗｈｉｃｈ ｃｏｕｌｄ ｎｏｔ ｆｉｎｄ ｒｅｓｕｌｔｓ ｔｈａｔ ａｒｅ ｓｉｍｉｌａｒ ｗ ｔｈ ｔｈｅ ｑｕｅｒｙ
ｓｔｒｉｎｇｓ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｎ—ｇｒａｍ ｓｔｉｒｎｇ ｓｅｇｍｅｎｔａｔｉｏｎ，ｗｈｉｃｈ ｉｓ ｔｈｅ ｆｏｕｎｄａｔｉｏｎ ｆｏｒ ｆｕｚｚｙ ｑｕｅｒｙ．Ｄａｔａ ｓｅｔｓ，ａｓ
ｗｅｌｌ ａｓ ｔｈｅ ｋｅｙｗｏｒｄ ｓｔｒｉｎｇｓ ａｒｅ ｓｅｇｍｅｎｔｅｄ ｂｙ ｉｔ，ａｎｄ ｔｈｅｎ ｔｈｅ ｓｔｒｉｎｇ ｅｄｉｔ ｄｉｓｔａｎｃｅ ｉｓ ｕｓｅｄ ｔｏ ａｃｈｉｅｖｅ ｓｉｍｉｌａｒｆｕｚｚｙ ｑｕｅｒｙ，ｗｈｉｃｈ ｈａｓ
ｖｅｒｙ ｉｍｐｏｒｔａｎｔ印ｐＨｃａｔｉｏｎｓ ｉｎ ｄａｔａ ｃｌｅａｎｉｎｇ ａｎｄ ｃｌｏｎｉｎｇ ｐａｐｅｍ．
Ｋｅｙ ｗｏｒｄｓ：ｆｕｚｚｙ ｑｕｅｒｙ；ｅｄｉｔ ｄｉｓｔａｎｃｅ；ｎ—ｇｒａｍ；ｓｔｒｉｎｇ ｓｅｇｍｅｎｔａｔｉｏｎ
０ 引 言
其检索结果是“错误的输入，错误的输出”，对于用户
因记忆不清或误操作单词中的个别字母，甚至在有的
在信息膨胀的互联网时代，如何从海量的数据中
数据库中也有可能存在不正确的数据即“脏数据”。
快捷有效地管理和检索信息成为当前一项紧迫的研
在这些情况下，就可能无法得到想要的检索结果。原
究任务 ¨。
来对关键字的索引无法满足这种检索要求，为此本文
目前随着信息的增多，人们迫切地要求信息系统
提出一种全新的解决方法，首先对关键字进行分割处
能够支持相似字符串的模糊查询－２ Ｊ，传统的查询技
理，再对分割的片段字符串创建索引，然后通过对片
术，用户在进行查询的时候，有可能输人错误的单词，
段字符串进行检索实现模糊检索。为此本文提出一
中文里也经常出现模糊音、模糊字的现象。在这些情
种基于ｎ—ｇｒａｍ的字符串分割技术为实现基于关键字
况下，可能就无法得到想要的检索结果。尽管目前有
模糊检索提供基础。
些搜索引擎中加入了“您是否要找 书”这种功
能，也依然无法满足人们的检索要求。因此，怎样从
１基于关键字的查询
海量的数据中搜索出与查询字符串相类似的查询结
１．１传统的查询方法
果，是本文努力研究的方向 。
搜索引擎是一种典型的利用信息检索技术实现
基于关键字的查询技术是实现各种查询的基础，
的搜索平台，随着网络与通信技术的迅速发展，Ｗｅｂ
但目前基于关键字查询一般都是前缀精确匹配 Ｊ，
信息爆炸性的增长，已经成为一个巨大的海量信息空
收稿日期：２０１０－０５－２６ 。
作者简介：李文（１９８６一），女，山东济宁人，福建师范大学硕士研究生，研究方向：数据库；洪亲，女，高工，研究方向：数据库；
滕中坚，男，教授，研究方向：计算机图形图像处理及应用；石兆英，女，讲师，研究方向：数据结构；胡小丹，助教，硕士，研究
方向：计算机图形图像处理及应用；刘海博，女，助教，硕士，研究方向：嵌入式系统。
计算机与现代化 ２０１０年第９期
间，搜索引擎成为网络必不可少的工具 Ｊ。本文就
用户在输入一个错误的查询字符串，或者在数据库中
存在的一个有错误的记录，也都可以作为查询结果返
回给用户，而这些记录很有可能就是用户所需要的。
以搜索引擎为例来说明传统的查询方法。目前，互联
网上的大部分搜索引擎都是采用基于关键字的查询
技术，典型代表为Ｇｏｏｇｌｅ和百度 Ｊ。这些传统的基
于关键字的搜索引擎，往往都是对整个关键字创建索
引 ¨，这种查询方法往往只能做到完全前缀匹配 Ｊ，
在用户输入有误或者数据库中存在“脏数据”等情况
因此，这种新的检索技术将更加人性化、方便、灵活、
有效地满足人们实际的检索需求。
表１为在设定编辑距离为１的情况下，所能实现
的查询范围，其中Ｙ表示可以查询的情况，Ｎ表示不
下，可能就无法搜索到用户需要的信息。如图１所
可以。
示，为搜索引擎进行信息检索时的流程图 Ｊ，从图１
表１不同情况下可以实现的查询
中可以清晰地看出，传统的搜索技术，将用户输入的
查询字符串进行切词处理，而本文所研究的技术是对
条件 ＥＤ＝０ ＥＤ＝Ｉ ＥＤ＞ｌ
词再进行分割。
输入正确，无“脏数据” Ｙ Ｙ Ｎ
输人正确，有“脏数据” Ｙ Ｙ Ｎ
输入错误，无“脏数据” Ｙ Ｙ Ｎ
输入错误，有“脏数据” Ｎ Ｎ Ｎ
要实现上述这种相似字符串的模糊查询，首先将
整个数据集进行字符串分割，根据所得到的倒排列表
创建索引，然后将用户输人的查询字符串进行字符串
分割，再与索引结构中的字符串片段进行模糊匹配，
将查询结果按照匹配程度反馈给用户。
图１搜索引擎的查询过程流程图
综上所述，字符串的分割技术是本文创建索引，
１．２基于ｎ－ｇｒａｍ的字符串分割技术的查询方法
以及实现相似字符串的模糊查询技术的重要前提。
本文所研究的字符串分割技术，解决了传统的基
于关键字的查询技术的完全前缀匹配的问题。能够
２基于ｎ－ｇｒａｍ的字符串分割技术
在用户输入有误或数据库中存在“脏数据”的情况
２．１ ｎ－ｇｒａｍ技术
下，依然查找到用户需要的查询信息¨引。如图２所
示为采用基于ｎ—ｇｒａｍ的字符串分割技术的查询方法
ｎ—ｇｒａｍ的定义：设∑为一个字母表，Ｓ是一个由
的流程图。
中的字母组成的一个字符串。ＩＳｌ表示Ｓ的长度，Ｓ
［ｉ］是Ｓ中第ｉ个字母（ｉ从１开始），ｓ［ｉ，ｊ］是ｓ中从
第ｉ个到第ｊ个字母，ｎ是一个整数。
Ｓ中的一个ｎ—ｇｒａｍ的定义为一个（ｉ，ｇ）对，其中
ｇ表示Ｓ中从第ｉ个字母开始的一个ｎ—ｇｒａｍ，如Ｓ［ｉ，
ｉ＋ｎ一１］，Ｇ（Ｓ，ｎ）表示字符串ｓ中所有的ｎ—ｇｒａｍ的
集合，如Ｓ＝ｓｍｉｔｈ，ｎ＝３，则ｃ（ｓ，ｎ）＝｛（１，ｓｍｉ），（２，
ｍｉｔ），（３，ｉｔ｝１）｝¨ 。
综上所述，ｎ—ｇｒａｍ其实就是以一定的长度并按一
定的规律将一个字符串进行分割，分割成的每个ｎ－
图２基于ｎ—ｇｒａｍ的查询技术的查询流程图
ｇｒａｍｓ都是这个字符串的一个子串 引。在本文中，对
将两个串ｓ１和ｓ２之间编辑距离ＥＤ（ｓ１，ｓ２）定
多个字符串进行分割时，将空格以及其他特殊字符也
义为将串ｓ１转换成ｓ２，所需要的字符编辑操作（删
作为一般的字符进行处理。
除、插入、替换）的次数 ¨。该技术采用编辑距离来
２．２字符串分割算法实现
限定字符串的相似程度。如输入查找字串ｃｅｔ且限
该算法可以根据用户输入的分割字符串的长度
定检索出的内容与输人查找字串允许一个字符不同
来对数据集或查询字符串进行分割。算法的实现主
（即编辑距离ＥＤ＝１）时，如果数据库内容存在，那么
要采用两个结构体。一个是分割字符串的结构体。
可能检索出的结果是￥ｃｅｔ、，Ｉ：ｅｔ、ｃ ｔ、ｃｅ 、ｅｔ ，其
这个结构体主要的功能是，程序从源文件中读取到一
中 表示可以是空或任意一个字符。这样一来，即使
行数据，然后程序根据分割字符长度来分割该行数
２０１０年第９期 李文等：基于ｎ－ｇｒａｍ的字符串分割技术的算法实现
据，最后存放在这个结构体中。另一个是目标文件的
结构体，也就是说，将最终分割好的字符串以这个结
构体为单位进行存储。之所以采用结构体的方式进
行存储，是因为如果采用字符串的存储方式 那么每
次添加一个字符串都要重新再从头到尾读写一下目
标文件，这样会很浪费时间。
该算法包括４个主要函数：
（１）Ｉｎｓｅｒｔ Ｓｅｇｍｅｎｔａｔｉｏｎ Ｓｔｉｒｎｇ（参量ｃＤｅｓｔＦｉｌｅ、参
量ｃＰｔｒ、参量ｉｎｄｅｘ、参量ｉＳｅｑＬｅｎ）。该函数用来将一
个字符串ｃＰｔｒ分割好，转化为ｓｅｑＳｔｉｆｎｇ，并在目标文
件中查找是否已经存在这个字符串片段，如果有，则
删除；如果没有，则存人到目标文件中。
（２）Ｄｅａｌ Ｗｉｔｈ Ｉｎｓｅｒｔ Ｓｔｒｉｎｇ（参量ｃＤｅｓｔＦｉｌｅ、参量
ｓｅｑＳｔｒｉｎｇ、参量ｉＳｅｑＬｅｎ）。该函数调用函数（１），将
ｓｅｑＳｔｒｉｎｇ参数中的相关信息存人到目标文件中。
（３）Ｄｅａｌ Ｗｉｔｈ Ｓｅｇｍｅｎｔａｔｉｏｎ Ｓｔｒｉｎｇ（参量ｃＰｔｒ、参
量ｐＳｅｑＳｔｒｉｎｇ、参量ｉＳｅｑＬｅｎ、参量ｉｎｄｅｘ）。该函数是
将字符串ｃＳｔｒ，根据ｉＳｅｑＬｅｎ来分割，并将分割好的字
符串存入到ｐＳｅｑＳｔｒｉｎｇ中。
（４）Ｄｅａｌ Ｗｉｔｈ Ｐｒｏｃｅｓｓ（参量ｃＤｅｓｔＦｉｌｅ、参量ｃＳｒｃ—
Ｆｉｌｅ、参量ｉＳｅｑＬｅｎ）。该函数分是割字符串的主函数，
调用函数（３）和函数（２），从源文件ｃＳｒｃＦｉｌｅ中读取记
录，按照ｉＳｅｑＬｅｎ的值，即用户输人的子串长度进行
分割，最后将分割好的结果放入目标文件
ｃＤｅｓｔＦｉｌｅ中。
本算法使用ｃ语言编写，该算法主要实现过程
描述如下：
Ⅱ源文件存在
记录字符数＞０
目标文件若不存在，则新建一个
ＬＯＯＰ
Ｉｆ可以从源文件中读取一行数据
从源文件读取一行数据
Ｄｅａｌ Ｗｉｔｈ ｒｒｏｃｅｓｓ（目标文件名，源文件名，分割长度）
ｅｌｓｅ
ｂｒｅａｋ
ｅｌｓｅ打印结果，退出程序
如图３所示，为该算法的主要流程图，其中Ｓｅｑ—
Ｓｔｒｉｎｇ为声明的分割字符串的结构体。
２．３实验结果与分析
该算法的时间复杂度为Ｏ（ｎ／２），其中ｎ表示记
录数。该算法呈线性增长趋势，有较高的效率。表２
为利用该算法对包含不同记录数的ＴＸＴ文件，采用
不同ｎ—ｇｒａｍ进行分割时所用的时间比较，单位为ｍｓ，
运行环境为Ｐｅｎｔｉｕｍ（Ｒ）４，ＣＰＵ ３．ＯＯＧＨｚ，１Ｇ内存的
Ｗｉｎｄｏｗｓ ＸＰ系统。
图３字符串分割算法流程图
表２对不同记录数文件分割所使用的时间
记录数 ２－ｇｒａｍｓ ３－ｇｒａｍｓ ４一ｇｒａｍｓ
５ ｌｌＯｍｓ ８８ｍｓ ７２ｍｓ
ｌＯ ２６６ｍｓ ２３８ｍｓ ２Ｏ９ｍｓ
５０ ８８２ｍｓ ７２７ｍｓ ５８０ｍｓ
３ 结束语
相似字符串的模糊查询一直是人们努力研究的方
向，本文所提出的这种基于ｎ—ｇｒａｍ的字符串分割技
术，是实现相似字符串模糊查询的一项关键技术。本
文创新点在于可以通过字符串的分割，查找到与输人
字符串相似的查询结果，而非完全前缀匹配。而且，这
种技术的实现，对将来在数据挖掘、数据清洗、拼写检
查以及论文抄袭等方面都有很重要的应用ｌ】 。
参考文献：
［１］刘兴字．基于倒排索引的全文检索技术研究［Ｄ］．武汉：
华中科技大学硕士学位论文，２００４．
［２］崔维梅，范荣鹏．搜索引擎技术的现状和热点［Ｊ］．青年
记者，２００６（１６）：１１６．１ｌ７．
［３］ Ｍｏｔｏｄａ Ｈ，Ｙｏｓｈｉｄａ Ｋ．Ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｔｅｃｈｎｉｑｕｅｓ ｔＯ ｍａｋｅ
ｃｏｍｐｕｔｅｒｓ ｅａｓｉｅｒ ｔＯ ｕｓｅ［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒ－
ｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ．１９９７：１６２２－１６３１．
［４］ Ｋｕｋｉｃｈ Ｋ．Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ａｕｔｏｍａｔｉｃａｌｌｙ ｃｏｒｒｅｃｔｉｎｇ ｗｏｒｄｓ ｉｎ
ｔｅｘｔ［Ｊ］．ＡＣＭ Ｃｏｍｐｕｔ．Ｓｕｒｖ．，１９９２，２４（４）：３７７－４３９．
［５］ 冯冰洁，杨天奇．后缀树聚类算法在元搜索引擎中的应
用［Ｊ］．微计算机信息，２０１０（３）：２０４－２０６．
［６］ Ｂｅｈｍ Ａｌｅｘａｎｄｅｒ，ｊｉ Ｓｈｅｎｇｙｕｅ，Ｌｉ Ｃｈｅｎ，ｅｔ ａ１．Ｓｐａｃｅ－ｃｏｎｓｔｒａｉｎ．
ｅｄ ｇｒａｍ－ｂａｓｅｄ ｉｎｄｅ￣ｎｇ ｆｏｒ ｅｆｆｉｃｉｅｎｔ ａｐｐｒｏｘｉｍａｔｅ ｓｔｒｉｎｇ ｓｅａｒｃｈ
［Ｃ］／／ＩＣＤＥ．２００９：６０４－－６１５． （下转第９１页 ）
２０１０年第９期
靳建彬等：基于遗传算法的！！ 兰里兰竺 兰！ 查———————————
钟凛
－／－－－
鬈
蓑
藁量
示
神经网络收敛速度得到明显提商，
嚣
１ｃ【匕明
；
月
，
文献：
［１］ａＰ ｇｅｌｌｏ Ｅ，Ａｎｇｅｌ。Ａ ’
。Ａ Ｄ．ｃｏｏｐｅ碍ｔｉ
＿Ｃ唧咖 ＆
ｖｅ
ｂｔｅｉ０ｈ
ａｖ
ｉｏｒｓ ｉ
‘
ｎ ｍ
ｕ
…
ｍ－
ｒｏ
ｏｏｔ
－＿－‘
ｓｙｓｔｅｍｓ ｔｈｒｏｕｇｈ ｉｍｐｌｉｃｉｔ ｃｏｌｎｍｕｎｌｃ ‘ ‘
ｎ
‘Ｌ
［Ｊ］．
‘……
Ｒ０
ｂｏ
ｆｉ
。
ｃ
ｓ
龃ｄ
图３优化网络训
ＴＩ１ＡＩＮＬｒｄ，Ｅ ２８／５０，ＭＳＥ０．０００９８４８３５／０・００ｌ，ｂ龇哪
２．删
厶
。
ＴＲＡＩＮＬＭ，ｐｅｒｆｏｒｍａｎｃｅ ｇｏａｌ ｍｅｔ・
ｆ］４ 阎平凡，奎 张长水．人工神经网篁络与模拟进化算法【备与俣似堪 异 “Ｍ］ ～ ．ｊ匕
统在２８步之内就能够找到最优 缩 ，ｌＩ又似埋发 业
‘
ｆ １５
、
弓｝∈钤
．
张钹．神经网络中
ＢＰ
鼻 刚万 ｌ
算法的分析［ｊ］．模式识别
Ｌ ＪＪ’佚 ～
（３）：
１９１－
１９５．
耋 底腐蚀管道极限承载力的研冤Ｌ鬣 金
飞．Ｇ
Ａ－Ｂ
Ｐ
人
工神经网络应用于海 Ｊ Ｊ‘ 目博汗‘‘ ’
ｒ
『
１
９］
８
。
Ｎｔ！ｔ兴．ｇ 篓嚣
．北京：电子工业出版 ｏｏ４．
李钟侠．神经网络结构及兵秘但 化 堪 开
，
菇 算
Ⅲ
…
茹机器人协作中的
ｂ－
图４ １０ ４一＂，ｆｆ￣ ’
…
譬
快
１
５０ －１５８ ．
路径
’
ｍ阜
； 鬣 暑
达到期望目
［
…
１３
］李姚张蒂 ＰＩＤ￣Ｎ］［Ｊ Ｎ新Ｎ￣凇Ｎ， ２１１７，
和遗传算法的智能
计算
１５嚣（１５ ） ：６１０－０ １２．
差大小的隋熏 况下用节点删除法和扩张ｉ丢调讽佣疋。 噘
ｒ
ｒ
］丛爽．面向
１４
杰而向
Ｍａｔｌａｂ 工具箱的柙绘
箱的神经网络理论与应用
矬 司 门ｎ
．
［１１］Ｌｉ Ｃ，Ｌｕ Ｊ，Ｌｕ Ｙ・Ｅ
ｆ
ｉｆ
ｃ
ｉ
ｅｎｔ
ｍ
ｅｒ
ｇ
ｉｎ
ｇ ａ
ｎｄ
ｉｆ
ｈ
ｅ
ｒ
ｉ
ｎｇ
ａ１
ｇｏ
ｒｉ
ｔｈｍ
ｓ
接第８７页）
．
ｆ ｏｒ ａｐｐｒｏｘｉｍａｔｅ ｓｔｎｎｇ ８ｅａＩ ‘Ｉ
ｓ
ｔ
ｒｉ
ｎ
ｇ
８
ｅａｒ
ｃ
ｈｅ
ｃ
８
［
Ｌ ｕ …
ｃ
］
／
／
Ｉ
ｃ
ＤＥ２
—
０ｏ
８
：
Ｌｉ Ｇｕｏｌｉａｎｇ ，Ｆｅｎ
ｇ Ｊｉ
ａｎｈ ｕａ，
ｗａｎｇ Ｊｉ
ｉ
ａｎ￣
ａｎｙ
ｏｎｇ，ｅｔ ａ
’・
ｌ Ａｎ
ｅｎｅ
一
ｃ－
．
—
…
…
ｔ ｉｖｅ ａ ｎｄ
ｖ ｅｒｓａｔ
ｉ
ｌｅｋ
ｋ
ｅｖｗ
眦 ｅ
ｎ
ｇｉｎ
ｅ
ｏｎｎｅｔ
ｅｒｏ
ｇｃｎ
ｕｕ
￣
．
［１２］Ｘｉａｏ Ｃｈｕａｎ，Ｗａｎｇ Ｗｅｊ
Ｌ
ｉｎ Ｘ ｕｅｍ
ｉｎ ．Ｅ
ｄ
－
Ｊｏ
ｉ
ｎ：Ａ
ｎ
ｅｆｆ ｉｃｉｅ
ｎ
ｔ
，
ｄａｔａ ｓ０ｕ脚
，ｍ
［Ｃ］
ｃ
／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈ
ｅ
。
ｖＬＤ
Ｂ
Ｅ
ｎ
ｄ
。
ｗｍ
“～…
ｅｎ
ｔ．
．
．
ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｉｍｉｌａｒｉｔｙ ｊｏｍｓ ｗｌｔｎ ｅｑ Ⅱ
ｅ
ｄ
ｉ
ｓｔ
ａ
ｎｃｅ
ｎ
ｃ。ＩＩｓ
ｗ¨……‘
ｎｔ
ｓ
２）：１４
５２
－索１４
５５
术．
『Ｃ１／／ＶＬＤＢ．２００８：１３１－１４０．
ｆ］
８
．
ｒ １
陆宜梅．
Ｗｅｂ
搜索技术现状分析Ｌ
搜
技
现状分析［Ｊ］．沈阳大学学报，
Ｊ Ｊ・ ｐ曙人手子 ’
ｍ１ ＲＡ，ＦｉｓｅｈｅｒＭ Ｊ，Ｔｈｅ ｓｔｉｒｎｇ－ｔｏ。ｓｔｒｉｎｇ ｃｏ 帆ｐ
［９］ 之关键字查询［ＥＢ／ＯＬ］ＥＢ／ＯＬ］．一
．
ｈｔｔｐ：／。。／ｗｗｗ．
咿 ‘
， 删４
＿一一
．‘
：［１ ４：Ｙ］ｌⅪｅｍ ｕ［Ｊｒ］ｈ．ｌＡ】ａＣｎＭ，ｗ‰ “，１９ａ７ｎｇ４，ｗ２１ｅ（ｉ１，）“： ｎ１６ｘ８－ｕ１ｅ７ｆ３ｒＩｉ．ｎ，昌ｅｔ ａ１．雎ｃｉｅｎｔ ｓｉｍｃｉｌｓ
．
三
ｉｔｖ ｊｏｉｎｓ ｆｏｒ ｎｅａｒ ｄｕｐｌｉｃａｔｅ ｄｅｔｅｃ【 ｕ Ｌ Ｊ川………”。
。
Ｇｕｏｌｉｎａ
ｇ 一ｅｔ
ａｔ．Ｅｔｈｅｌ
ｅｎ
ｔ ｌｎｔ
ｅ
ｒａｃ
ｕ
ｖｅ
…
…
Ｊ
ｆ
ｉ Ｓｈｅｎ
ｇｙｕｅ，Ｌｉ
ｃ，
ｕｚｚｙ ｋｅｙｗｏｒｄ ｓｅａｒｃｈ【ｃ］
『ｃ
／／Ｉｎｔｅｍａｔｉ
０ｎ
０ｎａ１
ａｌ
ｗ０ｎｕ ｗ儿Ｊ
Ｗ０ｄ
ｄＷｉｄ
ｅ
…
ｗ
ｅｂ