时间戳

首页 > 解决方案 > 莱文斯坦距离，多路径

c++ - 莱文斯坦距离，多路径

问题描述

编辑： TL；DR 版本：如何获得两个单词之间 Damerau–Levenshtein 距离的所有可能回溯？我正在使用https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm来计算距离，并使用简单的回溯算法（如下所示）来重建更正列表。

更多详情如下：

只是在尝试获得一组完整的可能对齐方式时遇到了最佳字符串对齐方式（类似于 Damerau-Levenshtein 距离）。

目标是对齐 2 个字符串，以便在自动建议算法中进行进一步比较。特别是，我想忽略第一个单词末尾的插入。

在某些情况下可能存在多个“最佳”对齐的问题，例如

align("goto", "go to home")

1) go to
   go to home

2) go t   o
   go to home

不幸的是，我的实现只找到了第二个变体，而我需要两个或第一个。

我尝试执行某种 A* 或 BFS 路径查找，但看起来成本计算矩阵仅针对 (2) 变体进行了“调整”。下面有屏幕截图，我可以在其中找到红色路径，但看起来没有绿色路径： 截屏

但是，有人做了一个网络演示，它完全实现了我想要的： 网络演示

我在这里缺少什么？

可能是我的实现太长了这里不能贴，所以有一个github的链接：https ://github.com/victor-istomin/incrementalSpellCheck/blob/f_improvement/spellCheck.hpp

距离实现位于optimalStringAlignementDistance() 和optimalStringAlignmentBacktrace() 方法中。

标签： c++levenshtein-distancedamerau-levenshtein

解决方案

推荐阅读