4

私は python n00b です。2 つの名前の 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

最初のループと2番目のループの同様のもの。また、関数の先頭近くに別の min() と max() があるので、それらについても同じことを行います。min() と max() を置き換えると、時間が短縮されました。これらは便利な機能ですが、置き換えた方法よりもコストがかかります。

(3)。len(ass1) の代わりに common1 を使用します。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

2 番目のループも同様の形式です。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 に答える