目次
1.TextDistanceのライブラリ
2.文字列の距離や類似性のアルゴリズム
2.1 編集ベース（Edit based）
2.2 トークンベース（Token based）
2.3 順序ベース（Sequence based）
2.4 圧縮ベース（Compression based）
2.5 音声ベース（Phonetic based）
2.6 シンプルアルゴリズム（Simple algorithm）
前回は距離と類似度について解説しました。今回の記事は文字列の距離や類似性を解説したいと思います。文字列類似性アルゴリズムは、ドメインに分類できます。
記事：距離と類似度の解説
1.TextDistanceのライブラリ
Pythonは文字列の距離を計算するTextDistanceのライブラリがあります。TextDistanceは多くのアルゴリズムによって2つ以上のシーケンス間の距離を比較するためのPythonライブラリです。
特徴：
・30以上のアルゴリズム
・純粋なPythonの実装
・簡単な使い方
・比較する3つ以上のシーケンス
・一部のアルゴリズムでは、1つのクラスに複数の実装があります。
・最高速度のためのオプションのnumpyの使用法。
ライブラリのインストール
| !pip install textdistance |
詳細：https://pypi.org/project/textdistance/
2.文字列の距離や類似性のアルゴリズム
2.1 編集ベース（Edit based）
編集ベースアルゴリズムは、ある文字列を別の文字列に変換するために必要な操作の数を計算しようとします。 操作の数が多いほど、2つの文字列間の類似性は低くなります。 この場合、文字列のすべてのインデックス文字に同等の重要性が与えられることに注意してください。
編集ベースアルゴリズムの一覧
| Algorithm | Class | Functions |
| Hamming | Hamming | hamming |
| MLIPNS | Mlipns | mlipns |
| Levenshtein | Levenshtein | levenshtein |
| Damerau-Levenshtein | DamerauLevenshtein | damerau_levenshtein |
| Jaro-Winkler | JaroWinkler | jaro_winkler, jaro |
| Strcmp95 | StrCmp95 | strcmp95 |
| Needleman-Wunsch | NeedlemanWunsch | needleman_wunsch |
| Gotoh | Gotoh | gotoh |
| Smith-Waterman | SmithWaterman | smith_waterman |
編集ベースアルゴリズムの例
| print(textdistance.hamming.distance(‘test’, ‘text’)) print(textdistance.hamming.similarity(‘test’, ‘text’)) |
1
3
2.2 トークンベース（Token based）
トークンベースのアルゴリズムでは、期待される入力は完全な文字列ではなく、トークンのセットです。 アイデアは、両方のセットで同様のトークンを見つけることです。 共通トークンの数が多いほど、セット間の類似性が高くなります。 文字列は、区切り文字を使用して分割することでセットに変換できます。 このようにして、文を単語のトークンまたはn-gram文字に変換できます。 ここで、異なる長さのトークンは同じ重要性を持っていることになります。
トークンベースアルゴリズムの一覧
| Algorithm | Class | Functions |
| Jaccard index | Jaccard | jaccard |
| Sørensen–Dice coefficient | Sorensen | sorensen, sorensen_dice, dice |
| Tversky index | Tversky | tversky |
| Overlap coefficient | Overlap | overlap |
| Tanimoto distance | Tanimoto | tanimoto |
| Cosine similarity | Cosine | cosine |
| Monge-Elkan | MongeElkan | monge_elkan |
| Bag distance | Bag | bag |
トークンベースアルゴリズムの例
| tokens_1 = “hello world”.split() tokens_2 = “world hello”.split() print(textdistance.jaccard(tokens_1 , tokens_2))
tokens_1 = “hello new world”.split() tokens_2 = “hello world”.split() print(textdistance.jaccard(tokens_1 , tokens_2)) |
1.0
0.6666666666666666
2.3 順序ベース（Sequence based）
順序ベースアルゴリズムでは、類似性は2つの文字列間の共通のサブ文字列の要因です。 アルゴリズムは、両方の文字列に存在する最長のシーケンスを見つけようとします。これらのシーケンスが見つかるほど、類似度スコアが高くなります。 ここでは、同じ長さの文字の組み合わせも同じように重要であることに注意してください。
順序ベースアルゴリズムの一覧
| Algorithm | Class | Functions |
| longest common subsequence similarity | LCSSeq | lcsseq |
| longest common substring similarity | LCSStr | lcsstr |
| Ratcliff-Obershelp similarity | RatcliffObershelp | ratcliff_obershelp |
順序ベースアルゴリズムの例
| string1, string2 = ‘test’, ‘text’ print(textdistance.ratcliff_obershelp(string1, string2))
string1, string2 = “helloworld”, “worldhello” print(textdistance.ratcliff_obershelp(string1, string2)) |
0.75
0.5
2.4 圧縮ベース（Compression based）
圧縮ベースアルゴリズムは、特性ではなく、ビットの配列として2つの文字列を比較します。
圧縮ベースアルゴリズムの一覧
| Algorithm | Class | Function |
| Arithmetic coding | ArithNCD | arith_ncd |
| RLE | RLENCD | rle_ncd |
| BWT RLE | BWTRLENCD | bwtrle_ncd |
| Algorithm | Class | Function | |||
| Square Root | SqrtNCD | sqrt_ncd | |||
| Entropy | EntropyNCD | entropy_ncd | |||
| BZ2 | BZ2NCD | bz2_ncd | |||
| LZMA | LZMANCD | lzma_ncd | |||
| ZLib | ZLIBNCD | zlib_ncd | |||
圧縮ベースアルゴリズムの例
| string1, string2 = ‘test’, ‘text’ print(textdistance.arith_ncd(string1, string2))
string1, string2 = ‘test’, ‘text’ print(textdistance.rle_ncd(string1, string2)) |
1.3333333333333333
1.0
2.5 音声ベース（Phonetic based）
音声アルゴリズムは、単一の単語の特定の音声表現を作成します。 通常、このような表現は、固定長、文字のみで構成される可変長文字列、または文字と数字の両方の組み合わせのいずれかです。
音声ベースアルゴリズムの一覧
| Algorithm | Class | Functions |
| MRA | MRA | mra |
| Editex | Editex | editex |
音声ベースアルゴリズムの例
| string1, string2 = ‘test’, ‘text’ print(textdistance.mra(string1, string2))
string1, string2 = ‘test’, ‘text’ print(textdistance.editex(string1, string2)) |
2
1
2.6 一般的なアルゴリズム（Simple algorithm）
一般的なアルゴリズムは、文字列の接頭辞、接尾辞、長さなどで類似性の計算です。
一般的なアルゴリズムの一覧
| Algorithm | Class | Functions |
| Prefix similarity | Prefix | prefix |
| Postfix similarity | Postfix | postfix |
| Length distance | Length | length |
| Identity similarity | Identity | identity |
| Matrix similarity | Matrix | matrix |
一般的なアルゴリズムの例
| string1, string2 = ‘test’, ‘text’
print(textdistance.prefix(string1, string2)) print(textdistance.postfix(string1, string2)) print(textdistance.length(string1, string2)) print(textdistance.identity(string1, string2)) print(textdistance.matrix(string1, string2)) |
te
t
0
0
0
担当者：HM
香川県高松市出身 データ分析にて、博士（理学）を取得後、自動車メーカー会社にてデータ分析に関わる。その後コンサルティングファームでデータ分析プロジェクトを歴任後独立 気が付けばデータ分析プロジェクトだけで５０以上担当
理化学研究所にて研究員を拝命中 応用数理学会所属