如何在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: 我不需要最优解。

- Aufwind

---

我认为你的假设是正确的。Levenshtein距离和Bitap算法都值得考虑。http://en.wikipedia.org/wiki/Bitap_algorithm。 - hochl

@hochl：即使是我上面提到的问题呢？ - Aufwind

@Aufwind：在比较之前，您应该将字符串拆分为单词，然后计算匹配的单词数。例如，对于“Fraunhofer IAIS”，搜索每个地址以查找类似于“Fraunhofer”和“IAIS”的单词。您还应规范化所有单词的大小写（例如，小写），并可能希望忽略“噪声词”（如“of”）。给出像“完全匹配= 5，接近匹配= 1”这样的分数，并选择得分最高的地址。也许一个好的启发式方法是给长时间匹配更高的分数。 - Ferdinand Beyer

哦，这里有一篇与您的问题密切相关的非常有趣的阅读材料：“如何编写拼写纠正器”http://norvig.com/spell-correct.html - Ferdinand Beyer

+1个好建议，也许按单词拆分，仅包括长度大于4个字符的单词。也许排除仅由大写字母组成的单词。 - hochl

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

- Björn Lindqvist

Answer 2

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

这里是一个Python实现double-metaphone algo。

- Bite code