云端 Mac 上的 iOS 编辑距离验收：Unicode 字符与计算预算

搜索框需要给拼写错误提供候选词时，编辑距离往往只有几十行代码，却容易在中文、组合重音和表情输入上算错。把测试放进云端 Mac 的固定工作目录，可以让跨时区成员复用同一份 Swift 样本；关键不是比较机器跑得多快，而是固定“一个字符”的含义，以及一次比较最多允许多少计算。

固定距离与字符契约

本文使用 Levenshtein 距离：插入、删除、替换各计一次，不把相邻交换算成一次。因此 ab 到 ba 的距离是二，不是一。自动纠错若需要交换操作，应更换算法，不能只调整期望值。

字符串按 Swift Character 拆分，即扩展字素簇。一个家庭表情可能包含多个标量，但作为一个字符参与比较；预组合与分解形式的等价重音字符，在 Swift 字符相等语义下可以相等。

大小写折叠、全半角转换、去重音不属于距离函数。若产品需要这些规则，应先建立独立预处理层，并同时保存原始文本。

距离较小只表示所选操作模型下修改较少，不代表两个词语义相近，也不能直接作为身份匹配或安全判断依据。

实现带预算的滚动数组

在云端 Mac 上确认 xcrun swift --version 可执行，将下面内容保存为 edit-distance.swift。实现只保留前后两行，把较短输入放在列方向，避免保存整张矩阵。

输入设置三道边界：每串最多 16384 个 UTF-8 字节、512 个字符，两串长度乘积最多 65536。这些数字是示例工程预算，不是性能测试结论。生产环境应依据候选词数量和交互延迟目标调整。

enum DistanceError: Error {
    case inputLimit
    case workLimit
}

func distance(_ lhs: String, _ rhs: String) throws -> Int {
    guard lhs.utf8.count <= 16_384,
          rhs.utf8.count <= 16_384 else {
        throw DistanceError.inputLimit
    }

    let a = Array(lhs)
    let b = Array(rhs)
    guard a.count <= 512, b.count <= 512 else {
        throw DistanceError.inputLimit
    }

    if a.isEmpty { return b.count }
    if b.isEmpty { return a.count }

    guard a.count <= 65_536 / b.count else {
        throw DistanceError.workLimit
    }

    let columns = a.count <= b.count ? a : b
    let rows = a.count <= b.count ? b : a
    var previous = Array(0...columns.count)
    var current = Array(repeating: 0, count: columns.count + 1)

    for i in rows.indices {
        current[0] = i + 1
        for j in columns.indices {
            let substitution = previous[j]
                + (rows[i] == columns[j] ? 0 : 1)
            current[j + 1] = min(
                previous[j + 1] + 1,
                min(current[j] + 1, substitution)
            )
        }
        swap(&previous, &current)
    }
    return previous[columns.count]
}

除法检查避免先乘后判带来的整数溢出。空串在除法前返回，消除除零风险。字节限制先于数组构造，防止少量字符携带大量组合标记时，仅靠字符数限制仍接受过大的输入。

添加可直接执行的验收样本

把以下代码接在同一文件末尾，再运行 xcrun swift edit-distance.swift。使用显式失败函数，不依赖可能在优化配置下被关闭的断言。

func require(_ condition: Bool) {
    if !condition { fatalError("Distance contract failed") }
}

let fixtures: [(String, String, Int)] = [
    ("", "", 0),
    ("", "构建", 2),
    ("kitten", "sitting", 3),
    ("构建", "构件", 1),
    ("ab", "ba", 2),
    ("\u{00E9}", "e\u{0301}", 0),
    ("👨‍👩‍👧‍👦", "", 1)
]

for (a, b, expected) in fixtures {
    let forward = try distance(a, b)
    let backward = try distance(b, a)
    require(forward == expected)
    require(backward == expected)
}

do {
    _ = try distance(
        String(repeating: "a", count: 257),
        String(repeating: "b", count: 257)
    )
    fatalError("Expected work limit")
} catch DistanceError.workLimit {
}

这组样本分别验证初始化、替换、交换语义和 Unicode 单位。预算拒绝测试只接收指定错误，其他错误会继续向外传播，不能被宽泛捕获后误判为通过。

用性质测试覆盖组合输入

固定样本能抓住已知错误，组合测试则适合发现行交换、边界初始化和重复字符处理缺陷。继续使用 a、b、一个中文字符组成长度不超过三的全部短串，对任意两串验证：

• 自身距离为零，交换参数后结果不变。
• 距离不小于字符长度差的绝对值。
• 距离不大于两个字符长度的最大值。

再对少量三元组检查三角不等式。性质成立不能证明算法完全正确，所以必须与已知结果并用。对超出预算的输入，不应要求返回距离或参与这些性质比较。

分离预处理层测试

若搜索会忽略大小写，单独验证预处理输出，再验证输出之间的距离。不要在动态规划循环中调用与当前区域有关的转换，否则同一词对可能随环境变化，而且每个单元都会重复承担转换成本。

接入流水线并限制总工作量

将脚本与应用代码一同提交，在单元测试之前执行，非零退出即阻断后续步骤。记录源码提交标识、Swift 版本与失败样本，不必依赖墙上时钟设定毫秒级阈值；共享任务负载变化会让这种阈值产生噪声。

一次比较有预算，不代表整个搜索请求有预算。候选词应先按业务类别或长度差缩小范围，再限制候选数量。需要取消时，在候选之间检查取消状态；同步距离函数不会因为外层任务取消而自动中断。

上线前补齐四项：空输入策略、超限错误展示、候选总预算、预处理版本。超限应明确返回“未计算”，不能伪装成一个很大的距离。这样搜索排序才不会把资源保护措施误当成文本不相似的证据。

常见问题