标签: levenshtein-distance

我有一大堆查询并使用levenshtein计算拼写错误,现在levenshtein导致mysql占用完整的cpu时间.我的查询是UNION语句中的全文搜索+ levenshtein.sql1是我当前的查询,sql2只是全文搜索,这是快速的,并没有使用太多的CPU时间,最后一个leventhein一个将达到峰值!

你们中的任何人都有另一种方式来获取拼写错误吗？请不要回答规范化数据,我已经想到了,但不适用于我的数据,因为我不能预先进行匹配/计算并创建一个带索引的单独表.

            $sql1 = "(SELECT * FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='' AND MATCH(prop_value) AGAINST ('+usama bin laden' IN BOOLEAN MODE)) UNION (SELECT s.* FROM (SELECT levenshtein(prop_value, 'usama bin laden') AS dist, sanction_id, prop_type, prop_value FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='') s WHERE dist < 3) ORDER BY sanction_id";

        $sql2 = "SELECT * FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='' AND MATCH(prop_value) AGAINST ('+usama bin laden' IN BOOLEAN MODE) ORDER BY sanction_id";

        $sql3 = "SELECT s.* FROM (SELECT levenshtein(prop_value, 'usama …

我有一个mySQL表,人们可以在其中添加他们的名字和兴趣.我想使用某种单词匹配,找到100%匹配或近似匹配.我听说过levenshtein距离,但不知道如何让它循环通过我的桌子.

    $input = $_POST["interest"];
    $result = mysql_query("SELECT interest_desc FROM interests");

做了一些谷歌搜索,并达到了这一点

   function closest($seed, $haystack){
   $shortest = -1;
     foreach ($haystack as $word){
      $lev = levenshtein($seed, $word);
       if ($lev == 0) {
           $closest = $word; $shortest = 0; break;
       }
       if ($lev <= $shortest || $shortest < 0) {
       $closest  = $word; $shortest = $lev;
       }
}
return $closest;
}
$array = mysql_fetch_row($result);
$closestmatch = closest($input,$array);
echo $closetmatch;

让我解释.

我必须为公司做一些模糊匹配,所以ATM我使用levenshtein距离计算器,然后计算两个术语之间的相似性百分比.如果术语的相似度超过80%,则Fuzzymatch将返回"TRUE".

我的问题是我正在实习,很快就离开了.那些将继续这样做的人不知道如何在宏中使用excel,并希望我尽我所能地实现我所做的.

所以我的问题是:无论函数效率如何,是否有任何方法可以在Excel中制作一个标准函数来计算我以前做过的,而不需要使用宏？

谢谢.

我尝试根据给定的十六进制值获得最匹配的颜色名称.例如,如果我们有六角颜色,#f00我们就得到颜色名称red.

'#ff0000' => 'red'
'#000000' => 'black'
'#ffff00' => 'yellow'

我目前使用levenshtein距离算法来获得最接近的颜色名称,到目前为止效果很好,但有时并不像预期的那样.

例如:

'#0769ad' => 'chocolate'
'#00aaee' => 'mediumspringgreen'

那么任何想法如何让结果更接近？

这是我为获得最接近的颜色而做的:

Array.closest = (function () {

    // http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#JavaScript
    function levDist(s, t) {
        if (!s.length) return t.length;
        if (!t.length) return s.length;

        return Math.min(
            levDist(s.substring(1), t) + 1,
            levDist(t.substring(1), s) + 1,
            levDist(s.substring(1), t.substring(1)) + (s[0] !== t[0] ? 1 : 0)
        );
    }

    return function (arr, str) {
        // http://stackoverflow.com/q/11919065/1250044#comment16113902_11919065
        return arr.sort(function (a, b) {
            return levDist(a, str) …

我有两个带数值的向量.如

v1 <- c(1, 3, 4, 5, 6, 7, 8)
v2 <- c(54, 23, 12, 53, 7, 8)

我想计算插入,删除和替换的数量,我需要将一个向量转换为另一个向量,每个操作分别具有一定的成本c1 c2和c3.我知道基础包上的函数adist为字符串执行此操作,但我不知道与数字等效的函数.

我想用一个字母引用每个数字,但我有超过2000个唯一数字,所以如果有人知道如何在R中获得2000个不同的字符,这对我来说也是一个解决方案.

谢谢你的帮助.

我在数据库表中有大约一千万个文件的spamsum复合哈希值,我想找到彼此相似的文件.Spamsum哈希由两个最大64字节的CTPH哈希组成,它们看起来像这样:

384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND

它们可以分为三个部分(在冒号上分割字符串):

1. 块大小:384在上面的哈希中
2. 第一个签名: w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND
3. 第二个签名: wemfOGxqCfOTPi0ND

块大小是指第一个签名的块大小,第二个签名的块大小是第一个签名的块大小(此处:384 x 2 = 768).每个文件都有这些复合哈希中的一个,这意味着每个文件都有两个具有不同块大小的签名.

只有当它们的块大小相对应时,才能比较spamsum签名.也就是说,上面的复合哈希可以与包含块大小为384或768的签名的任何其他复合哈希进行比较.具有相似块大小的哈希的签名字符串的相似性可以作为两者之间相似性的度量.哈希表示的文件.

所以如果我们有:

• file1.blk2 = 768
• file1.sig2 = wemfOGxqCfOTPi0ND
• file2.blk1 = 768
• file2.sig1 = LsmfOGxqCfOTPi0ND

通过计算两个签名的一些加权编辑距离(如Levenshtein距离),我们可以了解两个文件的相似程度.这两个文件看起来非常相似.

leven_dist(file1.sig2, file2.sig1) = 2

还可以计算两个哈希值之间的归一化相似度得分(详见此处).

我想找到基于这些哈希值超过70%相似的任何两个文件,并且我非常喜欢使用可用的软件包(或API/SDK),尽管我不怕编码通过问题.

我试图打破哈希并使用Lucene(4.7.0)索引它们,但搜索似乎缓慢而乏味.这是我尝试过的Lucene查询的示例(对于每个单一签名 - 每个哈希两次并使用区分大小写的KeywordAnalyzer):

(blk1:768 AND sig1:wemfOGxqCfOTPi0ND~0.7) OR (blk2:768 AND sig2:wemfOGxqCfOTPi0ND~0.7)

似乎Lucene的速度非常快Levenshtein自动机不接受超过2的编辑距离限制(我需要它支持高达0.7 x64≃19)并且它的正常编辑距离算法不适用于长搜索术语(使用的强力方法)一旦达到距离限制,就不会切断计算.)也就是说,可能是我的查询没有针对我想做的事情进行优化,所以请不要犹豫,纠正我.

我想知道我是否可以使用Lucene提供的任何算法来完成我所需要的,而不是直接计算编辑距离.我听说BK树是索引此类搜索的最佳方式,但我不知道算法的可用实现(Lucene是否使用了这些？).我也听说过一个可能的解决方案是使用n-gram方法缩小搜索列表的范围,但我不确定如何在包容性和速度方面编辑距离计算(我很确定Lucene支持那个).顺便说一句,有没有办法让Lucene在并行模式下运行术语搜索？

鉴于我使用Lucene仅预先匹配哈希并且我稍后使用适当的算法计算真实相似度得分,我只需要一种至少与相似性得分计算中使用的Levenshtein距离一样包容的方法 - 即,我不希望预匹配方法排除将被评分算法标记为匹配的哈希值.

任何帮助/理论/参考/代码或线索开始是值得赞赏的.

我有2个查询:

    query1:????
    query2:??

当我使用python库Levenshtein运行此代码时:

from Levenshtein import distance, hamming, median
lev_edit_dist = distance(query1,query2)
print lev_edit_dist

我得到12的输出.现在的问题是12的值是如何得出的？

因为在笔画方面的差异,肯定超过12.

假设我有一个清单: -

person_name = ['zakesh', 'oldman LLC', 'bikash', 'goldman LLC', 'zikash','rakesh']

我试图以这样的方式对列表进行分组,以便两个字符串之间的Levenshtein距离最大.为了找出两个单词之间的比例,我使用的是python包fuzzywuzzy.

例子 :-

>>> from fuzzywuzzy import fuzz
>>> combined_list = ['rakesh', 'zakesh', 'bikash', 'zikash', 'goldman LLC', 'oldman LLC']
>>> fuzz.ratio('goldman LLC', 'oldman LLC')
95
>>> fuzz.ratio('rakesh', 'zakesh')
83
>>> fuzz.ratio('bikash', 'zikash')
83
>>> 

我的最终目标:

我的最终目标是将Levenshtein之间的距离分组超过80%？

我的清单应该是这样的: -

person_name = ['bikash', 'zikash', 'rakesh', 'zakesh', 'goldman LLC', 'oldman LLC'] because the distance between `bikash` and `zikash` is very high so they should be together.

码:

我试图通过排序实现这一点,但关键功能应该是 …

我有一个问题，我们可以用ed值除以两个字符串的长度来归一化levenshtein编辑距离吗？我之所以这样问是因为，如果我们比较两个长度不相等的字符串，那么两个长度之间的差异也将被计算在内。例如：ed（'has a'，'has a ball'）= 4，而ed（'has a'，'has a ball the round'）=15。如果我们增加字符串的长度，则编辑距离即使它们相似，也会增加。因此，我无法设置一个值，好的编辑距离值应该是多少。

我构建了一种算法，可以从英语翻译成多种语言。由于我们应该向他们显示输入的单词的适当建议，因此我制定了在该语言词典中进行搜索的逻辑。

我已实现在该语言词典中进行搜索的逻辑：