Расстояние редактирования с выравниванием

Минимальное число вставок, удалений и замен между двумя короткими строками и один оптимальный путь выравнивания.

Ваш пример

До 80 кодовых точек Unicode в каждой строке. Пустая строка разрешена. Регистр, пробелы и составные знаки различаются; нормализация не выполняется.

Разбор примера

Минимум операций: 1

Один оптимальный путь; ∅ обозначает отсутствие символа
ПараИз исходнойВ нужнойДействие
1ккСовпадение
2оиЗамена
3ттСовпадение
  1. Первые строка и столбец таблицы соответствуют вставке или удалению всего префикса.
  2. В каждой клетке выбираем минимум стоимости трёх возможных продолжений.
  3. Выравнивание читается слева направо; это соответствие символов, а не номера позиций для редактирования изменяющейся строки.
Длина исходной строки
3
Длина нужной строки
3
Расстояние
1

Метод и условия расчёта

Динамическая таблица хранит расстояние между префиксами. Каждый переход — вставка, удаление или замена стоимостью 1; совпадение стоит 0.

Теория к методу

Условная проверенная строка «тихий дом» содержит девять символов с пробелом. OCR выдал «тихий дм»: пропущена одна буква. При единичной стоимости правки CER равен 1/9, приблизительно 11,1%. Это ошибка распознавания выбранной строки, а не процент ошибок во всей старой книге.

Выберите контрольный фрагмент по изображению и вручную сверьте его транскрипцию. Эталон нельзя получать простым копированием проверяемого OCR: тогда общая ошибка окажется невидимой. Запишите страницу, область и правило обработки переносов, пробелов и знаков. Одной уверенности в понятном смысле предложения недостаточно для посимвольной проверки.

Пример: Эталон «лес» распознан как «лессс». Что означает CER при единичных правках?

Нужны две вставки с, длина эталона равна трём: CER=2/3≈66,7%. Это не две ошибки на пять распознанных знаков: в данной метрике знаменатель берётся из эталона. Проверяемое утверждение относится только к этой строке.

Вопросы по теме

Это проверка правильности слова?

Нет. Расстояние сравнивает последовательности кодовых точек, не проверяет словарь, смысл или правописание.

Почему может быть другое правильное выравнивание?

Минимальных путей иногда несколько. Здесь при равенстве выбирается диагональный переход, затем удаление, затем вставка.

Можно ли исключить пробелы?

Можно объявить такую процедуру заранее, но оценка будет отвечать другому правилу. Между системами и повторными проверками правило сохраняют.

Низкий CER гарантирует правильную фамилию?

Нет. Одна редкая фамилия может быть испорчена при хорошем среднем показателе. Для исторического вывода проверяют конкретное значимое место.

Методы алгоритмов: углубление: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.