在搜索、推荐、纠错、模糊匹配等场景中，我们经常需要回答一个看似简单的问题：
两个字符串到底有多像？

Levenshtein 编辑距离是解决这一问题的经典算法之一，它度量了从一个字符串变成另一个字符串所需的最少编辑次数（插入、删除、替换）。
本案例基于 Kotlin Multiplatform（KMP）与 OpenHarmony，实现了一个字符串编辑距离与相似度评分工具：

• 计算两个字符串的 Levenshtein 编辑距离；
• 给出 0–100% 的相似度评分；
• 统计替换 / 插入 / 删除三类操作次数；
• 生成对齐示意，帮助直观看出差异位置；
• 提供 ArkTS 单页面板，支持在终端设备上交互式体验。

---

一、Levenshtein 编辑距离简介

对于两个字符串 \( s \) 和 \( t \)，Levenshtein 编辑距离定义为：
从 \( s \) 经过插入一个字符、删除一个字符、替换一个字符三种操作，最少多少步能变成 \( t \)。

示例：

• kitten → sitting 的编辑距离为 3，一种合理的编辑序列是：
  • kitten → sitten （将 k 替换为 s）
  • sitten → sittin （将 e 替换为 i）
  • sittin → sitting（插入 g）

我们还可以基于距离给出一个相似度评分：

[
similarity = 1 - \frac{distance}{\max(|s|, |t|)}
]

并将其转成百分比展示。

---

二、Kotlin 字符串编辑距离分析引擎

1. 输入格式设计

为与现有案例风格统一，本案例使用文本键值形式的输入：

STR-A:kitten
STR-B:sitting

支持：

• 多行输入；
• 使用 | 或 ; 分隔（如 STR-A:foo|STR-B:bar）。

解析逻辑在 Kotlin 中由 parseStringPairInput 完成：

private data class StringPair(
    val first: String,
    val second: String
)

private fun parseStringPairInput(raw: String): StringPair? {
    val parts = raw.split("\n", "|", ";")
        .map { it.trim() }
        .filter { it.isNotEmpty() }

    var a: String? = null
    var b: String? = null

    for (part in parts) {
        when {
            part.startsWith("STR-A", ignoreCase = true) -> {
                a = part.substringAfter(":", "").trim()
            }
            part.startsWith("STR-B", ignoreCase = true) -> {
                b = part.substringAfter(":", "").trim()
            }
        }
    }

    val s1 = a
    val s2 = b
    return if (s1 != null && s2 != null) StringPair(s1, s2) else null
}

---

2. 分析入口：stringEditDistanceAnalyzer

在 App.kt 中，我们通过 @JsExport 暴露了如下分析函数：

@JsExport
fun stringEditDistanceAnalyzer(inputData: String): String {
    val sanitized = inputData.trim()
    if (sanitized.isEmpty()) {
        return "❌ 输入为空，请按 STR-A:hello\\nSTR-B:world 形式提供两个字符串"
    }

    val (a, b) = parseStringPairInput(sanitized)
        ?: return "❌ 未解析到 STR-A / STR-B，请检查输入格式"

    val distResult = levenshteinDistance(a, b)
    val distance = distResult.distance
    val maxLen = maxOf(a.length, b.length).coerceAtLeast(1)
    val similarity = 1.0 - distance.toDouble() / maxLen.toDouble()

    val builder = StringBuilder()
    builder.appendLine("🧮 字符串编辑距离与相似度分析报告")
    builder.appendLine("━━━━━━━━━━━━━━━━━━━━━━━━━━")
    builder.appendLine("STR-A: \"$a\" (长度: ${a.length})")
    builder.appendLine("STR-B: \"$b\" (长度: ${b.length})")
    builder.appendLine()

    builder.appendLine("📏 Levenshtein 编辑距离: $distance")
    builder.appendLine("🔗 相似度评分: ${round2(similarity * 100)}%")
    builder.appendLine()

    builder.appendLine("📊 操作统计")
    builder.appendLine("  替换 (substitutions): ${distResult.substitutions}")
    builder.appendLine("  插入 (insertions): ${distResult.insertions}")
    builder.appendLine("  删除 (deletions): ${distResult.deletions}")
    builder.appendLine()

    builder.appendLine("🧷 对齐视图（仅示意，非唯一方案）")
    builder.appendLine("A': ${distResult.alignedA}")
    builder.appendLine("B': ${distResult.alignedB}")

    return builder.toString().trim()
}

输出内容涵盖：

• 两个原始字符串与长度；
• 编辑距离与相似度百分比；
• 三类编辑操作统计；
• 对齐后的字符串示意。

---

3. DP 算法与路径回溯

3.1 结果结构体

private data class EditDistanceResult(
    val distance: Int,
    val substitutions: Int,
    val insertions: Int,
    val deletions: Int,
    val alignedA: String,
    val alignedB: String
)

3.2 Levenshtein DP 实现

private fun levenshteinDistance(a: String, b: String): EditDistanceResult {
    val n = a.length
    val m = b.length

    if (n == 0 && m == 0) {
        return EditDistanceResult(0, 0, 0, 0, "", "")
    }

    val dp = Array(n + 1) { IntArray(m + 1) }

    for (i in 0..n) {
        dp[i][0] = i
    }
    for (j in 0..m) {
        dp[0][j] = j
    }

    for (i in 1..n) {
        for (j in 1..m) {
            val cost = if (a[i - 1] == b[j - 1]) 0 else 1
            val delete = dp[i - 1][j] + 1
            val insert = dp[i][j - 1] + 1
            val replace = dp[i - 1][j - 1] + cost
            dp[i][j] = minOf(delete, insert, replace)
        }
    }

    var i = n
    var j = m
    val alignedA = StringBuilder()
    val alignedB = StringBuilder()
    var substitutions = 0
    var insertions = 0
    var deletions = 0

    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] && a[i - 1] == b[j - 1]) {
            alignedA.append(a[i - 1])
            alignedB.append(b[j - 1])
            i--
            j--
        } else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
            alignedA.append(a[i - 1])
            alignedB.append(b[j - 1])
            substitutions++
            i--
            j--
        } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
            alignedA.append(a[i - 1])
            alignedB.append('-')
            deletions++
            i--
        } else if (j > 0 && dp[i][j] == dp[i][j - 1] + 1) {
            alignedA.append('-')
            alignedB.append(b[j - 1])
            insertions++
            j--
        } else {
            break
        }
    }

    val alignedAStr = alignedA.reverse().toString()
    val alignedBStr = alignedB.reverse().toString()

    return EditDistanceResult(
        distance = dp[n][m],
        substitutions = substitutions,
        insertions = insertions,
        deletions = deletions,
        alignedA = alignedAStr,
        alignedB = alignedBStr
    )
}

复杂度分析：

• 时间复杂度：\( O(nm) \)，其中 \( n = |a|, m = |b| \)；
• 空间复杂度：\( O(nm) \)（可优化为 O(min(n,m))，此处以可读性为主）。

同时，我们在 DP 填表完成后，从右下角回溯到左上角，构造了一份对齐示意，并统计替换/插入/删除操作数量。

---

三、JavaScript / ArkTS 集成

通过 @JsExport，stringEditDistanceAnalyzer 已经被编译到 hellokjs.js 中，并在 hellokjs.d.ts 暴露：

export declare function stringEditDistanceAnalyzer(inputData: string): string;

在 ArkTS 中，你可以直接：

import { stringEditDistanceAnalyzer } from './hellokjs';

// ...
this.result = stringEditDistanceAnalyzer(this.inputData);

inputData 内容类似：

STR-A:kitten
STR-B:sitting

即可获得完整的分析报告字符串。

---

四、ArkTS 单页面板设计建议

建议将该案例挂在首页（Index 页面），布局风格参考前几个算法案例：

• 顶部标题：「字符串编辑距离与相似度评分」；
• 输入区域：
  • 两个输入框或一个多行 TextArea，显示 STR-A / STR-B 示例；
  • 右上角显示两个字符串的长度；
• 操作区域：
  • 「▶ 运行相似度分析」按钮；
  • 「↻ 填入示例 (kitten / sitting)」按钮；
• 结果区域：
  • 编辑距离与相似度百分比；
  • 替换/插入/删除操作统计；
  • 对齐视图（A': ... / B': ...）。

配合你现有的深蓝卡片UI，可以打造一个很适合作为“字符串工具箱”一员的可视化面板。

---

五、典型应用场景

1. 搜索联想与模糊匹配

   • 比较用户输入与候选字符串的相似度，过滤掉差距过大的结果。

2. 拼写纠错

   • 计算用户输入单词与词典单词的编辑距离，推荐最相近的几个候选。

3. 去重与归一化

   • 对相似名称（如商品名、联系人名）进行聚类时，用相似度评分作为聚合依据。

4. 日志与监控中的模糊匹配

   • 判断新的异常信息与历史日志模板的相似度，辅助归类与告警聚合。

---

六、总结

本案例通过 Levenshtein 编辑距离，将抽象的「字符串相似度」量化为一个直观的数字，并给出可解释的对齐视图与操作统计。
在 KMP + OpenHarmony 的架构下，我们实现了：

1. 一次实现，多端复用 的编辑距离算法核心；
2. 在 OpenHarmony 设备端通过 ArkTS UI 提供了交互式的相似度分析体验；
3. 与之前的时间序列分析、任务依赖调度、括号匹配等案例形成互补，进一步丰富了你的算法案例库维度。

无论是学习算法、构建实际工具，还是作为日常「玩算法」的小实验，这个字符串编辑距离与相似度评分案例都非常实用。***

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net