クラウドMacで検証するiOS編集距離：Unicodeと計算予算

検索ボックスで入力ミスに対する候補を提示する場合、編集距離の実装は数十行で済むことが多い一方、中国語、結合アクセント、絵文字を含む入力では計算を誤りがちです。テストをクラウドMacの固定の作業ディレクトリに置けば、異なるタイムゾーンで働くメンバーも同じSwiftのサンプルを使えます。重要なのはマシンの速さを比べることではなく、「1文字」の定義と、1回の比較に許容する計算量を固定することです。

距離の定義と文字の扱いを固定する

この記事ではLevenshtein距離を使います。挿入・削除・置換をそれぞれ1回と数え、隣接する文字の入れ替えを1回とは数えません。そのため、abからbaへの距離は2であり、1ではありません。自動修正で入れ替え操作を扱う必要がある場合は、期待値だけを変更するのではなく、アルゴリズムを変更してください。

文字列はSwiftのCharacter、つまり拡張書記素クラスタ単位に分割します。家族の絵文字は複数のUnicodeスカラーで構成されていても、比較では1文字として扱います。また、合成済み形式と分解形式で表された等価なアクセント付き文字は、Swiftの文字の等価性判定では等しいとみなされる場合があります。

大文字・小文字の同一視、全角・半角の変換、アクセントの除去は、距離関数の役割ではありません。製品でこれらの規則が必要なら、独立した前処理層を設け、元のテキストも併せて保存してください。

距離が小さいということは、選択した操作モデルで変更回数が少ないことだけを意味します。2つの語の意味が近いことを示すものではなく、本人照合やセキュリティ上の判断の根拠として、そのまま使うこともできません。

計算予算付きのローリング配列を実装する

クラウドMacでxcrun swift --versionが実行できることを確認し、以下の内容をedit-distance.swiftとして保存します。この実装では直前と現在の2行だけを保持し、短いほうの入力を列方向に配置することで、行列全体の保存を避けます。

入力には3つの上限を設けます。各文字列はUTF-8で最大16384バイト、最大512文字とし、2つの文字列の文字数の積は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、中国語の文字1つを使い、長さが3以下の短い文字列をすべて生成して、任意の2つの文字列について次を確認します。

• 自分自身との距離は0であり、引数の順序を入れ替えても結果は変わらない。
• 距離は、2つの文字列の文字数の差の絶対値以上になる。
• 距離は、2つの文字列の文字数のうち大きいほう以下になる。

さらに、少数の文字列の三つ組で三角不等式も確認します。これらの性質が成り立っても、アルゴリズムが完全に正しいことの証明にはならないため、結果が既知のテストと併用する必要があります。予算を超える入力には、距離を返すことを要求したり、これらの性質の検証に参加させたりしないでください。

前処理層のテストを分離する

検索で大文字・小文字を区別しない場合は、前処理の出力を個別に検証したうえで、その出力同士の距離を検証します。動的計画法のループ内で現在のロケールに依存する変換を呼び出してはいけません。同じ語の組み合わせでも環境によって結果が変わる可能性があり、各セルで変換コストも繰り返し発生するためです。

パイプラインに組み込み、総計算量を制限する

スクリプトをアプリのコードと一緒にコミットし、単体テストの前に実行します。終了コードが非ゼロなら、後続の処理を止めます。ソースコードのコミット識別子、Swiftのバージョン、失敗したサンプルを記録してください。実経過時間を基準にミリ秒単位のしきい値を設ける必要はありません。共有環境では実行中のタスクの負荷が変動し、そのようなしきい値は判定のノイズになるためです。

1回の比較に予算があっても、検索リクエスト全体の予算があるとは限りません。候補語は、まず業務上のカテゴリや文字数の差で絞り込み、そのうえで候補数を制限します。キャンセルに対応する場合は、候補の処理と処理の間でキャンセル状態を確認してください。同期的な距離関数は、外側のタスクがキャンセルされても自動的には中断しません。

リリース前に、空入力の扱い、上限超過エラーの表示、候補全体の予算、前処理のバージョンの4項目を整えてください。上限を超えた場合は、明確に「未計算」として返し、非常に大きな距離に見せかけてはいけません。これにより、検索結果の順位付けで、リソース保護のための措置がテキストの類似度の低さを示す根拠として誤って扱われることを防げます。

よくある質問