Соответствие нечеткой строки с весовыми коэффициентами

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

Рассмотрим этот пример, используя библиотеку Python difflib. Я работаю с именами организаций, которые имеют много стандартизованных компонентов и поэтому не могут использоваться для дифференциации между объектами.

from difflib import SequenceMatcher  
e1a = SequenceMatcher(None, "ZOECON RESEARCH INSTITUTE", 
                            "LONDON RESEARCH INSTITUTE")
print e1a.ratio()
0.88

e1b = SequenceMatcher(None, "ZOECON", "LONDON")
print e1b.ratio() 
0.333333333333

e2a = SequenceMatcher(None, "WORLDWIDE SEMICONDUCTOR MANUFACTURING CORP",
                            "TAIWAN SEMICONDUCTOR MANUFACTURING CORP")
print e2a.ratio() 
0.83950617284

e2b = SequenceMatcher(None, "WORLDWIDE",
                            "TAIWAN")
print e2b.ratio() 
0.133333333333

Оба примера высоко оценивают полную строку, потому что RESEARCH, INSTITUTE, SEMICONDUCTOR, MANUFACTURING и CORP - это высокочастотные, общие термины во многих именах организаций. Я ищу любые идеи о том, как интегрировать частотные диапазоны в соответствие нечеткой строкой (не обязательно используя difflib), так что на оценки не влияют общие термины, и результаты могут больше походить на "e1b", и "e2b".

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

Ответы

Ответ 1

Вот вам странная идея:

Сжатие ввода и разности.

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

Ответ 2

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

дает вам возможность добавить свой собственный вес.

вам, конечно, нужно будет обрабатывать смещения, например..

"лондонская компания для кожи"

Ответ 3

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

Возможно, вам стоит взглянуть на http://nltk.org/, чтобы получить представление о некоторых методах НЛП. Вы не достаточно подробно рассказываете нам о своих данных, но тег-маркер POS может помочь идентифицировать более релевантные термины. Доступные базы данных с названиями городов, стран и... могут помочь очистить данные, прежде чем обрабатывать их дальше.

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

Ответ 4

Я просто предлагаю другой подход. Поскольку вы упомянули, что имена сущностей поступают из списка ссылок, мне интересно, есть ли у вас дополнительная контекстная информация, например, имена соавторов, названия продуктов/документов, адрес w/city, state, country?

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

 Author-paper relation
 Co-author relation
 author-institute relation
 institute-city relation
 ....

Затем пришло время использовать подход с разрешением на основе графа, подробно описанный ниже:

Этот подход имеет очень хорошую производительность в области соавторской работы.