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

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

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

この方法で実装すると、1万件の文字列同士の類似度計算において、 **一般的な[levenshteinライブラリ](https://github.com/maxbachmann/python-Levenshtein)よりも120倍近く高速に計算することが可能です！**

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

![logo](https://raw.githubusercontent.com/maxbachmann/RapidFuzz/a0b75e630e39d9649a4915a6e1d29912d2bc039f/docs/img/RapidFuzz.svg)

([RapidFuzzのGitHubリポジトリ](https://github.com/maxbachmann/RapidFuzz/blob/main/docs/img/RapidFuzz.svg)より引用)

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

# 検証環境
Google Cloudの [n2d-standard-4](https://cloud.google.com/compute/docs/general-purpose-machines#n2d_machines) VM（4vCPU、16GBメモリ）を使用しました。
Pythonと検証ライブラリのバージョンは以下をご参照下さい。

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

    Python 3.7.12

    Levenshtein==0.20.9
    rapidfuzz==2.13.7


# レーベンシュタイン距離とは
[Wikipedia(レーベンシュタイン距離)](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)より引用させていただきます。
> レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。

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

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

# PythonのLevenshteinライブラリと問題点
Pythonでは、[Levenshtein](https://github.com/maxbachmann/python-Levenshtein)というライブラリが多く使われています。以下コマンドでインストールします。


```
pip install Levenshtein
```

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

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


```python
import Levenshtein

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

    1
    0.8333333333333334


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


```python
%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`ライブラリで疑似生成します。


```python
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つ目の問題点です。


```python
%%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](https://github.com/maxbachmann/RapidFuzz)をご紹介します。`RapidFuzz`は、PythonとC++で実装された文字列類似度の高速計算用ライブラリです。

![logo](https://raw.githubusercontent.com/maxbachmann/RapidFuzz/a0b75e630e39d9649a4915a6e1d29912d2bc039f/docs/img/RapidFuzz.svg)

([RapidFuzzのGitHubリポジトリ](https://github.com/maxbachmann/RapidFuzz/blob/main/docs/img/RapidFuzz.svg)より引用)

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


```
pip install rapidfuzz
```

:::note

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

:::

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


```python
from rapidfuzz.process import cdist
```


```python
%%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倍以上という驚異的な速度です！**

:::note

これだけの速度差が出た理由は大きく2点あります（詳細は後述）。
1. RapidFuzzライブラリが、入力値として文字列のみならず **配列にも最適化されている** ため
2. 引数の`workers=-1`により **並列処理された** ため

:::

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

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

## ①N:N（配列同士）で比較
配列同士の比較では、[rapidfuzz.process.cdist](https://maxbachmann.github.io/RapidFuzz/Usage/process.html#cdist)関数を使います。

必須の引数は以下2つです。どちらも`list`の他、`numpy.ndarray`や`pandas.Series`等のデータ型を使用できます。
- `queries`（比較する文字列の配列）
- `choices`（比較される文字列の配列）

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


```python
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


:::note

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

:::

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

以下は[ジャロ・ウィンクラー距離](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A3%E3%83%AD%E3%83%BB%E3%82%A6%E3%82%A3%E3%83%B3%E3%82%AF%E3%83%A9%E3%83%BC%E8%B7%9D%E9%9B%A2)の例になります（0に近いほど、2つの文字列は似ている）。Python関数も指定できますが、RapidFuzzが提供するAPI関数の使用が推奨されています。


```python
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`を付与した場合です。


```python
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に置換されます。


```python
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`）


```python
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


:::note

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

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

:::

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


```python
%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](https://maxbachmann.github.io/RapidFuzz/Usage/process.html#extract)
- [extract_iter](https://maxbachmann.github.io/RapidFuzz/Usage/process.html#extract-iter)
- [extractOne](https://maxbachmann.github.io/RapidFuzz/Usage/process.html#extractone)

### extract
extract関数で必須の引数は以下2つです。`choices`には`list`、`numpy.ndarray`の他、`dict`や`pandas.Series`などの **マッピングオブジェクトも指定可能** です。
- `query` : 比較する文字列
- `choices` : 比較される文字列の配列

```python
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`件出力されます（タイの場合はインデックス順）。

:::note

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

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

```python
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関数を使用します。

```python
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件ずつに個別処理を行いたい場合や、メモリ使用量を節約したいシーンで有効かと思います。


```python
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関数と同じです。結果はタプルで応答されます。

```python
from rapidfuzz.process import extractOne

extractOne(query, choices)
```

    ('cat', 100.0, 'A')

## ③1:1（単体の文字列同士）で比較
単体の文字列同士を比較する場合は、`rapidfuzz.distance`モジュールを使用します。このモジュールには
- `distance` : 編集距離
- `normalized_distance` : 正規化された編集距離
- `similarity` : 類似度
- `normalized_similarity` : 正規化された類似度

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

```python
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](https://maxbachmann.github.io/RapidFuzz/Usage/distance/DamerauLevenshtein.html) : ダメラウ・レーベンシュタイン距離
- [Hamming](https://maxbachmann.github.io/RapidFuzz/Usage/distance/Hamming.html) : ハミング距離
- [Indel](https://maxbachmann.github.io/RapidFuzz/Usage/distance/Indel.html) : インデル距離
- [Jaro](https://maxbachmann.github.io/RapidFuzz/Usage/distance/Jaro.html) : ジャロ距離
- [JaroWinkler](https://maxbachmann.github.io/RapidFuzz/Usage/distance/JaroWinkler.html) : ジャロ・ウィンクラー距離
- [Levenshtein](https://maxbachmann.github.io/RapidFuzz/Usage/distance/Levenshtein.html) : レーベンシュタイン距離
- [Optimal String Alignment (OSA)](https://maxbachmann.github.io/RapidFuzz/Usage/distance/OSA.html) : OSA距離
- [Prefix](https://maxbachmann.github.io/RapidFuzz/Usage/distance/Prefix.html) : 接頭辞距離
- [Postfix](https://maxbachmann.github.io/RapidFuzz/Usage/distance/Postfix.html) : 接尾辞距離

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

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

以下は[レーベンシュタイン距離のパフォーマンス比較](https://maxbachmann.github.io/RapidFuzz/Usage/distance/Levenshtein.html#uniform)からの引用です。 **文字列長が長くなるほど、RapidFuzzは他ライブラリよりもずっと高速に計算できる** ことが分かります！

![](https://maxbachmann.github.io/RapidFuzz/_images/uniform_levenshtein.svg)

## ⑤高速な前処理
`RapidFuzz`には、[rapidfuzz.utils.default_process](https://maxbachmann.github.io/RapidFuzz/Usage/utils.html)という前処理関数が提供されています。文字列を入力すると
- 英数字のみを抽出（記号を除去）
- 先頭と末尾のスペースを削除
- 小文字化

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

```python
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`を詳解させていただきました。

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