标签: levenshtein-distance

我正在玩Haskell 计算Levenshtein距离,并对下面的性能问题感到有点沮丧.如果你为Haskell实现最"正常"的方式,就像下面(dist)一样,一切正常:

dist :: (Ord a) => [a] -> [a] -> Int
dist s1 s2 = ldist s1 s2 (L.length s1, L.length s2)

ldist :: (Ord a) => [a] -> [a] -> (Int, Int) -> Int
ldist _ _ (0, 0) = 0
ldist _ _ (i, 0) = i
ldist _ _ (0, j) = j
ldist s1 s2 (i+1, j+1) = output
  where output | (s1!!(i)) == (s2!!(j)) = ldist s1 s2 (i, j)
               | otherwise …

我正在尝试使用模糊结果进行匹配查询，并根据编辑距离对结果进行排序。然而，elasticsearch 返回一个基于频率和每个查询的相关性分数 (_score)。无论如何，有没有办法仅从elasticsearch 获取编辑距离。另外，编写我自己的自定义函数来计算编辑距离是否会减慢搜索速度？

我在R中有两个类型字符向量

我希望能够使用jarowinkler将引用列表与原始字符列表进行比较,并指定%相似度得分.因此,例如,如果我有10个参考项目和20个原始数据项目,我希望能够获得比较的最佳分数以及算法与之匹配的内容(因此2个向量为10).如果我有大小为8和10个参考项目的原始数据,我应该只得到8个项目的2个向量结果,每个项目的匹配和得分最高

item,match,matched_to ice,78,ice-cream

下面是我的代码,没什么可看的.

NumItems.Raw = length(words)
NumItems.Ref = length(Ref.Desc)

for (item in words) 
{
  for (refitem in Ref.Desc)
  {
    jarowinkler(refitem,item)

    # Find Best match Score
    # Find Best Item in reference table
    # Add both items to vectors
    # decrement NumItems.Raw
    # Loop
  }
} 

我的问题是，我们希望用户输入这样的代码： 639195-EM-66-XA-53-WX在输入中的某处，因此结果可能如下所示：The code is 639195-EM-66-XA-53-WX, let me in。如果他们在代码中犯了一个小错误（编辑距离为 1），我们仍然希望匹配该字符串。例如The code is 739195-EM-66-XA-53-WX, let me in。（改为6代码7的第一个字母）

即使用户跳过破折号，算法也应该匹配，并且应该忽略小写/大写字母。这些要求很容易满足，因为我可以删除所有破折号并执行 to_uppercase。

有类似的算法吗？

生成与原始代码距离为 1 的所有字符串的计算成本很高。

我也在考虑使用类似 Levenshtein distance 的东西，但忽略用户在第二个字符串中添加的缺失字母，但这会允许代码中间出现错误的字母。

在用户输入中搜索代码似乎好一点，但仍然不是很干净。

在我的应用程序中，我需要通过搜索姓氏和名字来识别一个人。 一个要求是在一定程度上接受拼写错误。

我尝试通过名字和姓氏来识别一个人的身份：

\n
1. 使用 soundex 进行 sql 查询
\n
2. 使用 levenshtein-distance (LD) 进行 sql 查询，该距离是用此 LD 函数计算的
\n

屏幕截图包含一些测试记录和我的 sql 查询的结果，其中包括每列的 soundex 值和 LD

我当前的查询如下所示

SELECT t2.*\n        , t1.Firstname + \' \' + t1.Lastname as SourceName\n        , \'Torsten Mueller\' as TargetName\n        , dbo.FUNC_LEVENSHTEIN(t1.Firstname +\' \'+ t1.Lastname\n                            , \'Torsten Mueller\', 8) as LEVENSHTEIN_Distance     \n FROM #TestSoundex t1\n LEFT JOIN #TestSoundex t2 ON t1.Id = t2.Id\n WHERE t1.Soundex_Firstname = SOUNDEX(\'Torsten\')\n       AND t1.Soundex_Lastname = SOUNDEX(\'Mueller\')\n …

我的adist函数有问题。基本上，我使用的是RDocumentation的示例。

attr(adist(c("kitten", "sitting"), counts = TRUE), "trafos") here

但是，当我尝试运行时，又增加了一个字

attr(adist(c("kitten", "sitting", "hi"), counts = TRUE), "trafos") 

我正在取得这些结果：

     [,1]      [,2]      [,3]     
[1,] "MMMMMM"  "SMMMSMI" "SMDDDDI"

[2,] "SMMMSMD" "MMMMMMM" "SDDDMDD"

[3,] "SMIIIID" "SIIIMII" "MMI" 

在第三列的第三行中，我正在使用MMI，但我无法理解为什么是同一单词“ hi”。因此必须是MM。（匹配，匹配且无插入）

参考：https : //www.rdocumentation.org/packages/utils/versions/3.6.0/topics/adist

我正在使用另一个示例：

test <- c('x','hi', 'y','x')

attr(adist(test, y=NULL , counts = TRUE), "trafos")

我正在取得这些结果。但是至少对角线需要为M，因为同一个单词。

     [,1] [,2] [,3] [,4]
[1,] "M"  "SI" "SI" "MI"

[2,] "SD" "MM" "SD" "SD"

[3,] "SD" "SI" "MI" "SI"

[4,] "MI" "SI" "SI" "MI"

我不明白这是怎么回事。

这是一个字符串T：

'男士衬衫团队 brienne 有趣的讽刺衬衫具有图形 T 恤杯子 婴儿装 真正的激情 辉煌的设计 详细的插图 强烈的欣赏 东西 创意 br 商店 在不同的衬衫上发现了数千种设计 婴儿装杯子 有趣的流行文化 抽象 诙谐 很多设计使一天好起来 几乎所有其他人都会遇到 ul li 质量短袖圆领衬衫 100 棉柔软耐用舒适手感合身标准尺寸怀疑 l xl 可用 li li 可持续性标签公司构想的信念纺织品行业开始采取行动，负责任地制造棉 li li 服装使用 state art 直接服装设备印刷裂纹剥离水洗 li li图形 T 恤设计专业印刷独特的设计看起来很棒让人微笑有趣可爱的复古富有表现力的艺术品 li ul'

我已经突出显示了上面字符串的一部分，因为上面是字符串的预处理版本，因此可能难以阅读。

我得到以下值：

fuzz.partial_ratio('short sleeve', T) 给 50

fuzz.partial_ratio('long sleeve', T) 给 73

fuzz.partial_ratio('dsfsdf sleeve', T) 给 62

fuzz.partial_ratio('sleeve', T) 给 50

我对此感到非常困惑。第一个和第四个值不应该是 100 吗？当然我错过了一些东西，但我无法弄清楚。

编辑：这是我在卸载 python-Levenshtein 库后运行的另一个示例：

'第一个成功方式妻子告诉 v 2 长袖衬衫 …

我有大量包含序列的记录('ATCGTGTGCATCAGTTTCGA ...'),最多500个字符.我还有一个较小序列的列表,通常是10-20个字符.我想使用Levenshtein距离来在记录中找到这些较小的序列,允许小的变化或插入(L_distance <= 2).

问题是我还想获得这些较小序列的起始位置,显然它只比较相同长度的序列.

>>> import Levenshtein
>>> s1 = raw_input('first word: ')
first word: ATCGTAATACGATCGTACGACATCGCGGCCCTAGC
>>> s2 = raw_input('second word: ')
first word: TACGAT
>>> Levenshtein.distance(s1,s2)
29

在这个例子中,我想获得位置(7)和距离(在这种情况下为0).

有没有一种简单的方法来解决这个问题,或者我是否必须将较大的序列分解为较小的序列然后为所有这些序列运行Levenshtein距离？这可能需要太多时间.

谢谢.

更新#Naive实现在查找完全匹配后生成所有子字符串.

def find_tag(pattern,text,errors):       
    m = len(pattern)
    i=0
    min_distance=errors+1
    while i<=len(text)-m:
        distance = Levenshtein.distance(text[i:i+m],pattern)
        print text[i:i+m],distance #to see all matches.
        if distance<=errors:
            if distance<min_distance:
                match=[i,distance]
                min_distance=distance
        i+=1
    return match

#Real example. In this case just looking for one pattern, but we have about 50.
import re, Levenshtein

text = …

是否有任何字符串距离算法没有考虑到单词的顺序？

以下算法未提供所需结果(在该示例中,所需结果应为1):

import jaro
jaro.jaro_winkler_metric(u'Michael Jordan',u'Jordan Michael')
>>>0.47

import Levenshtein
Levenshtein.ratio('Michael Jordan', 'Jordan Michael')
>>>0.5

from difflib import SequenceMatcher
SequenceMatcher(None, 'Michael Jordan', 'Jordan Michael').ratio()
>>>0.5

制作它的一种方法是按字母顺序排列字符串,然后使用上述算法:

''.join(sorted('Michael Jordan'))
>>>' JMaacdehilnor'

''.join(sorted('Jordan Michael'))
>>>' JMaacdehilnor'

但是这里姓名和姓氏的信息丢失了,不会有"稳定"的结果.

我创建了一个使用permutationsfrom 的函数,itertools它接受所有可能的单词编译并比较字符串并输出最大值.结果令人满意,但是当我必须比较数百万个名字时,整个程序真的很慢.

可以做的其他事情是对单词进行排序,例如:

' '.join(sorted('Michael Jordan'.split()))
>>>'Jordan Michael'
' '.join(sorted('Jordan Michael'.split()))
>>>'Jordan Michael'

似乎很好的方式和简单的方法来减少计算,但我们放松了一些敏感的情况.例:

name1 = ' '.join(sorted('Bizen Dim'.split()))
>>>'Bizen Dim'
name2 = ' '.join(sorted('Dim Mpizen'.split()))
>>>'Dim Mpizen'

SequenceMatcher(None, name1, name2).ratio()
>>>  0.55

这两个名字是相同的,有些人将'他们的名字'从'b'翻译成'mp'(我就是其中之一).用这种方式我们就失去了这个'匹配'.

是否有任何字符串距离算法比较单词而不考虑单词的顺序？或者是否有建议如何有效地实现所需的功能？

假设我们有100万行像这样:

import sqlite3
db = sqlite3.connect(':memory:')
c = db.cursor()
c.execute('CREATE TABLE mytable (id integer, description text)')
c.execute('INSERT INTO mytable VALUES (1, "Riemann")')
c.execute('INSERT INTO mytable VALUES (2, "All the Carmichael numbers")')

背景:

我知道如何用Sqlite做到这一点:

• 找到一个单字查询的行,最多有一些拼写错误与spellfix模块和Levenshtein距离(我在这里发布了一个详细的答案,关于如何编译它,如何使用它,...):

  db.enable_load_extension(True)
  db.load_extension('./spellfix')
  c.execute('SELECT * FROM mytable WHERE editdist3(description, "Riehmand") < 300'); print c.fetchall()
  
  #Query: 'Riehmand'
  #Answer: [(1, u'Riemann')]
  

  Run Code Online (Sandbox Code Playgroud)

  使用1M行,这将是超级慢!如此处详述,postgresql可能会对此进行优化trigrams.Sqlite提供的快速解决方案是使用VIRTUAL TABLE USING spellfix:

  c.execute('CREATE VIRTUAL TABLE mytable3 USING spellfix1')
  c.execute('INSERT …

  Run Code Online (Sandbox Code Playgroud)