给定两个长度相同的Python列表。如何返回相似值的最佳匹配？

Question

给出两个包含字符串的python列表（人名）：

list_1 = ['J. Payne', 'George Bush', 'Billy Idol', 'M Stuart', 'Luc van den Bergen']
list_2 = ['John Payne', 'George W. Bush', 'Billy Idol', 'M. Stuart', 'Luc Bergen']

我希望能够得到最相似的名称映射。

'J. Payne'           -> 'John Payne'
'George Bush'        -> 'George W. Bush'
'Billy Idol'         -> 'Billy Idol'
'M Stuart'           -> 'M. Stuart'
'Luc van den Bergen' -> 'Luc Bergen'

有没有一种简洁的方式在Python中完成这个操作？这些列表平均包含5或6个名称，有时会更多，但这很少见。有时每个列表中只有一个名称，但可能拼写略有不同。

- Aufwind

---

你对“最相似”的算法定义是什么？ - cdhowie

@cdhowie：名称的不同拼写，名称的缩写，中间词（例如比利时的“van”）的可选性以及可选的中间名。我不知道如何以算法方式定义它。我想将那些拼写最接近的名称进行映射。 - Aufwind

为了做到这一点，您需要将有关名称“接近度”的想法转换为可以应用于两个字符串的函数。计算机不处理模糊的规范；它们处理数学。 :) - cdhowie

@cdhowie 感谢您的建议。我希望有一个已经能够完成这个任务的Python模块，因为我不想重复造轮子。例如下面提到的difflib模块。但是您提到了数学和计算机之间的关系，这点很有道理。 :-) - Aufwind

列表大小是否总是相同的，并且list_2中是否恰好有一个与list_1中每个项目匹配？如果是这样，距离匹配可以大大提高。 - Björn Lindqvist

@Björn：我不能保证这两个标准总是被满足的，但假设它们都被满足了，改进效果会怎样呢？我很好奇。 :-) 如果你有时间解释一下，我期待着理解。 - Aufwind

Answer 1

使用在这里定义的函数: http://hetland.org/coding/python/levenshtein.py

>>> for i in list_1:
...     print i, '==>', min(list_2, key=lambda j:levenshtein(i,j))
... 

你可以使用functools.partial代替lambda函数。

>>> from functools import partial
>>> for i in list_1:
...     print i, '==>', min(list_2, key=partial(levenshtein,i))
...

J. Payne ==> John Payne
George Bush ==> George W. Bush
Billy Idol ==> Billy Idol
M Stuart ==> M. Stuart
Luc van den Bergen ==> Luc Bergen

- John La Rooy

---

你的levenstein函数和@jellybean的difflib.get_closest_matches()方法之间的主要区别是什么？ - Aufwind

@Aufwind，我认为difflib使用了非常不同的算法。帮助文档说它使用SequenceMatcher。不知道要处理哪些数据，很难确定哪种算法更好。 - John La Rooy

Answer 2

你可以尝试使用difflib：

import difflib

list_1 = ['J. Payne', 'George Bush', 'Billy Idol', 'M Stuart', 'Luc van den Bergen']
list_2 = ['John Payne', 'George W. Bush', 'Billy Idol', 'M. Stuart', 'Luc Bergen']

mymap = {}
for elem in list_1:
    closest = difflib.get_close_matches(elem, list_2)
    if closest:
        mymap[elem] = closest[0]

print mymap

输出：

{'George Bush': 'George W. Bush', 
 'Luc van den Bergen': 'Luc Bergen', 
 'Billy Idol': 'Billy Idol', 
 'J. Payne': 'John Payne', 
 'M Stuart': 'M. Stuart'}

- Johannes Charra

Answer 3

这里提供了一种解决方案的变体，它还优化了全局最小距离。它使用匈牙利算法来确保字符串配对是最优的。请注意保留HTML标签。

from munkres import Munkres
def match_lists(l1, l2):
    # Compute a matrix of string distances for all combinations of
    # items in l1 and l2.
    matrix = [[levenshtein(i1, i2) for i2 in l2] for i1 in l1]

    # Now figure out what the global minimum distance between the
    # pairs is.
    indexes = Munkres().compute(matrix)
    for row, col in indexes:
        yield l1[row], l2[col]

l1 = [
    'bolton',
    'manchester city',
    'manchester united',
    'wolves',
    'liverpool',
    'sunderland',
    'wigan',
    'norwich',
    'arsenal',
    'aston villa',
    'chelsea',
    'fulham',
    'newcastle utd',
    'stoke city',
    'everton',
    'tottenham',
    'blackburn',
    'west brom',
    'qpr',
    'swansea'
    ]
l2 = [
    'bolton wanderers',
    'manchester city',
    'manchester united',
    'wolverhampton',
    'liverpool',
    'norwich city',
    'sunderland',
    'wigan athletic',
    'arsenal',
    'aston villa',
    'chelsea',
    'fulham',
    'newcastle united',
    'stoke city',
    'everton',
    'tottenham hotspur',
    'blackburn rovers',
    'west bromwich',
    'queens park rangers',
    'swansea city'
    ]
for i1, i2 in match_lists(l1, l2):
    print i1, '=>', i2

针对所给列表，如果差异主要来自于备选拼写和昵称，而不是拼写错误，那么使用这种方法比仅使用levenshtein或difflib能够得到更好的结果。可以在此处找到munkres模块：http://software.clapper.org/munkres/

- Björn Lindqvist