Как сопоставить наиболее похожие строки из одного списка в другой в python?

Даны два списка, содержащие строки.

  1. Один содержит названия организаций (в основном университетов) по всему миру, написанные не только по-английски, но и всегда с использованием латинского алфавита.

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

Пример:

addresses = [
             "Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium",
             "Machine Learning and Computational Biology Research Group, Max Planck Institutes     Tübingen, Tübingen, Germany 72076",
             "Department of Computer Science and Engineering, University of Washington, Seattle, USA 98185",
             "Knowledge Discovery Department, Fraunhofer IAIS, Sankt Augustin, Germany 53754",    
             "Computer Science Department, University of California, Santa Barbara, USA 93106",
             "Fraunhofer IAIS, Sankt Augustin, Germany",
             "Department of Computer Science, Cornell University, Ithaca, NY",
             "University of Wisconsin-Madison"
            ]

organisations = [
                 "Catholic University of Leuven"
                 "Fraunhofer IAIS"
                 "Cornell University of Ithaca"
                 "Tübingener Max Plank Institut"
                ]

Как вы можете видеть, желаемое отображение будет:

"Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium",
--> Catholic University of  Leuven
"Machine Learning and Computational Biology Research Group, Max Planck Institutes     Tübingen, Tübingen, Germany 72076",
--> Max Plank Institut Tübingen
"Department of Computer Science and Engineering, University of Washington, Seattle, USA 98185",
--> --
"Knowledge Discovery Department, Fraunhofer IAIS, Sankt Augustin, Germany 53754",
--> Fraunhofer IAIS 
"Computer Science Department, University of California, Santa Barbara, USA 93106",
"Fraunhofer IAIS, Sankt Augustin, Germany",
--> Fraunhofer IAIS
"Department of Computer Science, Cornell University, Ithaca, NY"
--> "Cornell University of Ithaca",
"University of Wisconsin-Madison",
--> --

Я думал использовать какой-то «алгоритм расстояния» для вычисления сходства строк. Поскольку я не могу просто искать организацию в адресе, просто выполняя if address in organisation, потому что в разных местах он может быть написан немного по-разному. Итак, мое первое предположение заключалось в использовании модуля difflib. Особенно функция difflib.get_close_matches() для выбора для каждого адреса ближайшей строки из списка организаций. Но я не совсем уверен, что результаты будут достаточно точными. Хотя я не знаю, насколько высоко я должен установить соотношение, которое должно быть мерой сходства.

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

PS: мне не нужно оптимальное решение.


python string-matching
person Aufwind    schedule 08.12.2011    source источник
comment
Возможно, вам будет полезно: stackoverflow.com/questions /577463/   -  person Marijn van Vliet    schedule 08.12.2011
comment
@Rodin: ссылка, которую вы разместили, гласит: Расстояние Левенштейна измеряет расстояние с точки зрения количества операций, необходимых для преобразования одной строки в другую. Эти операции включают вставку, удаление и замену. Список моих организаций содержит около 8000 записей, мой список адресов содержит 230000 элементов. Подходит ли Левенштейн, если строки организации очень короткие (например, Fraunhofer IAIS), а адрес очень длинный (например: Knowledge Discovery Department, Fraunhofer IAIS, Санкт-Августин, Германия) 53754)?   -  person Aufwind    schedule 08.12.2011
comment
Я думаю, что вы на правильном пути со своим предположением. На ум приходит расстояние Левенштейна, и это: en.wikipedia.org/wiki/Bitap_algorithm.   -  person hochl    schedule 08.12.2011
comment
@hochl: Даже в отношении проблем, которые я прокомментировал выше?   -  person Aufwind    schedule 08.12.2011
comment
@Aufwind: Вы должны разделить свои строки на слова перед их сравнением, а затем подсчитать количество совпадающих слов. Например, для Fraunhofer IAIS выполните поиск по каждому адресу похожих слов как для Fraunhofer, так и для IAIS. Вы также должны нормализовать регистр всех слов (например, строчные) и, возможно, захотите игнорировать шумовые слова, такие как of. Дайте оценки, такие как точное совпадение = 5, точное совпадение = 1 и возьмите адрес с наибольшим количеством очков. Возможно, хорошей эвристикой было бы давать более высокие оценки длинным матчам.   -  person Ferdinand Beyer    schedule 08.12.2011
comment
О, вот очень интересное чтение, тесно связанное с вашей проблемой: Как написать корректор орфографии norvig.com/ правильное заклинание.html   -  person Ferdinand Beyer    schedule 08.12.2011
comment
+1 хорошее предложение, возможно, разбитое по словам и только слова длиннее 4 символов. Возможно исключить слова, состоящие только из заглавных букв.   -  person hochl    schedule 08.12.2011

Ответы (2)


arrow_upward
2
arrow_downward

Используйте следующее в качестве функции расстояния между строками (вместо простого расстояния Левенштейна):

def strdist(s1, s2):
    words1 = set(w for w in s1.split() if len(w) > 3)
    words2 = set(w for w in s2.split() if len(w) > 3)

    scores = [min(levenshtein(w1, w2) for w2 in words2) for w1 in words1]
    n_shared_words = len([s for s in scores if s <= 3])
    return -n_shared_words

Затем используйте алгоритм назначения Munkres показан здесь, так как существует сопоставление 1:1 между организациями и адресами.

person Björn Lindqvist    schedule 08.12.2011

arrow_upward
0
arrow_downward

Вы можете использовать soundex или метафон, чтобы перевести предложение в список фонем, а затем сравнить наиболее похожие списки.

Вот реализация на Python алгоритма двойного метафона.

person e-satis    schedule 08.12.2011