Приблизительное совпадение строк

Question

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

Приложение предназначено только для сопоставления названий компаний и ничего больше.

Самая большая проблема - это, вероятно, часть имени компании и часть с коротким именем Пример: 1. CompanyA pty ltd vs companyA pty. ООО. против компании 2. WES Engineering против W.E.S. Инженерное дело (крайне редкое явление)

Как вы думаете, адекватно ли Левенштейну редактировать расстояние?

Я использую C #

С уважением, Max

Answer 1

Существуют различные метрики расстояния строки, которые вы можете использовать.

Я бы порекомендовал Яро-Винклер . В отличие от расстояния редактирования, где результат сравнения выражается в дискретных единицах правок, JW дает вам оценку 0-1. Это особенно подходит для имен собственных. Также посмотрите этот хороший учебник и этот ТАК вопрос.

Я не работал с C #, но вот несколько реализаций JW, которые я нашел в Интернете:

Impl 1 (у них тоже есть версия DOT NET, если вы посмотрите на список файлов)

Impl 2

---

Если вы хотите выполнить более сложное сопоставление, вы можете попытаться выполнить некоторую пользовательскую нормализацию словоформ, обычно встречающихся в названиях компаний, таких как ltd/limited, inc/incorporated, corp/corporation, чтобы учесть нечувствительность к регистру, сокращения и т. Д. Таким образом, если вы вычисляете 1027 *

distance (normalize("foo corp."), normalize("FOO CORPORATION") )

вы должны получить результат, равный 0, а не 14 (это то, что вы получите, если вычислите расстояние редактирования Левенштейна).

Answer 2

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

Answer 3

Да, для этого подходит расстояние Левенштейна.Это будет работать для всех тех, кого вы перечислили по крайней мере.

Вы также можете использовать Soundex , но я не думаю, что вам это понадобится.

Answer 4

Я уже дал ответ на другой вопрос.

https://stackoverflow.com/a/30120166/2282794

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

Если мы просто хотим поговорить об алгоритмах сопоставления приближенных строк, то их много. Немногие из них: Яро-Винклер, Редактировать расстояние (Левенштейн), Сходство Жакара, алгоритмы, основанные на Soundex / Фонетике и т. Д. Простое прибегание к поиску даст нам все детали. Вы можете реализовать их все в C #

Ирония в том, что они работают, пока вы пытаетесь сопоставить две заданные строки ввода. Хорошо, теоретически, чтобы продемонстрировать, как работает нечеткое или приближенное сопоставление строк.

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

Возможно, я только что говорил о Lucene, который специфичен для Java, но есть и Lucene для .Net.

https://lucenenet.apache.org/