Pythonで文字列の類似度を120倍高速に計算するRapidFuzzを勧めたい

はじめに

みずほリサーチ&テクノロジーズ株式会社の@fujineです。

本記事では、文字列同士の類似度を計算する「レーベンシュタイン距離」をRapidFuzzで超高速に処理する方法を解説いたします。

この方法で実装すると、1万件の文字列同士の類似度計算において、 一般的なlevenshteinライブラリよりも120倍近く高速に計算することが可能です！

執筆時点でQiitaにはRapidFuzzの記事はまだ無いため、 本記事がQiita初の解説記事 となります。

(RapidFuzzのGitHubリポジトリより引用)

本記事の概要

• Pythonで一般的に用いられているlevenshteinライブラリは、比較対象データが多いと処理が長時間化し、実用的ではない
• RapidFuzzは上記ライブラリよりも約120倍高速であり、エンタープライズ規模のデータにも十分に適用可能
• RapidFuzzはレーベンシュタイン距離以外のアルゴリズムや、並列処理、前処理など多様な機能を提供しているため、読者の皆さんには積極的に使ってもらいたい

検証環境

Google Cloudの n2d-standard-4 VM（4vCPU、16GBメモリ）を使用しました。
Pythonと検証ライブラリのバージョンは以下をご参照下さい。

python -V
pip freeze | grep -E "Levenshtein|rapidfuzz"

Python 3.7.12

Levenshtein==0.20.9
rapidfuzz==2.13.7

レーベンシュタイン距離とは

Wikipedia(レーベンシュタイン距離)より引用させていただきます。

レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。

レーベンシュタイン距離は、

• 検索エンジンにおけるスペルミスのチェック・訂正
• バイオインフォマティクスにおけるDNA配列の類似性分析
• 人名、企業名、住所などの名寄せ処理

など、様々な分野で活用されています。

PythonのLevenshteinライブラリと問題点

Pythonでは、Levenshteinというライブラリが多く使われています。以下コマンドでインストールします。

pip install Levenshtein

このライブラリは、レーベンシュタイン距離を含む様々な距離計算や文字列処理を提供しています。使い方もとても簡単です。

• Levenshtein.distance(a, b)は、文字列aとbの編集距離をintで返します。
• Levenshtein.ratio(a, b)は、文字列長で正規化された類似度をfloatで返します（1に近いほど似ている）。

import Levenshtein

a, b = 'mizuho', 'mizuno'
print(Levenshtein.distance(a, b))
print(Levenshtein.ratio(a, b))

1
0.8333333333333334

計算時間は平均で約0.4μsと高速です。

%timeit Levenshtein.ratio(a, b)

400 ns ± 0.796 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

これだけなら十分に実用的だと思われますが、何が問題なのでしょうか？

実は、名寄せ処理のように多数の文字列群同士で計算しようとすると、2つの不便な点があります。

①配列を直接入力できない

例えば、1万人の顧客名が事前登録されたmaster名簿と、ある日に行われた取引の顧客名が記録されたtransactionという2つのデータがあるとします。

masterの各顧客名と最も類似する名前をtransactionから探し、その類似度を記録してみましょう。

人名のデータはFakerライブラリで疑似生成します。

import numpy as np
import pandas as pd
from faker import Faker

# 疑似データを生成
fake = Faker()
N = 10000
master = pd.Series([fake.name() for _ in range(N)]).sort_values()
transaction = pd.Series([fake.name() for _ in range(N)])

# 先頭5件を出力
print(master[:5].to_list())
print(transaction[:5].to_list())

['Aaron Beck', 'Aaron Bell', 'Aaron Chapman', 'Aaron Chung', 'Aaron Collins']
['Catherine Miller', 'Christian Greer', 'Tommy Wood', 'Scott Hayes', 'Christy Gaines']

Levenshteinライブラリの関数には文字列しか指定できないため、masterとtransactionから顧客名を1つずつ取得するループ処理を組む必要があります。

繰り返し数が多いほどループ処理自体のオーバーヘッドが目立ってしまう ことに加え、 類似度計算以外のコードが増えてしまう のが1つ目の問題点です。

%%time

similarity = []
for m in master.to_list():
    max_ratio, max_transaction = 0, None
    for t in transaction.to_list():
        ratio = Levenshtein.ratio(m, t)
        if ratio > max_ratio:
            max_ratio, max_transaction = ratio, t
            
    similarity.append((m, max_transaction, max_ratio))
        
similarity = pd.DataFrame(similarity, columns=['master', 'transaction', 'ratio'])
print(similarity)

              master     transaction     ratio
0         Aaron Beck    Aaron Tucker  0.727273
1         Aaron Bell       Erin Bell  0.736842
2      Aaron Chapman   Sarah Chapman  0.769231
3        Aaron Chung      Dana Chung  0.761905
4      Aaron Collins  Harold Collins  0.814815
...              ...             ...       ...
9995  Zachary Warren    Zachary Ward  0.846154
9996   Zachary Yoder  Zachary Fowler  0.814815
9997    Zoe Bartlett  Blake Bartlett  0.769231
9998   Zoe Cervantes  Jack Cervantes  0.740741
9999        Zoe Reed       Sean Reed  0.705882

[10000 rows x 3 columns]
CPU times: user 49.3 s, sys: 11.7 ms, total: 49.3 s
Wall time: 49.3 s

②組合せ数が多いと、実用的な時間で処理できない

先ほどのコードでは $1万 * 1万 = 1億通り$ の組合せを計算しており、その計算時間は約50秒でした。実際の業務では、10万件、100万件（あるいはそれ以上の）規模のデータを扱うケースがよくあります。もし上記のコードを100万件のデータで実行した場合、計算時間は$50秒 * 100^2 \fallingdotseq 5.8日間$も掛かる見込みであり、これは実用的な計算時間ではありません。

計算時間を短縮する方法として、

• masterとtransactionをそれぞれ分割して並列処理する
• 動的計画法を適用し、類似度が低そうな文字列を枝刈りすることで、計算対象を削減する

といった手段が挙げられます。どちらも一定の効果が期待できますが、 データの分割や並列処理、動的計画法などのコードは自身で実装する必要があり、コードの複雑化は保守性の観点から避けたい 所です。

解決策

Levenshteinライブラリの上記問題点を解決するライブラリとして、RapidFuzzをご紹介します。RapidFuzzは、PythonとC++で実装された文字列類似度の高速計算用ライブラリです。

(RapidFuzzのGitHubリポジトリより引用)

以下コマンドでインストールします。

pip install rapidfuzz

Windowsの場合はVisual C++ 2019 redistributable もインストールして下さい。
https://github.com/maxbachmann/RapidFuzz#requirements

実際、どれだけ速いのか比較してみましょう。同様の処理をrapidfuzz.process.cdistで実行してみます。

from rapidfuzz.process import cdist

%%time
similarity_fast = cdist(master, transaction, workers=-1)
similarity_fast = pd.DataFrame({
    'master': master.values,
    'transaction': transaction.iloc[similarity_fast.argmax(axis=1)].values,
    'ratio': similarity_fast.max(axis=1) / 100
})
print(similarity_fast)

              master     transaction     ratio
0         Aaron Beck    Aaron Tucker  0.727273
1         Aaron Bell       Erin Bell  0.736842
2      Aaron Chapman   Sarah Chapman  0.769231
3        Aaron Chung      Dana Chung  0.761905
4      Aaron Collins  Harold Collins  0.814815
...              ...             ...       ...
9995  Zachary Warren    Zachary Ward  0.846154
9996   Zachary Yoder  Zachary Fowler  0.814815
9997    Zoe Bartlett  Blake Bartlett  0.769231
9998   Zoe Cervantes  Jack Cervantes  0.740741
9999        Zoe Reed       Sean Reed  0.705882

[10000 rows x 3 columns]
CPU times: user 1.27 s, sys: 88.1 ms, total: 1.36 s
Wall time: 426 ms

同じ処理が わずか約0.4秒 で完了してしまいました！Levenshteinライブラリの約50秒と比較して、120倍以上という驚異的な速度です！

これだけの速度差が出た理由は大きく2点あります（詳細は後述）。

1. RapidFuzzライブラリが、入力値として文字列のみならず 配列にも最適化されている ため
2. 引数のworkers=-1により 並列処理された ため

RapidFuzzを詳解

これだけ凄いライブラリ、使い倒さなければ損です！

以下、入力のパターンやアルゴリズムに応じた関数が提供されています。それぞれの使い方や注意点を解説していきましょう。

①N:N（配列同士）で比較

配列同士の比較では、rapidfuzz.process.cdist関数を使います。

必須の引数は以下2つです。どちらもlistの他、numpy.ndarrayやpandas.Series等のデータ型を使用できます。

• queries（比較する文字列の配列）
• choices（比較される文字列の配列）

N行のqueriesとM行のchoicesを引数に与えると、計算結果がnumpy.ndarray(N, M)として取得できます。特に指定しなければ、rapidfuzz.fuzz.ratio（正規化されたレーベンシュタイン距離）で類似度が計算されます。

queries = pd.Series(['cat', 'dog', 'bear'])
choices = pd.Series(['cut', 'dot', 'beer'])

score = cdist(queries, choices)
print(pd.DataFrame(score, index=queries, columns=choices))

            cut        dot  beer
cat   66.666664  33.333332   0.0
dog    0.000000  66.666664   0.0
bear   0.000000   0.000000  75.0

rapidfuzz.fuzz.ratioの計算結果は[0, 100]の範囲で正規化されます。[0, 1]で正規化したい場合は、cdist()の結果を100で除算しましょう。

scorer引数で、 距離計算に用いるアルゴリズム を指定します。

以下はジャロ・ウィンクラー距離の例になります（0に近いほど、2つの文字列は似ている）。Python関数も指定できますが、RapidFuzzが提供するAPI関数の使用が推奨されています。

from rapidfuzz.distance import JaroWinkler

score = cdist(queries, choices, scorer=JaroWinkler.normalized_distance)
print(pd.DataFrame(score, index=queries, columns=choices))

      cut       dot      beer
cat   0.2  0.444444  1.000000
dog   1.0  0.177778  1.000000
bear  1.0  1.000000  0.133333

processor引数を指定すると、距離計算の前にqueriesとchoicesにそれぞれ 前処理を適用 できます。

以下は、文字列の末尾にsを付与した場合です。

processor = lambda x: x + 's'

score = cdist(queries, choices, processor=processor)
print(pd.DataFrame(score, index=queries.map(processor), columns=choices.map(processor)))

            cuts       dots      beers
cats   75.000000  50.000000  22.222221
dogs   25.000000  75.000000  22.222221
bears  22.222221  22.222221  80.000000

score_cutoff引数で、スコアの閾値を指定できます。指定すると、scorerのスコアがscore_cutoff以下の場合は0に置換されます。

score = cdist(queries, choices, score_cutoff=60)
print(pd.DataFrame(score, index=queries, columns=choices))

            cut        dot  beer
cat   66.666664   0.000000   0.0
dog    0.000000  66.666664   0.0
bear   0.000000   0.000000  75.0

score_hint引数は、公式ドキュメントには「スコアの期待値を指定すると高速になる」と記載されています。ただし、今回の検証では変化を観測することは出来ませんでした。

dtype引数で、計算結果のデータ型を指定します。指定可能なパターンは以下の通りです。

• scorerがfloatを返す場合、numpy.float32/float64/uint8のいずれか（デフォルトはnumpy.float32）
• scorerがintを返す場合、numpy.int8/int16/int32/int64のいずれか（デフォルトはnumpy.int32）

import numpy as np

score = cdist(queries, choices, dtype=np.uint8)
print(pd.DataFrame(score, index=queries, columns=choices))

      cut  dot  beer
cat    67   33     0
dog     0   67     0
bear    0    0    75

cdist()では、入力の配列サイズが大きいほど計算結果のサイズも大きくなり、結果としてメモリ使用量も増加します。

そこで、dtype引数にuint8など低ビットなデータ型を指定することで、（精度は犠牲になりますが）メモリ使用量を抑える効果があります。

workers引数で並列数を指定します（デフォルトは1）。-1で全てのCPUコアを使用します。scorerがPython関数の場合は使用できません（GILの制約）。

%time score = cdist(master, transaction, workers=1)
del score

%time score = cdist(master, transaction, workers=-1)
del score

CPU times: user 566 ms, sys: 52 ms, total: 618 ms
Wall time: 617 ms
CPU times: user 1.17 s, sys: 60 ms, total: 1.23 s
Wall time: 313 ms

②1:N（単体の文字列と配列）で比較

続いて、単体の文字列と配列同士を比較する場合は、rapidfuzz.processパッケージより以下3つの関数が使えます。

• extract
• extract_iter
• extractOne

extract

extract関数で必須の引数は以下2つです。choicesにはlist、numpy.ndarrayの他、dictやpandas.Seriesなどの マッピングオブジェクトも指定可能 です。

• query : 比較する文字列
• choices : 比較される文字列の配列

from rapidfuzz.process import extract

query = 'cat'
choices = pd.Series(['cat', 'cats', 'cut', 'act', 'cute', 'nat'],
                    index=list('ABCDEF'))

extract(query, choices)

[('cat', 100.0, 'A'),
 ('cats', 85.71428571428572, 'B'),
 ('cut', 66.66666666666667, 'C'),
 ('act', 66.66666666666667, 'D'),
 ('nat', 66.66666666666667, 'F')]

実行結果はタプルのリストで、タプルの中身は(類似した文字列, スコア, 配列のインデックス)となっています。

デフォルトではスコアが高い順で5件出力されます（タイの場合はインデックス順）。

extract関数が便利な点として、choicesにマッピングオブジェクトを指定した場合、 計算結果からKeyやインデックスが取得できる ことにあります。

この仕組みを利用すれば、類似度が高いデータのみをchoicesから簡単に選択することができます。

score = pd.DataFrame(extract(query, choices), 
                     columns=['choices', 'score', 'index'])
print(choices.reindex(score['index']))

index
A     cat
B    cats
C     cut
D     act
F     nat
dtype: object

limit引数で、抽出件数を指定できます（デフォルトは5）。類似度が最も高い結果のみを取得したい場合は、後述するextractOne関数を使用します。

extract(query, choices, limit=3)

[('cat', 100.0, 'A'),
 ('cats', 85.71428571428572, 'B'),
 ('cut', 66.66666666666667, 'C')]

他の引数としてscorer、processor 、score_cutoff、score_hintがあります。使用方法はcdist関数と同じです。

extract_iter

extract関数のジェネレーター版です。計算結果をyieldで取得することができます。

引数はextract関数と同じです。計算結果に1件ずつに個別処理を行いたい場合や、メモリ使用量を節約したいシーンで有効かと思います。

from rapidfuzz.process import extract_iter

for res in extract_iter(query, choices):
    print(res)

('cat', 100.0, 'A')
('cats', 85.71428571428572, 'B')
('cut', 66.66666666666667, 'C')
('act', 66.66666666666667, 'D')
('cute', 57.14285714285714, 'E')
('nat', 66.66666666666667, 'F')

extractOne

extractOne関数は、最も類似度が高い結果1件のみを取得したい場合に使用します。

引数はextract関数と同じです。結果はタプルで応答されます。

from rapidfuzz.process import extractOne

extractOne(query, choices)

('cat', 100.0, 'A')

③1:1（単体の文字列同士）で比較

単体の文字列同士を比較する場合は、rapidfuzz.distanceモジュールを使用します。このモジュールには

• distance : 編集距離
• normalized_distance : 正規化された編集距離
• similarity : 類似度
• normalized_similarity : 正規化された類似度

という4つの算出方法が提供されており、用途に応じて使い分けられるようになっています。

from rapidfuzz.distance import Levenshtein

s1 = 'mizuho'
s2 = 'mizuno'

print(Levenshtein.distance(s1, s2))
print(Levenshtein.normalized_distance(s1, s2))
print(Levenshtein.similarity(s1, s2))
print(Levenshtein.normalized_similarity(s1, s2))

1
0.16666666666666666
5
0.8333333333333334

④レーベンシュタイン距離以外のアルゴリズムを使用

ここまでの解説ではレーベンシュタイン距離を対象としていましたが、rapidfuzzは他にも以下アルゴリズムを提供しており、いずれもrapidfuzz.distanceモジュールから利用可能です。

• DamerauLevenshtein : ダメラウ・レーベンシュタイン距離
• Hamming : ハミング距離
• Indel : インデル距離
• Jaro : ジャロ距離
• JaroWinkler : ジャロ・ウィンクラー距離
• Levenshtein : レーベンシュタイン距離
• Optimal String Alignment (OSA) : OSA距離
• Prefix : 接頭辞距離
• Postfix : 接尾辞距離

どのアルゴリズムも、①N:Nや②1:Nでご紹介したcdist()やextract()のscorer引数に指定できる他、③のように1:1の計算にも利用可能です。

また、各アルゴリズムの公式ドキュメントには、RapidFuzzと他ライブラリのパフォーマンス比較グラフも掲載されています。

以下はレーベンシュタイン距離のパフォーマンス比較からの引用です。 文字列長が長くなるほど、RapidFuzzは他ライブラリよりもずっと高速に計算できる ことが分かります！

⑤高速な前処理

RapidFuzzには、rapidfuzz.utils.default_processという前処理関数が提供されています。文字列を入力すると

• 英数字のみを抽出（記号を除去）
• 先頭と末尾のスペースを削除
• 小文字化

を行います。 reライブラリや組み込み関数と比較すると、5倍以上も高速 です。

import re
from rapidfuzz.utils import default_process

s = ' 🐍Python-3.11🐍 '

print(default_process(s))
%timeit default_process(s)

p = re.compile(r'[^a-zA-Z0-9 ]')
%timeit p.sub(' ', s).strip().lower()

python 3 11
161 ns ± 0.211 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
957 ns ± 8.93 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

まとめ

文字列同士の類似度を高速計算するRapidFuzzを詳解させていただきました。

本記事をきっかけに、読者の皆さんにも積極的に使っていただけたら幸いです。