(19)中华人民共和国国家知识产权局
(12)发明专利说明书 | ||
(10)申请公布号 CN 101025750 A (43)申请公布日 2007.08.29 | ||
(21)申请号 CN200710006052.X
(22)申请日 2007.01.24
(71)申请人 丁光耀
地址 610031 四川省成都市二环路北一段111号西南交大北园28幢3单元11号
(72)发明人 丁光耀
字符串长度怎么判断(74)专利代理机构 成都博通专利事务所
代理人 陈树明
(51)Int.CI
G06F17/30
权利要求说明书 说明书 幅图 |
(54)发明名称
基于离散性、交叉性、非完全性的特性字符串匹配方法 | |
(57)摘要
本发明公开了一种基于离散性、交叉性、非完全性的特性字符串匹配方法，其步骤为：A.用户在用户界面中设置或由信息处理设备自动设置离散数、交叉数、非完全数，输入检索词；B.信息处理设备根据用户输入的检索词，对指定的一个文本，以A步设置的离散数、交叉数、非完全数作为匹配约束条件，进行基于该三种特性的字符串匹配运算，输出精确检索、离散检索、交叉检索、交叉离散检索、非完全检索、离散非完全检索、交叉非完全检索、离散交叉非完全检索共八种检索方式中的一种方式的匹配结果。该种方法提供了八种信息检索方式且操作简单、灵活、方便，可进行定性、定量检索，检索功能强，应用领域广。 | |
法律状态
法律状态公告日 | 法律状态信息 | 法律状态 |
权 利 要 求 说 明 书
1、一种基于离散性、交叉性、非完全性的特性字符串匹配方法，其步骤为：
A步 设置特性参数值并输入检索词 用户在用户界面中设置或由信息处理设备自动设置：反映离散性的离散数即检索词各字符出现在文本中的离散的字符数，反映交叉性的交叉数即检索词各字符出现在文本中的交叉的字符数或子串数，反映非完全性的非完全数即检索词各字符未出现在文本中的字符数；并由用户在用户界面中输入检索词；
B步 字符串匹配及输出 信息处理设备根据用户输入的检索词，对指定的一个文本，以A步设置的离散数、交叉数、非完全数作为匹配约束条件，进行基于该三种特性的字符串匹配运算，输出精确检索、离散检索、交叉检索、离散交叉检索、非完全检索、离散非完全检索、
交叉非完全检索、离散交叉非完全检索共八种检索方式中的一种方式的匹配结果。
2、根据权利要求1所述的一种基于离散性、交叉性、非完全性的特性字符串匹配方法，其特征在于，所述B步的字符串匹配及输出的具体步骤为：
a步输入参数合法性检验：
计算出检索词的长度m以及文本的长度n；对n、m、离散数、交叉数、非完全数，进行合法性检验，若不满足合法性，则退出匹配，并返回不匹配的结果；否则，交叉数、非完全数不能超过m-1，若超过则改为m-1；
b步循环初始化：
设置滑动窗位置＝1，表示文本中当前第一个正准备处理的位置；
对检索词＝p<sub>1</sub>p<sub>2</sub>……p<sub>m</sub>中的所有字符，进行稳定的升序排序，并存储在数组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，实际离散数，实际交叉数，实际非完全数。
3、根据权利要求1所述的一种基于离散性、交叉性、非完全性的特性字符串匹配方法，其特征在于，所述B步的字符串匹配及输出的具体步骤为：
a步输入参数合法性检验：
计算出检索词的长度m以及文本的长度n；对n、m、离散数、交叉数、非完全数，进行合法性检验，若不满足合法性，退出匹配，并返回空指针结果；否则，交叉数、非完全数不能超过m-1，若超过则改为m-1；
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论