Здравствуйте, Artazor, Вы писали:
A>Зело спасибствую.
A>То, что нужно нести в ячейке не одно число — я сообразил, но не по-левенштейновски.
Достаточно одного числа. Это просто признак какое действие было совершено. Его можно вычислить на обратном проходе. Просто кода будет чуть больше. А хранить его не обязательно.
A>А тут всего лишь bool.
Ну по смыслу это не bool, конечно, а enum (или что-то другое перечислимое). Просто тут действий всего два: вставка и замена. Так например у расстояния Дамерау—Левенштейна действий четыре, поэтому если хранить, то потребуется уже два бита.
A>Для этого у меня созрел план:
A>1) Найти длиннейшую общую подпоследовательность в строках Haystack и Needle: Common = "RX153aa"
A>2) Найти наименьшую подстроку из Haystack содержащую данную подпоследовательноть Common: Chunk = "RX153afla"
A>3) Посчитать расстояние Демеро-Левенштейна между Needle и Chunk: damlev("RX153afla","RX153-alfa") = 2; (один инсершн, и одна транспозиция) ну и соотнести с длинной Needle, вычтя полученное соотношение из 1.
Вообще, такой подход мне не нравится. Например, он может очень плохо работать в случае появления лишних символов в needle, которые с чем-нибудь там совпадут в тексте.
A>Собственно Haystack — это то что набрал оператор. Возможно с ошибками. Но проблема в том, что от оператора приходит не сам код (иначе можно было бы считать расстояние по Дамеро-Левенштейну), а фраза, СОДЕРЖАЩАЯ код где-то посерёдке. Причём окружение кода может быть произвольным, например
Всё же лучше считай сразу расстояние Дамеро-Левенштейна между полным образцом и полным текстом. Просто возьми эти граничные условия:
WM>Можно начинать с любого символа из haystack — на соответсвующей стороне матрицы будут нули (а не 0,1,2,3,… как в Левенштейне);Можно закончить на любом символе из haystack (а не только в углу матрицы).
Эта простые модификации позволят тебе сразу найти кусок в тексте, который наиболее похож на образец.
Такой способ будет более устойчив к ошибкам в выборе общей части, чем в твоём варианте. К тому же он ещё и работать будет быстрее.
