问题标签 [edit-distance]

Are there some edit-distance in python that take account of the accent. Where for exemple hold the following property

I am working on finding the similarity/differences in the source code of different java programs. I've used an implementation of the Levenshtein algorithm to find how similar two programs are. I want to know if there is any algorithm that can help in finding the exact positions where two strings differ.

我只是想知道，对于我们在两个字符串之间具有 Levenshtein 距离（或编辑距离）的字符串，是否有类似的图形？

我的意思是，一个标量度量，它标识将 graph 转换为 graph 的原子操作（节点和边插入/删除）的G1数量G2。

如果我们有三个字符串 a、b、c，并且我们知道（或已经计算）edit_distance(a,b) 和 edit_distance(b,c)，我们是否可以在不实际比较 a 和 c 的情况下有效地计算 edit_distance(a,c)。

*edit_distance(a,b) = 将 a 转换为 b 所需的字符插入、删除和替换次数。*

在 R 中，我有两个字符向量，a 和 b。

我想要一个函数来计算 a 的每个元素和 b 的相应元素之间的字符不匹配。使用上面的示例，这样的函数应该返回c(2,3,1). 无需对齐字符串。我需要逐个字符地比较每对字符串并计算每对中的匹配和/或不匹配。R中是否存在任何此类功能？

或者，以另一种方式问这个问题，是否有一个函数可以给我两个字符串之间的编辑距离，其中唯一允许的操作是替换（忽略插入或删除）？

我已经实现了Zhang 和 Shasha 的算法来计算两棵树之间的最小编辑距离。一切正常，我对当前的运行时间非常满意。

现在我还想生成一个突出显示更改/删除/插入节点的差异。根据他们的论文，很自然地要求生成计算距离的映射，并且根据本演示文稿的最后一张幻灯片，似乎可以从最后的森林距离表和树距离表中轻松提取映射。不幸的是，我还没有弄清楚确切的规则。

任何额外的描述将不胜感激。非常感谢！

假设您为字符串 X = "AGGGCT" 和字符串 Y = "AGGCA" 提供了 dp 表

m = X + 1 的长度

n = Y + 1 的长度

你想重建三个字符串如下

如果可能的话，如何用 C/C++/Java 重新构造字符串 row1、row2 和 row3。

本文讨论了利用后缀树改进匹配时间的近似子串匹配技术。每个答案都针对不同的算法。

1. 近似子字符串匹配尝试在允许不匹配P的字符串中查找子字符串（模式） 。Tk
2. 要了解如何创建后缀树，请单击此处。然而，一些算法需要额外的预处理。

我邀请人们添加新算法（即使它不完整）并改进答案。

我有这样的字符串 xxoxxooo，我想将其编辑为这种形式 xoxoxoxo，我的问题是如何找到最小数量的交换，我只能交换 2 个邻居作为交换。我考虑过遍历字符串并找到最近的冗余 x 并将其移动到当前位置，但我认为这太慢了，因为字符串可以有 1e6 * 2 个字符。有任何想法吗？

我需要一种有效的方法来计算两个无序符号集合之间的最小编辑距离。就像仅适用于序列的 Levenshtein 距离一样，我需要以不同的每个符号成本进行插入、删除和替换。我也有兴趣恢复编辑脚本。

由于我要完成的工作与计算字符串编辑距离非常相似，因此我认为它可能被称为无序字符串编辑距离，或者只是设置编辑距离。然而，谷歌并没有用这些搜索词出现任何东西，所以我很想知道这个问题是否有其他名字？

为了澄清，问题将通过以下方式解决

例如，unordered_edit_distance('abc', 'cba')将是0，edit_distance('abc', 'cba')而是2。不幸的是，排列的数量增长得非常快，即使对于中等大小的输入也不实用。

编辑更清楚地表明操作与不同的成本相关联。