给定两个相同长度的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个名字。有时候会多一些，但这种情况很少见。有时候每个列表里只有一个名字，而这些名字的拼写可能会有一点不同。

Answer 1

这里有一个变种的解决方案，它还优化了全局最小距离。它使用了匈牙利算法，确保字符串配对是最优的。

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/

Answer 2

这里使用了一个函数，具体可以在这个链接找到：http://hetland.org/coding/python/levenshtein.py

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

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

你可以用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

Answer 3

你可以试试 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'}