CN1983249A - 字符串规划存贮索引查找技术 - Google Patents

Abstract

本发明是一种字符串存贮、索引、模糊检索技术。首先对数据库字符串按字符元进行统计分析，并根据数据库状况决定标记方案。按标记位值V_n建立索引表，若按标记位值V_n聚集存贮后建立索引表则性能更好，称为双表处理；也可将数据库，按标记位值V_n重新组织存贮，即单表处理。检索时，先对检索关键词进行标记，取得位值V_t：双表处理，以V_t与索引表中的标记位值V_n进行位比较，按符合位比较条件的标记位值V_n，在句型数据库中查找V_n，或W_n，对查找到的记录，按需要，与检索关键词进行W位值比较、质数代换整除或通常的字符串模糊匹配等处理；单表处理，以V_t与表中的标记位值V_n进行位比较，对符合位比较条件的V_n的各字符串字段D_n或其对应的信息字段F_n、W_n，按需要，与检索关键词进行通常的字符串模糊匹配、质数代换整除、W位值比较等处理。在CPU赛扬800Hz，内存256M，810主板，硬盘40G测试，检索每条字符串5个汉字、2,035,454条字符串、10,177,270个汉字的表，由于数据库不能全部读入内存，对于每个关键词，必须从硬盘读入部分数据，第一次响应时间为0.9秒，第二次以后，响应时间为0.14至0.18秒。在位标记字符串检索的速度上再提高了一个数量级，可用于自然语言处理中快速查找参考句型，其它方面的字符串模糊检索也可以应用。

Description

字符串规划存贮索引查找技术

技术领域

本发明是一种字符串存贮、索引、模糊检索技术。首先对字符串按字符元进行统计分析，并根据数据库状况、硬件条件、应用范围决定标记方案。然后，按标记位值V_n进行索引，如按标记位值V_n聚集存贮后进行索引则更优；也可按标记位值V_n，对数据库重新组织存贮。检索时，先对检索关键词进行标记，取得位值V_t，与数据库索引标记位值V_n进行位比较，再对符合位比较条件的字符串记录，按需要，进行W位值比较、质数代换整除或通常的字符串模糊匹配等处理。该技术可以在位标记字符串检索的基础上再提高一个数量级，可用于自然语言处理中快速查找参考句型，其它方面的字符串模糊检索也可以应用。

背景技术

字符串的模糊检索技术，最简单的是BF算法，采用逐字符比较方式进行。改进后的模式匹配算法，如KMP算法，对小字符集的拼音文字来说，避免了回溯，但对字符集大、单字符频度低的汉字字符串而言，实质意义不大。

2004年，为解决繁难汉字的查找录入，本人建立了GBK范围内21000个汉字的偏旁数据库。由于不同用户对偏旁的拆分有差异，理想的汉字偏旁数据库必须包含一个汉字的任意层级偏旁，如“ ”必须分解成由艹、

、罒、厂、剡、炎、刂、火、火，才能达到以“任意层级的偏旁组合检索任意汉字”的目的。设用户用查找包含艹、火两个偏旁的汉字，以sql语句查询，计算机即用其中一个偏旁扫描数据库全部记录的偏旁，在包含该偏旁的记录中，再用另一个偏旁进行比较，得到结果集。为了提高查找速度，本人提出用400多个质数代换汉字的400多个基本偏旁，则每个汉字有其基本偏旁的质数乘积。若用户查找包含n个偏旁的汉字，即用n个偏旁的质数乘积对全部汉字的质数乘积进行除法运算，若能整除，则相应的汉字包含这n个偏旁。提出质数代换整除检索的出发点，是把多个关键词的“串行”搜索变成一次性的“并行”搜索，测试表明，质数代换整除检索能一定程度提高检索速度。对于通常的汉字数据库，则用一个质数代表多个汉字，在整除运算筛选之后，再用模式匹配算法得到最终结果集。因此，2004年10月19日，本人申请了“质数代换字符串检索技术”专利，申请号200410067258.X。

但对长字符串实施“质数代换字符串检索技术”，需要较多的空间存贮质数乘积值。为了提高字符串模糊检索的速度，并减少对存贮空间的需求，把质数改为bit，把整除运算改为位比较，即用一个数据的n个位(bit)来标记字符串的组成信息，标记后之后的数据称该字符串的“位值”，对两个字符串的位值进行比较，并结合通常的逐字符比较法，实现字符串的模糊检索。测试表明，速度是一般的逐字符比较模糊检索的数倍乃至十几倍以上，2005年1月17日，本人申请专利“位标记字符串检索技术”。在赛扬800的cpu上测试，用该技术能在0.3秒内从26.7万条书名中找到目标记录。

另一方面，质数代换整除查找结果的字符排列秩序是多样的，这一特点，非常适合于自然语言处理中筛选参考句型，但质数代换音节整除响应速度不够，需要把位标记字符串检索技术同质数代换字符串检索技术给合起来，即用位标记比较方法对参考句型的进行初步筛选，再用质数代换整除得到最终参考句型，在赛扬800的cpu中，0.9秒约能处理100万条记录，速度尚不理想，但以此推算，在cpu主频2.4G的中档微机上，应能在0.3秒内从100万条记录中找到参考句型。

100万个参考句型，若能支持99.7％的现代汉语语句，在中档微机上，基于参考句型的语音输入应有现实可行性。当然，参考句型越多，比如说，达到400万个，语言处理的准确程度就越高。但在主频2.4G的中档微机上，查找400万个句型需1秒多时间，加上语法分析、填补词语等用时，所用时间更多。所以进一步地提高字符串模糊查找的速度，并提高自然语言处理的水平是有意义的。

发明内容

本发明是在“位标记字符串检索技术”基础上提出的，关于“位标记字符串检索技术”的标记重叠概率、查找选择概率、分组标记概率计算，以及相关的位比较逻辑代数原理，可以参见该技术申请文件。对于语言处理，本技术与位标记字符串检索技术、质数代换字符串检索技术结合起来，可形成一套完整的方案，所以本文件结合语音输入处理说明字符串规划存贮索引查找方法，其它方面的字符串模糊查找，可以参照实施。

1.基于参考句型的语音输入方案综述

语音输入、机器翻译、搜索引擎均需进行分词，提高拼音串的分词准确程度已成为提升汉语语音输入水平的关键。汉语拼音串自动分词的算法主要有：最大匹配法(MM)、最少分词词频选择法(FWF)和逐词遍历法。这些分词方法是基于词汇表的方法，准确率不能满足需要，提高准确率需要新的分词方法。

如果按每个句子10个汉字计算，5000常用汉字的10次全排列是一个巨大的数字，当然，由于语义、语法限制，不是所有汉字排列在一起即是句子，但汉语句子的总数可以说是难以穷尽的，至少就目前的技术水平而言，在普通微机，不可能列出足够数量的句子，更不可能实现瞬时响应，找到与拼音串完全对应的句子。但很多语句是有共同主干的，如：“他毕业五年了”，“他早就毕业了”，“他还没毕业”，“他明年六月毕业”等句子中，“他毕业”是主干、核心，我们称为基本句型，记为J；另外，本文件中的“基本句型”也包括词语搭配，如：套|房子，间|房子，本|书等；以及筛选入库的词语、诗句、格言等，如：坚忍不拔。

对于计算机语言处理来说，如果确定了一个拼音串的主干、核心，以之为基础，根据语法、词频、上下文填补其它词汇，应该是能提高处理的水平。质数代换整除运算筛选的结果是不考虑字符元的秩序的，非常适合用来确定一个句子的主干，就语音输入来说，就是为拼音串查找参考句型。

设有汉语字词搭配及基本句型数据库，不考虑声调，用400多个质数代表400多个汉语音节，其中有基本句型“他毕业了”，该句型的拼音为“tabiyele”，代换成29*67*281*577，即315032191。如果语音转换或者拼音输入“tazaojiubiyele”，代换成29*349*269*67*281*577，即29575537123271。以29575537123271为被除数，以数据库全部字词搭配及基本句型的F_n值为除数，若能整除或模运算余数为0，则该句型为可参考的基本句型或字词搭配。29575537123271/315032191＝93881，余数为0，则“他毕业了”是“tazaojiubiyele”的可参考句型，其中“毕业”为动词，是谓语，而词库中拼音为“zaojiu”的词有“早就”“造就”“枣酒”，通过语法、语义、词频等其它方面能起到辅助作用，可将“tazaojiubiyele”转换成“他早就毕业了”。

若参考句型数据库中有：“流利英语”，如果我们想要的句子是：“流利的英语帮他找到一个好工作”，语音转换或拼音输入：Liulideyingyubangtazhaodaoyigehaogongzuo；如果我们想要的句子是：“这人的英语说得不流利”，语音转换或拼音输入：zherendeyingyushuodebuliuli；如果我们想要的句子是：“经过半年英语培训，他已经说得流利多了”，语音转换或拼音输入：Jingguobannianyingyupeixuntayijingshuodeliuliduole，都可以用质数代换整除判断确定“流利英语”是参考句型之一。对于查找到的一个拼音串的多个参考句型J，一般来说，以长“句”优先；同样长的参考句型，可进行字符元跳格匹配，字符元秩序与需要处理的拼音串T的字符元秩序一致的参考句型优先考虑；字符元秩序一致时，如果拼音串T字符元之间有其它词语，则根据参考句型语法信息G，选择可插入其它成分的参考句型。

“质数代换字符串检索技术”的优点是便于查找参考句型，但速度不能满足应用需要，在赛扬800的cpu中，0.1秒只能进行1-2万个左右的长整数整除判断。所以本人在申请号200510023383.5的“位标记字符串检索技术”修改文本中，说明了以“位标记字符串检索技术”优越性能进行预选，即对拼音串按汉语的音节进行标记，汉语有400多个音节，在对参考句型数据库音节出现频率进行统计之后，按频率均衡分组，以32个bit进行标记。这样的筛选效果会最优，但结果集R₁中会出现毫无关系的参考句型。在R₁中，再按一个质数代换一个音节，用整除运算进行筛选，得到参考句型。两个方法结合起来，在赛扬800的cpu中，0.3秒约能处理26.7万个句型，处理100万个句型需要0.9秒，以此推算，在主频2.4G的目前中档微机上，0.3秒应能处理100万个参考句型，使基于参考句型的分词初步有现实可行性。按cpu以往的发展速度，18个月提高一倍，以及目前多核技术的趋势，能处理200万、400万个参考句型的微机不久应该普遍使用。当然，我们关心的，究竟多少句型能覆盖99.7％的语句，以及如何进行句型提炼。另一方面，我们也希望通过算法改进，使基于参考句型的语音输入方法，具有当下的普遍可行性，这是本发明提出的意义所在。

2.参考句型探讨

由于语言研究的不足，没有关于汉语句型的资料，但我们可以做一个估计：

一个人到30岁可以认为已经完全掌握了母语，能很好地表达自己的思想，理解他人的语言，阅读一般的报刊书籍。如果每天学习200个基本句型，到30岁算10000天，则共掌握2,000,000个基本句型。虽然我们的知识与日俱增，但增加的主要是词汇，所以现代汉语的句型或许小于这个数字。

汉语词语主要是动词、名词、形容词三类，搭配相应主要有三类：动词和名词、动词和形容词、名词和形容词。名词的数量很大，但名词中相当多是多字词，计算机容易识别处理。动词是语句的枢纽，又是语言中最灵活的词语，有资料认为现代汉语约有1200-2000个动词，也有认为是6000个的，有部分动词的组句能力很强；而且，一般来说，动词是一两个汉字。所以，就计算机处理来说，提练参考句型重点是动词，尤其是单字动词与其他词语的搭配，其次是单字名词、单字形容词与其他词语的搭配。

动词与名词的关系有动宾关系、主谓关系。动宾关系如：打电话、打牌、打扑克；跺脚。主谓关系如：兔子跑、敌人跑。“说|法语”可以形成主主谓关系：“他法语说得好”；也可以形成动宾关系：“他说法语”，因为质数代换整除筛选不考虑语序，参考句型数据库中“说|法语”只需出现一次。本文件中用“|”表示该参考句型是非固定的，即可调换秩序，或经常插入其它成分或词语。

动词与形容词的关系有动补关系、状谓关系。动补关系如：跑快：“他跑得很快！”状谓关系如：“认真学习”，而“他学习很认真”又是动补关系，“学习认真”可以认为是主谓关系，同样，句型数据库中“认真|学习”只需出现一次。

名词与形容词的关系有修饰关系、主谓关系。如：热天，天的很热。参考句型数据库中“天|热”只需出现一次。

不过，如果计算机处理能力足够，我们不妨把句型定多一些。如果把“他说英语”作为一个基本句型，无疑利于计算机处理，但“主谓宾”俱全，会增加句型的数量。所以我们可以考虑，把“他说英语”切分为“他说”、“说英语”两个基本句型，同样的，有“我说”、“说法语”、“说阿拉伯语”等，则整体上可以减少基本句型的数量。当然，句型数据库中也可以有一定数量常用的“主谓宾”俱全的句子，如格言、诗句等。内存大的主频2.1Gcpu中档微机，利用本文件的方法，是可以处理三四百万条参考句型的数据库，对于低档微机，可以对参考句型分类建库，如：通用120万、科技80万、文史80万、报刊80万条。如果处理新闻文稿则使用通用120万+报刊80万条参考句型数据库。

不过，本质上是语义搭配的句型分词不能解决所有问题，如：“读一遍”、“读两遍”，以至“读五百遍”，我们可以认为“读|遍”是一个搭配，也可将“一遍”、“两遍”筛选入库，但“遍”与更多的数词的搭配使用，不可能都入库，得借助语法处理。

3.规划存贮的提出

一个典型的语音输入数据库的参考句型库jxk包括以下信息：参考句型、拼音串、位标记值、音节代换质数乘积值、频率以及语法信息，而语法信息又可包括参考句型各成分的词性、搭配之间是否可插入其它成分等。由于语言研究的不足，没有研究单位对现代汉语作过分析，并提练过参考句型。根据上文估计，200万个句型应该能较好地覆盖，而参考句型及词语搭配，短则2个字，多的可能7、8个汉字。所以，本人用10万多条两字词与4万多条三字词重复交叉，搭配成4,019,576条，每条5个汉字的无意义的参考句型，建成测试数据库，记为jxk。参考句型数据库应该有拼音串的字段，但拼音串的字段要占用许多空间，所以构造的测试数据库，对汉语的400多个音节，每个音节用一个汉字代替，同时避免了汉语拼音音节切分的问题，如fangan可切分为fang+an或fan+gan。如：兴代表xing。下面是表的模式：

参考句型J    音节代字D    位标记值W音节代换质数乘积值F    语法信息G

不比整行字   不比正兴字   5008

华北轴对称   花被周对成   5008

护耳当头炮   胡儿当头炮   5008

四党浦城县   四当仆成仙   5008

吃准备用品   吃准被永拼   5008

必争东北面   比正东被棉   5008

固化正对面   古花正对棉   5008

共识好杀戮   工是好沙卢   5123

磠砂南宫市   卢沙男工是   5123

华新闽南话   花心民男花   5123

告示南宫市   高是男工是   5123

划入即使是   花如几是是   5123

心急比色计   心几比色几   5123

公民熊欣欣   工民兄心心   5123

歹心好比是   代心好比是   5123

入睡风化壳   如水丰花科   300032

奉公自尾鹿   丰工百微卢   300032

转告水驱比    专高水区比    300032

高唐公开化    高唐工开花    300032

可比唯心论    科比微心伦    300032

从这个局部看，“位标记字符串检索技术”中，无论一条记录的字符元或其位值如何，都必须用其位值与关键词位值进行一次位比较判断。如上表所示，“如水丰花科、丰工百微卢、专高水区比、高唐工开花、科比微心伦”5条音节代字D的位值W均为300032，检索中，需用关键词位值W_t与之进行5次位值比较判断。如果，位值W300032的记录有50条，则需进行50次位值比较，这是低效的，无用的。要避免这种低效的处理，方法是按位值重新组织字符串的存贮，使每种位值与关键词位值只比较一次，或少数几次。

4.存贮组织方法

拼接构造的全部为五个音节参考句型测试数据库，记录条数4,019,576条。以长整数的31个bit进行标记，可能重叠为1、2、3、4个bit，也可能不重叠，所以位值理论上有206367种。实际统计为206320种，每种位值平均对应的参考句型为19.48条。

1.双表处理

减少位值无效比较，最直接的方法是：按位值对数据库进行聚集存贮，将位值相同的记录存贮在相邻的空间，同时严格按位值大小排列。然后按位值分组总计查询，存为另外的表，记为syb。表中有字段“索引位值”，是从参考句型表jxk中去除重复提取出来，为区别一般的位值W，记为V，表中有字段“统计”是各“索引位值”V在参考句型表jxk中出现的次数。对表syb也进行聚集存贮，使之按“索引位值”V大小排列。不进行聚集存贮，将降低查找效率。

设关键词音节代字D_t为“幺苗非中”，标记后索引位值V_t＝5898240，以之与syb表中全部的“索引位值”V_n进行位比较，记所有的bit为“1”的数据为V_T，得到满足V_t→V_n＝V_T，或者其等价变换条件的记录集R_v，共有28个“索引位值”满足这个条件，见下表：

索引位值V  统计T

5898240    36

5898241    17

5898242    15

5898244    14

5898248    13

5898256    12

5898272    30

5898304    7

5898368    14

5898496    13

5898752    23

5899264    10

5900288    11

5902336    15

5906432    14

5914624    24

5931008    16

5963776    12

6160384    6

7995392    9

14286848   21

22675456   6

39452672   20

73007104   15

140115968  21

274333696  12

542769152  19

1079640064 22

对每一个满足条件的V_n，在参考句型表jxk中位值W查找等值的W_n。如首先在参考句型表jxk查找W_n＝5898240的第一个记录，在找到第一个符合记录后，用关键词音节代字D_t“幺苗非中”与该记录的音节代字D_n进行模糊匹配，确定该记录是否符合条件。在实际语音输入处理中，可以关键词的质数乘积值F_t与该记录的质数F_n相除，如能整除，则该记录之参考句型有效，否则放弃。

在找到W_n＝5898240的第一个符合记录后，可按syb.T字段确定jxk中此记录往后需要进行模糊匹配或整除判断的记录数是36条。处理后，在参考句型表jxk查找W_n＝5898241的第一个记录，该位值需要进行模糊匹配或整除判断的记录是17条。这样，直到最后的W_n＝1079640064的参考句型。

因为两表均按位值进行聚集索引，对R_v所列的每一个值，在句型库jxk中，只需从小到大向前查找。

2.单表处理

双表处理是：一个参考句型表jxk，一个位索引表syb，实际还有一个音节信息表yjb，包含汉语拼音的400多个音节的音节代字、统计频率、标记分组、基本位值、代换质数等信息。单表处理处理，同样有音节信息表yjb，但将参考句型表jxk与位索引表syb合并一个表syjxb：

先将索引表syb扩充，增加D₁至D₁₀十个字段，F₁至F₁₀十个字段，J₁至J₁₀十个字段等，即成为syjxb的架构。然后，写一段代码将参考句型库jxk中的信息读出并写入该表。如，对于位值V＝526406的记录，在jxk中找到位值W＝526406，读入该位值的10条记录的句型信息，相应地写入各字段中。如果参考句型库jxk中位值W＝526406的记录只有7条，则只填入D₁至D₇，F₁至F₇，J1至J7等字段，其余空白。如果参考句型库jxk中位值W＝526406的记录超过10条，则在syjxb中插入另一个v＝526412的记录，写入参考句型库jxk中位值W＝526406的记录中其他记录的信息，以此类推。下面是syjxb的局部：

索引V	D1	D2	D3	…	D8	D9	D10	F1	…
										526406	男收林把丘	切几一京在	一斗几观枪	…					…
526408	分门辟究观	牛爱枪间帆	收若内在没	…	收只内在没	写闰枪收火	林亲只幺在		…
										526409	辟是内在没	里收是究分	分是辟究观	…					…

526410	松写收幺钻	在几写京闻	在火瓜分几	…	京光昏宁几	爱代分光京	辟幺宁几里		…
										526412	瓜火钧须观	内亲端里没	昏丘冲闻门	…	把枪盘只闻	只闻端里没	更须盘只闻		…
526416	间切间里仙	辟林准间正	收火周里京	…	周究收火厅	娃里周闻间	京在仙另辟		…
										526417	亲间民正厅	闻另林产是	仙产牛派观	…					…
526418	幺头闻代林	亲代周里京	另没松闻暖	…	几收次头京				…
										526420	幺一爱袄娃	另京丹里闻	斗京把仙桌	…	头光幺一林	一幺火里仙	端收次头京		…
526424	没在分头来	周间帆火里	来厅内丘仙	…					…

关键词音节代字D_t，标记后位值记为V_t，以之与syjxb表中全部的“索引位值”V_n进行位比较，得到满足V_t→V_n＝V_T，或者其等价变换条件的记录集R_v，以关键词音节代字D_t与字段D₁至D₁₀进行模糊匹配，或者以关键词音节质数代换值F_t与F₁至F₁₀进行整除，若D_n或F_n满足条件，则以之确定J_n为参考句型。要注意的是可能同时有数个J_n符合条件，是参考句型。

5.选择标记存贮索引

拼接构造的全部为五个音节参考句型测试数据库，记录条数4,019,576条。参考句型都是5个字符元，以长整数符号位之外的31个bit进行标记，可能重叠为1、2、3、4个bit，也可能不重叠，所以索引位值V理论上有206367种。实际统计为206320种，每种位值平均对应的参考句型为19.48条。如果参考句型是6个字，理论上索引位值V有942648种，每种位值班平均对应4.24条句型，如果参考句型是7个字，理论上索引位值V有3572223种，每种位值班平均对应1.12条句型。其不利之处是：syb中索引位值V_n太多，以关键词位值V_t与之进行比较，不能提高效率，其次是符合条件的记录在jxk中过于分散，如果数据库很大，不能整体装入内存，检索时需要从硬盘读入，即使进行聚集存贮，也无助于提高效率。

这里提供另一备选方案：从400多个音节中选择一部分高频音节，以之对参考句型数据库进行标记，得到V值，按V值规划存贮索引，查找定位后，再用完整标记位值W进行比较筛选，下表是进行选择标记的音节信息表yjb的局部：

jiao	交	0.5431437	120787	0.03004969	24	23	8388608	167
									zhong	中	1.495395	119824	0.02981011	23	22	4194304	173
xia	下	0.2759932	119216	0.02965885	22	21	2097152	179
									sheng	声	0.7076554	118790	0.02955287	21	23	1048576	181
jing	京	0.8198212	115391	0.02870726	20	19	524288	191
									fa	发	0.600911	115302	0.02868512	19	21	262144	193
dian	典	0.4591378	114725	0.02854157	18	4	131072	197
									zhu	朱	0.6329921	114394	0.02845922	17	19	65536	199
ke	科	0.7285779	113406	0.02821342	16	15	32768	211
									he	禾	0.9572256	113349	0.02819924	15	14	16384	223
chang	长	0.3614466	109633	0.02727477	14	13	8192	227
									gong	工	0.9642788	108595	0.02701653	13	12	4096	229
shou	收	0.5025882	104602	0.02602314	12	11	2048	233
									xin	心	0.5713299	104523	0.02600349	11	10	1024	239
er	儿	0.3855799	100695	0.02505115	10	9	512	241
									si	四	0.33355662299	99674	0.02479714	9	8	256	251
cheng	成	0.7522638	99636	0.02478769	8	7	128	257
									guan	观	0.5021671	99453	0.02474216	7	22	64	263
bao	包	0.3649206	99178	0.02467375	6	15	32	269
									zheng	正	0.5170103	97346	0.02421798	5	26	16	271
ban	半	0.312101	95787	0.02383013	31	3	1.07E+09	277
									ge	哥	0.7350784	92446	0.02299894	30	28	5.37E+08	281
qian		0.3907119	91197	0.02268821	29	24	2.68E+08	283
									ju	局	0.507957	90805	0.02259069	28	13	1.34E+08	293
qing	青	0.4394522	90010	0.02239291	27		67108864	307
									yang	样	0.302653	88926	0.02212323	26		33554432	311
yin	因	0.3078113	88856	0.02210581	25		16777216	313
									fang	方	0.5175103	88612	0.02204511	24		8388608	317
tong	同	0.5170366	86890	0.02161671	23		4194304	331
									ye	也	0.7386575	85841	0.02135574	22		2097152	337
xue	学	0.993465	85504	0.0212719	21		1048576	347

shi这个音节，代字为“是”，3.20149，是指现代汉语中，400多个音节中shi的频率，是一份不太准确的统计数据，jxk中有437341条记录包含“是”，即10.88028％的记录包含这个音节，用长整数31个bit标记，与cha、pai、se、min、kuang、cong、guai、pang、nüe等音节，对应长整数右起第一个bit。在400个音节中，选择其中62个音节作为控制音节K，分为31组，对应31个bit，标记后的位值，我们也记为V。下表是选择标记的jxk的局部：

参考句型J   音节代字D   完全标记位值W 控制字K    控制字数  选择标记位值V

换签自主国  欢千字朱国  805372032     国千朱字   4         805372032

换人自转式  欢人字专是  539000961     人是字     3         2097281

换伞自转轴  欢三字专周  1610645648    字         1         128

换上自组织  欢上字租只  805307016     上只字     3         268435592

换肾自尊心  欢身字尊心  537003200     心字       2         1152

换收自作孽  欢收字左聂  541068416     收字       2         2176

换手宗白华  欢收宗百花  537139200     花收       2         6144

有之大法师  优只达发是  25427977      达发是优只 5         25427977

有知大范围  优只达帆微  25198600      达微优只   4         25198600

卧龙反射炉  窝龙帆舌卢  289408008                0         0

卧铺反射率  窝仆帆舌吕  285245960                0         0

卧射反射器  窝舌帆舌起  285212712     起         1         32

卧式反射体  窝是帆舌踢  285278217     是         1         1

参考句型J“换签自主国”的音节代字为“欢千字朱国”，其中“欢”与“国”在完全标记中同属30组，而“国千朱字”均是选择音节，所以选择标记位值V与完全标记位值W相同。

选择标记位值V＝0的记录有201774条，这些记录不包含任何一个控制音节。

选择标记位值V＝34234368的记录只有2条：“余典京长低”、“无低副余京”。查询得知，统计T＜20的V有75048种，总计324715条记录，如果直接进行聚集索引，不能改进其存贮分布状况。我们将这些V更改为2147483647，就是使所有的bit为“1”，然后对数据库进行聚集索引，数据库成为：

V＝0 201774条，不含任何控制字符元，记为V₀

V＝1-2147483646有11873种，3,493,087条每V值平均294.2条，为V_n

V＝2147483647 324715条，所有bit均为“1”，记为V_T

如检索关键词不含任何控制字符元K，因为是逆检索，所以仅需将V₀范围的音节代字的完全标记位值W_n与关键词之完全标记位值W_t进行位比较判断。

设检索关键词10个音节中含j个控制音节K，其它(10-j)个为非控制字符元，j个控制字符元的选择控制标记值为V_t，则jxk中需与关键词完全标记位值W_t进行位比较的位值W_n有：V₀及V_T范围的记录，V_n范围内满足下式或其等价变换式的记录：V_t&V_n＞0，当然也有：W_t&W_T＞0。

62个控制音节频率合计为：P_k＝53.60，其余的非控制音节频率合计为：P_f＝46.40，对于检索关键词n＝10个音节的语句来说，出现控制音节j个、r个非控制音节，r+j＝10的概率可按n重贝努利实验计算。

62个控制音节在句型数据库中出现百分比为229.41％，平均百分比为：0.0370。如果检索关键词n＝10个音节中出现控制音节5个、5个非控制音节。按公式

$P\left[\underset{i=1}{\overset{n}{U}}{A}_i\right]=\underset{1\&le;i\&le;n}{\mathrm{\&Sigma;}}P\left(A_i\right)-\underset{1\&le;i<j\&le;n}{\mathrm{\&Sigma;}}P\left(A_i{A}_j\right)+\&CenterDot;\&CenterDot;\&CenterDot;+{(-1)}^{n-1}P(A_1+A_2\&CenterDot;\&CenterDot;\&CenterDot;A_n)$

R_n＝4,019,576*(5*0.037-10*0.037^2+10*0.037^3-5*0.037^4+0.037^5)＝690593

需要进行位比较的记录集R＝R₀+R_T+R_n＝201774+324715+690593＝1217082

其中201774+324715条记录是连续的，其余690593条记录是保留下来的，也相对集中。当整个数据库不能装入内存，需要从硬盘读入时，可以减少硬盘寻道定位时间。

6.缩位标记存贮索引

选择标记存贮索引方法，如果认真的统计分析后进行，能一定程度减少逆检索的位比较次数，改善记录的存贮分布，但并不理想，下面说明另一种标记方案。

从位标记检索的筛选效果来说，数据库字符串平均长m及关键词长k一定时，标记所用bit数n越大，筛选效果越好。但从存贮索引的角度来说，标记所用bit数n越大，位值种类越多，则有不利的方面：其一，索引表值增多，定位的次数也增多。其二，需要读入的数据存贮空间分散。在数据库大，内存有限的环境下，需要从外存读入的数据越分散，硬盘寻道和定位的时间也越多。

m	n	组合累计	4000000	m	n	组合累计	4000000
								1	31	31	129032.26	1	24	24	166666.67
2	465	496	8064.52	2	276	300	13333.33
								3	4495	4991	801.44	3	2024	2324	1721.17
4	31465	36456	109.72	4	10626	12950	308.88
								5	169911	206367	19.38	5	42504	55454	72.13
6	736281	942648	4.24	6	134596	190050	21.05
								7	2629575	3572223	1.12	7	346104	536154	7.46
8	7888725	11460948	0.35	8	735471	1271625	3.15
								9	20160075	31621023	0.13	9	1307504	2579129	1.55
m	n	组合累计	4000000	m	n	组合累计	4000000
								1	20	20	200000.00	1	16	16	250000.00
2	190	210	19047.62	2	120	136	29411.76
								3	1140	1350	2962.96	3	560	696	5747.13
4	4845	6195	645.68	4	1820	2516	1589.83
								5	15504	21699	184.34	5	4368	6884	581.06
6	38760	60459	66.16	6	8008	14892	268.60
								7	77520	137979	28.99	7	11440	26332	151.91
8	125970	263949	15.15	8	12870	39202	102.04
								9	167960	431909	9.26	9	11440	50642	78.99

所以，规划存贮索引标记的所用的bit数，需要综合考虑cup、内存、外存、数据库的记录多少、每条记录所有字段长、字符串的字符元数等方面的因素。4000000条记录的数据库，如果字符串平均长m为6，可以考虑用20个bit标记，其位值也记为V，根据V对jxk聚集存贮索引，每一连续区域平均有66.16条记录，当然，位比较后的筛选效果会较低，所以存贮索引之外，同时进行一次31个bit的标记，位值记为W，在用位值V进行索引定位后，再用位值W进行位比较筛选。

设数据库及关键词均用“1”标记，标记所用位数为n，位标记后S_n的位值V_n的“1”为m个，检索关键词标记后的“1”为k个，逆检索即查找被关键词T包含的记录J，概率计算方法为：

$P=\frac{C_k^m}{C_n^m}=\frac{\frac{k!}{m!(k-m)!}}{\frac{n!}{m!(n-m)!}}=\frac{k!(n-m)!}{n!(k-m)!}$

构造的测试数据库字符元为5，设检索关键词的音节为10，用20个bit标记后，因重叠，“1”的bit的平均数会略少于5、10，因计算复杂，这里认为“1”的bit为5、10。

$P_{20}=\frac{C_{10}^5}{C_{20}^5}=\frac{\frac{10!}{5!(10-5)!}}{\frac{20!}{5!(20-5)!}}=0.016254$

用V_t与V_n进行比较后，在jxk中需要查找的区域有21699*0.016254＝353，是比较理想的。

但是缩位标记也有不足之处，按概率计算公式，当句型长m为5时，检索关键词长为k，位标记所用bit数n不同取值时的概率：

k	m	n	k！	(n-m)！	n！	(k-m)！	p
								101214101214101214101214	555555555555	323232242424202020161616	36288004.79E+088.72E+1036288004.79E+088.72E+1036288004.79E+088.72E+1036288004.79E+088.72E+10	1.09E+281.09E+281.09E+281.22E+171.22E+171.22E+171.31E+121.31E+121.31E+12399168003991680039916800	2.63E+352.63E+352.63E+356.2E+236.2E+236.2E+232.43E+182.43E+182.43E+182.09E+132.09E+132.09E+13	1205040362880120504036288012050403628801205040362880	0.0012510.0039330.0099420.0059290.0186340.0471010.0162540.0510840.1291280.0576920.1813190.458333

设用20个bit标记，如果语句包含12音节，位值比较后筛选概率为0.051084，14音节则0.129128，增加得很快。虽然汉语语句平均长在10音节左右，但语言处理中会有较长的句子，所以逆检索中，缩位过度是不可取的。

7.长检索关键词的切分处理

汉语句式本来比较短，所以本文多以检索关键词含10个音节分析，也就是认为句子的长度是10个汉字，但现代书面文体，有长达15、16个汉字乃至20多个汉字的语句，如：

中国经济的持续快速增长一直是西方经济学界所津津乐道的迷团。

Zhongguojingjidechixukuaisuzengzhangyizhishixifangjingjixuejiesuojinjinledaodemituan.

该句有28个汉字，其拼音串有28个音节，对于32位的cpu，直接对该句进行质数代换检索，整除运算的处理是困难的，进行位标记检索筛选，概率筛选的效果是不佳的，缩位标记索引可能无法进行，所以对长句有必要进行切分处理。自然，计算机并不知道对拼音串按意群进行合理切分，可能将一个属于词语的音节分为两半，我们可以这样处理：

Zhongguojingjidechixukuaisuzengzhang

Zengzhangyizhishixifangjingjixuejie

xuejiesuojinjinledaodemituan.

也就是第一次切分0-11共11个音节，第二次切分10-20共11个音节，第三次切分19以后的音节。对这样切分出来的3个片段，分别进行处理，得出初步结果。初步结果中，“津津乐道”、“西方经济学界”“经济增长”“持续快速增长”是计算机能判断转换的部分，句子处理为：

Zhongguo经济de持续快速增长yizhishi西方经济学界suo津津乐道demituan.

下一步，将已转换的部分去除，得到下面拼音串：

Zhongguodeyizhishisuodemituan

如果jxk中有：“中国是”“是迷团”“一直是”等搭配，则可处理为：

中国de一直是suode谜团

再合并被去除的已判断的部分：

中国经济de持续快速增长一直是西方经济学界suo津津乐道de迷团。

借助语法、词频、字频、前后汉字之间的“联想”，可将句子转换为：

中国经济的持续快速增长一直是西方经济学界所津津乐道的迷团。

上面说明了汉语语音处理中，字符串规划存贮索引查找的方法。把其它语言的标音符号视为汉语拼音，即可用该方法处理其它语言。机器翻译、搜索引擎中的查找参考句型，也不难组织实施。对于一般的字符串模糊检索，同样可以进行字符串规划存贮索引，提高查找速度。

另外，本文件说明的是以位标记为基础进行规划存贮索引，当然，按照这个原理，也可以用质数代换方法实施规划存贮索引，但占用空间较多而查询速度会较慢。

具体实施方式

本文件说明了多种标记存贮方案，应用中可根据数据库的特点以及硬件环境选择实施，下面用sql server 2000和vb6.0具体说明单表实施的方法。由于测试硬件水平低，仅对syjxb中每个位值V_n从jxk中读入10条音节代字D，忽略其他字段和多余的记录，所以实际转换进入syjxb的音节代字是2035454条，共10,177,270个汉字。

1.测试代码

Dim V As Long

Dim Vlin As Long

Dim T As String

Dim Dlin as String

Dim x As Integer

Dim shijian As Single

V＝0

Vlin＝0

T＝Text1.Text

For x＝1 To Len(T)

Dlin＝Mid(T，x，1)

yjbrs.MoveFirst

yjbrs.Find″D＝&Dlin&″

‘从音节信息表yjb中找到检索关键词每个音节的基本位值。

With yjbrs

Vlin＝.Fields(″W″)

End With

V＝V Or Vlin

‘对检索关键词的每个音节的位值进行位的“或”运算，得到关键词关键词的位值V。

Next

shijian＝Timer

strQuery＝″SELECT V，D＝case when D₁ LIKE′％″&T&″％′then D₁ when D₂ LIKE′％″&T&″％′then D₂ when D₃ LIKE′％″&T&″％′then D₃ when D₄ LIKE′％″&T&″％′then D₄ when D₅ LIKE′％″&T&″％′then D₅ when D₆ LIKE′％″&T&″％′then D₆ when D₇LIKE′％″&T&″％′then D₇ when D₈ LIKE′％″&T&″％′then D₈ when D₉ LIKE′％″&T&″％′then D₉ when D₁₀ LIKE′％″&T&″％′then D₁₀ End FROM(SELECT*from syjxbWHERE((syjxb.V&″&V&″)＝″&V&″))DERIVEDTBL WHERE((D₁ LIKE′％″&T&″％′)or(D₂ LIKE′％″&T&″％′)or(D₃ LIKE′％″&T&″％′)or(D₄ LIKE％″&T&″％′)or(D₅ LIKE′％″&T&″％′)or(D₆ LIKE′％″&T&″％′)or(D₇ LIKE′％″&T&″％′)or(D₈LIKE′％″&T&″％′)or(D₉ LIKE′％″&T&″％′)or(D₁₀ LIKE′％″&T&″％′))″

‘内部查询进行位值比较SELECT*from syjxb WHERE(syjxb.V&″&V&″)＝″&V&″)，外部查询的where字句，以检索关键词T与D₁至D₁₀进行模式匹配，任一字段包含检索关键词，该记录入选。D＝case when……End，通过判断筛选显示字段。如果D₁至D₁₀中，有两个字符串符合，用这个方法，是不能完全显示的，如果独立编写自然语言处理程序，查找参考句型，这个问题容易解决。

Adodc1.RecordSource＝strQuery

Adodc1.Refresh

DataList1.ListField＝″D″

DataList1.ReFill

shijian＝Timer-shijian

Beep

MsgBox(CStr(shijian)+″秒。″)

2.测试结果

编程语言为VB，操作系统为Windowxp，CPU赛扬800Hz，内存256M，810主板，硬盘40G。由于内存数量限制，数据库不能全部读入内存，对于每个关键词，必须从硬盘读入数据，第一次响应时间为0.9秒，第二次以后，由于数据已读入内存，响应时间为0.14至0.18秒。如果不用规划存贮，仅用位标记检索，用时约为1.7-1.8秒。考虑到字符串多达2035454条，计10,177,270个汉字，硬件水平的状况，可以说性能的良好的。

其它数据库字符串模糊查找可参照实行。

Claims (1)

1.一种字符串存贮、索引、模糊检索技术，其特征在于，包括以下步骤：

a.对数据库字符串按字符元进行统计分析，按一定方案进行位标记，得到每条字符串的位值V_n。

b.按标记位值V_n建立索引表，若按标记位值V_n对数据库进行聚集存贮后，再按V_n建立索引表，则性能更优，称为双表处理；

或是将数据库按标记位值V_n重新组织，称为单表处理。

c.检索时，先对检索关键词进行标记，取得位值V_t后：

双表处理，以V_t与索引表中的标记位值V_n进行位比较，按符合位比较条件的标记位值V_n，在句型数据库中查找V_n，或W_n，对查找到的记录，按需要，与检索关键词进行W位值比较、质数代换整除或通常的字符串模糊匹配等处理，得到结果；

单表处理，以V_t与表中的标记位值V_n进行位比较，对符合位比较条件的V_n的各字符串字段D_n或其对应的信息字段F_n、W_n，按需要，与检索关键词进行通常的字符串模糊匹配、质数代换整除、W位值比较等处理，得到结果。