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

Question

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

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

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

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

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

Answer 1

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

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

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