Levenshtein距离
class String
def levenshtein(other, ins=2, del=2, sub=1)
return nil if self.nil?
return nil if other.nil?
dm = []
dm[0] = (0..self.length).collect { |i| i * ins }
fill = [0] * (self.length - 1)
for i in 1..other.length
dm[i] = [i * del, fill.flatten]
end
for i in 1..other.length
for j in 1..self.length
dm[i][j] = [
dm[i-1][j-1] +
(self[j-1] == other[i-1] ? 0 : sub),
dm[i][j-1] + ins,
dm[i-1][j] + del
].min
end
end
dm[other.length][self.length]
end
end
s1 = "ACUGAUGUGA"
s2 = "AUGGAA"
d1 = s1.levenshtein(s2) # 9
s3 = "pennsylvania"
s4 = "pencilvaneya"
d2 = s3.levenshtein(s4) # 7
s5 = "abcd"
s6 = "abcd"
d3 = s5.levenshtein(s6) # 0
定义similar?
def similar?(other,thresh=2)
if self.levenshtein(other) < thresh
true
else
false
end
end
"polarty".similar?("hilarity")
分享到:
相关推荐
在信息技术领域,字符串处理是常见的任务之一,其中计算两个字符串的相似度是尤为重要的一个环节。Levenshtein算法,也称为编辑距离算法,就是用于衡量两个字符串之间差异程度的一种方法。本文将深入探讨如何使用...
在"用Levenshtein距离算法最快的JS实现来测量两个字符串之间的差异"这个主题中,我们关注的是如何高效地在JavaScript中执行这个算法。通常,Levenshtein距离的计算会涉及到二维数组的填充,这可能导致性能问题,尤其...
在Python编程环境中,Levenshtein库是一个非常实用的工具,用于计算两个字符串之间的编辑距离。编辑距离,也称为Levenshtein距离,是衡量两个字符串差异的一种度量,定义为由一个字符串转换成另一个字符串最少的单...
编辑距离,又称Levenshtein距离,是一种衡量两个字符串相似度的指标,广泛应用于文本处理、数据校验、搜索引擎优化等多个领域。这个概念源于俄国科学家瓦迪姆·列文斯坦在1965年提出,它定义了将一个字符串转换成另...
编辑距离,又称Levenshtein距离,是一种衡量两个字符串相似度的方法。它是通过计算将一个字符串转换成另一个字符串所需的最少单字符编辑(插入、删除或替换)次数来定义的。在文本处理、生物信息学、搜索建议等领域...
1. **levenshtein_distance()**:这是计算两个字符串之间Levenshtein距离的主要函数。它返回一个整数值,表示将一个字符串转换为另一个字符串所需的最小编辑距离。 2. **ratio()**:此函数返回两个字符串的相似度,...
这个文件中可能定义了一个或多个函数,用于计算两个字符串之间的Levenshtein距离,并可能提供了一些辅助函数,用于处理字符串操作和结果的返回。 `LevenshteinUnit.dcu` 是编译后的单位对象文件,包含了经过编译的`...
最终,矩阵的右下角元素就是两个字符串的Levenshtein距离。 编辑距离算法的应用非常广泛,例如: - **拼写检查**:通过计算用户输入的单词与词库中正确单词的编辑距离,可以找出最接近的匹配项,辅助纠正拼写错误...
在这个名为"LevenshteinDistance"的项目中,我们有一个简单的Java实现来计算两个字符串之间的Levenshtein距离。该项目可能包含以下关键组件: 1. **算法实现**:Java代码会实现一个二维动态规划矩阵,用于存储两个...
通过计算两个字符串的词袋模型向量之间的夹角余弦值来衡量相似性。词袋模型忽略了词语的顺序,只关注词汇的出现与否。 7. **Smith-Waterman 算法**: 在生物信息学中常用,通过局部对齐找到两个序列的最大匹配...
这个算法主要用于衡量两个字符串之间的差异,即需要进行多少次单字符操作(插入、删除或替换)才能将一个字符串转换为另一个字符串。在文本处理、信息检索、生物信息学等领域有着广泛的应用。 字符串相似度是评估两...
3. **余弦相似度**:它通过计算两个字符串的向量在高维空间中的夹角余弦值来评估相似性。每个字符串被看作是一个词频向量,向量的夹角越小,相似度越高。 4. **Hamming距离**:如果两个字符串长度相同,Hamming距离...
Python 中可以使用 LevenshteinDistance 函数来计算两个字符串之间的编辑距离。 FuzzyWuzzy 是一个 Python 库,用于字符串模糊匹配。它提供了多种字符串相似度计算方法,包括 ratio、partial_ratio、token_sort_...
通过上述实现,我们可以有效地计算两个字符串之间的相似度,并根据需要进行排序。然而,这种方法存在一些潜在的问题: - **性能问题**:对于非常大的字符串,这种逐字符比较的方式可能会非常慢。 - **多字节字符处理...
在上述代码中,`LevenshteinDistance`函数接受两个字符串作为参数,并返回它们之间的Levenshtein距离。初始化二维数组`dp`用于存储中间结果,`min`函数用于找到三个整数中的最小值。 从压缩包文件"levenshtein-...
3. **余弦相似度**:这是一种基于向量空间模型的方法,通过计算两个字符串的词频向量的夹角余弦值来确定它们的相似性。在Delphi中,可以先将字符串转换为词频向量,然后使用向量的点积和模长来计算相似度。 4. **...
题目编号为1298的问题,要求实现计算两个字符串之间的编辑距离。具体来说,输入两个字符串`a`和`b`,输出从字符串`a`转换到字符串`b`所需的最少编辑操作次数。此题在信息学奥林匹克竞赛(NOIP)中有出现,并且给出了三...
Levenshtein Distance(简称LD),又称编辑距离,是衡量两个字符串相似度的一种方法。这个概念由俄国科学家Vladimir Levenshtein在1965年提出,因此得名。 编辑距离定义了将一个字符串转换成另一个字符串所需的最少...
在这个前端项目中,“l-digity”是一个JavaScript库,它提供了一个简单易用的API,使得开发者可以方便地在前端代码中计算两个字符串的Levenshtein距离。例如,你可以使用它来判断用户输入的单词是否与预设的关键词...