如何在Java或Kotlin中实现字符串精确差异检测及相似度计算？

核心思路 #

基于编辑距离算法（Levenshtein距离）实现，既能计算相似度，也能定位具体差异。编辑距离指将一个字符串转换成另一个所需的最少编辑操作（插入、删除、替换）次数，以此为基础推导相似度，同时通过回溯编辑路径找出具体差异位置。

一、相似度百分比计算 #

实现逻辑 #

相似度 = (1 - 编辑距离 / 两个字符串的最大长度) × 100%，结果保留两位小数，同时处理两个字符串均为空的极端情况。

Kotlin代码示例 #

fun calculateSimilarity(s1: String, s2: String): Double {
    if (s1.isEmpty() && s2.isEmpty()) return 100.0
    val maxLength = maxOf(s1.length, s2.length)
    val editDistance = computeLevenshteinDistance(s1, s2)
    return ((1.0 - editDistance.toDouble() / maxLength) * 100).run {
        String.format("%.2f", this).toDouble()
    }
}

private fun computeLevenshteinDistance(s1: String, s2: String): Int {
    val dp = Array(s1.length + 1) { IntArray(s2.length + 1) }
    for (i in 0..s1.length) dp[i][0] = i
    for (j in 0..s2.length) dp[0][j] = j
    
    for (i in 1..s1.length) {
        for (j in 1..s2.length) {
            val cost = if (s1[i-1] == s2[j-1]) 0 else 1
            dp[i][j] = minOf(
                dp[i-1][j] + 1,    // 删除操作
                dp[i][j-1] + 1,    // 插入操作
                dp[i-1][j-1] + cost // 替换操作
            )
        }
    }
    return dp[s1.length][s2.length]
}

二、差异可视化实现 #

实现逻辑 #

通过回溯Levenshtein距离的DP表，标记不同类型的差异：

• 原字符串中被删除的字符：用红色删除线标记
• 目标字符串中新增的字符：用绿色下划线标记
• 被替换的字符：用黄色背景标记

Kotlin代码示例（Android SpannableString实现） #

fun getDiffSpannable(original: String, target: String): SpannableString {
    val dp = computeLevenshteinDistanceDP(original, target)
    val diffResult = StringBuilder()
    val spans = mutableListOf<Pair<IntRange, Any>>()
    
    var i = original.length
    var j = target.length
    
    while (i > 0 || j > 0) {
        when {
            i > 0 && j > 0 && original[i-1] == target[j-1] -> {
                diffResult.append(original[i-1])
                i--
                j--
            }
            i > 0 && (j == 0 || dp[i-1][j] + 1 == dp[i][j]) -> {
                // 标记原字符串删除的字符
                val start = diffResult.length
                diffResult.append(original[i-1])
                spans.add(start..diffResult.length-1 to object : StrikethroughSpan() {
                    override fun updateDrawState(ds: TextPaint) {
                        super.updateDrawState(ds)
                        ds.color = Color.RED
                    }
                })
                i--
            }
            j > 0 && (i == 0 || dp[i][j-1] + 1 == dp[i][j]) -> {
                // 标记目标字符串新增的字符
                val start = diffResult.length
                diffResult.append(target[j-1])
                spans.add(start..diffResult.length-1 to object : UnderlineSpan() {
                    override fun updateDrawState(ds: TextPaint) {
                        super.updateDrawState(ds)
                        ds.color = Color.GREEN
                    }
                })
                j--
            }
            else -> {
                // 标记被替换的字符（显示目标字符）
                val start = diffResult.length
                diffResult.append(target[j-1])
                spans.add(start..diffResult.length-1 to BackgroundColorSpan(Color.YELLOW))
                i--
                j--
            }
        }
    }
    
    val reversed = diffResult.reverse().toString()
    val spannable = SpannableString(reversed)
    spans.forEach { (range, span) ->
        // 反转后转换索引位置
        val reversedStart = reversed.length - range.last - 1
        val reversedEnd = reversed.length - range.first
        spannable.setSpan(span, reversedStart, reversedEnd, Spannable.SPAN_EXCLUSIVE_EXCLUSIVE)
    }
    return spannable
}

// 返回DP表用于回溯差异路径
private fun computeLevenshteinDistanceDP(s1: String, s2: String): Array<IntArray> {
    val dp = Array(s1.length + 1) { IntArray(s2.length + 1) }
    for (i in 0..s1.length) dp[i][0] = i
    for (j in 0..s2.length) dp[0][j] = j
    
    for (i in 1..s1.length) {
        for (j in 1..s2.length) {
            val cost = if (s1[i-1] == s2[j-1]) 0 else 1
            dp[i][j] = minOf(
                dp[i-1][j] + 1,
                dp[i][j-1] + 1,
                dp[i-1][j-1] + cost
            )
        }
    }
    return dp
}

Android端使用方式 #

val originalStr = "Java easy"
val targetStr = "Jva easie"
val similarity = calculateSimilarity(originalStr, targetStr)
similarityTextView.text = "相似度: $similarity%"
diffTextView.text = getDiffSpannable(originalStr, targetStr)

三、优化建议 #

• 性能优化：处理超长字符串时，可限制对比的最大长度（如前1000字符），或用滚动数组优化DP表的空间占用。
• 样式自定义：根据需求修改Span的颜色、样式，比如用不同字体颜色区分差异类型。
• 多语言兼容：上述代码天然支持Unicode字符，可直接处理中文、日文等非英文字符。

内容的提问来源于stack exchange，提问作者Varun A M