雲端 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 版本與失敗樣本，不必依賴實際經過時間設定毫秒級門檻；共用機器上的工作負載變化，會讓這類門檻產生雜訊。

單次比較有預算，不代表整個搜尋請求也有預算。候選詞應先依業務類別或長度差縮小範圍，再限制候選數量。需要取消時，應在候選詞之間檢查取消狀態；同步距離函式不會因為外層工作取消就自動中斷。

上線前須補齊四項：空輸入策略、超限錯誤的呈現方式、候選詞總預算，以及前處理版本。超限時應明確回傳「未計算」，不能偽裝成一個很大的距離。如此才能避免搜尋排序將資源保護措施誤當成文字不相似的證據。

常見問題