ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 2094|回复: 10

[讨论] 有关于字符串模糊匹配算法,最小编辑距离算法,请求完善,高手指点

[复制链接]

TA的精华主题

TA的得分主题

发表于 2019-6-7 11:33 | 显示全部楼层 |阅读模式
各位,端午节快乐!    我在处理和字符串相关的内容,,,需要使用模糊匹配相关的字符串,我用VBA写了一段代码,可以简单实现计算.但是,出现一点瑕疵,需要完善一下代码,请求各位赐教!


代码如下:

'最小编辑距离算法

Function Min_ed(str1, str2)

Dim str1_len
Dim str2_len
Dim arr()
Dim xx, yy
Dim temp1, temp2, temp3
str1_len = Len(str1)
str2_len = Len(str2)
ReDim arr(str1_len, str2_len)

For xx = 0 To str1_len
    For yy = 0 To str2_len
        If xx = 0 Then
            arr(xx, yy) = yy
        ElseIf yy = 0 Then
            arr(xx, yy) = xx
        Else
            If UCase(Mid(str2, xx, 1)) = UCase(Mid(str1, yy, 1)) Then
                temp1 = arr(xx - 1, yy - 1)      '左上角的值
                temp2 = arr(xx - 1, yy) + 1      '上边的值
                temp3 = arr(xx, yy - 1) + 1      '左边的值
                arr(xx, yy) = Application.WorksheetFunction.Min(temp1, temp2, temp3)
            Else
                temp1 = arr(xx - 1, yy - 1) + 1
                temp2 = arr(xx - 1, yy) + 1
                temp3 = arr(xx, yy - 1) + 1
                arr(xx, yy) = Application.WorksheetFunction.Min(temp1, temp2, temp3)
            End If
        End If
    Next     
Next

Min_ed = arr(str1_len, str2_len)          '取数组最后一行一列的数值

End Function





这是最小编辑距离算法的原理

https://blog.csdn.net/weixin_43080758/article/details/83272957   

这是别人用python算法实现的

其实python有一个第三方库叫  FuzzyWuzzy  就很好的实现了这种算法



在计算的时候出现了一点问题:
比如   str1="我爱中国"    str2="我爱中华人民共和国"     str3="我爱天国"      
计算如下:
Min_ed(str1, str2)=6
Min_ed(str1, str3)=1

按道理来说,str2 完全包含 str1 ,str2不完全包含str3,,,,str1和str2的最小编辑距离应该小于str1和str3的最小编辑距离,,,,
不是算法的问题,,,只是需要做一个分支语句,,,使计算这种包含关系的字符串的结果为0


请各位赐教!









TA的精华主题

TA的得分主题

发表于 2019-6-7 14:56 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2019-6-7 16:21 | 显示全部楼层
yjh_27 发表于 2019-6-7 14:56
你对最小编辑距离理解有误。

不是这样计算的吗,请指教

TA的精华主题

TA的得分主题

发表于 2019-6-7 17:05 | 显示全部楼层
比如   str1="我爱中"    str2="我爱中华人民共和国"     str3="我爱天国"      
计算如下:
Min_ed(str1, str2)=6
比如   str1="我爱中国"    str2="爱我中国"     str3="我爱天国"      
计算如下:
Min_ed(str1, str2)=2

TA的精华主题

TA的得分主题

发表于 2019-6-7 17:26 | 显示全部楼层
str2增加了那么多  增删改 都有权重   你有没有理解这个算法???

TA的精华主题

TA的得分主题

 楼主| 发表于 2019-6-7 17:53 | 显示全部楼层
yjh_27 发表于 2019-6-7 17:05
比如   str1="我爱中国"    str2="我爱中华人民共和国"     str3="我爱天国"      
计算如下:
Min_ed(str ...

可能我的表述有些问题,,,是这样的,请看图片,,下图是python 里的一个函数计算的,数值越大,两个字符串越接近

包含关系的字符串,可以采用另外一种方式计算,,,但是,假如一个字符串只有一个字符或很少的字符,,,另一个字符串有20个字符,且这两个字符串之间是包含关系,,,但是这两个字符串的意思可能明显不一样,,,需要排除这种情情况



1.jpg

TA的精华主题

TA的得分主题

 楼主| 发表于 2019-6-7 17:54 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
时间的音符 发表于 2019-6-7 17:26
str2增加了那么多  增删改 都有权重   你有没有理解这个算法???

怎么分配权重呢

TA的精华主题

TA的得分主题

发表于 2019-6-7 17:58 | 显示全部楼层
iris_2356 发表于 2019-6-7 17:53
可能我的表述有些问题,,,是这样的,请看图片,,下图是python 里的一个函数计算的,数值越大,两个字符串越接 ...

参见4L签名链接

TA的精华主题

TA的得分主题

发表于 2019-6-7 18:08 | 显示全部楼层
https://blog.csdn.net/coolwriter/article/details/81222143
你这代码默认增删改权重都为1   这个网址里面才分配了权重

TA的精华主题

TA的得分主题

发表于 2019-6-7 18:27 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 时间的音符 于 2019-6-7 18:28 编辑

把加的权重修改成0,其他修改为1了
1.png
2.png
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-29 23:24 , Processed in 0.057738 second(s), 10 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表