Проверка расстояния редактирования iOS на облачном Mac

Когда строке поиска нужно предлагать варианты исправления опечаток, реализация расстояния редактирования часто занимает всего несколько десятков строк. Но на китайских иероглифах, комбинируемых диакритических знаках и эмодзи легко получить неверный результат. Если разместить тесты в постоянном рабочем каталоге облачного Mac, участники команды из разных часовых поясов смогут использовать один и тот же набор примеров на Swift. Главное здесь — не сравнить скорость машин, а зафиксировать, что считается «одним символом» и какой объём вычислений допустим для одного сравнения.

Фиксируем модель расстояния и правила подсчёта символов

В этой статье используется расстояние Левенштейна: вставка, удаление и замена имеют стоимость один, а перестановка соседних символов не считается одной операцией. Поэтому расстояние от ab до ba равно двум, а не одному. Если автокоррекция должна учитывать перестановку как отдельную операцию, нужно заменить алгоритм, а не просто изменить ожидаемый результат.

Строки разбиваются на элементы Swift Character, то есть расширенные графемные кластеры. Семейный эмодзи может содержать несколько скалярных значений Unicode, но участвует в сравнении как один символ. Эквивалентные символы с диакритикой в предсоставленной и разложенной формах могут считаться равными в соответствии с семантикой сравнения символов 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 и одного китайского иероглифа все строки длиной не более трёх символов. Для каждой пары проверьте:

• Расстояние строки до самой себя равно нулю, а перестановка аргументов не меняет результат.
• Расстояние не меньше абсолютной разности длин строк в символах.
• Расстояние не больше максимальной из длин двух строк в символах.

Затем проверьте неравенство треугольника на небольшом числе троек. Выполнение этих свойств не доказывает полную корректность алгоритма, поэтому такие проверки нужно сочетать с примерами, для которых результат известен заранее. Для входных данных, выходящих за пределы бюджета, не следует требовать вычисления расстояния или включать их в проверки этих свойств.

Тестируем слой предобработки отдельно

Если поиск не учитывает регистр, сначала отдельно проверьте результат предобработки, а затем — расстояние между полученными строками. Не вызывайте преобразования, зависящие от текущей локали, внутри цикла динамического программирования. Иначе результат для одной и той же пары слов может зависеть от окружения, а затраты на преобразование будут повторяться в каждой ячейке.

Подключаем проверки к CI и ограничиваем общий объём работы

Добавьте скрипт в репозиторий вместе с кодом приложения и запускайте его перед модульными тестами. Ненулевой код завершения должен блокировать последующие шаги. Записывайте идентификатор коммита, версию Swift и пример, вызвавший сбой. Задавать миллисекундные пороги по фактическому времени выполнения необязательно: изменения нагрузки от других задач на общей машине будут вносить шум.

Наличие бюджета у одного сравнения ещё не означает, что ограничен весь поисковый запрос. Сначала сузьте список кандидатов по категории, используемой в продукте, или по разнице длин, а затем ограничьте их количество. Если нужна отмена, проверяйте её состояние между кандидатами: синхронная функция расстояния не прервётся автоматически при отмене внешней задачи.

Перед выпуском определите четыре вещи: политику для пустого ввода, отображение ошибок превышения лимита, общий бюджет кандидатов и версию предобработки. При превышении лимита нужно явно возвращать «не вычислено», а не маскировать отказ под очень большое расстояние. Тогда ранжирование результатов поиска не примет защиту ресурсов за свидетельство непохожести текстов.

Часто задаваемые вопросы