标签: levenshtein-distance

我有以下实现,但我想添加一个阈值,所以如果结果将大于它,只需停止计算并返回.

我该怎么办呢？

编辑:这是我目前的代码,threshold尚未使用...目标是它被使用

    public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
    {
        // Return trivial case - where they are equal
        if (string1.Equals(string2))
            return 0;

        // Return trivial case - where one is empty
        if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
            return (string1 ?? "").Length + (string2 ?? "").Length;


        // Ensure string2 (inner cycle) is longer
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return trivial case - where string1 is …

我正在构建一个Android应用程序,它采用字符串输入并使用Google API返回排名的书籍列表.

我正在寻找一种方法来比较用户输入的开放式字符串,以及列表中的第一项,以查看他们输入的内容是否"可能"是一本书.我有大量关于书籍,标题,作者,描述等的信息,所以我可以搜索任何部分.

一个例子是:

'eyre affair fforde', 'fforde eyre affair', 'the eyre affair'
----> 
'Likely' to be 'The Eyre Affair by Jasper Fforde'

最好的方法是什么？我已经看过levenshtein距离,但是不认为它可以用这种开放式输入,n-gram似乎是一个很好的方法,或模糊匹配.

还有其他想法吗？

我对如何完成这项任务缺乏想法.我正在计算单词的频率,实际上是单词的基本形式(例如,运行将被视为运行).我查看了Levenshtein距离的一些实现(我遇到的一个实现是来自dotnerperls).

我也试过双Metaphone,但它不是我想要的.

那么,请给我一些关于如何调整Levenshtein距离算法对语言相似词进行分类的想法,因为该算法仅用于确定编辑所需的编辑数量,而不考虑它们在语言上是否相似

示例:1."运行"将被计为"运行"一词的一次出现."单词"同样是"单词"3的出现."恐惧"不会被视为"齿轮"的出现

另外,我在C#中实现它.

提前致谢.

编辑:我按照Rene的建议编辑了它.另一个注意事项:我正在考虑考虑一个单词是否是另一个单词的子串,但该实现不会那么动态.我认为另一个想法是:"如果将-s或-ing添加到string1,string1 == string2,则string2会出现string1." 然而,事实并非如此,因为有些词语具有不规则的复数.

我使用Levenshtein距离在OCR之后找到类似的字符串.但是,对于某些字符串,编辑距离是相同的,尽管视觉外观明显不同.

例如,字符串Co将返回以下匹配项:

CY (1)
CZ (1)
Ca (1)

考虑到,这Co是OCR引擎的结果,Ca将比那些更可能匹配.因此,在计算Levenshtein距离之后,我想通过视觉相似性排序来改进查询结果.为了计算这种相似性,我想使用标准的sans-serif字体,比如Arial.

是否有我可以用于此目的的库,或者我如何自己实现？或者,是否有任何字符串相似性算法比Levenshtein距离更准确,我还可以使用它？

我正在使用字符串编辑距离 (Levenshtein-distance) 来比较眼动追踪实验中的扫描路径。（现在我stringdist在 R 中使用这个包）

基本上，字符串的字母指的是 6x4 矩阵中的（凝视）位置。矩阵配置如下：

     [,1] [,2] [,3] [,4]
[1,]  'a'  'g'  'm'  's' 
[2,]  'b'  'h'  'n'  't'
[3,]  'c'  'i'  'o'  'u'
[4,]  'd'  'j'  'p'  'v'
[5,]  'e'  'k'  'q'  'w'
[6,]  'f'  'l'  'r'  'x'

如果我使用的基本Levenshtein距离比较字符串，进行比较a，并g在一个字符串给出了相同的估计为comparicona和x。

例如：

'abc' compared to 'agc' -> 1
'abc' compared to 'axc' -> 1

这意味着字符串同样（不同）相似

我希望能够以在矩阵中包含邻接的方式对字符串比较进行权重。例如之间的距离a和x应该那么之间加权为较大的a和g。

一种方法是计算矩阵中从一个字母到另一个字母的“步行”（水平和垂直步骤），然后除以最大“步行”距离（即从a到 …

假设您有两个包含相似项目的字符串列表，但有更改（例如，列表 1：Apples,fruits_b,orange；列表 2：Fruit,apples,banana,orange_juice）。

给定距离度量，例如 Levenshtein 距离，找到最佳配对的好算法是什么，即最小化所有配对的距离总和的配对？

与我的示例相对应的结果是：

Apples    - apples
fruits_b  - Fruit
orange    - orange_juice
          - banana

附属问题：是否有一些工具已经实现了这个或类似的东西？

有没有一种好方法可以使用 Levenstein 距离将一个特定字符串与第二个较长字符串中的任何区域进行匹配？

例子：

str1='aaaaa'
str2='bbbbbbaabaabbbb'

if str1 in str2 with a distance < 2:
    return True

因此，在上面的示例中，字符串 2 的一部分是aabaa，distance(str1,str2) < 2因此语句应该返回True。

我能想到的唯一方法是一次从 str2 中取出 5 个字符，与 str1 进行比较，然后在 str2 中重复此操作。不幸的是，这看起来效率很低，我需要以这种方式处理大量数据。

我发现了Levenshtein distancePython的一些实现。

我想知道如何有效地修改这些算法，以便在编辑距离大于n（例如 3）时它们会中断，而不是运行到最后？

因此，如果我只是想知道距离是否大于阈值，那么本质上我不想让算法运行太长时间来计算最终距离。

我在这里找到了一些相关的帖子：

1. 修改 Levenshtein Distance 算法以不计算所有距离
2. 莱文斯坦距离限制
3. 计算编辑距离的最有效方法
4. Levenshtein 距离算法比 O(n*m) 更好？

但是，我仍然没有看到任何 Python 代码执行我上面描述的操作（这或多或少也是这些帖子所描述的）。

PS：下面@amirouche提供的解决方案基于我通过一些基准测试测试过的最快实现（来自此处： https : //en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python，https :// stackoverflow.com/a/32558749/9024698）及其有界版本是我的测试中最快的版本（不排除可能有更快的版本）。

我有两个字符串向量：

a <- c('Alpha', 'Beta', 'Gamma', 'Delta')
b <- c('Epsilon', 'Zeta', 'Eta', 'Theta')

我想计算每对字符串的编辑距离或编辑距离。

如果我使用

stringdist(a, b, method="lv")

输出是一个向量，其中包含向量 a 中每个字符串和向量 b 中相应字符串的编辑距离（即 Alpha 与 Epsilon、Beta 与 Zeta 等）。

我需要的是一个向量中的每个字符串与另一个向量中的所有其他字符串之间的成对比较（即 Alpha 与 Epsilon、Alpha 与 Zeta、Alpha 与 Eta、Alpha 与 Theta、Beta 与 Epsilon 等） 。

谢谢

我有一个使用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, …