这是CS人士运用该理论的一项练习。
想象一下，您有2个带有元素的容器。文件夹，URL，文件，字符串，这真的没有关系。
什么是计算添加和删除的算法？
注意：如果有很多方法可以解决此问题，请为每个答案发布一个，以便对其进行分析和投票。
编辑：所有的答案用4个容器解决了问题。是否可以仅使用首字母2？
我有一个使用Levenshtein距离的存储过程来确定最接近用户输入的结果.唯一真正影响速度的是在选择具有最小距离的记录之前计算所有记录的Levenshtein距离的函数(我通过用0代替对Levenshtein函数的调用来验证这一点).该表有150万条记录,因此即使是最轻微的调整也可能会缩短几秒钟.现在整个事情都持续了10多分钟.这是我正在使用的方法:
ALTER function dbo.Levenshtein
(
@Source nvarchar(200),
@Target nvarchar(200)
)
RETURNS int
AS
BEGIN
DECLARE @Source_len int, @Target_len int, @i int, @j int, @Source_char nchar, @Dist int, @Dist_temp int, @Distv0 varbinary(8000), @Distv1 varbinary(8000)
SELECT @Source_len = LEN(@Source), @Target_len = LEN(@Target), @Distv1 = 0x0000, @j = 1, @i = 1, @Dist = 0
WHILE @j <= @Target_len
BEGIN
SELECT @Distv1 = @Distv1 + CAST(@j AS binary(2)), @j = @j + 1
END
WHILE @i <= @Source_len
BEGIN
SELECT @Source_char = SUBSTRING(@Source, …我已经阅读了关于计算两个不同单词之间距离的Levenshtein距离.
我有一个源字符串,我必须将它与所有10,000个目标字匹配.应该返回最接近的单词.
问题是我给出了10,000个目标词的列表,输入源词也很大....所以在这里应用什么最短,最有效的算法.每个组合(蛮力逻辑)的每个n的Levenshtein距离计算将非常耗时.
任何提示或想法都是最受欢迎的.
c algorithm edit-distance data-structures levenshtein-distance
编辑距离可以找到一个字符串到另一个字符串所需的插入，删除或替换的数量。我还想在此算法中包含交换。例如，“ apple”和“ appel”的编辑距离应为1。
如果我们有三个字符串a,b,c并且我们知道(或已经计算过)edit_distance(a,b)和edit_distance(b,c),我们是否可以有效地计算edit_distance(a,c)而无需实际比较a和c.
*edit_distance(a,b)=将a转换为b所需的字符插入,删除和替换次数.*
我正在使用动态编程使用 Levenshtein（编辑）距离做一些工作。我想我理解 Wagner-Fischer 算法可以有效地做到这一点。但是，该算法看起来并不具有建设性。如果我计算出两个字符串之间的编辑距离是，例如，10，那么我还想确定一个特定的 10 个编辑序列，将一个转换为另一个。这也可以有效地完成吗？如果是这样，如何？
我熟悉python的nltk.metrics.distance模块,它通常用于计算两个字符串的编辑距离.
我感兴趣的是一个函数,它计算这样的距离,但不像通常那样以字符方式表示.我的意思是你只能替换/添加/删除整个令牌(而不是chars).
常规编辑距离和我想要的标记化版本的示例:
> char_dist("aa bbbb cc",
"aa b cc")
3 # add 'b' character three-times
> token_dist("aa bbbb cc",
"aa b cc")
1 # replace 'bbbb' token with 'b' token
是否已经有一些功能,可以token_dist在python中计算？我宁愿使用已经实现和测试过的东西而不是编写我自己的代码.谢谢你的提示.
Damerau-Levenshtein 距离是这样的：
"abcd", "aacd" => 1 DL distance
"abcd", "aadc" => 2 DL distance
我可以在python中使用pyxDamerauLevenshtein modul来确定2个单词的DL距离。我想制作一个生成器方法，它可以在给定的 DL 距离内生成给定关键字参数的每个单词。我只处理 1 或 2 个 DL 距离。
python 中是否有任何工具可以用来生成给定 DL 距离中单词的单词？
在尝试学习 R 时，我想在 R 中实现下面的算法。考虑下面的两个列表：
List 1: "crashed", "red", "car"
List 2: "crashed", "blue", "bus"
我想知道将“list1”转换为“list2”需要多少操作。正如你所看到的，我只需要执行两个操作：
1. Replace "red" with "blue".
2. Replace "car" with "bus".
但是，我们如何才能自动找到这样的动作数量呢？我们可以通过多种操作来转换句子：添加、删除或替换列表中的单词。现在，我将尽力解释该算法应该如何工作：
第一步：我将创建一个如下表：
行：i= 0,1,2,3，列：j = 0,1,2,3
(example: value[0,0] = 0 , value[0, 1] = 1 ...)
crashed red car
0 1 2 3
crashed 1
blue 2
bus 3
现在，我将尝试填满表格。请注意，表中的每个单元格显示了我们需要执行的重新格式化句子的操作数量（添加、删除或替换）。考虑“crashed”和“crashed”（ ）之间的交互value[1,1]，显然我们不需要更改它，因此该值将为“0”。因为它们是相同的词。基本上，我们得到了对角线值=value[0,0]
crashed red car
0 1 2 3
crashed 1 0
blue 2
bus 3 …我正在寻找一种计算 Levenshtein 编辑距离的算法，该算法也支持在 C# 中实现的两个相邻字母转置的情况。
例如单词“animals”和“ainmals”：字母“n”和“i”之间的切换不会被记为两个替换——这将产生很大的距离——而是将被记为两个字母的转置——更短的距离-
到目前为止我在搜索中所达到的
请注意,它不需要真正计算Levenshtein编辑距离.只是检查它是否为1.
方法的签名可能如下所示:
bool Is1EditDistance(string s1, string s2).
例如:1."abc"和"ab"返回true 2."abc"和"aebc"返回true 3."abc"和"a"返回false.
我试过递归批准,但它效率不高.
更新:得到了朋友的回答:
for (int i = 0; i < s1.Length && i < s2.Length; i++)
{
if (s1[i] != s2[i])
{
return s1.Substring(i + 1) == s2.Substring(i + 1) //case of change
|| s1.Substring(i + 1) == s2.Substring(i) //case of s1 has extra
|| s1.Substring(i) == s2.Substring(i + 1); //case of s2 has extra
}
}
return Math.Abs(s1.Length - s2.Length) == 1;
在python中是否有一些考虑到重音的编辑距离.例如,举行以下财产
d('ab', 'ac') > d('àb', 'ab') > 0