(19)中华人民共和国国家知识产权局
(12)发明专利说明书 | ||
| 字符串长度可以用lenngtn吗js (10)申请公布号 CN 101561813 A (43)申请公布日 2009.10.21 | ||
(21)申请号 CN200910011738.7
(22)申请日 2009.05.27
(71)申请人 东北大学
地址 110004 辽宁省沈阳市和平区文化路3号巷11号
(72)发明人 于戈 申德荣 朱命冬 寇月 聂铁铮 王振华
(74)专利代理机构 沈阳东大专利代理有限公司
代理人 李运萍
(51)Int.CI
G06F17/30
G06F17/22
权利要求说明书 说明书 幅图 |
(54)发明名称
一种Web环境下的字符串相似度的分析方法 | |
(57)摘要
一种Web环境下的字符串相似度分析方法，首先定义基本操作代价；对字符串预处理，识别它的词首字符和去除非实意字符；创建距离矩阵，通过创建匹配索引实现编辑距离的优化；然后，判断缩写词，先判断两个字符串是否是缩写关系，如果是缩写关系则进行距离优化；其中，缩写关系由2个因素决定：①判断两者是否有相似度；②判断两者的词首字符是否被匹配；之后对缩写词距离优化，通过减少连续插入字符和连续删除字符的代价实现。本发明的字符串相似度分析方法能很好地处理web中经常出现的省略、缩写和字符顺序颠倒情况，具有较高适用性，在Web未知环境下，具有较高的匹配精度。 | |
法律状态
法律状态公告日 | 法律状态信息 | 法律状态 |
权 利 要 求 说 明 书
1.一种Web环境下的字符串相似度分析方法，其特征在于：该方法包括如下步骤；
步骤1.定义基本操作代价，基本操作代价由删除字符代价、插入字符代价、替换字符代价组成；
步骤2.字符串预处理，识别词首字符和去除非实义字符；
步骤3.计算编辑距离，通过创建匹配索引实现字符串中字符位置的交换，进而优化编辑距离；其中匹配索引是指将一个字符串以最小代价的编辑操作序列转换成另一个字符串的过程中，原本被插入或删除的字符通过改变字符顺序能够以更小的代价进行替换的字符的索引；
步骤4.判断是否为缩写词，首先判断两个字符串是否是缩写关系；如果是缩写关系则进行距离优化；其中，缩写关系由2个因素决定：①判断两者是否有相似度；②判断两者的词首字符是否被匹配；缩写词距离优化，通过减少连续插入字符和连续删除字符的代价实现。
2.根据权利要求1所述一种Web环境下的字符串相似度分析方法，其特征在于：步骤2所述的词首字符是指字符串中第一个实义字符和字符串中非实义字符后的实义字符；非实义字符是指不具有实际意义的字符，包括空格、逗号、括号。
3.根据权利要求1所述一种Web环境下的字符串相似度分析方法，其特征在于：步骤3所述的匹配索引，在进行字符串交换之前，需要先计算一下两个字符串的距离变化，只有当距离变化小于0时才进行位置交换；具体公式如下：
ed′(x，y)＝ed(x，y)+distanceChange
<maths><math><mrow><mi>dis</mi><mi>tan</mi><mi>ceChange</mi><mo>=</mo><munder><mi>Σ</mi><mrow><mi>i</mi><mo>∈</mo><mi>I</mi></mrow></munder><mi>cos</mi><mi>t</mi><mrow><mo>(</mo><msup><msub><mi>x</mi><mi>i</mi></ms
ub><mo>′</mo></msup><mo>)</mo></mrow><mo>-</mo><munder><mi>Σ</mi><mrow><mi>i</mi><mo>∈</mo><mi>I</mi></mrow></munder><mi>cos</mi><mi>t</mi><mrow><mo>(</mo><msub><mi>x</mi><mi>i</mi></msub><mo>)</mo></mrow><mo>+</mo><munder><mi>Σ</mi><mrow><mi>j</mi><mo>∈</mo><mi>p</mi></mrow></munder><mi>ρ</mi><mo>*</mo><msub><mi>dis</mi><mi>j</mi></msub><mo>-</mo><mo>-</mo><mo>-</mo><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow></math></maths>
其中，ed′(x，y)是指交换后两个字符串的距离；ed(x，y)是指交换前两个字符串的距离；distanceChange指距离所发生的变化，如果distanceChange小于0，则是距离变小，反之是变大；cost(x<sub>i</sub>′)是指x<sub>i</sub>′在交换后匹配的代价；cost(x<sub>i</sub>)是指字符x<sub>i</sub>在交换前匹配的代价；ρ是由用户设定的交换代价系数；dis<sub>j</sub>是指需要交换位置的第j个编辑操作序列对在编辑操作序列中的距离；I为在所要处理的匹配索引中涉及到字符串X中字符的位置集合；P为针对匹配索引需要进行交换处理的编辑操作序列对的集合。
4.根据权利要求1所述一种Web环境下的字符串相似度分析方法，其特征在于：步骤4中所述的判断缩写词的公式如下：
<maths><math><mrow><mi>sim</mi><mrow><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo></mrow><mo>=</mo><mfrac><mrow><msup><mi>ed</mi><mo>′</mo></msup><mrow><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo></mrow></mrow><mrow><mi>Max</mi><mrow><mo>(</mo><mo>|</mo><mi>x</mi><mo>|</mo><mo>,</mo><mo>|</mo><mi>y</mi><mo>|</mo><mo>)</mo></mrow></mrow></mfrac></mrow></math></maths>
(2)
<maths><math><mrow><msub><mi>P</mi><mi>xy</mi></msub><mo>=</mo><mi>λ</mi><mo>*</mo><mi>sin</mi><mrow><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo></mrow><mo>+</mo><mrow><mo>(</mo><mn>1</mn><mo>-</mo><mi>λ</mi><mo>)</mo></mrow><mo>*</mo><mfrac><mrow><msub><mi>P</mi><mi>x</mi></msub><mo>+</mo><msub><mi>P</mi><mi>y</mi></msub></mrow><mn>2
</mn></mfrac></mrow></math></maths>
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论