클라우드 Mac에서 검증하는 iOS 편집 거리와 유니코드 경계

검색창에서 오타 교정 후보를 제시할 때 편집 거리 구현은 수십 줄이면 충분한 경우가 많습니다. 하지만 중국어, 결합형 발음 구별 기호, 이모지 입력에서는 잘못된 결과가 나오기 쉽습니다. 테스트를 클라우드 Mac의 고정 작업 디렉터리에 두면 서로 다른 시간대의 팀원도 같은 Swift 샘플을 재사용할 수 있습니다. 핵심은 어느 머신이 더 빠른지 비교하는 것이 아니라, ‘한 문자’의 의미와 한 번의 비교에 허용할 연산량을 명확히 정하는 데 있습니다.

거리 모델과 문자 단위 확정하기

이 글에서는 레벤슈타인 거리를 사용합니다. 삽입, 삭제, 치환은 각각 한 번의 연산으로 세며, 인접한 문자 교환을 한 번의 연산으로 취급하지 않습니다. 따라서 ab에서 ba까지의 거리는 1이 아니라 2입니다. 자동 교정에 교환 연산이 필요하다면 예상값만 바꿀 것이 아니라 알고리즘을 바꿔야 합니다.

문자열은 Swift의 Character, 즉 확장 자소 클러스터 단위로 나눕니다. 가족 이모지는 여러 유니코드 스칼라로 구성될 수 있지만 비교할 때는 한 문자로 취급합니다. 미리 조합된 형태와 분해된 형태의 동등한 악센트 문자는 Swift의 문자 동등성 규칙에 따라 같다고 판단될 수 있습니다.

대소문자 폴딩, 전각·반각 변환, 발음 구별 기호 제거는 거리 함수의 역할이 아닙니다. 제품에 이런 규칙이 필요하다면 별도의 전처리 계층을 만들고 원문도 함께 보존해야 합니다.

거리가 작다는 것은 선택한 연산 모델에서 수정 횟수가 적다는 뜻일 뿐입니다. 두 단어의 의미가 비슷하다는 뜻은 아니며, 신원 매칭이나 보안 판단의 근거로 바로 사용할 수도 없습니다.

연산 한도를 둔 롤링 배열 구현하기

클라우드 Mac에서 xcrun swift --version이 실행되는지 확인한 뒤, 다음 내용을 edit-distance.swift로 저장합니다. 이 구현은 이전 행과 현재 행만 유지하며, 더 짧은 입력을 열 방향에 배치해 전체 행렬을 저장하지 않습니다.

입력에는 세 가지 한도를 둡니다. 각 문자열은 UTF-8 기준 최대 16384바이트, 최대 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]
}

나눗셈으로 한도를 검사하면 먼저 곱한 뒤 검사할 때 발생할 수 있는 정수 오버플로를 피할 수 있습니다. 빈 문자열은 나눗셈 전에 결과를 반환하므로 0으로 나눌 위험도 없습니다. 바이트 한도는 배열을 만들기 전에 검사합니다. 적은 수의 문자에 결합 부호가 대량으로 붙어 있으면 문자 수 제한만으로는 지나치게 큰 입력을 걸러낼 수 없기 때문입니다.

바로 실행할 수 있는 검증 샘플 추가하기

다음 코드를 같은 파일 끝에 붙이고 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 {
}

이 샘플들은 초기화, 치환, 교환 처리 규칙, 유니코드 비교 단위를 검증합니다. 연산 한도 초과로 입력을 거부하는 테스트는 지정한 오류만 받아들입니다. 다른 오류는 그대로 상위로 전파되어야 하며, 포괄적으로 잡아 테스트가 통과한 것으로 잘못 처리해서는 안 됩니다.

성질 테스트로 입력 조합 검증하기

고정 샘플은 이미 알려진 오류를 잡는 데 유용하고, 조합 테스트는 행 교환, 경계 초기화, 반복 문자 처리의 결함을 찾는 데 적합합니다. a, b, 중국어 문자 하나로 길이가 3 이하인 모든 짧은 문자열을 만들고, 가능한 모든 문자열 쌍에 대해 다음을 검증합니다.

• 자기 자신과의 거리는 0이며, 인수의 순서를 바꿔도 결과가 같습니다.
• 거리는 두 문자열의 문자 수 차이의 절댓값보다 작지 않습니다.
• 거리는 두 문자열의 문자 수 중 큰 값보다 크지 않습니다.

이어서 소수의 문자열 세 쌍에 대해 삼각 부등식도 확인합니다. 이런 성질이 성립한다고 알고리즘의 완전한 정확성이 증명되는 것은 아니므로, 결과를 이미 아는 사례와 함께 사용해야 합니다. 한도를 넘는 입력에는 거리 반환을 요구하거나 이런 성질 비교에 참여시켜서는 안 됩니다.

전처리 계층 테스트 분리하기

검색에서 대소문자를 구분하지 않는다면 먼저 전처리 결과를 별도로 검증한 뒤, 그 결과 사이의 거리를 검증합니다. 동적 계획법 루프 안에서 현재 로케일에 의존하는 변환을 호출하지 마세요. 같은 단어 쌍의 결과가 환경에 따라 달라질 수 있고, 각 셀에서 변환 비용까지 반복해서 발생합니다.

파이프라인에 연결하고 전체 작업량 제한하기

스크립트를 애플리케이션 코드와 함께 커밋하고 단위 테스트 전에 실행합니다. 종료 코드가 0이 아니면 이후 단계를 차단해야 합니다. 소스 커밋 식별자, Swift 버전, 실패한 샘플을 기록합니다. 실제 경과 시간을 기준으로 밀리초 단위 임계값을 설정할 필요는 없습니다. 공유 환경에서 다른 작업의 부하가 달라지면 이런 임계값에 잡음이 생깁니다.

한 번의 비교에 연산 한도가 있다고 해서 검색 요청 전체에도 한도가 있는 것은 아닙니다. 먼저 서비스에서 사용하는 분류나 길이 차이로 후보 범위를 좁힌 뒤 후보 수를 제한해야 합니다. 취소가 필요하면 후보 사이에서 취소 상태를 확인합니다. 동기 거리 함수는 바깥쪽 작업이 취소되었다고 자동으로 중단되지 않습니다.

배포 전에는 빈 입력 처리 정책, 한도 초과 오류 표시, 전체 후보 처리 예산, 전처리 버전의 네 가지를 확정해야 합니다. 한도를 넘으면 명확하게 ‘계산하지 않음’을 반환해야 하며, 매우 큰 거리값으로 위장해서는 안 됩니다. 그래야 검색 순위 로직이 자원 보호 조치를 텍스트가 서로 다르다는 근거로 오해하지 않습니다.

자주 묻는 질문