【编程实践】计算文本、字符串相似度:Levenshtein 距离
2023-09-27 14:24:38 时间
目录
Levenshtein 距离简介
Perplexity AI:
https://www.perplexity.ai/
The Levenshtein distance is a measure of the similarity between two strings, which is calculated by counting the number of deletions, insertions, or substitutions required to transform one string into another[1][2][3]. It can be used to measure the difference between two words or phrases[4][5].
Levenshtein 距离是两个字符串之间相似性的度量,它是通过计算将一个字符串转换为另一个字符串所需的删除、插入或替换的次数来计算的 [1][2][3]。它可以用来衡量两个词或短语之间的差异[4][5]。
Open AI:
用Kotlin实现计算文本、字符串相似度:Levenshtein 距离的代码示例
/**
* 计算两个文本、字符串之间的Levenshtein距离
* @param s1 文本、字符串1
* @param s2 文本、字符串2
* @return Levenshtein距离
*/
fun levenshteinDistance(s1: String, s2: String): Int {
var n = s1.length
var m = s2.length
if (n == 0) return m
if (m == 0) return n
var d = Array(n + 1) { IntArray(m + 1) }
// 初始化
for (i in 0..n) d[i][0] = i
for (j in 0..m) d[0][j] = j
// 计算
for (i in 1..n) {
for (j in 1..m) {
val cost = if (s1[i - 1] == s2[j - 1]) 0 else 1
d[i][j] = minOf(
d[i - 1][j] + 1,
d[i][j - 1] + 1,
d[i - 1][j - 1] + cost
)
}
}
return d[n][m]
}
我写的(网上抄的):
package com.github.aixcode.utils
import com.github.aixcode.utils.TextDistanceUtil.getSimilarity
object TextDistanceUtil {
/**
* Returns the Levenshtein distance between a and b, result 0~1
*/
fun getLevenshteinDistance(X: String, Y: String): Int {
val m = X.length
val n = Y.length
val T = Array(m + 1) { IntArray(n + 1) }
for (i in 1..m) {
T[i][0] = i
}
for (j in 1..n) {
T[0][j] = j
}
var cost: Int
for (i in 1..m) {
for (j in 1..n) {
cost = if (X[i - 1] == Y[j - 1]) 0 else 1
T[i][j] = Integer.min(Integer.min(T[i - 1][j] + 1, T[i][j - 1] + 1),
T[i - 1][j - 1] + cost)
}
}
return T[m][n]
}
fun getSimilarity(x: String, y: String): Double {
val maxLength = java.lang.Double.max(x.length.toDouble(), y.length.toDouble())
return if (maxLength > 0) {
// 如果需要,可以选择忽略大小写
(maxLength - getLevenshteinDistance(x, y)) / maxLength
} else 1.0
}
}
fun main() {
println(getSimilarity("c", "cql")) // 0.3333333333333333
println(getSimilarity("cq", "cql")) // 0.6666666666666666
println(getSimilarity("cql", "cql")) // 1.0
}
相关文章
- Js计算指定日期
- Haskell 学习笔记-03:函数式编程与量子计算
- 大数据-Hadoop-MapReduce(一):离线数据编程分析框架【Java语言】【运算效率低;被SparkCore的RDD编程取代】【不擅长实时计算、不擅长流式计算、不擅长DAG计算】
- 含有分布式电源的三相不平衡配电网潮流计算【IEEE33节点】(Matlab代码实现)
- 当今云计算的挑战:规划,流程和人员
- 利用C#编程计算某个字符在某个字符串中出现的次数【转】
- 托管与云计算之间的IT业务连续性计划的不同之处
- 计算Div标签内Checkbox个数或已被disabled的个数
- 3.知识图谱业务落地技术推荐之图神经网络算法库&图计算框架汇总
- 【云计算】Docker监控相关资料
- 2015年中国云计算市场回顾与展望
- 5G加速商业化 移动边缘计算测试年内完成
- Flink大数据实时计算系列-Flink的累加器和计数器
- 阿里云全力助推重庆云计算产业发展