Levenshtein Алгоритм сравнения расстояний/строк для фраз

Question

У меня есть две таблицы, каждая из которых предоставляет информацию о связке приложений, работающих в моей работе. Они были созданы двумя отдельными людьми, которые никогда, казалось, не соответствовали друг другу.

В результате имена, которые они предоставили приложениям, не являются постоянными между листами. Они, однако, схожи. Например, можно было бы назвать приложение «Office 2010», другое «MS Office 10» или что-то еще.

Я искал алгоритм Левенштейна, но это, похоже, применимо только к отдельным словам или фразам, где порядок слов постоянный, и только орфография отличается. (Я не компьютерный ученый, не стесняйтесь меня поправить).

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

Любые идеи? Спасибо всем, кто может помочь.

Answer 1

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

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

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