(19)中华人民共和国国家知识产权局
字符串长度17模式串长度8
(12)发明专利说明书
(10)申请公布号 CN 102298632 A
(43)申请公布日 2011.12.28
(21)申请号 CN201110262493.2
(22)申请日 2011.09.06
(71)申请人 神华集团有限责任公司
    地址 100011 北京市东城区安外西滨河路神华大厦
(72)发明人 韩建国 巩军
(74)专利代理机构 北京润平知识产权代理有限公司
    代理人 肖冰滨
(51)Int.CI
      G06F17/30
                                                                  权利要求说明书 说明书 幅图
(54)发明名称
      字符串相似度计算方法及装置以及物资分类方法及装置
(57)摘要
      本发明公开了一种字符串相似度计算方法及装置以及物资分类方法及装置，该相似度计算方法包括：计算字符串X与字符串d
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种字符串相似度计算方法，该方法包括：           
计算字符串X与字符串d<sub>i</sub>之间的初始相似度Sim，字符串d<sub>i</sub>为属于一集            合{C<sub>1</sub>，C<sub>2</sub>...C<sub>n</sub>}的类别C<sub>j</sub>的一字符串，该集合包含多个类别C，n为类别C的个            数，每一类别包含多个字符串；           
获取字符串X与字符串d<sub>i</sub>之间的最长公共前缀Prefix<sub>MaxCommon</sub>与最长公共            后缀Suffix<sub>MaxCommon</sub>；           
确定所述最长公共前缀Prefix<sub>MaxCommon</sub>的权重PW(Prefix<sub>MaxCommon</sub>，C<sub>j</sub>)以及所述            最长公共后缀Suffix<sub>MaxCommon</sub>的权重SW(Suffix<sub>MaxCommon</sub>，C<sub>j</sub>)以及           
计算字符串X与字符串d<sub>i</sub>之间的相似度Sim<sub>DynamicWeight</sub>(X，d<sub>i</sub>)，计算公式如            下：Sim<sub>DynamicWeight</sub>(X，d<sub>i</sub>)＝Sim+θ*PW<sub>MaxCommon</sub>*(1-Sim)+(1-θ)*SW<sub>MaxCommon</sub>*(1-Sim)，            其中θ为大于0且小于1的合并系数。           
2.根据权利要求1所述的方法，其特征在于，所述初始相似度Sim的计            算公式如下：           
Sim＝1/3(m/|length(X)|+m/|length(d<sub>i</sub>)|+(m-t)/m)，其中m为字符串X与字符串            d<sub>i</sub>相匹配的字符个数，length(X)和length(d<sub>i</sub>)分别表示字符串X与字符串d<sub>i</sub>的字            符，t表示字符串X与字符串d<sub>i</sub>相匹配的过
程中，字符位置发生变化的次数。           
3.根据权利要求1所述的方法，其特征在于，所述权重            PW(Prefix<sub>MaxCommon</sub>，C<sub>j</sub>)和SW(Suffix<sub>MaxCommon</sub>，C<sub>j</sub>)的计算公式如下：           
PW(Prefix<sub>MaxCommon</sub>，C<sub>j</sub>)＝Freq(Cateogy＝C<sub>j</sub>|Prefix＝Prefix<sub>MaxCommon</sub>)           
PW(Suffix<sub>MaxCommon</sub>，C<sub>j</sub>)＝Freq(Cateogy＝C<sub>j</sub>|Suffix＝Suffix<sub>MaxCommon</sub>)           
其中，Freq(Cateogy＝C<sub>j</sub>|Prefix＝Prefix<sub>MaxCommon</sub>)表示前缀为Prefix<sub>MaxCommon</sub>的字            符串于类别C<sub>j</sub>内出现的概率，Freq(Cateogy＝C<sub>j</sub>|Suffix＝Suffix<sub>MaxCommon</sub>)表示后缀为                                Suffix<sub>MaxCommon</sub>的字符串于类别C<sub>j</sub>内出现的概率。           
4.根据权利要求1所述的方法，其特征在于，所述权重            PW(Prefix<sub>MaxCommon</sub>，C<sub>j</sub>)和SW(Suffix<sub>MaxCommon</sub>，C<sub>j</sub>)的计算公式如下：           
PW(Prefix<sub>MaxCommon</sub>，C<sub>j</sub>)＝α*Freq(Cateogy＝C<sub>j</sub>|Prefix＝Prefix<sub>MaxCommon</sub>)+(1-α)/n           
PW(Suffix<sub>MaxCommon</sub>，C<sub>j</sub>)＝β*Freq(Cateogy＝C<sub>j</sub>|Suffix＝Suffix<sub>MaxCommon</sub>)+(1-β)/n           
其中，α和β为大于0且小于1的合并系数。           
5.一种物资分类方法，该方法包括：           
利用权利要求1-4中任一项权利要求所述的相似度计算方法，计算一待            分类物资的物资名称X与多个物资类别内每一物资的物资名称d<sub>i</sub>之间的相            似度Sim<sub>DynamicWeight</sub>(X，d<sub>i</sub>)；           
取相似度最大的K个物资名称，构成集合KNN；           
根据相似度最大的K个物资名称所属的类别，对待分类物资的候选类C<sub>j</sub>进行评分，评分公式如下：<maths><math><mrow><mi>p</mi><mrow><mo>(</mo><mi>X</mi><mo>,</mo><msub><mi>C</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>=</mo><munder><mi>Σ</mi><mrow><msub><mi>d</mi><mi>i</mi></msub><mo>∈</mo><mi>KNN</mi></mrow></munder><msub><mi>Sim</mi><mi>DynamicWeight</mi></msub><mrow><mo>(</mo><mi>X</mi><mo>,</mo><msub><mi>d</mi><mi>i</mi></msub><mo>)</mo></mrow><mo>*</mo><mi>y</mi><mrow><mo>(</mo><msub><mi>d</mi><mi>i</mi></msub><mo>,</mo><msub><mi>C</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>,</mo></mrow></math></maths>其中            y(d<sub>i</sub>，C<sub>j</sub>)为类别属性函数；以及           

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。