标签: levenshtein-distance

我正在尝试使用我在'net上找到的levenshtein算法来计算与搜索项最接近的值.为了实现模糊项匹配.我当前的查询运行大约45秒.我希望我可以优化它.我已经为我计算出levenshtein值的字段添加了索引.我发现的levenshtein函数可能不是最优化的,我在它的实现中不予赞誉.这是这个功能:

CREATE FUNCTION [dbo].[LEVENSHTEIN]( @s NVARCHAR(MAX), @t NVARCHAR(MAX) )
/*
Levenshtein Distance Algorithm: TSQL Implementation
by Joseph Gama

http://www.merriampark.com/ldtsql.htm

Returns the Levenshtein Distance between strings s1 and s2.
Original developer: Michael Gilleland http://www.merriampark.com/ld.htm
Translated to TSQL by Joseph Gama

Fixed by Herbert Oppolzer / devio
as described in http://devio.wordpress.com/2010/09/07/calculating-levenshtein-distance-in-tsql
*/
RETURNS INT AS
BEGIN

  DECLARE @d NVARCHAR(MAX), @LD INT, @m INT, @n INT, @i INT, @j INT,
    @s_i NCHAR(1), @t_j NCHAR(1),@cost INT

  --Step 1
  SET @n = LEN(@s)
  SET @m …

给定字符串A,BI需要计算B成为A的插入,删除和替换的数量.对此有什么好的算法？

如何在Damerau-Levenshtein距离算法的实现中禁用删除计数,或者如果已经实现了其他算法,请指向我.

示例(禁用删除计数):

string1:你好吗？

string2:oyu怎么样？

距离: 1(换位,4次删除不计算)

这是算法:

    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_transpositionRow
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return …

我正在尝试使用Postgres创建一个模糊搜索,并一直使用django-watson作为基础搜索引擎来解决问题.

我有一个名为search_tsv的字段,它是一个包含我要搜索的模型的所有字段值的tsvector.

我想要使​​用Levenshtein函数,它在文本字段中完全符合我的要求.但是,我真的不知道如何在tsvector的每个元素上运行它.

有没有办法做到这一点？

我正在使用动态编程使用 Levenshtein（编辑）距离做一些工作。我想我理解 Wagner-Fischer 算法可以有效地做到这一点。但是，该算法看起来并不具有建设性。如果我计算出两个字符串之间的编辑距离是，例如，10，那么我还想确定一个特定的 10 个编辑序列，将一个转换为另一个。这也可以有效地完成吗？如果是这样，如何？

我有以下两个字符串：

a = 'bjork gudmundsdottir'
b = 'b. gudmundsson gunnar'

两者之间的 Levenshtein 距离是12。当我使用以下公式计算 Levenshtein 距离时，我得到了0.01与python-Levenshtein库的差异：

>>> Ldist / max(len( a ), len( b ))
>>> float(12)/21
0.5714285714285714
# python-Levenshtein
Levenshtein.ratio(a,b)
0.5853658536585366
# difflib
>>> seq=difflib.SequenceMatcher(a=a,b=b)
>>> seq.ratio()
0.5853658536585366

造成这种差异的原因是什么？我在计算中做错了什么。请注意，我已经回顾了这个How python-Levenshtein.ratio 计算类似的问题，它并没有完全回答我的问题。

有人可以解释一下用于计算上述比率的公式吗？

我已经实现了算法,但现在我想找到与其他字符串具有最短编辑距离的字符串的编辑距离.

这是算法:

def lev(s1, s2):
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1)

我正在尝试将函数应用于笛卡尔RDD.该功能取自此处,我不知道如何使其适用于笛卡尔RDD.

val combined = rdd_valid.cartesian(rdd1)
combined.collect().foreach(a  => println(a))

(abcde,abdce)
(somethin,somthing)
(afghr, decsvt)

我的第一个想法是做

val newRDD = combined.map(Levenshtein.distance)

但它不起作用.

我正在使用Rosetta Code的教程来计算Levenshtein距离.看起来他们的代码在Swift2中,所以我Binary operator '+' cannot be applied to operands of type '[Int]' and 'Repeated<String.CharacterView>'这样做时会出现这个错误:var cur = [i + 2] + emptywhere let empty = repeatElement(s, count: 0).我怎么能这样做？

我想基于Levenshtein距离执行连接。

我有2张桌子：

1. Data：这是HDFS文件存储库中的CSV。列之一是Disease description，15K行。
2. df7_ct_map：我从Hive呼叫的表格。列之一是Disease Indication，20K行。

我试图通过将每个描述与适应症（它们是疾病的文字描述）相匹配来连接两个表。理想情况下，它们必须相同，但是如果两个文本都不相同，我希望选择包含最大数量的常用单词的匹配文本。

from pyspark.sql.functions import levenshtein  
joinedDF = df7_ct_map.join( Data, levenshtein(df7_ct_map("description"), 
Data("Indication")) < 3)
joinedDF.show(10)

问题Data是DataFrame这就是为什么我得到以下错误：

TypeError: 'DataFrame' object is not callable
TypeError                                 Traceback (most recent call last)
in engine
----> 1 joinedDF = df7_ct_map.join( Data, levenshtein(df7_ct_map("description"), Data("Indication")) < 3)

TypeError: 'DataFrame' object is not callable

一些忠告？我可以使用Fuzzywuzzy软件包吗？如果是这样，怎么办？