Алгоритм сравнения строк, релевантность, насколько «похожи» 2 строки

Question

У меня есть 2 источника информации для одних и тех же данных (компании), к которым я могу присоединиться через уникальный идентификатор (номер договора). Наличие второго, другого источника связано с тем, что 2 источника обновляются вручную, независимо. Итак, у меня есть ID и компания Имя в 2 таблицах.

Мне нужно придумать алгоритм , который бы сравнивал Имя в 2 таблицах для одного и того же ID и упорядочил все компании по переменная, которая указывает, насколько разные строки (чтобы выделить самые разные, чтобы быть в верхней части списка).

Я посмотрел на простой алгоритм вычисления расстояния Левенштейна, но он на буквенном уровне, поэтому я все еще ищу что-то лучшее.

Причина, по которой Левенштейн на самом деле не выполняет свою работу, заключается в следующем: у компаний есть название, префикс или постфикс с организационной формой (LTD, JSC, co. И т. Д.). Так что у нас может быть много JSC "Foo", которое будет сильно отличаться от Foo JSC., но то, что я действительно ищу в базе данных, это пары разных строк, таких как SomeLongCompanyName JSC и JSC OtherName.

Есть ли хорошие способы сделать это? (Мне не очень нравится идея использовать регулярные выражения для разделения слов в каждой строке, а затем находить совпадения для каждого слова в другой строке, используя расстояние Левенштейна, поэтому я ищу другие идеи)

Answer 1

Как насчет:
1. Заменить все знаки пунктуации на пробелы.
2. Разбить строку на слова, разделенные пробелами.
3. Переместить все слова из <= 4 символов в конец, отсортированныев алфавитном порядке. <br>4. Левенштейн.

Answer 2

Не могли бы вы отфильтровать (удалить) эти "общие слова" (аналогично удалению стоп-слов для полнотекстовой индексации) и затем выполнить поиск по ним?Если нет, то не могли бы вы отсортировать слова в алфавитном порядке перед сравнением?

В качестве альтернативы или в дополнение к расстоянию Левенштейна вы можете использовать Soundex .Это не очень хорошо, но его можно использовать для индексации данных (что невозможно при использовании Левенштейна).

Answer 3

Спасибо вам обоим за идеи. Я использовал 4 индекса, которые представляют собой расстояния Левенштейна, деленные на сумму длины обоих слов (относительных расстояний) следующего:

• Всего 2 строки
• Строка, состоящая из результата после разделения последовательностей слов, исключения символов без слов, упорядочения по возрастанию и объединения с пробелом в качестве разделителя.
• Строка, заключенная в кавычки (если такой строки нет, берется исходная строка)
• Строка, состоящая из алфавитно упорядоченных первых символов каждого слова.

каждое из них, в свою очередь, является целочисленным значением от 1 до 1000. Результирующее значение является произведением:
X1^E1 * X2^E2 * X3^E3 * X4^E4
Где X1..X4 - это индексы, а E1..E4 - предоставляемые пользователем предпочтения для значимого (значимого) каждого индекса. Чтобы сохранить результат в пределах разумных значений 1..1000, вектор (E1..E4) нормализуется.

Результаты впечатляют. Все это работает намного быстрее, чем я ожидал (построил его как сборку CLR в C # для Microsoft SQL Server 2008). После правильного выбора E1..E4 наибольший индекс (наибольшая разница) для ненулевых значений во всей базе данных составляет 765. До примерно 300 практически нет соответствующего названия компании. Приблизительно в 200 есть компании, которые имеют похожие названия, и некоторые из них имеют одинаковые имена, но написаны совершенно по-разному, с сокращениями, дополнительными словами и т. Д. Когда дело доходит до 100 и менее - практически все записи содержат имена, которые то же самое, но написано с небольшими отличиями, и к 30 может отличаться только порядок или пунктуация.
Все работает, результат лучше, чем я ожидал.

Я написал пост в своем блоге , чтобы поделиться этой библиотекой на случай, если кому-то еще понадобится.