如何绘制最“相似”的地图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 Organization 来查找地址中的组织，因为它在不同地方的写法可能略有不同。所以我的第一个猜测是使用 difflib 模块。特别是 difflib.get_close_matches() 函数，用于从组织列表中为每个地址选择最接近的字符串。但我不太相信结果会足够准确。尽管我不知道应该将比率设置为多高，但该比率似乎是相似性度量。

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

PS：我不需要最佳解决方案。

Answer 1

使用以下作为字符串距离函数（而不是普通的 levenshtein 距离）：

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 映射。

Answer 2

您可以使用 soundex 或 metaphone 将句子翻译成音素列表，然后比较最相似的列表。

以下是 double-metaphone 算法 的 Python 实现。