标签: levenshtein-distance

我正在玩Levenshteins编辑距离算法,我想扩展它来计算换位 - 即相邻字母的交换 - 作为1编辑.未修改的算法计算从另一个字符串到达​​某个字符串所需的插入,删除或替换.例如,从"KITTEN"到"SITTING"的编辑距离是3.这是维基百科的解释:

1. 小猫→坐着(用's'代替'k')
2. sitten→sittin(用'i'代替'e')
3. 坐着→坐着(在结尾插入'g').

按照相同的方法,从"CHIAR"到"CHAIR"的编辑距离为2:

1. CHIAR→CHAR(删除'我')
2. CHAR→CHAIR(插入'I')

我想把它算作"1编辑",因为我只交换两个相邻的字母.我该怎么做呢？

将模式与一组字符串逐个进行比较的最佳方法是什么,同时评估模式与每个字符串匹配的数量？在我使用正则表达式的有限经验中,使用正则表达式匹配字符串似乎是一个非常二元的操作...无论模式有多复杂,最终它要么匹配要么不匹配.我正在寻找更强大的功能,而不仅仅是匹配.是否有与此相关的好技术或算法？

这是一个例子:

假设我有一个模式foo bar,我想找到与以下字符串中最匹配的字符串:

foo for
foo bax
foo buo
fxx bar

现在,这些都没有实际匹配模式,但哪个不匹配最接近匹配？在这种情况下,foo bax它将是最佳选择,因为它匹配7个字符中的6个.

抱歉,如果这是一个重复的问题,当我查看这个问题是否已经存在时,我真的不知道究竟要搜索什么.

问题: 一些R包用Levenshtein距离实现来计算两个字符串的相似性,例如http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html.计算的距离可以很容易地对于弦长度进行归一化,例如通过将Levenshtein距离除以所涉及的最长弦的长度或者将其除以两个弦的长度的平均值.然而,对于语言学中的一些应用(例如方言学和接受多语言研究),建议将原始Levenshtein距离标准化为最长最小成本比对的长度(Heeringa,2004:130-132).从感性 - 语言学的角度来看,这往往会产生更有意义的距离测量.

示例: 德语字符串"tsYklUs"(Zyklus = cycle)可以7个插槽对齐转换为瑞典同源"sYkEl"(cyckel =(bi)循环),其中包含两个插入(I)和两个替换(S)总转化成本为4.标准化Levenshtein距离:4/7

(一个)

t--s--Y--k--l--U--s
---s--Y--k--E--l---
===================
I-----------S--S--I = 4

也可以将8个插槽对齐的字符串转换为3个插入(I)和1个删除(D),总的对齐成本也是4.标准化的Levenshtein距离:4/8

(B)

t--s--Y--k-----l--U--S
---s--Y--k--E--l------
======================
I-----------D-----I--I = 4

后者对准更有意义语言,因为它对准[1]彼此-phonemes而不是与[E]和[U]元音.

问题: 有没有人知道任何R函数可以让我将Levenshtein距离标准化为最长的最低成本比对而不是正确的字符串长度？感谢您的输入!

参考文献: WJ Heeringa(2004),使用Levenshtein距离测量方言发音差异.博士论文,格罗宁根大学.http://www.let.rug.nl/~heeringa/dialectology/thesis/

编辑 - 解决方案:我想我找到了一个解决方案.该adist函数可以返回对齐,并且似乎默认为最长的低成本对齐.举个例子,这里是与sykel和tsyklus相关的对齐方式:

> attr(adist("sykel", "tsyklus", counts = TRUE), "trafos")
     [,1]      
[1,] "IMMMDMII"

为了计算Heeringa(2004)推荐的长度标准化距离,我们可以编写一个适度的函数:

normLev.fnc <- function(a, b) {
  drop(adist(a, b) / nchar(attr(adist(a, b, counts = TRUE), "trafos")))
}

对于上面的示例,这将返回

> normLev.fnc("sykel", "tsyklus")
[1] 0.5

此函数还返回Heeringa(2004:131)示例的正确标准化距离:

> normLev.fnc("bine", "bEi")
[1] …

我用c ++实现了Damerau-Levenshtein距离,但它没有为输入提供正确的o/p(pantera,aorta)正确的o/p是4但是我的代码给出了5 .....

int  editdist(string s,string t,int n,int m) 
{
    int d1,d2,d3,cost;
    int i,j;
    for(i=0;i<=n;i++) 
    {
        for(j=0;j<=m;j++)
        {
          if(s[i+1]==t[j+1]) 
              cost=0;
          else
              cost=1;
          d1=d[i][j+1]+1;
          d2=d[i+1][j]+1;
          d3=d[i][j]+cost;
          d[i+1][j+1]=minimum(d1,d2,d3);
          if(i>0 && j>0 && s[i+1]==t[j] && s[i]==t[j+1] )   //transposition
          {
              d[i+1][j+1]=min(d[i+1][j+1],d[i-1][j-1]+cost);
          }
        }
    }
    return d[n+1][m+1]; 
}

我没有看到任何错误.有人可以发现代码有问题吗？

我在C++中使用Levenshtein Distance算法比较两个字符串来衡量它们彼此之间的距离.然而,普通的Levenshtein距离算法不区分由空格界定的单词边界.这导致距离计算小于我想要的距离.我正在比较标题,看它们彼此有多接近,我希望算法不会将字符计算为匹配,如果它们来自多个单词.

例如,如果我比较这两个字符串,我会得到以下结果,+指定匹配并-指定不匹配:

Al Chertoff Et
Al Church Department of finance Et
+++++------+--++-----++-+------+++
Al Ch      e  rt     of f       Et

我得到一个距离为20,在"Chertoff"四个单词中匹配单词,"Church Department of finance"而我真的希望它们被认为是彼此更远的,因为不允许字符与多个单词匹配并且与单词的距离为25 "Chertoff"大多数匹配一个单词"Department",三个字符匹配:

Al Chertoff Et
Al Church Department of finance Et
+++--------+--++---------------+++
Al         e  rt                Et
         Ch     off

我怎样才能调整Levenshtein距离来实现这个目标,还是有另一种距离算法更适合这个？也许在每个单词上使用Levenshtein距离单独单词工作并选择距离最短的单词？但是,如果将一个单词深深地匹配到字符串中会导致后续单词匹配得不好,因为它们的匹配在字符串中最早？这可能以某种方式完成,Levenshtein距离适应于单词级别吗？

例如,对于以下更复杂的示例,这个想法的最短距离是20:

Al Chertoff Deport Et
Al Church Department of finance Et
+++++----++++-++---------------+++
Al Ch     Dep rt                Et
     ertoff  o

而不是最大化"Chertoff"匹配并获得24的更长距离:

Al Chertoff Deport Et
Al …

我一直在尝试聚集多个URL数据集(每个约100万个),以查找每个URL的原始和拼写错误.我决定使用levenshtein距离作为相似性度量,并将dbscan作为聚类算法,因为k-means算法不起作用,因为我不知道聚类的数量.

我使用Scikit-learn实现dbscan时遇到了一些问题.

下面的代码片段适用于我使用的格式的小数据集,但由于它预先计算整个距离矩阵,因此占用O(n ^ 2)空间和时间,对于我的大型数据集来说太过分了.我已经运行了好几个小时,但它最终只占用了我的电脑的所有内存.

lev_similarity = -1*np.array([[distance.levenshtein(w1[0],w2[0]) for w1 in words] for w2 in words])
dbscan = sklearn.cluster.DBSCAN(eps = 7, min_samples = 1)
dbscan.fit(lev_similarity)

所以我想我需要一些方法来动态计算相似性,因此尝试了这种方法.

dbscan = sklearn.cluster.DBSCAN(eps = 7, min_samples = 1, metric = distance.levenshtein)
dbscan.fit(words)

但这种方法最终给我一个错误:

ValueError: could not convert string to float: URL

我意识到这意味着它试图将输入转换为相似函数浮动.但我不希望它这样做.据我所知,它只需要一个可以接受两个参数并返回一个浮点值的函数,然后它可以与mp进行比较,这是levenshtein距离应该做的.

我被困在这一点上,因为我不知道sklearn的dbscan的实现细节,以找出它为什么试图将它转换为float,而且我对如何避免O(n ^ 2)矩阵也没有更好的想法计算.

如果有更好或更快的方法来聚集这些我可能忽略的字符串,请告诉我.

我有一个带有自由文本字段的数据库，我想将其用于filteradata.frame或tibble。我也许可以通过大量工作创建一个数据中当前出现的搜索词的所有可能拼写错误的列表（请参阅下面一个术语的所有拼写示例），然后我可以像下面的示例代码一样stringr::str_detect使用。然而，当将来可能出现更多拼写错误时，这并不安全。如果我愿意接受一些限制/做出一些假设（例如，拼写错误之间的编辑距离可能有多远，或者就其他一些差异而言，人们不会使用完全不同的术语等），是否有一些做模糊版本的简单解决方案str_detect？

据我所知，明显的软件包似乎stringdist没有直接执行此操作的功能。我想我可以编写自己的函数，将类似stringdist::afind或的东西应用于向量的每个元素，并后处理结果以最终返回或布尔stringdist::amatch值的向量，但我想知道这个函数是否不存在于某处（并且更有效地实现）比我会做的）。TRUEFALSE

这是一个示例，说明了我如何str_detect可能会错过我想要的一行：

library(tidyverse)

search_terms = c("preclinical", "Preclincal", "Preclincial", "Preclinial", 
                 "Precllinical", "Preclilnical", "Preclinica", "Preclnical", 
                 "Peclinical", "Prclinical", "Peeclinical", "Pre clinical", 
                 "Precclinical", "Preclicnial", "Precliical", "Precliinical", 
                 "Preclinal", "Preclincail", "Preclinicgal", "Priclinical")

example_data = tibble(project=c("A111", "A123", "B112", "A224", "C149"),
                      disease_phase=c("Diabetes, Preclinical", "Lipid lowering, Perlcinical", 
                                      "Asthma, Phase I", "Phase II; Hypertension", "Phase 3"),
                      startdate = c("01DEC2018", "17-OKT-2017", "11/15/2019", "1. Dezember 2004", "2005-11-30")) 

# Finds only project …

我正在为Microsoft Office套件构建一个私有的拼写检查程序.我正在对拼写错误进行字符串比较,以及确定我想要包含哪些更正的潜在修复方法.

对于加权 Damerau-Levenshtein公式进行字符串比较,我看起来很高和很低,因为我希望交换,插入,删除和替换都具有不同的权重,而不仅仅是"1"的权重,所以我可以优先考虑一些更正超过其他人.例如,错字"agmes"理论上可以纠正为"游戏" 或 "年龄",因为两者都只需要一个编辑就可以移动到正确拼写的单词,但我想让"交换"编辑的权重更低,所以"游戏"将显示为首选更正.

我正在使用Excel进行分析,因此我使用的任何代码都需要在Visual Basic for Applications(VBA)中.我能找到的最好的是这个例子,看起来很棒,但它是用Java编写的.我尽力转换,但我远非专家,可以使用一点帮助!

任何人都可以看看附加的代码,并帮我弄清楚什么是错的？

谢谢!

编辑:我让它自己工作.这是VBA中加权的Damerau-Levenshtein公式.它使用Excel的内置数学函数进行一些评估.当将拼写错误与两种可能的校正进行比较时,具有最高成本的校正是首选字.这是因为两次掉期的成本必须大于删除和插入的成本,如果您分配成本最低的掉期(我认为这是理想的),这是不可能的.如果您需要更多信息,请查看Kevin的博客.

Public Function WeightedDL(source As String, target As String) As Double

    Dim deleteCost As Double
    Dim insertCost As Double
    Dim replaceCost As Double
    Dim swapCost As Double

    deleteCost = 1
    insertCost = 1.1
    replaceCost = 1.1
    swapCost = 1.2

    Dim i As Integer
    Dim j As Integer
    Dim k As Integer

    If Len(source) = 0 Then
        WeightedDL = Len(target) * insertCost
        Exit Function …

有没有办法计算2个字符串之间的%匹配？

我有一种情况,如果有85%,需要计算2个字符串之间的匹配

匹配然后我将结合2个表,我已经编写了组合2个表的代码

我的示例字符串是:

var str1 = 'i love javascript';
var str2 = 'i love javascripttt';

var matchPer = match(str1,str2); // result might be 80% , 85%, 90% ,95% etc

设置:我有关于人员及其父母姓名的数据,我想找到兄弟姐妹(父母姓名相同的人).

 pdata<-data.frame(parents_name=c("peter pan + marta steward",
                                 "pieter pan + marta steward",
                                 "armin dolgner + jane johanna dough",
                                 "jack jackson + sombody else"))

这里的预期输出将是一列,表示前两个观察属于X族,而第三和第四列各自属于一个独立的族.例如:

person_id    parents_name                           family_id
1            "peter pan + marta steward",           1
2            "pieter pan + marta steward",          1
3            "armin dolgner + jane johanna dough",  2
4            "jack jackson + sombody else"          3

目前的方法:我对距离度量很灵活.目前,我使用Levenshtein编辑距离匹配obs,允许两个字符的差异.但是,如果它们运行得更快,其他变体如"最大公共子串"将会很好.

对于较小的子样本,我stringdist::stringdist在循环中使用stringdist::stringdistmatrix,但随着样本量的增加,这变得越来越低效.

一旦使用某个样本大小,矩阵版本就会爆炸.我极其低效的循环尝试是:

#create data of the same complexity using random last-names
#(4mio obs and ~1-3 kids per parents) …