Я хочу использовать функции сходства строк для поиска поврежденных данных в моей базе данных.
Я наткнулся на несколько из них:
Я хотел знать, в чем разница между ними и в каких ситуациях они работают лучше всего?
Расширение моего комментария wiki-walk в errata и отмечая некоторые из литературы на первом этаже по сравнению алгоритмов, применимых к подобным проблемным пространствам, рассмотрим применимость этих алгоритмов, прежде чем мы определим, численно ли они сопоставимы.
Из Википедии Jaro-Winkler:
В информатике и статистике расстояние Яро-Винклера (Winkler, 1990) является мерой сходства между двумя строками. это вариант метрики расстояния Яро (Jaro, 1989, 1995) и главным образом [править], используемые в области записи связи (дубликат обнаружения). Чем выше расстояние Jaro-Winkler для двух строк, тем более похожи строки. Показателем расстояния Яро-Винклера является разработан и наилучшим образом подходит для коротких строк, таких как имена людей. оценка нормализуется так, что 0 не приравнивается к подобию, а 1 - точное соответствие.
В теории информации и информатике расстояние Левенштейна является строковой метрикой для измерения величины разницы между двумя последовательности. Термин "расстояние редактирования" часто используется для ссылки конкретно до расстояния Левенштейна.
Расстояние Левенштейна между двумя строками определяется как минимальное количество изменений, необходимых для преобразования одной строки в другую, с допустимые операции редактирования - это вставка, удаление или замена одного символа. Он назван в честь Владимира Левенштейн, который считал это расстояние в 1965 году.
В математике евклидовым расстоянием или евклидовой метрикой является "обычное" расстояние между двумя точками, которое можно измерить с помощью правителя, и дается формулой Пифагора. Используя эту формулу как расстояние, евклидово пространство (или даже любое внутреннее пространство произведения) становится метрическое пространство. Соответствующая норма называется евклидовой нормой. Старая литература относится к метрике как пифагорейская метрика.
И Q- или n-граммовое кодирование:
В областях вычислительной лингвистики и вероятности n-грамм является последовательной последовательностью из n элементов из заданной последовательности текста или речь. Эти предметы могут быть фонемами, слогами, буквами, слов или пар оснований в соответствии с приложением. n-граммы собранных из текстового или речевого корпуса.
Два основных преимущества n-граммовых моделей (и алгоритмы, которые используют их) относительная простота и возможность масштабирования - просто увеличение модели может быть использовано для хранения большего количества контекста с помощью хорошо понимаемый компромисс между пространством и временем, позволяющий проводить небольшие эксперименты масштабируются очень эффективно.
Проблема заключается в том, что эти алгоритмы решают различные проблемы, которые имеют различную применимость в пространстве всех возможных алгоритмов для решения проблемы самой длинной общей подпоследовательности, в ваши данные или прививку используемого metric. На самом деле, не все из них являются даже метриками, так как некоторые из них не удовлетворяют неравенству треугольника .
Вместо того, чтобы идти по пути определения сомнительной схемы обнаружения повреждения данных, сделать это правильно: используя контрольные суммы и бит четности для ваших данных. Не пытайтесь решить гораздо более сложную проблему, когда будет выполняться более простое решение.
Сходство строк очень много. Например
Но поскольку один размер не подходит всем. Каждый алгоритм сходства строк разработан для конкретного использования, хотя большинство из них схожи. Например Levenshtein_distance о том, сколько char вы измените, чтобы сделать две строки равными.
kitten → sitten
Здесь расстояние составляет 1 символ. Вы можете давать разные веса для удаления, добавления и замены. Например, ошибки OCR и ошибки клавиатуры дают меньше веса для некоторых изменений. OCR (некоторые символы очень похожи на другие), клавиатура некоторых символов очень близка друг к другу. Сходство биоинформационных струн позволяет много вставлять.
Ваш второй пример " Jaro-Winkler метрика расстояния спроектирована и наилучшим образом подходит для коротких строк, таких как имена людей
Поэтому вы должны помнить о своей проблеме.
Я хочу использовать функции сходства строк для поиска поврежденных данных в моей базе данных.
Как ваши данные повреждены? Это ошибка пользователя, аналогичная ошибке ввода с клавиатуры? Или это похоже на ошибки OCR? Или что-то еще?