4

我是 python n00b，我想要一些关于如何改进算法以提高此方法的性能以计算两个名称的 Jaro-Winkler 距离的建议。

def winklerCompareP(str1, str2):
"""Return approximate string comparator measure (between 0.0 and 1.0)

USAGE:
  score = winkler(str1, str2)

ARGUMENTS:
  str1  The first string
  str2  The second string

DESCRIPTION:
  As described in 'An Application of the Fellegi-Sunter Model of
  Record Linkage to the 1990 U.S. Decennial Census' by William E. Winkler
  and Yves Thibaudeau.

  Based on the 'jaro' string comparator, but modifies it according to whether
  the first few characters are the same or not.
"""

# Quick check if the strings are the same - - - - - - - - - - - - - - - - - -
#
jaro_winkler_marker_char = chr(1)
if (str1 == str2):
    return 1.0

len1 = len(str1)
len2 = len(str2)
halflen = max(len1,len2) / 2 - 1

ass1  = ''  # Characters assigned in str1
ass2  = '' # Characters assigned in str2
#ass1 = ''
#ass2 = ''
workstr1 = str1
workstr2 = str2

common1 = 0    # Number of common characters
common2 = 0

#print "'len1', str1[i], start, end, index, ass1, workstr2, common1"
# Analyse the first string    - - - - - - - - - - - - - - - - - - - - - - - - -
#
for i in range(len1):
    start = max(0,i-halflen)
    end   = min(i+halflen+1,len2)
    index = workstr2.find(str1[i],start,end)
    #print 'len1', str1[i], start, end, index, ass1, workstr2, common1
    if (index > -1):    # Found common character
        common1 += 1
        #ass1 += str1[i]
        ass1 = ass1 + str1[i]
        workstr2 = workstr2[:index]+jaro_winkler_marker_char+workstr2[index+1:]
#print "str1 analyse result", ass1, common1

#print "str1 analyse result", ass1, common1
# Analyse the second string - - - - - - - - - - - - - - - - - - - - - - - - -
#
for i in range(len2):
    start = max(0,i-halflen)
    end   = min(i+halflen+1,len1)
    index = workstr1.find(str2[i],start,end)
    #print 'len2', str2[i], start, end, index, ass1, workstr1, common2
    if (index > -1):    # Found common character
        common2 += 1
        #ass2 += str2[i]
        ass2 = ass2 + str2[i]
        workstr1 = workstr1[:index]+jaro_winkler_marker_char+workstr1[index+1:]

if (common1 != common2):
    print('Winkler: Wrong common values for strings "%s" and "%s"' % \
                (str1, str2) + ', common1: %i, common2: %i' % (common1, common2) + \
                ', common should be the same.')
    common1 = float(common1+common2) / 2.0    ##### This is just a fix #####

if (common1 == 0):
    return 0.0

# Compute number of transpositions    - - - - - - - - - - - - - - - - - - - - -
#
transposition = 0
for i in range(len(ass1)):
    if (ass1[i] != ass2[i]):
        transposition += 1
transposition = transposition / 2.0

# Now compute how many characters are common at beginning - - - - - - - - - -
#
minlen = min(len1,len2)
for same in range(minlen+1):
    if (str1[:same] != str2[:same]):
        break
same -= 1
if (same > 4):
    same = 4

common1 = float(common1)
w = 1./3.*(common1 / float(len1) + common1 / float(len2) + (common1-transposition) / common1)

wn = w + same*0.1 * (1.0 - w)
return wn

示例输出

ZIMMERMANN  ARMIENTO    0.814583333
ZIMMERMANN  ZIMMERMANN  1
ZIMMERMANN  CANNONS         0.766666667
CANNONS AKKER           0.8
CANNONS ALDERSON    0.845833333
CANNONS ALLANBY         0.833333333
4

3 回答 3

4

我更专注于优化以从 Python 中获得更多收益，而不是优化算法，因为我认为这里没有太多的算法改进。以下是我提出的一些 Python 优化。

(1)。由于您似乎使用的是 Python 2.x，请将所有 range() 更改为 xrange()。range() 在迭代它们之前生成完整的数字列表，而 xrange 根据需要生成它们。

(2)。对 max 和 min 进行以下替换：

start = max(0,i-halflen)

和

start = i - halflen if i > halflen else 0

和

end = min(i+halflen+1,len2)

和

end = i+halflen+1 if i+halflen+1 < len2 else len2

在第一个循环中，在第二个循环中类似。还有一个更远的 min() 和一个靠近函数开头的 max() ，所以对它们做同样的事情。更换 min() 和 max() 确实有助于减少时间。这些是方便的功能，但比我替换它们的方法更昂贵。

(3)。使用 common1 代替 len(ass1)。您已经在 common1 中跟踪了 ass1 的长度，所以让我们使用它而不是调用昂贵的函数来再次找到它。

(4)。替换以下代码：

minlen = min(len1,len2)
for same in xrange(minlen+1):
    if (str1[:same] != str2[:same]):
        break
same -= 1

和

for same in xrange(minlen):
    if str1[same] != str2[same]:
        break

这样做的原因主要是 str1[:same] 每次通过循环都会创建一个新字符串，并且您将检查您已经检查过的部分。此外，如果我们不需要，则无需检查是否'' != ''并在之后递减。same

(5)。使用psyco，一种即时编译器。下载并安装后，只需添加行

import psyco
psyco.full()

在文件的顶部使用它。除非您进行我提到的其他更改，否则不要使用 psyco。出于某种原因，当我在您的原始代码上运行它时，它实际上减慢了它的速度。

使用 timeit，我发现前 4 次更改的时间减少了大约 20% 左右。但是，当我将 psyco 与这些更改一起添加时，代码比原始代码快 3 到 4 倍。

如果你想要更快的速度

相当多的剩余时间在字符串的 find() 方法中。我决定尝试用我自己的替换它。对于第一个循环，我替换了

index = workstr2.find(str1[i],start,end)

和

index = -1
for j in xrange(start,end):
    if workstr2[j] == str1[i]:
        index = j
        break

以及第二个循环的类似形式。没有 psyco，这会减慢代码的速度，但是使用 psyco，它会加快很多。通过最后的更改，代码比原始代码快了大约 8 到 9 倍。

如果这还不够快

然后你可能应该转向制作一个 C 模块。

祝你好运！

于 2010-04-30T06:34:01.243 回答
3

我想如果您使用 PyLevenshtein 模块，您可以做得更好。对于大多数用例来说，它是 C 语言并且相当快。它包括一个 jaro-winkler 函数，它提供相同的输出，但在我的机器上它快 63 倍。

In [1]: import jw

In [2]: jw.winklerCompareP('ZIMMERMANN', 'CANNONS')
Out[2]: 0.41428571428571426

In [3]: timeit jw.winklerCompareP('ZIMMERMANN', 'CANNONS')
10000 loops, best of 3: 28.2 us per loop

In [4]: import Levenshtein

In [5]: Levenshtein.jaro_winkler('ZIMMERMANN', 'CANNONS')
Out[5]: 0.41428571428571431

In [6]: timeit Levenshtein.jaro_winkler('ZIMMERMANN', 'CANNONS')
1000000 loops, best of 3: 442 ns per loop
于 2011-01-31T23:46:50.807 回答
0

除了贾斯汀所说的一切，连接字符串是昂贵的——python 必须为新字符串分配内存，然后将两个字符串复制到其中。

所以这很糟糕：

ass1 = ''
for i in range(len1):
     ...
    if (index > -1):    # Found common character
        ...
        ass1 = ass1 + str1[i]

制作 ass1 和 ass2 字符列表并使用ass1.append(str1[i]). 从我对代码的快速阅读中我可以看出，之后您对 ass1 和 ass2 所做的唯一事情就是逐个字符地遍历它们，因此它们不需要是字符串。如果您稍后确实需要将它们用作字符串，那么您可以使用''.join(ass1).

于 2010-04-30T07:05:55.390 回答