当前位置： 文江博客话题详情

通过交换编辑距离

发布于 2024-12-25 18:29:59 字数 82 浏览 1 评论 0原文

编辑距离查找一个字符串到另一个字符串所需的插入、删除或替换的次数。我还想在这个算法中包含交换。例如，“apple”和“appel”的编辑距离应为 1。

原文

Edit distance finds the number of insertion, deletion or substitutions required to one string to another. I want to to also include swaps in this algorithm. For example "apple" and "appel" should give a edit distance of 1.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

天荒地未老 2025-01-01 18:29:59

您定义的编辑距离称为Damerau-Levenshtein 距离。您可以在维基百科页面上找到可能的实现。

The edit distance that you are defining is called the Damerau–Levenshtein distance. You can find possible implementations on the Wikipedia page.

回复 原文
ぽ尐不点ル 2025-01-01 18:29:59

请参阅此处的算法。

http://www.csse.monash.edu.au/~ lloyd/tildeAlgDS/Dynamic/Edit/

您可以为交换、添加、删除指定不同的成本。

m[i,j] = min(m[i-1,j-1]
         + if s1[i]=s2[j] then 0 else cost_swap fi,
         m[i-1, j] + cost_insert,
         m[i, j-1] + cost_delete ),  i=1..|s1|, j=1..|s2|

See the algorithm here.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

You can give different costs for swap, add, deletions.

m[i,j] = min(m[i-1,j-1]
         + if s1[i]=s2[j] then 0 else cost_swap fi,
         m[i-1, j] + cost_insert,
         m[i, j-1] + cost_delete ),  i=1..|s1|, j=1..|s2|
回复 原文
~没有更多了~

关于作者

雄赳赳气昂昂

暂无简介

文章
评论
25 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

佚名

文章 0 评论 0

羁客

文章 0 评论 0

天天爱笑的徐老师

文章 0 评论 0

星

文章 0 评论 0

夏日落

文章 0 评论 0

隐诗

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文