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

Question

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

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",
--> --

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

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

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

Answer 1

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

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 

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

Answer 2

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

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