Существует ли алгоритм расстояния редактирования, который принимает во внимание “перемещение блока”?
Это связано с тем, что выходной слой является узлом с сигмовидной активацией, который возвращает значения от 0 до 1. Поэтому результат никогда не будет 1 (или 0), поэтому код всегда будет возвращать «cat». ]
5 ответов
Взгляните на метрику расстояния Жаккара (JDM). Это старое, но хорошее дело, которое довольно хорошо разбирается в несоответствиях на уровне токенов, таких как фамилия, имя, фамилия. Для двух сравнений строк расчет JDM - это просто количество уникальных символов, общих для двух строк, деленное на общее количество уникальных символов между ними (другими словами, пересечение над объединением). Например, учитывая два аргумента «JEFFKTYZZER» и «TYZZERJEFF», числитель равен 7, а знаменатель - 8, что дает значение 0,875. Мой выбор символов в качестве токенов - не единственный доступный, кстати, н-граммы тоже часто используются.
Думаю, вы ищете расстояние Яро-Винклера , которое точно используется для сопоставления имен.
Я не уверен, что вам действительно нужно расстояние редактирования - которое работает просто для строк символов - или семантическое расстояние - выбирая наиболее подходящее или похожее значение. Вы можете посмотреть разделы поиска информации , чтобы узнать, как отличить наиболее подходящий термин / фразу для конкретного термина или фразы. В некотором смысле вы сравниваете очень короткие документы, а не строки символов.
В случае вашего приложения вам, вероятно, следует подумать об адаптации некоторых алгоритмов из биоинформатики.
Например, вы могли бы сначала объединить свои строки, убедившись, что все разделители - это пробелы или что-то еще вам нравится, что вы бы сравнили «Алан Тьюринг» с «Тьюринг Алан». Затем разделите одну из строк и выполните алгоритм точного сопоставления строк (например, Horspool -алгоритм) с частями другой строки, подсчитывая количество совпадающих подстрок.
Если вы хотите найти совпадения, которые просто похожи, но не равны, что-то вроде локального выравнивания может быть более подходящим, поскольку оно дает оценку, описывающую сходство, но упомянутый алгоритм Смита-Уотермана, вероятно, немного избыточен для вашего приложения и даже не является лучшим доступным алгоритмом локального выравнивания.
В зависимости от вашей среды программирования существует вероятность того, что реализация уже доступна. Я лично в последнее время работал с SeqAn , которая является библиотекой биоинформатики для C ++ и определенно обеспечивает желаемую функциональность.
Что ж, это был довольно абстрактный ответ, но я надеюсь, что он укажет вам правильное направление , но, к сожалению, в нем нет простой формулы для решения вашей проблемы.
Вы можете обнаружить расстояние сжатия полезно для этого. См. ответ, который я дал на очень похожий вопрос .
Или вы можете использовать систему подсчета на основе k-кортежей:
- Выберите небольшое значение k, например k = 4.
- Извлеките все подстроки вашей строки длиной k в список.
- Отсортируйте список. (O (knlog (n) time.)
- Сделайте то же самое для другой строки, с которой вы сравниваете. Теперь у вас есть два отсортированных списка.
- Подсчитайте количество k-кортежей, общих для двух строк. Если строки имеют длину n и m, это можно сделать за O (n + m) раз, используя слияние списков, так как списки отсортированы.