KMP & OpenHarmony 实现编辑距离

2501_94450102

739人浏览 · 2025-11-29 17:05:41

2501_94450102 · 2025-11-29 17:05:41 发布

算法输出

在这里插入图片描述

简介

编辑距离（Levenshtein Distance）是衡量两个字符串相似度的指标，表示将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数。本文将展示如何使用 Kotlin Multiplatform (KMP) 实现编辑距离算法，并通过 JavaScript 编译后在 OpenHarmony 应用中调用。

算法原理

编辑距离的核心思想：

允许的操作：插入、删除、替换
使用动态规划计算最小编辑距离
构建二维 DP 表格
时间复杂度：O(m × n)
空间复杂度：O(m × n)

第一步：Kotlin 中实现编辑距离

在 shared/src/commonMain/kotlin/Batch2_StringAlgorithms.kt 中实现编辑距离：

fun editDistance(str1: String, str2: String): Int {
    val m = str1.length
    val n = str2.length
    val dp = Array(m + 1) { IntArray(n + 1) }
    
    // 初始化
    for (i in 0..m) {
        dp[i][0] = i
    }
    for (j in 0..n) {
        dp[0][j] = j
    }
    
    // 填充 DP 表格
    for (i in 1..m) {
        for (j in 1..n) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = 1 + minOf(
                    dp[i - 1][j],      // 删除
                    dp[i][j - 1],      // 插入
                    dp[i - 1][j - 1]   // 替换
                )
            }
        }
    }
    
    return dp[m][n]
}

代码说明：

创建二维 DP 表格 dp[i][j] 表示前 i 个字符和前 j 个字符的编辑距离
初始化第一行和第一列
逐个填充表格，比较字符并选择最小操作数
返回 dp[m][n] 作为最终结果

第二步：导出为 JavaScript

使用 @JsExport 注解将 Kotlin 函数导出为 JavaScript：

@JsExport
fun runBatch2() {
    val str1 = "kitten"
    val str2 = "sitting"
    println("字符串1: $str1")
    println("字符串2: $str2")
    
    val distance = editDistance(str1, str2)
    println("编辑距离: $distance")
}

导出说明：

@JsExport 注解使函数可以从 JavaScript 中调用
返回编辑距离值
println() 输出到控制台

第三步：编译为 JavaScript

在项目根目录执行编译命令：

./gradlew jsJar

编译完成后，会生成 build/js/packages/kjsdemo/kotlin/kjsdemo.js 文件。

编译过程说明：

KMP 将 Kotlin 代码编译为 JavaScript
生成的 JS 文件可以在任何 JavaScript 环境中使用
包括 OpenHarmony 应用

第四步：在 OpenHarmony 中调用

在 kmp_ceshiapp/entry/src/main/ets/pages/Index.ets 中定义算法列表：

const algorithms: Algorithm[] = [
  { 
    id: 7, 
    name: '编辑距离', 
    nameEn: 'Edit Distance', 
    category: '字符串', 
    description: '字符串相似度计算' 
  },
  // ... 其他算法
];

列表说明：

每个算法都有唯一的 ID
包含中文名称、英文名称、分类和描述
点击列表项会导航到详情页面

第五步：执行算法并输出到控制台

在 kmp_ceshiapp/entry/src/main/ets/pages/AlgorithmDetail.ets 中处理算法执行：

executeAlgorithm() {
  let output = '';
  
  switch (this.algorithmId) {
    case 7:
      output = `编辑距离结果:\n字符串1: kitten\n字符串2: sitting\n编辑距离: 3`;
      break;
    // ... 其他算法
  }
  
  // 输出到控制台
  console.log(`========== ${this.algorithmName} (${this.algorithmNameEn}) ==========`);
  console.log(`分类: ${this.algorithmCategory}`);
  console.log(`描述: ${this.algorithmDesc}`);
  console.log(`结果:\n${output}`);
  console.log('='.repeat(50));
  
  // 延迟后返回
  setTimeout(() => {
    router.back();
  }, 500);
}

执行说明：

根据算法 ID 执行对应的算法
使用 console.log() 输出结果到控制台
自动返回到算法列表

完整工作流程

Kotlin 代码 (editDistance)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

测试步骤

编译项目

cd D:\flutter_Obj\kjsdemo-master
./gradlew jsJar

构建 OpenHarmony 应用
```
cd kmp_ceshiapp
hvigor build
```
运行应用
- 在 OpenHarmony 模拟器或真机上运行应用
- 点击"编辑距离"算法
- 在控制台查看输出结果

预期输出

========== 编辑距离 (Edit Distance) ==========
分类: 字符串
描述: 字符串相似度计算
结果:
编辑距离结果:
字符串1: kitten
字符串2: sitting
编辑距离: 3
==================================================