标签: levenshtein-distance

我把"chunk transposition"放在引号中,因为我不知道技术术语应该是什么或者是什么.只知道该过程是否有技术术语将非常有帮助.

关于编辑距离的维基百科文章给出了一些关于这个概念的好背景.

通过考虑"块转置",我的意思是

Turing, Alan.

应该匹配

Alan Turing

比它更匹配

Turing Machine

即距离计算应检测文本的子串何时在文本中移动.常见的Levenshtein距离公式不是这种情况.

字符串最多只有几百个字符 - 它们是作者姓名或作者姓名列表,可以是各种格式.我没有做DNA测序(虽然我怀疑那些会对这个主题有所了解的人).

Apaches Solr搜索引擎是否提供近似的字符串匹配,例如通过Levenshtein算法？

我正在寻找一种通过姓氏查找客户的方法.但我不能保证名字的正确性.如何配置SOLR以便即使我搜索"Levenstein"也会找到"Levenshtein"的人？

我在阵列中有5000个,有时更多的街道地址字符串.我想将它们与levenshtein进行比较以找到类似的匹配.如何在不循环遍历所有5000并将它们直接与其他4999进行比较的情况下执行此操作？

编辑:如果有人有建议,我也对替代方法感兴趣.总体目标是根据用户提交的街道地址查找类似的条目(并消除重复项).

我正在进行模糊搜索实现,作为实现的一部分,我们使用的是Apache的StringUtils.getLevenshteinDistance.目前,我们正在寻找模糊搜索的特定最大平均响应时间.经过各种改进和一些剖析后,花费最多时间的地方是计算Levenshtein距离.它占搜索字符串总时间的大约80-90%三个字母或更多.

现在,我知道在这里可以做些什么有一些限制,但我已经读过以前的SO问题和LD的维基百科链接,如果有人愿意将阈值限制在设定的最大距离,这可能有助于遏制花在算法上的时间,但我不确定如何准确地做到这一点.

如果我们仅对距离感兴趣,如果它小于阈值k,那么在矩阵中计算宽度为2k + 1的对角条纹就足够了.这样,算法可以在O(kl)时间内运行,其中l是最短字符串的长度.[3]

下面你将看到StringUtils的原始LH代码.之后是我的修改.我试图基本上计算设定长度与i,j对角线的距离(因此,在我的例子中,i,j对角线上方和下方的两个对角线).但是,这是不正确的,因为我已经这样做了.例如,在最高的对角线上,它总是会直接在上面选择单元格值,这将是0.如果有人能告诉我如何使这个功能如我所描述的那样,或者如何使它成为如此的一般建议, 这将不胜感激.

public static int getLevenshteinDistance(String s, String t) {
        if (s == null || t == null) {
            throw new IllegalArgumentException("Strings must not be null");
        }

        int n = s.length(); // length of s
        int m = t.length(); // length of t

        if (n == 0) {
            return m;
        } else if (m == 0) {
            return n;
        }

        if (n > m) {
            // swap the input strings to consume less memory
            String …

使用Commons Lang api,我可以通过LevensteinDistance计算两个字符串之间的相似性.结果是将一个字符串更改为另一个字符串所需的更改次数.我希望结果在0到1的范围内,这样可以更容易地识别字符串之间的相似性.结果将更接近0相似性.可能吗？

在我正在使用的示例下面:

public class TesteLevenstein {

    public static void main(String[] args) {      

        int distance1 = StringUtils.getLevenshteinDistance("Boat", "Coat");
        int distance2 = StringUtils.getLevenshteinDistance("Remember", "Alamo");
        int distance3 = StringUtils.getLevenshteinDistance("Steve", "Stereo");

        System.out.println("distance(Boat, Coat): " + distance1);
        System.out.println("distance(Remember, Alamo): " + distance2);
        System.out.println("distance(Steve, Stereo): " + distance3);        

    }
}

谢谢!

我正在尝试创建或找到Levenshtein距离公式的CoffeeScript实现,即编辑距离.这是我到目前为止,任何帮助都将非常感激.

levenshtein = (s1,s2) ->
    n = s1.length
    m = s2.length
    if n < m
        return levenshtein(s2, s1) 
    if not s1 
        return s2.length
    previous_row = [s2.length + 1]
    for c1, i in s1
        current_row = [i + 1]
        for c2, j in s2
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] # is this unnescessary?-> (c1 != c2)
            current_row.push(Math.min(insertions,deletions,substitutions))
        previous_row = current_row
    return previous_row[previous_row.length-1]
#End Levenshetein Function

顺便说一句:我知道这个代码在很多层面都是错误的,我很高兴接受任何建设性的批评.只是想改进,并找出这个公式!

CodeEdit1:修补了Trevor指出的错误,上面的当前代码包括这些更改

更新:我问的问题是 - 我们如何在CoffeeScript中使用Levenshtein？

以下是Levenshtein距离算法的"步骤",以帮助您了解我想要完成的任务. …

我想为Android开发一个软键盘,并且已经有了一个自动更正算法,如果输入字符和字典中单词的字符是键盘上的邻居,则根据事实提出建议.这与levenshtein算法结合使用(如果必须用不同的字符替换字符,则检查它们是否是邻居).这就是为什么经常调用此检查的原因.目前,它消耗了50%的自动更正时间.

我目前的做法是一个单独的三层,三层.第一层:第一个字符.第二层:第二个字符:第三层:如果字符是邻居,则保存信息的布尔值.但是我担心特里尼有点矫枉过正？每个孩子的实习生哈希图也会降低它的速度？我应该用自己的charToNumber函数构建一个hashmap吗？

你会怎么做？哪些瓶颈可以避免？每次执行检查时调用Character.toLowerCase()似乎都是低效的.

我希望你能帮助我加快任务:)

我正在编写一个自动更正的程序,该程序使用levenshtein距离来校正不超过64个字符的短语,该短语基于包含8000个单词的特定字典.

字典在每一行包含"Word word_frequency"对.我使用DictionarEntry对象来存储这些对.类Dictionar Entry有两个字段:value:存储单词字符串freq:存储频率字典存储为LinkedList.我从stdin读取了64个字符串.在处理之前我删除所有空格."Coo lweather" - >"Coolweather"我注意到计算每个前缀的levenshtein距离,在由levenshtein动态计算的矩阵的最后一行(参见维基百科示例)中,它返回所有前缀的距离.

函数lev将包含第二个参数字符串的l.distance的向量返回给所有第一个前缀,包括它自己.

我的问题是我必须遵守一些额外的规则:min lev.距离 - >最小字数 - >最大频率总和 - >最小字典值这可以解释为解决方案的总数大于1,我们采用具有最少字数的那些.如果还有不止一个,我们会遵循规则列表.

我正在应用的动态类似于背包动态.我不知道如何实现最小字数规则(最大频率一个非常相似)

这是我到目前为止尝试的输入/输出示例,其中失败了:"疼痛保留"答案应该如此保留,我获得的实际上是如此重新服务我选择了这种方法,因为它更有效.Java的时间限制为2秒.

更新:4月7日.我找到了问题的解决方案,但是cpu时间太长,所以我需要优化它.它不应高于2000毫秒,目前大约为6000毫秒.所以现在我的主要重点是优化它.

 public static String guess (String input, LinkedList<DictionarEntry> Dictionar){
       String curent = new String();
      String output = new String();

      int costMatrix[][][] = new int [input.length()][8000][input.length()];         
     int index[] = new int[128];
     int prev[]= new int[128];
        int d[]=new int  [128];
        int freq[]= new int[128];
        int wcount[]=new int[128];
        String values[] = new String[128];   
        for (int i=0 ; i < 128 ; …

我有一个50K到100K字符串的字典(最多可以有50多个字符),我试图找到一个给定的字符串是否在字典中具有一些"编辑"距离容差.(例如Levenshtein).在进行搜索之前,我很好地预先计​​算任何类型的数据结构.

我的目标是尽可能快地对该字典运行数千个字符串并返回最近的邻居.我会很好的只是得到一个布尔值,说明一个给定是否在字典中,如果有一个明显更快的算法这样做

为此,我首先尝试计算所有Levenshtein距离并采取最小值并且显然非常慢.所以我尝试在这篇文章的基础上实现Levenshtein Trie http://stevehanov.ca/blog/index.php?id=114

请参阅我的要点以重现基准:https://gist.github.com/nicolasmeunier/7493947

以下是我在机器上的一些基准测试:

编辑距离0(完美匹配)

Benchmark.measure { 10.times { dictionary.search(random_word, 0) } }
<Benchmark::Tms:0x007fa59bad8908 @label="", @real=0.010889, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.00999999999999801, @total=0.00999999999999801> 

*编辑距离2,变得慢很多*

Benchmark.measure { 10.times { dictionary.search(random_word, 2) } }
<Benchmark::Tms:0x007fa58c9ca778 @label="", @real=3.404604, @cstime=0.0, @cutime=0.0, @stime=0.020000000000000018, @utime=3.3900000000000006, @total=3.4100000000000006>

它从那里走下坡路,并且编辑距离大于2时变得非常慢.(每个测试字符串的平均值超过1秒).

我想知道如何/如果我可以显着加快这一点.如果现有的解决方案已经在ruby/gem中实现,我也不想重新发明轮子......

编辑1:在我的情况下,我希望我与字典匹配的大多数字符串不在那里.因此,如果有任何算法可以快速丢弃字符串,那可能会有所帮助.

谢谢,尼古拉斯

在levenshtein距离中,你问这个问题,给定这两个字符串,他们的levenshtein距离是多少.你将如何获得一个字符串和levenshtein距离并在levenshtein距离内生成所有字符串.(它也会采用字符集).所以,如果我传入一个字符串x和一个距离d.然后它会给我编辑距离内的所有字符串,包括d-1和d-2 .... dn; (n <d).

预期功能:

>>> getWithinDistance('apple',2,{'a','b',' '})
['applea','appleb','appel','app le'...]

请注意,该程序能够生成app le字符集中包含的空格.