问题标签 [edit-distance]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
string - 有效地计算 1 个字符串和大量其他字符串之间的编辑距离？
用例是自动完成选项，我想根据它们与固定字符串的相似程度对大量其他字符串进行排名。
是否有任何像 DFA RegEx 这样的混蛋可以比重新开始每个选项解决方案做得更好？
问这个问题的人似乎知道解决方案，但没有列出任何来源。
（ps“阅读此链接”类型回答欢迎。）
r - R中编辑距离的自定义替换矩阵
我需要根据替换的自定义成本函数计算两个字符串之间的编辑距离。例如，我想指定将 'a' 替换为 'b' 与将 'a' 替换为 'c' 不同的成本
是否有允许我将自定义成本矩阵作为参数传递的 R 包？如果没有，我将不得不为此修改一个包，那么您认为哪个包适合实现这种扩展？
谢谢。
python - Levenshtein 距离与权重/邻接罚分
我正在使用字符串编辑距离（Levenshtein-distance）来比较眼动追踪实验的扫描路径。（现在我正在使用stringdistR 中的包）
基本上，字符串的字母指的是 6x4 矩阵中的（注视）位置。矩阵配置如下：
如果我使用基本的 Levenshtein 距离来比较字符串，则字符串中的aand的比较给出与and的比较g相同的估计值。ax
例如：
这意味着字符串同样（不）相似
我希望能够以一种在矩阵中结合邻接的方式对字符串比较进行加权。例如 和 之间的距离应该被加权为大于a和之间的距离。xag
一种方法是计算矩阵中从一个字母到另一个字母的“步行”（水平和垂直步数）并除以最大“步行”距离（即从a到x）。a例如，从to 到的“步行”距离g是 1，从a到x它的距离是 8，导致权重分别为 1/8 和 1。
有没有办法实现这个（在 R 或 python 中）？
edit-distance - 计算仿射间隙距离的可用代码
鉴于计算 Levenshtein 编辑距离的代码（在 C、R、python、Java 中）无处不在，我对缺乏其他编辑距离（如仿射间隙距离）的实现感到有些惊讶。是否有易于使用的库来计算此度量？
谢谢！机器学习
graph - 计算图形编辑距离 (GED) 的工具
我阅读了很多关于计算图形编辑距离 (GED) 或其他图形相似性度量（例如http://goo.gl/gmDMgA）的理论，但我找不到完成此类计算的工具。
是否有一个编程库或软件可以计算两个图之间的图编辑距离，或者再次计算任何其他图相似性度量？
scala - Scala中的Kendall tau距离
这是Scala中Kendall tau 距离的正确实现吗
问题是我没有足够的数据来测试算法，只有来自维基百科的几个例子。而且我对算法的理解还不够好，无法生成自己的测试数据。大多数来源是关于Kendall tau 等级相关系数，这是相关但不同的动物。也许我可以以某种方式从另一个中得出一个？
现在让我们说性能并不重要。
更新
所以，现在我有了 Kendall tau 距离算法的三个实现。其中两个 (distance1和distance3) 给出相同的结果（见下文）。那么，哪一个是正确的？
以下是一些结果：
algorithm - Levenshtein 距离算法中的冗余
在典型的动态 Levenshtein 距离算法中，为了计算 cell 的值d[i][j]，其中i和分别是行号和列号j，我们取 和 的最小值。但是，在我看来，最小值和总是将是，在这种情况下，包括在计算中似乎是多余的。>在 Levenshtein 距离算法中是否有过这种情况，如果没有，省略这种比较不是更有效吗？d[i-1][j-1]+0/1d[i-1][j]+1d[i][j-1]+1d[i-1][j-1]+0/1d[i-1][j]+1d[i-1][j-1]+0/1d[i-1][j]+1d[i-1][j-1]+0/1d[i-1][j]+1
编辑：对不起，研究不足的问题；d[i-1][j-1]+0/1算法的任何标准运行都会显示>的实例d[i-1][j]+1：
（考虑第二行）。
scala - 烫伤：成对比较字符串？
使用烫伤我需要：
- 按前 3 个字符对字符串字段进行分组
edit-distance使用度量 ( http://en.wikipedia.org/wiki/Edit_distance )比较每个组中所有对中的字符串- 将结果写入记录所在的 CSV 文件中
string; string; distance
要对我使用的字符串进行分组map，groupBy如下例所示：
结果我得到：
aaa现在，在此示例中，我需要计算此列表中带有键的字符串的编辑距离：
next 用于此列表中所有带有 'bbb' 键的字符串：
等等
要计算每个组中所有字符串之间的编辑距离，我需要toList用自己的函数替换，我该怎么做？还有如何将我的函数结果写入 CSV 文件？
谢谢！
更新
如何List从烫伤中获得Pipe？
toList只是返回另一个Pipe，所以我不能全部使用它：
dynamic-programming - 确定产生 Levenshtein 距离的编辑序列
我正在使用动态编程使用 Levenshtein（编辑）距离做一些工作。我想我理解 Wagner-Fischer 算法可以有效地做到这一点。但是，该算法看起来并不具有建设性。如果我计算出两个字符串之间的编辑距离是 10，那么我还想确定一个特定的 10 次编辑序列，它将一个变成另一个。这也能有效地完成吗？如果是这样，怎么做？