基于离散性、交叉性、非完全性的特性字符串匹配方法

摘要

本发明公开了一种基于离散性、交叉性、非完全性的特性字符串匹配方法，其步骤为：A.用户在用户界面中设置或由信息处理设备自动设置离散数、交叉数、非完全数，输入检索词；B.信息处理设备根据用户输入的检索词，对指定的一个文本，以A步设置的离散数、交叉数、非完全数作为匹配约束条件，进行基于该三种特性的字符串匹配运算，输出精确检索、离散检索、交叉检索、交叉离散检索、非完全检索、离散非完全检索、交叉非完全检索、离散交叉非完全检索共八种检索方式中的一种方式的匹配结果。该种方法提供了八种信息检索方式且操作简单、灵活、方便，可进行定性、定量检索，检索功能强，应用领域广。

说明书

技术领域

本发明涉及基于离散性、交叉性、非完全性的特性字符串匹配方法，属于信息检索领域。

背景技术

随着网络信息技术的快速发展，网络信息形成了信息时代的巨大宝藏。信息检索呈现大众化、家庭化的趋势，用户如何进行信息检索构成网络信息的瓶颈。字符串匹配，尤其是非精确字符串匹配，则是信息检索的基础，其重要性犹如发动机之于各种运动机械，是各种信息检索的主要核心竞争技术，直接影响到信息检索的检索方式、检索功能、检索效果、用户界面等。

四十年来，国内外对非精确字符串匹配的方法研究一直采用基于错误因素的距离计算，最常用的是Levenshtein距离，也称为ED(Edit Distance)距离。这种基于错误因素距离计算方法，存在一些固有问题，造成了信息检索方式的过于单调且信息检索质量也受到一定的影响，问题主要体现在以下四点：

1)现有的基于错误因素距离计算的非精确字符串匹配研究思路，是一种基于问题现象的研究思路，如插入、删除、替换、交换、反向错误等。这些现象问题并非完全独立、可以严格界定，呈现出多样化特征，是典型的问题现象。例如，本质上可以用一个插入错误和一个删除错误定性地表示一个替换错误，用一个插入错误和一个删除错误定性地表示一个交换错误。理论上，基于错误因素的字符串匹配分类方法并不理想，字符串匹配至今没有形成科学的分类体系，这是其中的重要原因之一。

最直接的负面效果体现在：采用错误因素很难界定匹配问题的相关理念、特征、值域，选择何种字符串匹配方法处理特定性质的字符串匹配问题变得复杂化，因此，信息检索只能模糊化，信息检索方式只有精确检索和模糊检索(或非精确检索)。

2)现有的基于错误因素描述字符串匹配问题的多态性，直接影响到检索方式的分类以及质量。下表反映出基于错误因素对特定问题的错误现象进行描述的多态性。

        基于错误因素对特定问题进行描述的多态性表

文本 模式基于错误因素描述ABCDEFGH ABCDEFGH精确匹配(即子串匹配)：不允许删除、插入、交换等错误ABCDEFGH CDEF精确匹配(即子串匹配)：允许前面、后面的删除ABCDEFGH CDF非精确匹配：1、存在一个删除(E)；或2、存在若干前面、后面删除，并且存在一个中间删除(E)；或3、存在一个插入(F)；或4、存在一个替换(E，F)；等ABCDEFGH CEDF非精确匹配：1、存在一个交换(DE，ED)；或2、存在两个替换(D，E)，(E，D)；或3、存在一个插入(D)和一个删除(D)；等ABCDEFGH CEFD非精确匹配：1、存在一个删除(D)和一个插入(D)；或2、存在两个插入(C)，(D)；或3、存在两个插入(E)，(F)；等ABCDEFGH ACEFXD非精确匹配：1、存在两个删除(B)，(D)和两个插入(X)，(D)；或2、存在两个删除(B)，(D)和两个替换(G，X)，(H，D)；等

表中，忽略距离计算的量化影响，基于错误因素对特定文本与模式的匹配问题，存在多种基于错误因素的定性表示方法，反映出描述同一问题的多态性，不便于分类处理。

3)基于错误因素距离计算的非精确字符串匹配方法，由于通过距离计算对各种错误因素进行统一量化处理，如ED(Edit Distance)距离计算，使得匹配中不同错误因素的性质模糊化。距离只反映出文本与模式在特定错误模型下的差异量，但不能反映出所有错误现象、究竟是什么错误类型的差异，以及错误出现在什么位置等问题。因此，在提高查全率、查准率、定位精度，以及在定性定量检索上，缺少灵活方便的应对手段和方法。

4)另一方面基于错误因素距离计算的非精确字符串匹配方法，只考虑错误因素对精确匹配的负面影响，很少讨论错误因素在应用中的积极意义。例如：在本专利中，离散特性不再被看作一种错误，认识到离散特性在信息检索中有很多应用价值。例如，在信息输入中，可利用离散检索，让用户通过缺省输入，避免方言错误、避免模糊音输入、减少输入码长等；在数据库检索、网络搜索引擎中，可利用离散特性选择检索词，进行离散检索，提高查全率等。

以上问题，呈现出字符串匹配基础体系的不健全，直接影响到信息检索的检索方式、检索功能、检索效果以及用户操作界面，在信息检索中造成了检索方式单调(精确与模糊)，检索质量、查全率不高，匹配方法的多样性，但却难以展开综合应用。亟待解决。

发明内容

本发明的目的在于解决上述问题，提出一种基于离散性、交叉性、非完全性的特性字符串匹配方法，该种方法提供了多种信息检索方式且操作简单、灵活、方便，检索功能强大。

本发明解决其技术问题所采用的技术方案为：一种基于离散性、交叉性、非完全性的特性字符串匹配方法，其步骤为：

A步  设置特性参数值并输入检索词  用户在用户界面中设置或由信息处理设备自动设置：反映离散性的离散数即检索词各字符出现在文本中的离散的字符数，反映交叉性的交叉数即检索词各字符出现在文本中的交叉的字符数或子串数，反映非完全性的非完全数即检索词各字符未出现在文本中的字符数；并由用户在用户界面中输入检索词；

B步  字符串匹配及输出：信息处理设备根据用户输入的检索词，对指定的一个文本，以A步设置的离散数、交叉数、非完全数作为匹配约束条件，进行基于该三种特性的字符串匹配运算，输出精确检索、离散检索、交叉检索、离散交叉检索、非完全检索、离散非完全检索、交叉非完全检索、离散交叉非完全检索共八种检索方式中的一种方式的匹配结果。

与现有技术相比，本发明的有益效果是：

一、本发明提出的三种特性参数：离散性、交叉性、非完全性，具有完全不同的性质和概念，是互为独立的特性，基于三种特性的字符串匹配研究思路更为科学地揭示了字符串匹配问题的内在规律，错误因素是三种特性的外在表现。可通过下表的示例比较，得到清楚的说明。

                     基于错误因素及本发明对特定问题的描述差异表

文本 模式现有基于错误因素的描述本发明基于三种特性的描述BCDEFGH ABCDEFGH精确匹配(即子串匹配)：不允许删除、插入、交换等错误精确匹配(即子串匹配)：不允许离散、交叉、非完全ABCDEFGH CDEF精确匹配(即子串匹配)：只允许前面、后面的删除精确匹配(即子串匹配)：不允许离散、交叉、非完全ABCDEFGH CDF非精确匹配：1、存在一个删除(E)；或2、存在若干前面、后面删除并且存在一个中间删除；或3、存在一个插入(F)；或4、存在一个替换(E，F)；等离散匹配：只存在一个离散(E)ABCDEFGH CEDF非精确匹配：1、存在交换(DE，ED)；或2、存在两个替换(D，E)，(E，D)；3、存在插入(D)和删除(D)；等交叉匹配：只存在一个交叉(D)ABCDEFGH CEFD非精确匹配：1、存在删除(D)和插入(D)；或2、存在两个插入(C)，(D)；或3、存在两个插入(E)，(F)等交叉匹配：只存在一个交叉(D)ABCDEFGH ACEFXD非精确匹配：1、存在两个删除(B)，(D)和两个插入(X)，(D)；或2、在两个删除(B)，(D)和两个替换(G，X)，(H，D)；等离散交叉非完全匹配：存在一个离散(B)、一个交叉(D)、一个非完全(X)

可见，基于错误因素对特定文本与模式的字符串匹配问题，存在多种基于错误因素的描述方法，反映出描述同一问题的多态性，不便于细致的分类处理。而本发明对同一问题只存在一种描述方法，准确地反映了文本与模式的匹配关系，因此可以准确地分类。上表中关于两个子串匹配问题，基于错误因素有两种不同的描述方法；本发明对两个子串匹配问题，只存在一种描述方法，更为符合子串的定义。通过上表对比，还可以清楚地了解到离散特性与删除错误的差异，交叉特性与交换错误的差异，非完全性与插入错误的差异。

二、由三种特性进行组合，可以将信息检索方式严格地分为8种不同的类型，为用户提供了8种可供选择的信息检索方式。且基于特性的字符串匹配，不是简单地把特性看成一种消极错误。例如，利用离散检索，可让用户通过检索词的缺省输入，避免方言错误、避免模糊音输入、减少输入码长等。而现有的基于错误因素距离计算的字符串匹配方法，由于错误因素的可替代性，不能形成科学的分类体系，因此检索方式只有精确和模糊方式。

三、本发明具体通过设置三种特性值的大小，作为字符串匹配的约束条件参数，在提高查全率、查准率、定位精度上，提供更为灵活、方便、定性、定量的应对手段和方法，以满足不同性质的检索要求，方便用户对特定问题查全率、查准率、定位精度的综合考虑、随意调节。设置的特性值越大，检索条件越宽松，查全率越高；特性值越小，检索条件越严格，查准率越高；设置的某特性值为零，表示不允许该种特性的匹配，因此，可以通过设置特性参数值零，进行有选择的定性、定量检索，充分发挥各特性在信息检索中的潜在应用价值，这正是特性字符串匹配优越性的具体表现。

四、对不同的检索方式，可进行统一的集成化字符串匹配编程，用一个字符串匹配程序，满足8种信息检索方式的特定性质的信息检索。各种检索方式只是输入的检索特性值的不同，应用程序设计人员不必考虑选择何种字符串匹配方法进行不同方式的信息检索，而是对三种特性值进行统一处理，更方便其实施、推广。

五、由于各种因素造成的不可预知的文本信息错误，如：传输错误、自动识别输入错误、存储错误等，会造成信息检索的遗漏，一些有用但有错误的信息无法正常检出。在本发明中，通过适当设置离散数、交叉数、非完全数，既可实现容错检索。

六、A步设置特性参数值并输入检索词时，用户界面可以为三种特性参数的部分组合，三种参数即可以全由用户设置，也可部分或所有特性参数不由用户设置而由信息处理设备自动设置，形成少于三个特性参数甚至无特性参数组成的用户界面，此时，未出现在用户界面中的特性参数值为信息处理设备根据特殊用途自动设置的隐含值。这种用户界面特性参数组合方式，可适应于特殊的应用要求与环境，减少用户需要考虑的特性参数设置数目，用户只需输入检索词、更少的特性参数值即可，方便用户的操作。

上述的B步的字符串匹配及输出的第一种作法的具体步骤为：

a步  输入参数合法性检验：

计算出检索词的长度m以及文本的长度n；对n、m、离散数、交叉数、非完全数，进行合法性检验，若不满足合法性，则退出匹配，并返回不匹配的结果；否则，交叉数、非完全数不能超过m-1，若超过则改为m-1；

b步  循环初始化：

设置滑动窗位置＝1，表示文本中当前第一个正准备处理的位置；

对检索词＝p₁p₂……p_m中的所有字符，进行稳定的升序排序，并存储在数组PT中，数组PT中同时存储了各字符在检索词中原来的位置，分别称为数组PT中存储的字符子数组PTc以及数组PT中存储的位置子数组PTp；

从文本中的第一个字符开始，选取长度为min(m+离散数-1，n)的子串作为滑动窗子串，在该滑动窗子串前增加一个小于任何字符的特殊符号，对滑动窗子串的字符进行稳定的升序排序，并存储在数组WT中，数组WT中同时存储了各字符在文本中原有的位置，且特殊符号的位置为零，分别称为数组WT中存储的字符子数组WTc以及数组WT中存储的位置子数组WTp；min为最小值函数；

c步  判定循环是否结束：

若(n-滑动窗位置+1+非完全数)小于m，则结束处理，并返回不匹配结果；

d步进行下一个滑动窗子串匹配的参数初始化：

滑动窗位置开始，在文本中选取长度为min(m+离散数，n-滑动窗位置+1)的子串作为滑动窗子串，再删除数组WT中最小的存储的位置以及对应的字符，然后对滑动窗子串的最后一个字符进行稳定插入排序，插入到数组WT中，若(n-滑动窗位置+1)＜(m+离散数)则不用再进行插入排序；

数组POS中全部初始化为-1，实际非完全数＝0，数组WT的位置W＝1，数组PT的位置P＝1，最大位置＝0；最小位置＝n；

e步  滑动窗子串匹配是否结束：

若数组WT比较结束或者数组PT比较结束，则转g步；

f步滑动窗子串字符与检索词的字符进行循环比较：

根据WTc中位置W存储的字符与PTc中位置P存储的字符的比较情况，分别进行以下情况处理

若WTc中位置W存储的字符＜PTc中位置P存储的字符，则位置W增加1，转e步；

若WTp中位置W存储的字符＞PTp中位置P存储的字符，则位置P增加1，实际非完全数增加1；若实际非完全数小于或等于非完全数，则转e步，否则，滑动窗位置增加1，转c步；

若WTc中位置W存储的字符＝PTc中位置P存储的字符，则将WTp中位置W存储的数值存储到数组POS中，其存储位置为PTp中位置P存储的数值；若WTp中位置W存储的数值＞最大位置，则将WTp中位置W存储的数值存入最大位置中；若WTp中位置W存储的数值＜最小位置，则将WTp中位置W存储的数值存入最小位置中；位置W增加1，位置P增加1，转e步；

g步  判定滑动窗子串是否满足约束条件：

求实际非完全数＝(实际非完全数+m-位置P+1)；若实际非完全数＞非完全数，则滑动窗位置增加1，转c步；

求实际离散数＝(最大位置-最小位置+1-m+实际非完全数)；若实际离散数＞离散数，则滑动窗位置增加1，转c步；

计算实际交叉数；若实际交叉数＞交叉数，则滑动窗位置增加1，转c步；

h步  计算出相似度：

相似度＝(2m-2×实际非完全数-实际交叉数)÷(2m+实际离散数-实际非完全数)；

i步  结束匹配并返回如下结果：

返回相似度，数组POS，实际离散数，实际交叉数，实际非完全数。

这种基于特性的字符串匹配运算过程，通过离散数、交叉数、非完全数的数值，用一个程序即可自动进行不同的8种信息检索方式的统一匹配，并返回满足不同特性约束条件的匹配结果，实现了更为规范的信息检索集成化环境。

返回的相似度，代表了文本与模式满足特性约束条件的匹配程度，为零到1的实数。例如：若返回的相似度为0.50，则表示模式与文本匹配的子字符序列有50％的相似程度。可以根据所有检出文本的最大相似度进行排序输出，方便用户选择。返回的数组POS则记录了具体匹配的位置。返回的实际离散数、实际交叉数、实际非完全数，则记录了匹配的子字符序列的实际匹配状况，便于进一步的后续处理。这些返回数据可以组织成一个结构数据返回，也可以单独地返回。

匹配过程中，当实际非完全数不满足约束条件，立即进行下一个滑动窗的匹配，且只有当实际非完全数以及实际离散数，满足给定约束条件的情况下，才计算实际交叉数的大小，因此该方法的时间复杂性为：

平均时间复杂度接近于0(nm+nd)；

最坏时间复杂度为0(nm+nd+nmLog₂(m))≈0(nmLog₂(m))。

上述的B步中的字符串匹配及输出的第二种作法的具体步骤为：

a步  输入参数合法性检验：

计算出检索词的长度m以及文本的长度n；对n、m、离散数、交叉数、非完全数，进行合法性检验，若不满足合法性，退出匹配，并返回空指针结果；否则，交叉数、非完全数不能超过m-1，若超过则改为m-1；

b步  循环初始化：

设置有一个节点的OUT链，该节点中包含如下初始信息：最大位置＝0、最小位置＝0，相似度＝1；

设置滑动窗位置＝1，表示文本中当前第一个正准备处理的位置；

对检索词＝p₁p₂……p_m中的所有字符，进行稳定的升序排序，并存储在数组PT中，数组PT中同时存储了各字符在检索词中原来的位置，分别称为数组PT中存储的字符子数组PTc以及数组PT中存储的位置子数组PTp；

从文本中的第一个字符开始，选取长度为min(m+离散数-1，n)的子串作为滑动窗子串，在该滑动窗子串前增加一个小于任何字符的特殊符号，对滑动窗子串的字符进行稳定的升序排序，并存储在数组WT中，数组WT中同时存储了各字符在文本中原有的位置，且特殊符号的位置为零，分别称为数组WT中存储的字符子数组WTc以及数组WT中存储的位置子数组WTp；min为最小值函数；

c步  判定循环是否结束：

若(n-滑动窗位置+1+非完全数)小于m，则删除OUT链首节点，退出匹配并返回OUT链；

d步  进行下一个滑动窗子串匹配的参数初始化：

滑动窗位置开始，在文本中选取长度为min(m+离散数，n-滑动窗位置+1)的子串作为滑动窗子串，再删除数组WT中最小的存储的位置以及对应的字符，然后对滑动窗子串的最后一个字符进行稳定插入排序，插入到数组WT中，若(n-滑动窗位置+1)＜(m+离散数)则不用再进行插入排序；

数组POS中全部初始化为-1，实际非完全数＝0，数组WT的位置W＝1，数组PT的位置P＝1，最大位置＝0；最小位置＝n；

e步  滑动窗子串匹配是否结束：

若数组WT比较结束或者数组PT比较结束，则转g步；

f步  滑动窗子串字符与检索词的字符进行循环比较：根据WTc中位置W存储的字符与PTc中位置P存储的字符的比较情况，分别进行以下情况处理：

若WTc中位置W存储的字符＜PTc中位置P存储的字符，则位置W增加1，转e步；

若WTp中位置W存储的字符＞PTp中位置P存储的字符，则位置P增加1，实际非完全数增加1；若实际非完全数小于或等于非完全数，则转e步，否则，滑动窗位置增加1，转c步；

若WTc中位置W存储的字符＝PTc中位置P存储的字符，则将WTp中位置W存储的数值存储到数组POS中，其存储位置为PTp中位置P存储的数值；若WTp中位置W存储的数值＞最大位置，则将WTp中位置W存储的数值存入最大位置中；若WTp中位置W存储的数值＜最小位置，则将WTp中位置W存储的数值存入最小位置中；位置W增加1，位置P增加1，转e步；

g步  判定滑动窗子串是否满足约束条件：

求实际非完全数＝(实际非完全数+m-位置P+1)；若实际非完全数＞非完全数，则滑动窗位置增加1，转c步；

求实际离散数＝(最大位置-最小位置+1-m+实际非完全数)；若实际离散数＞离散数，则滑动窗位置增加1，转c步；

计算实际交叉数；若实际交叉数＞交叉数，则滑动窗位置增加1，转c步；

h步  计算出相似度：

相似度＝(2m-2×实际非完全数-实际交叉数)÷(2m+实际离散数-实际非完全数)；

i步  将匹配结果插入OUT链：

滑动窗位置增加1；将相似度、最大位置、最小位置、数组POS、实际离散数、实际交叉数、实际非完全数组织成一个新节点；

若(新节点中的最小位置＞OUT链最后一个节点中的最大位置)则将新节点直接插入OUT链最后，转c步；

若(新节点中的最小位置小于或等于OUT链最后一个节点中的最大位置)且(新节点相似度＞OUT链最后一个节点相似度)则将新节点替换OUT链最后一个节点，转c步；否则放弃新节点，转c步。

以上的字符串匹配运算的第二种作法的具体步骤与第一种作法的步骤基本相同，不同的仅仅是：

为适应全文检索，a步中不符合参数要求时，返回的是一个空指针，表示无匹配的子字符串；b步中增设了一个OUT链，用于记录文本中的所有满足匹配条件的无重叠子字符序列以及相应信息；相应的c步中不再输出不匹配结果，而改为输出OUT链；并在i步中根据匹配的结果对OUT链进行修改。实际匹配时，可能存在满足约束条件的，有位置重叠的两个子字符序列，或者有位置重叠的连环多个子字符序列，解决的方法为：对于有位置重叠的两个子字符序列，或者有位置重叠的连环多个子字符序列，只输出相似度大的子字符序列。根据相似度，选择有位置重叠的匹配结果，可以提高定位精度。

若返回的OUT链为空，表示不匹配，否则OUT链包含了所有匹配出的子字符序列，每个子字符序列包括：相似度、最大位置、最小位置、数组POS、实际离散数、实际交叉数、实际非完全数。

因此，第二种作法除具有第一种作法的全部优点外，还为信息检索用户提供了一个全面、详细的检索词在指定文本中的匹配信息，为用户对信息的取舍给出了最完整的参考信息。

该方法的时间复杂性为：

平均时间复杂度接近于0(nm+nd)；

最坏时间复杂度为0(nmLog₂(m)。

上述的g步中的计算实际交叉数的第一种作法为：

(1)步初始化：假设用数组LPOS存放最大可间隔升序序列，且数组LPOS的第一个位置的数值初始化为-1，LP用于指示当前数组LPOS处理的位置并初始化为1；数组POS最后添加一个结束标志，取数组POS中第一个数值到比较数据中；

(2)步判断是否结束：若比较数据为结束标记，转(4)步；

(3)步循环处理：根据比较进行三种情况处理；

若比较数据大于数组LPOS中LP位置的数据，则LP增加1，将比较数据存储到数组LPOS中LP位置处，取数组POS中下一个数值到比较数据中，转(2)步；

若比较数据小于数组LPOS中LP位置的数据，则从数组LPOS中第一个位置向后进行折半查找，搜索第一个大于或等于比较数据的数据，并用比较数据改写该数据，取数组POS中下一个数值到比较数据中，转(2)步；

若比较数据等于数组LPOS中LP位置的数据，则取数组POS中下一个数值到比较数据中，转(2)步；

(4)步得出实际交叉数：实际交叉数＝m-实际非完全数-LP+1。

这是一种基于字符为单位的交叉数计算方法。

数组POS在匹配过程中，用于存放检索词中已经匹配的字符在文本中的出现位置，数组POS中数据的特点是：除数值-1以外，其它数据均为大于0的整数，且互不相等。数组POS的最大可间隔升序序列的长度是指：按数组POS中数据的位序，在数组POS寻找出一个最大可间隔升序序列，该序列的数据个数即为最大可间隔升序序列的长度。由于数值-1代表了未匹配的字符，因此数值-1不计入最大可间隔升序序列中。

通过最大可间隔升序序列的长度，即可求出文本与模式匹配时的实际交叉数。从而通过该方法准确地计算出实际交叉数，并与设置的交叉数进行比较，筛选出满足交叉数约束条件的文本，并给出检索词与指定检索文本的交叉特性匹配状况，方便、灵活地满足用户的检索要求。交叉数的另一个作用是配合离散数、非完全数计算相似度，方便检出文本的排序，或者匹配结果的选择，满足用户的检索要求。

该算法的时间复杂度为：0(mlog₂(m))。

上述的g步中的计算实际交叉数的第二种作法为：

(1)步初始化：最大连续序列长度＝0，当前连续序列长度＝1，连续后继整数出现总数＝0；依次将数组POS中大于零的全部数值存入临时数组中，临时数组最后添加一个结束标志；若临时数组中的非零元素个数小于等于1，直接返回交叉数等于零的结果；否则，用数组LPOS存放最大可间隔升序序列，且数组LPOS的第一个位置的数值初始化为临时数组中第一个数值；LP用于指示当前数组LPOS处理的位置，并初始化为1；取临时数组中第二个数值到比较数据中；

(2)步判断是否结束：若比较数据为结束标记，转(5)步；

(3)步进行连续性处理：若比较数据减1等于上一个位置的数据，则当前连续序列长度增加1，连续后继整数出现总数增加1，转(4)步；否则将当前连续序列长度与最大连续序列长度中较大的数值，重新存入最大连续序列长度中，当前连续序列长度＝1；

(4)步根据比较进行两种情况处理

若比较数据大于数组LPOS中LP位置的数据，则LP增加1，将比较数据存储到数组LPOS中LP位置处，取临时数组中下一个数值到比较数据中，转(2)步；

若比较数据小于数组LPOS中LP位置的数据，则从数组LPOS中第一个位置向后进行折半查找，搜索第一个大于比较数据的数据，并用比较数据改写该数据；取临时数组中下一个数值到比较数据中，转(2)步；

(5)步实际交叉数＝m-实际非完全数-LP-连续后继整数出现总数+Max(最大连续序列长度，当前连续序列长度)-1，其中Max为求最大值函数。

该第二种作法是对第一种作法的改进，称为基于子串为单位的交叉数计算方法：当模式中的一个子串整体出现交叉时，算作一个交叉；而第一种方法的交叉数则为该子串的长度。这种改进方式的理由为：当模式中的一个子串整体出现交叉时，认为整体是一个有语义的结构子串，例如两个英文单词间的整体交叉算作一个交叉数。这种改进处理方式更符合检索的实际，使得整体交叉的相似度明显高于第一种方法的相似度，其输出的相似度与用户的实际要求更一致，便于用户优先选择。

该算法的时间复杂度为：0(mlog₂(m))。

上述的A步设置特性参数值时，特性参数值不由信息设备自动设置的特性参数，用户界面则有相应的供用户设置特性参数的数值输入框。

上述的用户界面中的数值输入框为单纯数值输入框或者组合框，在数值输入框的每个框附近还显示有相应特性参数名称。

上述的A步输入检索词时，用户界面有一个文本框供用户输入检索词。

上述的A步设置特性参数值后，信息处理设备根据用户在用户界面中设置或由信息处理设备自动设置的离散数、交叉数、非完全数，还进行检索方式的判断，判断出检索方式属于精确检索、离散检索、交叉检索、离散交叉检索、非完全检索、离散非完全检索、交叉非完全检索、离散交叉非完全检索共八种检索方式中的一种方式，并提供给用户界面显示出检索方式的名称。

这样的用户界面给用户提供了一种灵活、方便、简单、容易的操作方式：通过对特性参数设置不同的数值，即可自动显示相应信息检索方式的名称，供用户选择不同的信息检索方式，同时数值框的数值还代表了信息检索的约束条件。因此，通过设置不同的特性参数，可进行不同的定性、定量的信息检索。用户界面的提示信息醒目、直观，使用户操作容易，无需学习。

下面结合附图和具体实施方式对本发明作进一步的详细说明。

附图说明

图1是本发明实施例一的方法中字符串匹配及输出的流程示意图。

图2是本发明实施例二的方法中字符串匹配及输出的流程示意图。

图3是本发明实施例一的精确检索方式的用户界面。

图4是本发明实施例一的离散检索方式的用户界面。

图5是本发明实施例一的交叉检索方式的用户界面。

图6是本发明实施例一的离散交叉检索方式的用户界面。

图7是本发明实施例一的非完全检索方式的用户界面。

图8是本发明实施例一的离散非完全检索方式的用户界面。

图9是本发明实施例一的交叉非完全检索方式的用户界面。

图10是本发明实施例一的离散交叉非完全检索方式的用户界面。

图11是本发明实施例二的离散交叉非完全检索的用户界面。

图12是本发明实施例二的离散交叉检索的用户界面。

图13是本发明实施例二的离散检索的用户界面。

具体实施方式

实施例一

本发明的第一种具体实施方式为，一种基于离散性、交叉性、非完全性的特性字符串匹配方法，其步骤为：

A步  设置特性参数值并输入检索词  用户在用户界面中设置或由信息处理设备自动设置：反映离散性的离散数即检索词各字符出现在文本中的离散的字符数，反映交叉性的交叉数即检索词各字符出现在文本中的交叉的字符数或子串数，反映非完全性的非完全数即检索词各字符未出现在文本中的字符数；并由用户在用户界面中输入检索词；

B步  字符串匹配及输出：信息处理设备根据用户输入的检索词，对指定的一个文本，以A步设置的离散数、交叉数、非完全数作为匹配约束条件，进行基于该三种特性的字符串匹配运算，输出精确检索、离散检索、交叉检索、离散交叉检索、非完全检索、离散非完全检索、交叉非完全检索、离散交叉非完全检索共八种检索方式中的一种方式的匹配结果。

图1的流程图为本例中B步的字符串匹配及输出的流程示意图。图1示出其大体流程为：a步 输入特性参数合法性检验；b步 循环初始化：初始化滑动窗位置为1，滑动窗大小＝检索词长度+离散数；c步判定循环是否结束；如果循环结束，输出不存在符合条件的匹配结果，否则执行后面d步、e步、f步，当前滑动窗子串与检索词进行比较；g步计算实际离散数、实际交叉数、实际非完全数，并判定是否满足特性约束条件？如里不满足条件，则滑动窗向前移动一个字符位置，转c步；否则，执行h步根据三个实际特性参数计算相似度；i步返回满足特性约束条件的匹配结果。

本例中B步的字符串匹配及输出的完整具体步骤为：

a步  输入参数合法性检验：

计算出检索词的长度m以及文本的长度n；对n、m、离散数、交叉数、非完全数，进行合法性检验，若不满足合法性，则退出匹配，并返回不匹配的结果；否则，交叉数、非完全数不能超过m-1，若超过则改为m-1；

b步  循环初始化：

设置滑动窗位置＝1，表示文本中当前第一个正准备处理的位置；

对检索词＝p₁p₂……p_m中的所有字符，进行稳定的升序排序，并存储在数组PT中，数组PT中同时存储了各字符在检索词中原来的位置，分别称为数组PT中存储的字符子数组PTc以及数组PT中存储的位置子数组PTp；

从文本中的第一个字符开始，选取长度为min(m+离散数-1，n)的子串作为滑动窗子串，在该滑动窗子串前增加一个小于任何字符的特殊符号，对滑动窗子串的字符进行稳定的升序排序，并存储在数组WT中，数组WT中同时存储了各字符在文本中原有的位置，且特殊符号的位置为零，分别称为数组WT中存储的字符子数组WTc以及数组WT中存储的位置子数组WTp；min为最小值函数；

c步  判定循环是否结束：

若(n-滑动窗位置+1+非完全数)小于m，则结束处理，并返回不匹配结果；

d步  进行下一个滑动窗子串匹配的参数初始化：

滑动窗位置开始，在文本中选取长度为min(m+离散数，n-滑动窗位置+1)的子串作为滑动窗子串，再删除数组WT中最小的存储的位置以及对应的字符，然后对滑动窗子串的最后一个字符进行稳定插入排序，插入到数组WT中，若(n-滑动窗位置+1)＜(m+离散数)则不用再进行插入排序；

数组POS中全部初始化为-1，实际非完全数＝0，数组WT的位置W＝1，数组PT的位置P＝1，最大位置＝0；最小位置＝n；

e步  滑动窗子串匹配是否结束：

若数组WT比较结束或者数组PT比较结束，则转g步；

f步  滑动窗子串字符与检索词的字符进行循环比较：

根据WTc中位置W存储的字符与PTc中位置P存储的字符的比较情况，分别进行以下情况处理

若WTc中位置W存储的字符＜PTc中位置P存储的字符，则位置W增加1，转e步；

若WTp中位置W存储的字符＞PTp中位置P存储的字符，则位置P增加1，实际非完全数增加1；若实际非完全数小于或等于非完全数，则转e步，否则，滑动窗位置增加1，转c步；

若WTc中位置W存储的字符＝PTc中位置P存储的字符，则将WTp中位置W存储的数值存储到数组POS中，其存储位置为PTp中位置P存储的数值；若WTp中位置W存储的数值＞最大位置，则将WTp中位置W存储的数值存入最大位置中；若WTp中位置W存储的数值＜最小位置，则将WTp中位置W存储的数值存入最小位置中；位置W增加1，位置P增加1，转e步；

g步  判定滑动窗子串是否满足约束条件：

求实际非完全数＝(实际非完全数+m-位置P+1)；若实际非完全数＞非完全数，则滑动窗位置增加1，转c步；

求实际离散数＝(最大位置-最小位置+1-m+实际非完全数)；若实际离散数＞离散数，则滑动窗位置增加1，转c步；

计算实际交叉数；若实际交叉数＞交叉数，则滑动窗位置增加1，转c步；

h步  计算出相似度：

相似度＝(2m-2×实际非完全数-实际交叉数)÷(2m+实际离散数-实际非完全数)；

i步  结束匹配并返回如下结果：

返回相似度，数组POS，实际离散数，实际交叉数，实际非完全数。

以上g步中的实际交叉数的作法可以为：

(1)步初始化：假设用数组LPOS存放最大可间隔升序序列，且数组LPOS的第一个位置的数值初始化为-1，LP用于指示当前数组LPOS处理的位置并初始化为1；数组POS最后添加一个结束标志，取数组POS中第一个数值到比较数据中；

(2)步判断是否结束：若比较数据为结束标记，转(4)步；

(3)步循环处理：根据比较进行三种情况处理；

若比较数据大于数组LPOS中LP位置的数据，则LP增加1，将比较数据存储到数组LPOS中LP位置处，取数组POS中下一个数值到比较数据中，转(2)步；

若比较数据小于数组LPOS中LP位置的数据，则从数组LPOS中第一个位置向后进行折半查找，搜索第一个大于或等于比较数据的数据，并用比较数据改写该数据，取数组POS中下一个数值到比较数据中，转(2)步；

若比较数据等于数组LPOS中LP位置的数据，则取数组POS中下一个数值到比较数据中，转(2)步；

(4)步得出实际交叉数：实际交叉数＝m-实际非完全数-LP+1。

这种方式计算的实际交叉数为以字符为单位的实际交叉数。

以上g步中的计算实际交叉数的作法还可以为：

(1)步初始化：最大连续序列长度＝0，当前连续序列长度＝1，连续后继整数出现总数＝0；依次将数组POS中大于零的全部数值存入临时数组中，临时数组最后添加一个结束标志；若临时数组中的非零元素个数小于等于1，直接返回交叉数等于零的结果；否则，用数组LPOS存放最大可间隔升序序列，且数组LPOS的第一个位置的数值初始化为临时数组中第一个数值；LP用于指示当前数组LPOS处理的位置，并初始化为1；取临时数组中第二个数值到比较数据中；

(2)步判断是否结束：若比较数据为结束标记，转(5)步；

(3)步进行连续性处理：若比较数据减1等于上一个位置的数据，则当前连续序列长度增加1，连续后继整数出现总数增加1，转(4)步；否则将当前连续序列长度与最大连续序列长度中较大的数值，重新存入最大连续序列长度中，当前连续序列长度＝1；

(4)步根据比较进行两种情况处理

若比较数据大于数组LPOS中LP位置的数据，则LP增加1，将比较数据存储到数组LPOS中LP位置处，取临时数组中下一个数值到比较数据中，转(2)步；

若比较数据小于数组LPOS中LP位置的数据，则从数组LPOS中第一个位置向后进行折半查找，搜索第一个大于比较数据的数据，并用比较数据改写该数据；取临时数组中下一个数值到比较数据中，转(2)步；

(5)步实际交叉数＝m-实际非完全数-LP-连续后继整数出现总数+Max(最大连续序列长度，当前连续序列长度)-1，其中Max为求最大值函数。

这种方式计算的实际交叉数为以子串为单位的实际交叉数。

本例中A步设置特性参数值时，特性参数值不由信息设备自动设置的特性参数，用户界面则有相应的供用户设置特性参数的数值输入框。用户界面中的数值输入框为单纯数值输入框或者组合框，在数值输入框的每个框附近还显示有相应特性参数名称。A步输入检索词时，用户界面有一个文本框供用户输入检索词。

本例中A步设置特性参数值后，信息处理设备根据用户在用户界面中设置或由信息处理设备自动设置的离散数、交叉数、非完全数，还进行检索方式的判断，判断出检索方式属于精确检索、离散检索、交叉检索、离散交叉检索、非完全检索、离散非完全检索、交叉非完全检索、离散交叉非完全检索共八种检索方式中的一种方式，并提供给用户界面显示出检索方式的名称。

下面是依据本例的方法具体设计的用户界面及其检索实例的结果。

用户界面根据数值输入框设置的不同数据，可以呈现八种信息检索方式名称，进行八种不同方式的信息检索。

1、八种信息检索方式之一的精确检索方式的用户界面实例：

图3为精确检索方式的用户界面，该种方式，对用户提供的检索词进行精确检索，为缺省方式。离散数、交叉数、非完全数均为0，表示检索词中的字符不允许离散，不允许交叉，不允许非完全，必须完整地出现在被检索出的文本中。

检索实例：文本＝“中华人民共和国信息产业部”

检索词＝“信息产业部”

通过本例的方法进行匹配后，能检索出文本“中华人民共和国信息产业部”。该例相似度为：100％。(注：加粗并添加下划线的字符为匹配的字符)

2、八种信息检索方式之二的离散检索方式的用户界面实例：

图4为离散检索方式的用户界面，该种方式，离散数＞0，表示对用户提供的检索词进行离散检索，被检出的文本满足的条件为：检索词出现在文本中的字符不允许交叉，不允许非完全，但其离散的字符数允许小于或等于设置的离散数。

示例：文本＝“……string pattern matching……”，设置离散数＝10

检索词＝“string matching”

用检索词“string matching”，通过本例的字符串匹配方法，进行离散检索，能检索出文献数据库中的文章“……string pattern matching……”。该例匹配的实际离散数为8个字符，其中“pattern”为文本中离散的字符，相似度为：79％。

示例：文本＝“……string pattern matching……”，设置离散数＝8

检索词＝“strg paten machg”

通过本例的字符串匹配方法，同样能检索出文献数据库中的文章“……string pattern matching……”。该例匹配的实际离散数为7个字符，其中“in”“t”“r”“t”“in”为文本中离散的字符，其相似度为：82％。

该例进行基于离散特性的定性、定量(离散数＝8)检索，让英语拼写不准确的人如释重负，不需要输入完整的英文单词作为检索词，充分体现了基于离散特性字符串匹配的优越性能。

3、八种信息检索方式之三的交叉检索方式的用户界面实例：

图5为交叉检索方式的用户界面，该种方式，交叉数＞0，表示对用户提供的检索词进行交叉检索，被检出的文本满足的条件为：检索词出现在文本中的字符不允许离散，不允许非完全，但其交叉的字符数或子串数允许小于或等于设置的交叉数。

例如：文本＝“拼音笔划声调组合输入法”

检索词＝“拼音声调笔划”

并设置交叉数＝5(注：一个中文符号为两个字符长度)。

通过本例的字符串匹配方法，进行交叉检索，可以检索出文本“拼音笔划声调组合输入法”。该例匹配的以字符为单位的实际交叉数为4，以子串为单位的实际交叉数为1，其中“笔划”或“声调”为交叉的字符，该例的以字符为单位的相似度为83％，以子串为单位的相似度为96％。

具体实施时，实际交叉数的计算方法，可根据检索的需要选择其中的一种进行计算。一般以子串为单位计算，更符合实际要求。

4、八种信息检索方式之四的离散交叉检索方式的用户界面实例：

图6为离散交叉检索方式的用户界面，该种方式，离散数＞0且交叉数＞0，表示对用户提供的检索词进行离散交叉检索，被检出的文本满足的条件为：检索词出现在文本中的字符不允许非完全，但允许离散，允许交叉，其交叉的字符数或子串数允许小于或等于设置的交叉数，其离散的字符数允许小于或等于设置的离散数。

例如：文本＝“拼音、笔划、声调组合输入法”

检索词＝“拼音声调笔划”

并设置交叉数＝5，离散数＝5。

通过本例的字符串匹配方法，进行离散交叉检索，可以检索出“拼音、笔划、声调组合输入法”的文本。该例匹配的以字符为单位的实际交叉数为4，以子串为单位的实际交叉数为1；实际离散数也为4。其中“笔划”或“声调”为交叉的字符，而两个中文“、”号为离散的字符，该例以字符为单位的相似度为71％，以子串为单位的相似度为82％。

若离散数设置为零，或者交叉数设置为零，均不能用检索词“拼音声调笔划”检索出文本“拼音、笔划、声调组合输入法”。

5、八种信息检索方式之五的非完全检索方式的用户界面实例：

图7为非完全检索方式的用户界面，该种方式，非完全数＞0，表示对用户提供的检索词进行非完全检索，被检出的文本满足的条件为：检索词出现在文本中的字符不允许离散和交叉，但允许非完全，其非完全的字符数允许小于或等于设置的非完全数。

例如：文本＝“中华人民共和国信产部项目”

检索词＝“信息产业部项目”

并设置非完全数＝5。

通过本例的字符串匹配方法，进行非完全检索，可以检索出“中华人民共和国信产部项目”的文本。该例匹配的实际非完全数＝4，其中“息”与“业”为非完全匹配的字符，该例相似度为：83％。

6、八种信息检索方式之六的离散非完全检索方式的用户界面实例：

图8为离散非完全检索方式的用户界面，该种方式，离散数＞0且非完全数＞0，表示对用户提供的检索词进行离散非完全检索，被检出的文本满足的条件为：检索词出现在文本中的字符不允许交叉，但允许离散和非完全，其离散的字符数允许小于或等于设置的离散数，其非完全的字符数允许小于或等于设置的非完全数。

例如：文本＝“拼音、笔划组合输入法”

检索词＝“拼音声调笔划”

并设置离散数＝4，非完全数＝4。

通过本例的字符串匹配方法，进行离散非完全检索，可以检索出  “拼音、笔划组合输入法”的文本。该例匹配的实际离散数为2，实际非完全数为4，其中中文“、”为离散的字符，而“声调”为非完全匹配的字符，该例相似度为：73％。

7、八种信息检索方式之七的交叉非完全检索方式的用户界面实例：

图9为交叉非完全检索方式的用户界面，该种方式，交叉数＞0且非完全数＞0，表示对用户提供的检索词进行交叉非完全检索，被检出的文本满足的条件为：检索词出现在文本中的字符不允许离散，但允许交叉和非完全，其交叉的字符数或子串数允许小于或等于设置的交叉数，其非完全的字符数允许小于或等于设置的非完全数。

例如：文本＝“拼音笔划组合输入法”

检索词＝“拼音、划笔”

并设置交叉数＝4，非完全数＝4。

通过本例的字符串匹配方法，进行交叉非完全检索，可以检索出“拼音笔划组合输入法”的文本。该例匹配的以字符为单位的实际交叉数为2，以子串为单位的实际交叉数为1；实际非完全数为2。其中“笔”或“划”为交叉的字符，而中文“、”号为非完全的字符，该例以字符为单位的相似度为78％，以子串为单位的相似度为83％。

8、八种信息检索方式之八的离散交叉非完全检索方式的用户界面实例：

图10为离散交叉非完全检索方式的用户界面，该种方式，离散数＞0且交叉数＞0且非完全数＞0，表示对用户提供的检索词进行离散交叉非完全检索，被检出的文本满足的条件为：检索词出现在文本中的字符，其离散的字符数允许小于或等于设置的离散数、交叉的字符数或子串数允许小于或等于设置的交叉数，其非完全的字符数允许小于或等于设置的非完全数。

例如：文本＝“拼音、笔划、声调组合输入法”

检索词＝“声调-拼音-笔划”

并设置离散数＝5，交叉数＝5，非完全数＝5。

通过本例的字符串匹配方法，进行离散交叉非完全检索，可以检索出“拼音、笔划、声调组合输入法”的文本。该例匹配的实际离散数为4，匹配的以字符为单位的实际交叉数为4，以子串为单位的实际交叉数为1；实际非完全数为2。其中两个中文“、”号为离散的字符，“声调”为交叉的字符，而两个西文“-”号为非完全匹配的字符。该例以字符为单位的相似度为67％，以子串为单位的相似度为77％。

以上信息检索方式中的特性参数值，用户不必每次检索都进行设置，可按上一次检索的特性参数值进行信息检索。

以上信息检索方式用户界面，用户每当修改任意一个数值框中的数值，将自动调整信息检索方式的名称。显然本例的信息检索方式的判断及显示的规则为：

若离散数＝0且交叉数＝0且非完全数＝0，则为精确检索方式；若离散数＞0且交叉数＝0且非完全数＝0，则为离散检索方式；若离散数＝0且交叉数＞0且非完全数＝0，则为交叉检索方式；若离散数＞0且交叉数＞0且非完全数＝0，则为离散交叉检索方式；若离散数＝0且交叉数＝0且非完全数＞0，则为非完全检索方式；若离散数＞0且交叉数＝0且非完全数＞0，则为离散非完全检索方式；若离散数＝0且交叉数＞0且非完全数＞0，则为交叉非完全检索方式；若离散数＞0且交叉数＞0且非完全数＞0，则为离散交叉非完全检索方式。

本例的这种判别方法及其对应的输入值，以0代表“不允许”，其检索约束条件最严格，查准率最高；大于0的整数代表检索约束条件，数值越大，检索约束条件越宽松，查全率越高。数值越小，检索条件越严格，查准率越高。它能最简单、直观的反映不同要求的信息检索，并且进行处理时最为简便、有效。

实施例二

本例的方法与实施例一的方法基本相同，不同的仅仅是B步的字符串匹配及输出的具体步骤。

图2的流程图为本例中B步的字符串匹配及输出的流程示意图，其大体流程为：a步输入特性参数合法性检验；b步循环初始化：初始化滑动窗位置为1，滑动窗大小＝检索词长度+离散数，初始化有一个头节点的OUT链；c步判定循环是否结束，如果循环结束，删除OUT链头节点，并返回OUT链，否则执行后面d步、e步、f步，当前滑动窗子串与检索词进行比较；g步计算实际离散数、实际交叉数、实际非完全数，并判定是否满足特性约束条件？如里不满足条件，则滑动窗向前移动一个字符位置，转c步；否则，执行h步根据三个实际特性参数计算相似度；i步将匹配结果组成一个新节点；若无位置重叠，新节点插入OUT链最后，否则选择新节点与OUT链最后节点中相似度大的节点，替换OUT链最后一个节点；滑动窗向前移动一个字符位置，转c步。

本例中B步的字符串匹配及输出的完整具体步骤为：

a步  输入参数合法性检验：

计算出检索词的长度m以及文本的长度n；对n、m、离散数、交叉数、非完全数，进行合法性检验，若不满足合法性，退出匹配，并返回空指针结果；否则，交叉数、非完全数不能超过m-1，若超过则改为m-1；

b步  循环初始化：

设置有一个节点的OUT链，该节点中包含如下初始信息：最大位置＝0、最小位置＝0，相似度＝1；

设置滑动窗位置＝1，表示文本中当前第一个正准备处理的位置；

对检索词＝p₁p₂……p_m中的所有字符，进行稳定的升序排序，并存储在数组PT中，数组PT中同时存储了各字符在检索词中原来的位置，分别称为数组PT中存储的字符子数组PTc以及数组PT中存储的位置子数组PTp；

从文本中的第一个字符开始，选取长度为min(m+离散数-1，n)的子串作为滑动窗子串，在该滑动窗子串前增加一个小于任何字符的特殊符号，对滑动窗子串的字符进行稳定的升序排序，并存储在数组WT中，数组WT中同时存储了各字符在文本中原有的位置，且特殊符号的位置为零，分别称为数组WT中存储的字符子数组WTc以及数组WT中存储的位置子数组WTp；min为最小值函数；

c步  判定循环是否结束：

若(n-滑动窗位置+1+非完全数)小于m，则删除OUT链首节点，退出匹配并返回OUT链；

d步  进行下一个滑动窗子串匹配的参数初始化：

滑动窗位置开始，在文本中选取长度为min(m+离散数，n-滑动窗位置+1)的子串作为滑动窗子串，再删除数组WT中最小的存储的位置以及对应的字符，然后对滑动窗子串的最后一个字符进行稳定插入排序，插入到数组WT中，若(n-滑动窗位置+1)＜(m+离散数)则不用再进行插入排序；

数组POS中全部初始化为-1，实际非完全数＝0，数组WT的位置W＝1，数组PT的位置P＝1，最大位置＝0；最小位置＝n；

e步  滑动窗子串匹配是否结束：

若数组WT比较结束或者数组PT比较结束，则转g步；

f步  滑动窗子串字符与检索词的字符进行循环比较：根据WTc中位置W存储的字符与PTc中位置P存储的字符的比较情况，分别进行以下情况处理：

若WTc中位置W存储的字符＜PTc中位置P存储的字符，则位置W增加1，转e步；

若WTp中位置W存储的字符＞PTp中位置P存储的字符，则位置P增加1，实际非完全数增加1；若实际非完全数小于或等于非完全数，则转e步，否则，滑动窗位置增加1，转c步；

若WTc中位置W存储的字符＝PTc中位置P存储的字符，则将WTp中位置W存储的数值存储到数组POS中，其存储位置为PTp中位置P存储的数值；若WTp中位置W存储的数值＞最大位置，则将WTp中位置W存储的数值存入最大位置中；若WTp中位置W存储的数值＜最小位置，则将WTp中位置W存储的数值存入最小位置中；位置W增加1，位置P增加1，转e步；

g步  判定滑动窗子串是否满足约束条件：

求实际非完全数＝(实际非完全数+m-位置P+1)；若实际非完全数＞非完全数，则滑动窗位置增加1，转c步；

求实际离散数＝(最大位置-最小位置+1-m+实际非完全数)；若实际离散数＞离散数，则滑动窗位置增加1，转c步；

计算实际交叉数；若实际交叉数＞交叉数，则滑动窗位置增加1，转c步；

h步  计算出相似度：

相似度＝(2m-2×实际非完全数-实际交叉数)÷(2m+实际离散数-实际非完全数)；

i步  将匹配结果插入OUT链：

滑动窗位置增加1；将相似度、最大位置、最小位置、数组POS、实际离散数、实际交叉数、实际非完全数组织成一个新节点；

若(新节点中的最小位置＞OUT链最后一个节点中的最大位置)则将新节点直接插入OUT链最后，转c步；

若(新节点中的最小位置小于或等于OUT链最后一个节点中的最大位置)且(新节点相似度＞OUT链最后一个节点相似度)则将新节点替换OUT链最后一个节点，转c步；否则放弃新节点，转c步。

由于在实际匹配时，文本中可能出现多个满足检索约束条件的子串，且可能存在有位置重叠的两个子字符序列，或者有位置重叠的连环多个子字符序列，将产生许多冗余的重叠信息，对此，本例的方法，对于有位置重叠的两个子字符序列，或者有位置重叠的连环多个子字符序列，在其输出的OUT链上只输出相似度大的子字符序列，使输出信息既全面又不冗余。

若返回的OUT链为空，表示不匹配，否则OUT链包含了所有匹配出的子字符序列，每个子字符序列包括：相似度、最大位置、最小位置、数组POS、实际离散数、实际交叉数、实际非完全数等匹配信息。

因此，本例的作法除具有实施例一的全部优点外，还为信息检索系统提供了一个全面、详细的检索词在指定文本中的匹配信息，为信息检索系统对检出文本的取舍给出了最完整的参考信息。

下面是本例的方法的实际检索例子及用户界面

图11为离散交叉非完全检索的用户界面，该实例的用户界面中，用“离散”对应的英文单词“Discrete”的首字母D表示离散，用“交叉”对应的英文单词“Cross”的首字母C表示交叉，用“非完全”对应的英文单词“Non complete”的首字母N表示非完全。

该种方式，离散数＞0且交叉数＞0且非完全数＞0，表示对用户提供的检索词进行离散交叉非完全检索，被检出的文本满足的条件为：检索词出现在文本中的字符，其离散的字符数允许小于或等于设置的离散数、交叉的字符数或子串数允许小于或等于设置的交叉数，其非完全的字符数允许小于或等于设置的非完全数。

实例：文本＝“声调、拼音、笔划或声调、拼音笔划声调”

检索词＝“拼音-笔划-声调”

并设置N＝5，C＝5，D＝5。

通过本例的字符串匹配方法，进行离散交叉非完全检索，可以检索出文本“声调、拼音、笔划或声调、拼音笔划声调”。该例中，存在满足约束条件的有位置重叠的连环多个子字符序列，匹配处理后OUT链输出两个无位置重叠的匹配子串：“拼音、笔划或声调”和“拼音笔划声调”。OUT链的第一个节点包含第一个匹配子串“拼音、笔划或声调”及其相关信息：该子串的的实际离散数为4，实际交叉数为0，实际非完全数为2，其中“、”和“或”为离散的字符，而两个西文“-”号为非完全匹配的字符，该例相似度为：80％。

OUT链的第二个节点包含第二个匹配子串“拼音笔划声调”及其相关信息：实际离散数为0，实际交叉数为0，实际非完全数为2，其中两个西文“-”号为非完全匹配的字符，该子串的相似度为：92％。

本发明在A步设置特性参数值并输入检索词时，用户界面可以为三种特性参数输入框的部分组合，甚至没有特性参数输入框。也即部分或所有特性参数不由用户设置而由信息处理设备自动设置，形成少于三个特性参数甚至无特性参数输入组成的用户界面，此时，未出现在用户界面中的特性参数值，为信息处理设备根据特殊用途自动设置的隐含值。这种用户界面特性参数组合方式，可适应于特殊的应用要求与环境，减少用户需要考虑的特性参数设置数目，用户只需输入检索词、更少的特性参数值即可，方便用户的操作。

例如，将非完全特性不由用户设置而由信息处理设备自动设置为0，离散、交叉特性则可由用户选择设置的用户界面。该种界面只有离散数和交叉数两个特性值，用户可以选择精确、离散、交叉、离散交叉共4种信息检索方式。如图12所示：

图12中的“X”＝“精确”或“离散”或“交叉”或“离散交叉”。

又如，将非完全及交叉特性均不由用户设置而由信息处理设备自动设置为0，离散特性则可由用户选择设置的用户界面，该种界面根据离散数参数值，用户可以选择精确和离散2种信息检索方式。如图13所示：

图13中的“X”＝“精确”或“离散”。

再如，将非完全数由信息处理设备自动设置为(m/10的四舍五入整数值)，其中m为检索词的长度；交叉数由信息处理设备自动设置为(m/5的四舍五入整数值)；离散特性则可由用户选择设置的用户界面。该种界面根据设置的离散数、交叉数、非完全数值，可得到6种信息检索方式。用户界面如图13所示：

图13中的“X”＝如下6种信息检索名称之一：

当输入的检索词长度小于等于2，计算出非完全数＝0、交叉数＝0。若用户设置离散数＝0，则进行精确检索；若用户设置离散数＝3，则进行离散检索。

当输入的检索词长度为4，计算出非完全数＝0、交叉数＝1。若用户设置离散数＝0，则进行交叉检索；若用户设置离散数＝5，则进行离散交叉检索。

当输入的检索词长度大于等于5，计算出非完全数≥1、交叉数≥1。若用户设置离散数＝0，则进行交叉非完全检索；若用户设置离散数＝5，则进行离散交叉非完全检索。

这种交叉数、非完全数的信息处理设备自动设置方式，实现了这样一种信息检索操作理念：检索词越长，信息处理设备自动设置的交叉数、非完全数越大，检索匹配中允许的交叉、非完全字符越多；检索词越短，信息处理设备自动设置的交叉数、非完全数越小，检索匹配中允许的交叉、非完全字符越少。这种设置方式，更好地保证了检出文本的检出质量与定位精度。

这种信息处理设备自动设置的处理方法，符合大众的操作理念、习惯、要求，如同傻瓜相机、无级变速轿车的操作理念；而三种特性全部出现在用户界面中，由用户有选择地进行特性参数设置的操作理念，如同专业相机、多级变速轿车的操作理念。

以上用户界面中的特性参数名称，以及信息检索方式名称，在具体实施时，还可规定其它文字符号替代。

本发明用于信息检索的字符串匹配方法、数值输入框、数值的大小，相应地影响到信息检索的检索性能、检索方式以及提供多大约束的检索。

本发明充分考虑了信息检索功能的扩展，以及用户对信息检索操作上的需求：用户通过任意选择三种特性参数的数值框，输入不同的数值，即可选择8种检索方式之一，进行不同性质、满足不同约束要求的信息检索。本发明操作简单、灵活、方便，并且在功能上为查全、查准、定位精确提供了灵活多样的应对手段和方法，可以进行定性、定量检索。

本发明的基于三种特性的字符串匹配方法，应用于信息检索领域，如各种语言的网络信息搜索、网站内检索、数据库检索、电子词典、数据查询、信息输入、操作系统文件名检索等。不仅如此，在生物技术领域也有其用武之地：DNA匹配是目前遗传基因研究中的重要课题，基于特性的字符串匹配方法，以其灵活、方便、多样的定性、定量匹配功能，同样能够适应于DNA匹配的要求，进行DNA序列的定性、定量匹配分析。