如何在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",
--> --

我想用某种“距离算法”来计算字符串之间的相似度。因为我不能仅仅通过 if address in organisation 来查找地址中的组织名称，因为在不同地方可能会有些许不同的写法。所以我最初的想法是使用 difflib 模块，特别是 difflib.get_close_matches() 函数，来为每个地址选择最接近的组织名称。但是我对结果的准确性不是很有信心。我也不知道应该把相似度的比例设置得多高。

在花太多时间尝试 difflib 模块之前，我想问问这里更有经验的人，这样做是否正确，或者有没有更合适的工具或方法来解决我的问题。谢谢！

PS：我不需要一个最优的解决方案。

Answer 1

你可以使用soundex或metaphone这两种方法，把句子转换成一系列的音素，然后比较这些音素列表，找出最相似的。

下面是一个用Python实现的双重metaphone算法。

Answer 2

使用下面这个字符串距离函数（不要用普通的莱文斯坦距离）：

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分配算法，可以在这里找到，因为看起来组织和地址之间有一一对应的关系。