[go: up one dir, main page]

CN101030216A - 基于特性参数的字符串匹配方法 - Google Patents

基于特性参数的字符串匹配方法 Download PDF

Info

Publication number
CN101030216A
CN101030216A CNA2007100487900A CN200710048790A CN101030216A CN 101030216 A CN101030216 A CN 101030216A CN A2007100487900 A CNA2007100487900 A CN A2007100487900A CN 200710048790 A CN200710048790 A CN 200710048790A CN 101030216 A CN101030216 A CN 101030216A
Authority
CN
China
Prior art keywords
character
array
text
term
influence
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CNA2007100487900A
Other languages
English (en)
Inventor
丁光耀
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Priority to CNA2007100487900A priority Critical patent/CN101030216A/zh
Publication of CN101030216A publication Critical patent/CN101030216A/zh
Priority to PCT/CN2008/070603 priority patent/WO2008119297A1/zh
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90344—Query processing by using string matching techniques

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明公开了一种基于特性参数的字符串匹配方法，给定存储于存储设备中的一个文本以及输入设备输入的检索词。特性参数包括：离散数，交叉数，非完全数。特性参数的字符串匹配方法的主要步骤为：计算文本与检索词中字符的匹配关系；根据文本与检索词中字符的匹配关系计算特性参数；根据特性参数、文本与检索词的长度计算特性匹配度；返回特性匹配度。该方法还考虑了认知权值对特性匹配度的影响。该种方法提供了极强的检索容错能力，检索结果的排序输出更为合理；操作简单、灵活、方便，适合词典检索。

Description

基于特性参数的字符串匹配方法
                        技术领域
本发明涉及一种字符串匹配方法，具体来讲，涉及一种基于特性参数的字符串匹配方法。
                        背景技术
词典检索是字符串匹配技术最为基本的应用。现有的词典检索产品的检索技术分为两类：基于精确匹配的检索技术，以及基于非精确匹配的检索技术。精确匹配检索技术不能容错；而非精确匹配的检索技术，允许用户输入中出现少量的错误，因此有较高的应用价值。
四十年来，国内外对非精确字符串匹配的方法研究一直采用基于错误因素的距离计算，最常用的是Levenshtein距离以及ED(Edit Distance)距离，影响距离结果的错误因素主要包括插入错误、删除错误、替换错误、交换错误等。这种基于错误因素距离计算方法，存在一些固有问题，造成了词典检索结果过于笼统且容错能力有限，问题主要体现在以下几点：
1)、现有的基于错误因素距离计算的非精确字符串匹配研究思路，是一种基于问题现象的研究思路，如插入、删除、替换、交换、反向错误等。这些错误现象并非完全独立、可以严格界定，呈现出多样化特征，是典型的问题现象。例如，本质上可以用一个插入错误和一个删除错误定性地表示一个替换错误，用一个插入错误和一个删除错误定性地表示一个交换错误。因此，某些错误因素并非独立概念，字符串匹配至今没有形成科学的分类体系，这是其中的重要原因之一。
2)、现有的基于错误因素描述字符串匹配问题的多态性，直接影响到字符串匹配结果以及检索结果的排序。表1反映出基于错误因素对特定问题的错误现象进行描述的多态性。
  文本   检索词   基于错误因素描述
  ABCDEFGH   ABCDEFGH  精确匹配(即子串匹配)：不允许删除、插入、交换等错误
  AB CDEFGH   CDEF  精确匹配(即子串匹配)：允许前面、后面的删除
  AB CDE FGH   CDF  非精确匹配：1、存在一个删除(E)；或2、存在若干前面、后面删除，并且存在一个中间删除(E)；或3、存在一个插入(F)；或4、存在一个替换(E，F)；等
  AB CDEFGH   CEDF  非精确匹配：1、存在一个交换(DE，ED)；或2、存在两个替换(D，E)，(E，D)；或3、存在一个插入(D)和一个删除(D)；等
  AB CDEFGH   CEFD  非精确匹配：1、存在一个删除(D)和一个插入(D)；或2、存在两个插入(C)，(D)；或3、存在两个插入(E)，(F)；等
  AB CD EFGH   ACEFXD  非精确匹配：1、存在两个删除(B)，(D)和两个插入(X)，(D)；或2、存在两个删除(B)，(D)和两个替换(G，X)，(H，D)；等
                            表1
表1中，忽略距离计算的量化影响，基于错误因素对特定文本与检索词的匹配问题，存在多种基于错误因素的定性表示方法，反映出描述同一问题的多态性，不便于分类处理。
3)、基于错误因素距离计算的非精确字符串匹配方法，由于通过距离计算对各种错误因素进行统一量化处理，如ED(Edit Distance)距离计算，使得匹配中不同错误因素的性质模糊化，距离反映出的匹配结果过于笼统。例如距离为2，即可表示含有两个插入错误，也可表示含有2个删除错误，或者两个替换错误，或者2个混合的错误。而错误因素概念的非独立性，以及匹配中的错误性质的不确定性，又使得不能根据错误因素将匹配状况进一步细化表示。因此，词典检索中，在计算匹配度时，缺少准确的匹配状况的更为细致的参数依据，不利于检出结果的合理排序。
4)、现有的词典检索，很少从心理学、认知学、语言学、行为学的角度，讨论对词典检索的影响。实际上，每一个字符，根据在单词中的位置、发音、视觉等因素，存在不同程度的认知差异，有些字符容易记住，而有些字符则不易记住，或者随着时间的推移而逐渐淡化，这也是造成非精确输入的主要原因。因此检索中，应考虑各字符在单词中的认知差异对词典检索结果的影响。
以上问题，呈现出字符串匹配基础体系的不健全、不完善，直接影响到词典检索结果的合理排序，容错能力有限，匹配方法的多样性，但却难以展开综合应用，亟待解决。
                          发明内容
本发明的目的在于克服上述现有技术中的不足，提供一种检索结果排序更为合理、具有很强的容错能力的基于特性参数的字符串匹配方法。
为实现上述发明目的，本发明的一种基于特性参数的字符串匹配方法，给定存储于存储设备中的一个文本，以及输入设备输入的检索词，其特征在于，信息处理设备对给定的文本与检索词进行基于特性参数的字符串匹配，步骤为：
A步)、计算文本与检索词中字符的匹配关系；
B步)、根据文本与检索词中字符的匹配关系计算特性参数，特性参数包括反映检索词各字符出现在文本中的离散的字符数的离散数，反映检索词各字符出现在文本中的交叉的字符数的交叉数，反映检索词各字符未出现在文本中的字符数的非完全数；
C步)、根据特性参数、文本与检索词的长度计算特性匹配度；
D步)、输出特性匹配度。
与现有技术相比，本发明的有益效果是：
一、通过表2，现有基于错误因素及本发明基于三种特性的描述差异表的示例比较，得到清楚的说明。
  文本   检索词   现有基于错误因素的描   本发明基于三种特性
 述   的描述
  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)；或   交叉匹配：只存在一个交叉(D)
 3、存在两个插入(E)，(F)等
  ABCDEFGH   ACEFXD  非精确匹配：1、存在两个删除(B)，(D)和两个插入(X)，(D)；或2、在两个删除(B)，(D)和两个替换(G，X)，(H，D)；等  离散交叉非完全匹配：存在一个离散(B)、一个交叉(D)、一个非完全(X)
                         表2
可见，现有基于错误因素对特定文本与检索词的字符串匹配问题，存在多种基于错误因素的描述方法，反映出描述同一问题的多态性，不便于细致的分类处理。而采用本发明的三种特性对同一问题只存在一种描述方法，准确地反映了文本与检索词的字符对应。
表2中关于两个子串匹配问题，现有基于错误因素有两种不同的描述方法；本发明对两个子串匹配问题，只存在一种描述方法，更为符合子串的定义。
通过上表对比，还可以清楚地了解到离散特性与删除错误的差异，交叉特性与交换错误的差异，非完全性与插入错误的差异。
本发明采用的三种特性参数，即离散性、交叉性、非完全性，互相间具有完全不同的概念和性质，是互为独立的特性。错误因素是三种特性的外在表现，基于三种特性参数的字符串匹配研究思路，更为科学地揭示了字符串匹配问题的内在规律。
二、现有的错误因素概念的非独立性，以及匹配中的错误性质的不确定性，使得不能根据错误因素将匹配状况进一步细化表示。因此，词典检索中，在计算匹配度时，缺少准确的匹配状况的更为细致的参数依据，不利于检出结果的合理排序。
而本发明采用的三种特性参数：离散性、交叉性、非完全性，互相间具有完全不同的概念和性质，是互为独立的特性。通过三种特性参数计算特性匹配度，可以分别考虑三种特性对特性匹配度的影响，使得计算出的特性匹配度更精确地反映文本与检索词的相似程度。因此，依据本发明得到的特性匹配度，对词典单词所有的匹配结果的排序输出更为合理，容错能力大大提高，克服了基于错误因素距离计算结果过于笼统、不利于匹配度的综合计算的缺陷。
                      具体实施方式
下面结合具体实施方式，对本发明基于特性参数的字符串匹配方法作进一步详细的说明。
电子英文词典是由英文单词构成的电子词典库。电子英文词典检索是指：根据输入的英文单词，即检索词P，对电子英文词典库中的每一个单词，即文本T，进行字符串匹配运算，并根据匹配结果，对满足条件的单词排序输出，方便用户的选择。
电子英文词典的核心技术就是字符串匹配，其匹配结果直接影响到所有检出单词的最终排序位置，也是衡量电子英文词典检索效果的重要指标。
在本实施方式中，给定存储于存储设备中的一个文本为T＝“t1t2…tn”，以及输入设备输入的检索词为P＝“p1p2…pm”，其中ti、pj(1≤i≤n，1≤j≤m)为字符，m、n均大于零，所述A步的计算文本与检索词中字符的匹配关系的具体步骤为：
a步)、稳定排序检索词P
对检索词P＝“p1p2……pm”中的所有字符，进行稳定的升序排序，并存储在内存中数组PT中，数组PT中同时存储了各字符在检索词中原来的位置，分别称为数组PT中存储的字符子数组PTc以及数组PT中存储的位置子数组PTp；
b步)、稳定排序文本T
对文本T＝“t1t2……tn”中的所有字符，进行稳定的升序排序，并存储在内存中数组WT中，数组WT中同时存储了各字符在文本中原有的位置，分别称为数组WT中存储的字符子数组WTc以及数组WT中存储的位置子数组WTp；
c步)、参数初始化
内存中数组POS用于存储字符对应位置，全部初始化为-1，非完全数＝0，数组WT的位置W＝1，数组PT的位置P＝1，最大位置＝0，最小位置＝n；
d步)、循环是否结束
若数组WT比较结束或者数组PT比较结束，则转f步；
e步)、比较
根据WTc中位置W存储的字符与PTc中位置P存储的字符的比较情况，分别进行以下情况处理：
若WTc中位置W存储的字符＜PTc中位置P存储的字符，则位置W增加1，转d步；
若WTp中位置W存储的字符＞PTp中位置P存储的字符，则位置P增加1，非完全数增加1，转d步；
若WTc中位置W存储的字符＝PTc中位置P存储的字符，则将WTp中位置W存储的数值存储到数组POS中，其存储位置为PTp中位置P存储的数值；若WTp中位置W存储的数值＞最大位置，则将WTp中位置W存储的数值存入最大位置中；若WTp中位置W存储的数值＜最小位置，则将WTp中位置W存储的数值存入最小位置中；位置W增加1，位置P增加1，转d步；
f步)、结束
得到代表文本与检索词中字符的匹配关系的数组POS、最大位置、最小位置、位置P以及非完全数。
这种有序化文本与检索词，计算字符匹配关系的方法，可提高计算速度。
时间复杂度为：O(k×log2k)，k＝Max(m，n)；
在另一具体实施方式中，在前一具体实施方式的基础上，所述B步的根据文本与检索词中字符的匹配关系计算特性参数的步骤为：
a步)、非完全数＝(非完全数+m-位置P+1)；
b步)、离散数＝(最大位置-最小位置+1-m+非完全数)；
c步)、交叉数＝根据数组POS结果进行交叉数计算。
前述交叉数计算的步骤可以为：
(1)、求最大可间隔升序序列的长度；
(2)、交叉数＝m-非完全数-最大可间隔升序序列的长度。
前述求最大可间隔升序序列的长度的步骤可以为：
(1)、初始化
依次将数组POS中大于零的全部数值存入内存中的临时数组中，临时数组最后添加一个结束标志；若临时数组中的元素个数等于0，直接返回最大可间隔升序序列的长度等于0的结果；若临时数组中的元素个数等于1，直接返回最大可间隔升序序列的长度等于1的结果；否则，用内存中数组LPOS存放最大可间隔升序序列，且数组LPOS的第一个位置的数值初始化为临时数组中第一个数值；LP用于指示当前数组LPOS处理的位置，并初始化为1；取临时数组中第二个数值到比较数据中；
(2)、判断是否结束
若比较数据为结束标记，转(4)步；
(3)、根据比较进行两种情况处理
若比较数据大于数组LPOS中LP位置的数据，则LP增加1，将比较数据存储到数组LPOS中LP位置处，取临时数组中下一个数值到比较数据中，转(2)步；
若比较数据小于数组LPOS中LP位置的数据，则从数组LPOS中第一个位置向后进行折半查找，搜索第一个大于比较数据的数据，并用比较数据改写该数据；取临时数组中下一个数值到比较数据中，转(2)步；
(4)、最大可间隔升序序列的长度＝LP。
数组POS在匹配过程中，用于存放检索词中已经匹配的字符在文本中的出现位置，数组POS中数据的特点是：除数值-1以外，其它数据均为大于0的整数，且互不相等。由于数值-1代表了未匹配的字符，因此数值-1不计入最大可间隔升序序列中。
数组POS的最大可间隔升序序列的长度是指：按数组POS中数据的大小，在数组POS寻找出一个最大可间隔升序序列，该序列的数据个数即为最大可间隔升序序列的长度。
最大可间隔升序序列以及长度的严格定义如下：
定义：设任意序列a1a2……an(ai≠aj)，每个元素可比较，若存在最大的子序列ak1ak2……akm满足
1、1≤k1＜k2＜……＜km≤n且
2、ak1＜ak2＜……＜akm
则称子序列ak1ak2……akm为序列a1a2……an的最大可间隔升序序列，元数个数m为其长度。
例如7，8，9，1，2，6，3，4，12
最大可间隔升序序列：1，2，3，4，12；
最大可间隔升序序列长度：5
通过最大可间隔升序序列的长度，即可求出文本与检索词匹配时的交叉数。交叉数的作用是配合离散数、非完全数计算特性匹配度，方便检出文本的排序，满足用户的检索要求。
该算法的时间复杂度为：O(mlog2(m))。
在另一具体实施方式中，在前述A步、B步具体实施方式的基础上，所述C步的根据特性参数、文本与检索词的长度计算特性匹配度的步骤为：
a步)、计算检索词与文本的实际匹配字符的相关字符数
相关字符数＝2×(m-非完全数)；
b步)、计算特性参数对特性匹配度的影响因子1
影响因子1＝k1×交叉数；
c步)、计算特性参数对特性匹配度的影响因子2
影响因子2＝q1×非完全数+q2×交叉数+q3×离散数；
d步)、计算特性匹配度
特性匹配度＝(相关字符数-影响因子1)÷(m+n+影响因子2)；
其中，k1、q1、q2、q3是各特性参数在特性匹配度中的权重系数，k1为大于等于零且小于等于2的实数，q1、q2、q3为大于等于零的实数，权重系数k1、q1、q2、q3，可根据不同产品、不同应用场合选择不同的数值，从而影响检索出的文本的特性匹配度，并影响检索出的文本的排序。在一种具体应用中，权重系数k1、q1、q2、q3的值为k1＝2/3、q1＝1、q2＝2/3、q3＝1/3。
影响因子的引入，目的在于根据不同产品，不同应用环境，综合考虑不同特性参数对特性匹配度的影响权重，从而使得检索结果的排序更为符合特殊环境应用的用户要求。
在本实施例中，该特性匹配度为满足大于等于零且小于等于1的实数。
实例一
下面是依据上述A、B、C步具体实施方式的方法具体设计的电子英文词典库检索实例的检索结果与特点。
本实例的电子英文词典库，选择了六千个常用英语单词；权重系数k1、q1、q2、q3选择为：k1＝2/3、q1＝1、q2＝2/3、q3＝1/3；检索结果按计算出的特性匹配度降序排列，只输出前五个单词。
1、离散检索
输入英文单词时可以任意省略单词中的字符。
例如：目标单词为：“wonderful”
输入字符为：“wdfl”
检索结果为：1wonderful   2handful   3unfold   4wind   5windy
特性匹配度：0.546        0.487      0.444     0.375   0.343
2、交叉检索
输入英文单词时可以任意交叉单词中的字符。
例如：目标单词为：“what”
输入字符为：“whta”
检索结果为：1what    2wheat   3watch   4hat     5white
特性匹配度：0.846    0.733    0.625    0.615    0.581
3、允许非完全字符
输入英文单词时，允许出现错误字符。
例如：目标单词为：“error”
输入字符为：“irror”
检索结果为：1mirror  2error   3terror  4terrorist   5territory
特性匹配度：0.909    0.727    0.667    0.636        0.622
4、综合示例
输入英文单词时，可以离散、交叉、非完全混合。
例如：目标单词为：“marvelous”
输入字符为：“mvrilus”
检索结果为：1marvelous   2various   3survival   4minus   5visual
特性匹配度：0.607        0.600      0.536       0.522    0.520
其中输入时，省略了a、e、o，有一个错误字符i，有一个交叉(v，r)。
5、特殊示例
例如：目标单词为：“marvelous”
输入字符为：“mrxxxxxxlus”
检索结果为：1marvelous   2muscular    3marxist   4marxism   5luxurious
特性匹配度：0.366        0.317        0.312      0.312      0.302
在另一具体实施方式中，本发明的一种基于特性参数的字符串匹配方法，所述的文本T＝“t1t2…tn”中的每一个字符，对应存储了一个认知权值w，组成了文本的认知权值系列W＝“w1w2…wn”，且满足w1+w2+…+wn＝1，认知权值wi(1≤i≤n)代表了字符在文本“t1t2…tn”中被认知的概率；
前述在A步、B步具体实施方式的基础上，所述的所述C步的根据特性参数、文本与检索词的长度计算特性匹配度的步骤为：
a步)、计算检索词与文本的实际匹配字符的相关字符数
相关字符数＝2×(m-非完全数)；
b步)、计算特性参数对特性匹配度的影响因子1
影响因子1＝k1×交叉数；
c步)、计算特性参数对特性匹配度的影响因子2
影响因子2＝q1×非完全数+q2×交叉数+q3×离散数；
d步)、计算文本中已匹配字符的认知权值之和
根据数组POS中已匹配文本字符的位置，求出所有已匹配字符的认知权值之和；
e步)、特性匹配度＝[(相关字符数-影响因子1)÷(m+n+影响因子2)]×认知权值之和。
其中，k1、q1、q2、q3是各特性参数在特性匹配度中的权重系数，k1为大于等于零且小于等于2的实数，q1、q2、q3为大于等于零的实数，权重系数k1、q1、q2、q3，可根据不同产品、不同应用场合选择不同的数值，从而影响检索出的文本的特性匹配度，并影响检索出的文本的排序。
影响因子的引入，目的在于根据不同产品，不同应用环境，综合考虑不同特性参数对特性匹配度的影响权重，从而使得检索结果的排序更为符合特殊环境应用的用户要求。
上述增加认知权值对特性匹配度的影响方法，是对特性匹配度计算的一种改进，符合人们对特殊符号的实际认知差异，综合了心理学、行为学、语言学、统计学等多学科的认知思想，尤其适应于词典检索。强化了容易认知的字符的权重，淡化了容易出错的字符的权重，由此计算出的特性匹配度，其检出结果的排序更符合用户的要求。
决定认知权值的主要因素有：
1)字符是否单词的第一个位置；
2)字符是否为发音各音节的首字符；
3)字符在音节的发音中是否规范，或者是否作用明显；
4)字符在单词中视觉是否明显；
5)字符是否为单词中的字符等。
实例二
根据前述有认知权值的基于特性参数的字符串匹配方法的具体实施方式，本实例增加为有认知权值的电子英文词典检索。电子英文词典是由英文单词以及认知权值构成的电子词典库。
本实例二的方法与实例一的方法基本相同，不同的仅仅是文本T中的每一个字符，对应存储了一个认知权值，增加了认知权值对计算特性匹配度的影响。
下面是计算认知权值的一种方法：
1、字符是否单词的第一个位置，分值0.4；
2、字符是否为发音各音节的首字符，分值0.3；
3、字符在音节的发音中是否规范或者是否作用明显，分值0.1；
4、字符在单词中视觉是否明显，分值0.2；
5、是单词中的字符，分值1。
例如：考虑英语单词“what”。
字符w满足1、2、3、4、5，   字符w分值＝2；
字符h满足4、5，            字符h分值＝1.2；
字符a满足3、5，            字符a分值＝1.1；
字符t满足2、3、4、5，      字符w分值＝1.6。
英语单词“what”的总分值为5.9，各字符的认知权值为：
w的认知权值＝w分值/“what”总分值＝2/5.9；
h的认知权值＝h分值/“what”总分值＝1.2/5.9；
a的认知权值＝a分值/“what”总分值＝1.1/5.9；
t的认知权值＝t分值/“what”总分值＝1.6/5.9；
最后得到英语单词“what”的认知权值序列：2/5.9，1.2/5.9，1.1/5.9，1.6/5.9。
通过上述具体实施方式，我们可以看出，与现有基于错误因素的距离计算相比较，本发明计算特性匹配度的每一个特性参数的概念独立，计算出的特性参数，更为细致地反映了文本与检索词在各特性参数上的差异。因此根据三个特性参数计算出的特性匹配度，能更为合理地反映匹配状况，在词典检索结果的排序上更加符合用户的实际需求。
同时，我们还可以看出，本发明的基于特性参数的字符串匹配方法，具有极强的容错检索能力，适应于词典检索。
尽管上面对本发明说明性的具体实施方式进行了描述，但应当清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。

Claims (8)

1、一种基于特性参数的字符串匹配方法，给定存储于存储设备中的一个文本，以及输入设备输入的检索词，其特征在于，信息处理设备对给定的文本与检索词进行基于特性参数的字符串匹配，步骤为：
A步)、计算文本与检索词中字符的匹配关系；
B步)、根据文本与检索词中字符的匹配关系计算特性参数，特性参数包括反映检索词各字符出现在文本中的离散的字符数的离散数，反映检索词各字符出现在文本中的交叉的字符数的交叉数，反映检索词各字符未出现在文本中的字符数的非完全数；
C步)、根据特性参数、文本与检索词的长度计算特性匹配度；
D步)、输出特性匹配度。
2、根据权利要求1所述的一种基于特性参数的字符串匹配方法，给定存储于存储设备中的一个文本为T＝“t1t2…tn”，以及输入设备输入的检索词为P＝“p1p2…pm”，其中ti、pj(1≤i≤n，1≤j≤m)为字符，m、n均大于零，其特征在于，所述A步的计算文本与检索词中字符的匹配关系的具体步骤为：
a步)、稳定排序检索词P
对检索词P＝“p1p2……pm”中的所有字符，进行稳定的升序排序，并存储在内存中数组PT中，数组PT中同时存储了各字符在检索词中原来的位置，分别称为数组PT中存储的字符子数组PTc以及数组PT中存储的位置子数组PTp；
b步)、稳定排序文本T
对文本T＝“t1t2……tn”中的所有字符，进行稳定的升序排序，并存储在内存中数组WT中，数组WT中同时存储了各字符在文本中原有的位置，分别称为数组WT中存储的字符子数组WTc以及数组WT中存储的位置子数组WTp；
c步)、参数初始化
内存中数组POS用于存储字符对应位置，全部初始化为-1，非完全数＝0，数组WT的位置W＝1，数组PT的位置P＝1，最大位置＝0，最小位置＝n；
d步)、循环是否结束
若数组WT比较结束或者数组PT比较结束，则转f步；
e步)、比较
根据WTc中位置W存储的字符与PTc中位置P存储的字符的比较情况，分别进行以下情况处理：
若WTc中位置W存储的字符＜PTc中位置P存储的字符，则位置W增加1，转d步；
若WTp中位置W存储的字符＞PTp中位置P存储的字符，则位置P增加1，非完全数增加1，转d步；
若WTc中位置W存储的字符＝PTc中位置P存储的字符，则将WTp中位置W存储的数值存储到数组POS中，其存储位置为PTp中位置P存储的数值；若WTp中位置W存储的数值＞最大位置，则将WTp中位置W存储的数值存入最大位置中；若WTp中位置W存储的数值＜最小位置，则将WTp中位置W存储的数值存入最小位置中；位置W增加1，位置P增加1，转d步；
f步)、结束
得到代表文本与检索词中字符的匹配关系的数组POS、最大位置、最小位置、位置P以及非完全数。
3、根据权利要求2所述的一种基于特性参数的字符串匹配方法，其特征在于，所述B步的根据文本与检索词中字符的匹配关系计算特性参数的步骤为：
a步)、非完全数＝(非完全数+m-位置P+1)；
b步)、离散数＝(最大位置-最小位置+1-m+非完全数)；
c步)、交叉数＝根据数组POS结果进行交叉数计算。
4、根据权利要求3所述的一种基于特性参数的字符串匹配方法，其特征在于，所述C步的根据特性参数、文本与检索词的长度计算特性匹配度的步骤为：
a步)、计算检索词与文本的实际匹配字符的相关字符数
相关字符数＝2×(m-非完全数)；
b步)、计算特性参数对特性匹配度的影响因子1
影响因子1＝k1×交叉数；
c步)、计算特性参数对特性匹配度的影响因子2
影响因子2＝q1×非完全数+q2×交叉数+q3×离散数；
d步)、计算特性匹配度
特性匹配度＝(相关字符数-影响因子1)÷(m+n+影响因子2)；
其中，k1、q1、q2、q3是各特性参数在特性匹配度中的权重系数，k1为大于等于零且小于等于2的实数，q1、q2、q3为大于等于零的实数，权重系数k1、q1、q2、q3，可根据不同产品、不同应用场合选择不同的数值，从而影响检索出的文本的特性匹配度，并影响检索出的文本的排序。
5、根据权利要求4所述的一种基于特性参数的字符串匹配方法，其特征在于，所述的权重系数k1、q1、q2、q3的值为k1＝2/3、q1＝1、q2＝2/3、q3＝1/3。
6、根据权利要求3所述的一种基于特性参数的字符串匹配方法，其特征在于，交叉数计算的步骤为：
(1)、求最大可间隔升序序列的长度；
(2)、交叉数＝m-非完全数-最大可间隔升序序列的长度。
7、根据权利要求6所述的一种基于特性参数的字符串匹配方法，其特征在于，求最大可间隔升序序列的长度的步骤为：
(1)、初始化
依次将数组POS中大于零的全部数值存入内存中的临时数组中，临时数组最后添加一个结束标志；若临时数组中的元素个数等于0，直接返回最大可间隔升序序列的长度等于0的结果；若临时数组中的元素个数等于1，直接返回最大可间隔升序序列的长度等于1的结果；否则，用内存中数组LPOS存放最大可间隔升序序列，且数组LPOS的第一个位置的数值初始化为临时数组中第一个数值；LP用于指示当前数组LPOS处理的位置，并初始化为1；取临时数组中第二个数值到比较数据中；
(2)、判断是否结束
若比较数据为结束标记，转(4)步；
(3)、根据比较进行两种情况处理
若比较数据大于数组LPOS中LP位置的数据，则LP增加1，将比较数据存储到数组LPOS中LP位置处，取临时数组中下一个数值到比较数据中，转(2)步；
若比较数据小于数组LPOS中LP位置的数据，则从数组LPOS中第一个位置向后进行折半查找，搜索第一个大于比较数据的数据，并用比较数据改写该数据；取临时数组中下一个数值到比较数据中，转(2)步；
(4)、最大可间隔升序序列的长度＝LP。
8、根据权利要求3所述的一种基于特性参数的字符串匹配方法，其特征在于，所述的文本T＝“t1t2…tn”中的每一个字符，对应存储了一个认知权值w，组成了文本的认知权值系列W＝“w1w2…wn”，且满足w1+w2+…+wn＝1，认知权值wi(1≤i≤n)代表了字符在文本“t1t2…tn”中被认知的概率；
所述的C步的根据特性参数、文本与检索词的长度计算特性匹配度的步骤为：
a步)、计算检索词与文本的实际匹配字符的相关字符数
相关字符数＝2×(m-非完全数)；
b步)、计算特性参数对特性匹配度的影响因子1
影响因子1＝k1×交叉数；
c步)、计算特性参数对特性匹配度的影响因子2
影响因子2＝q1×非完全数+q2×交叉数+q3×离散数；
d步)、计算文本中已匹配字符的认知权值之和
根据数组POS中已匹配文本字符的位置，求出所有已匹配字符的认知权值之和；
e步)、特性匹配度＝[(相关字符数-影响因子1)÷(m+n+影响因子2)]×认知权值之和。
其中，k1、q1、q2、q3是各特性参数在特性匹配度中的权重系数，k1为大于等于零且小于等于2的实数，q1、q2、q3为大于等于零的实数，权重系数k1、q1、q2、q3，可根据不同产品、不同应用场合选择不同的数值，从而影响检索出的文本的特性匹配度，并影响检索出的文本的排序。
CNA2007100487900A 2007-04-02 2007-04-02 基于特性参数的字符串匹配方法 Pending CN101030216A (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
CNA2007100487900A CN101030216A (zh) 2007-04-02 2007-04-02 基于特性参数的字符串匹配方法
PCT/CN2008/070603 WO2008119297A1 (fr) 2007-04-02 2008-03-27 Procédé pour rechercher une chaîne de caractères selon des paramètres caractéristiques

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CNA2007100487900A CN101030216A (zh) 2007-04-02 2007-04-02 基于特性参数的字符串匹配方法

Publications (1)

Publication Number Publication Date
CN101030216A true CN101030216A (zh) 2007-09-05

Family

ID=38715562

Family Applications (1)

Application Number Title Priority Date Filing Date
CNA2007100487900A Pending CN101030216A (zh) 2007-04-02 2007-04-02 基于特性参数的字符串匹配方法

Country Status (2)

Country Link
CN (1) CN101030216A (zh)
WO (1) WO2008119297A1 (zh)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2008119297A1 (fr) * 2007-04-02 2008-10-09 Guangyao Ding Procédé pour rechercher une chaîne de caractères selon des paramètres caractéristiques
CN102184195A (zh) * 2011-04-20 2011-09-14 北京百度网讯科技有限公司 用于获取字符串间相似度的方法、装置和设备
CN102682033A (zh) * 2011-03-17 2012-09-19 环达电脑(上海)有限公司 通过二进制特征值匹配以查询文字的方法
CN101345957B (zh) * 2008-08-20 2013-01-09 宇龙计算机通信科技(深圳)有限公司 一种登录密码的识别方法、系统和移动终端
CN107239500A (zh) * 2017-05-03 2017-10-10 成都国腾实业集团有限公司 一种字符串匹配方法及系统
CN112182313A (zh) * 2020-09-30 2021-01-05 国网青海省电力公司 一种继电保护定值名称匹配方法、系统
CN112508845A (zh) * 2020-10-15 2021-03-16 福州大学 基于深度学习的osd菜单语言自动化检测方法及系统

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1158460A (zh) * 1996-12-31 1997-09-03 复旦大学 一种跨语种语料自动分类与检索方法
JP3924899B2 (ja) * 1998-02-20 2007-06-06 富士ゼロックス株式会社 テキスト検索装置およびテキスト検索方法
CN1392497A (zh) * 2002-07-24 2003-01-22 彭泉 大字符串匹配方法
CN1916896A (zh) * 2006-09-08 2007-02-21 丁光耀 基于离散性、交叉性、非完全性的字符串模式匹配方法
CN101030216A (zh) * 2007-04-02 2007-09-05 丁光耀 基于特性参数的字符串匹配方法

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2008119297A1 (fr) * 2007-04-02 2008-10-09 Guangyao Ding Procédé pour rechercher une chaîne de caractères selon des paramètres caractéristiques
CN101345957B (zh) * 2008-08-20 2013-01-09 宇龙计算机通信科技(深圳)有限公司 一种登录密码的识别方法、系统和移动终端
CN102682033A (zh) * 2011-03-17 2012-09-19 环达电脑(上海)有限公司 通过二进制特征值匹配以查询文字的方法
CN102184195A (zh) * 2011-04-20 2011-09-14 北京百度网讯科技有限公司 用于获取字符串间相似度的方法、装置和设备
CN102184195B (zh) * 2011-04-20 2014-01-08 北京百度网讯科技有限公司 用于获取字符串间相似度的方法、装置和设备
CN107239500A (zh) * 2017-05-03 2017-10-10 成都国腾实业集团有限公司 一种字符串匹配方法及系统
CN112182313A (zh) * 2020-09-30 2021-01-05 国网青海省电力公司 一种继电保护定值名称匹配方法、系统
CN112508845A (zh) * 2020-10-15 2021-03-16 福州大学 基于深度学习的osd菜单语言自动化检测方法及系统

Also Published As

Publication number Publication date
WO2008119297A1 (fr) 2008-10-09

Similar Documents

Publication Publication Date Title
CN101030216A (zh) 基于特性参数的字符串匹配方法
CN1174332C (zh) 转换表达方式的方法和装置
CN1171162C (zh) 基于字符分类检索字符串的装置和方法
CN1281191A (zh) 信息检索方法和信息检索装置
CN1158627C (zh) 用于字符识别的方法和装置
CN1489089A (zh) 文件检索系统和问题回答系统
CN100337407C (zh) 对结构化文档进行编码和解码的方法和系统
CN1251128C (zh) 文字列匹配装置和文字列匹配方法
CN1193779A (zh) 中文语句分词方法及其在中文查错系统中的应用
CN1728140A (zh) 信息检索系统中基于短语的索引编制
CN1211769A (zh) 基于贝叶斯网络的用于文件检索的方法和设备
CN1781093A (zh) 用于存储和访问互锁树数据仓库中的数据的系统和方法
CN1172994A (zh) 文件检索系统
CN1777888A (zh) 基于移动结构概念的句子结构分析及使用其的自然语言搜索
CN1215457C (zh) 语句识别装置和方法
CN1591428A (zh) 提供元数据索引的方法
CN101055588A (zh) 获取限制词信息的方法、优化输出的方法和输入法系统
CN1170908A (zh) 检索相关超文本文件的超文本文件检索装置
CN1177407A (zh) 基于速度的手写体识别方法和系统
CN1409842A (zh) 模式匹配方法和装置
CN1135060A (zh) 语言处理装置和方法
CN1855103A (zh) 特定元素、字符串向量生成及相似性计算的装置、方法
CN1156779C (zh) 文献检索的方法和装置
CN1647069A (zh) 对话控制系统和对话控制方法
CN1111841C (zh) 在语言识别中通过计算机来确定至少两个单词的序列出现概率的方法

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C12 Rejection of a patent application after its publication
RJ01 Rejection of invention patent application after publication