研究とテスト
文字列を比較するためにいくつかのアルゴリズムをテストし、必要に応じてより良いものを選
文字列Aと文字列Bを比較して、異なるアルゴリズムのメトリックを持っています。
文字列の類似性のルールは、大文字と小文字が異なる場合があります。 “Niche”と”chien”が似ていると考えたい場合は、アナグラムを検出する文字列類似アルゴリズムを使用します。 私たちの場合はそうではありません。 “Niche”という名前のアプリと”chien”という名前の別のアプリは、完全に異なる二つのアプリである可能性が非常に高いです。
いくつかのブレーンストーミングと研究の後、私たちは私たちのケースを助けるいくつかのアルゴリズム方法を思い付いた。 例えば、アナグラム（”niche”と”chien”）上の1（同様の文字列）のインデックスにつながる文字の順序を考慮していないように見えるので、コサインアルゴリズムは私た
ここに私たちが気づいたことがあります:
Levenshtein Algorithm
Levenshtein距離は、ある単語を別の単語に変更するために必要な単一文字編集の最小数であるため、結果は正の整数であり、文字列の長さに敏感です。 それはパターンを描くことをより困難にします。例えば
,
- “foo”と”bar”の間のレーベンシュタイン距離は3
- “beauties”と”beautiful”の間のレーベンシュタイン距離も3
- 私たち人間にとって、”beauties”/”beautiful”のペアは”foo”/”bar”のペアよりもはるかに似ています。 しかし、Levenshteinの距離は同じです。
ここで使用しているメトリックは、Levenshtein距離（1/levenshtein_distance）の逆数であるため、結果はパーセンテージであり、より簡単に読み取ることができます。 しかし、上記の問題は同じままでした。
ここで、1は同一の文字列を比較した結果であり、”ShazamIphone”と”ShazamAndroid”の類似度は0.167です。 “chien”と”niche”は0.25の類似性を持っています。
だからLevenshteinアルゴリズムの観点からChien/Nicheは”shazamiphone”/”ShazamAndroid”よりも”shazamiphone”から”shazamandroid”に取得するよりも、”chien”から”niche”に取得するために必要な編集が少ないため、”ShazamIphone”/”ShazamAndroid”よりも似ています。
Trigram Comparison
trigramアルゴリズムは、n-gramの場合であり、与えられたサンプルからのn個の（この場合は3つの）項目の連続したシーケンスです。 この場合、アプリケーション名はサンプルであり、文字はアイテムです。
だから、シーケンス”マーサ”は4つの卦{マーアートrth tha}を持っています。
二つの文字列を比較するためにTrigramメソッドを使用することができます。
例えば、”martha”とタイプミスを持つ同じ単語”marhta”を取ると、それらの卦を計算することができます。
卦”martha”:{mar art rth tha}
卦”marhta”:{mar arh rht hta}
類似性を測定するために、文字列:1{mar}一意の卦の数によって: 7{mar art rth tha arh rht hta}
The result is 1/7 = 14%
外側の文字の欠点のバランスをとるために（同じ卦で始まる文字列と終わる文字列の類似性を強化するために）、文字列を両側に空白で埋めて、これらのケースをさらに三つの卦”_ma”、”ha_”、”ta_”にします。
卦”martha”:{_ma mar art rth tha ha_}
卦”marhta”:{_ma mar arh rht hta ta_}
これで、一致する卦の数は2{_ma mar}
すべてのユニークな卦の数になります: 9{_ma mar art rth tha arh rht hta ha_}
The result is now 2/9 = 22%
このメソッドを使用して”Twitter v1″と”Twitter v2″を比較すると、
一致する卦の数：7{_tw twi wit itt tte ter er_}
すべての一意の卦の数：11{tw twi wit itt tte ter er__v1_v2v1_v2_}
The result is 7/11 = 63%
文字列を比較するためのTrigramメソッドの限界は、短い文字列が1つ（または2つ）であることです。.）異なる卦は、長いものよりも低い類似性を生成する傾向があります。
それが0を得る方法です。彼らはより多くの異なる卦を持っているように、”ShazamAndroid”と”ShazamIphone”の間の2つの類似性。
一致する卦の数は：5{_sh sha haz aza zam}
すべてのユニークな卦の数：20
文字列の長さに強い依存関係があるので、それは私たちのために良い比較をもた
ヤロ・ウィンクラー・アルゴリズム
“Jaro-Winkler distance（ジャロ・ウィンクラー・ディスタンス）は、計算機科学と統計学において、2つのシーケンス間の編集距離を測定するための文字列メトリックである。
非公式には、2つの単語の間のJaro距離は、1つの単語を他の単語に変更するために必要な1文字の転置の最小数です。
Jaro-Winkler distanceは接頭辞スケールを使用しており、接頭辞の長さが設定されているため、先頭から一致する文字列に対してより有利な評価が得られます”
出典：ウィキペディア。
同じ接頭辞を持つ単語に”より重要”を与えることで、Jaro-Winkler距離は私たちのユースケースにとって非常に興味深いように見えました。
最初からJaro距離の公式から始めて、ここでどのように動作しますか。 慌てないで、一歩一歩進んでください：
2つのシーケンスs1とs2の間のジャロ距離は次のように定義されます:
djはジャロ距離
mは一致する文字の数(s1とs2に現れる文字)
tは転置の数の半分(s1のi番目の文字とs2のi番目の文字を2で割ったものを比較)
|s1|は最初の文字列の長さ
|s2|は第二の文字列の長さ
を例とする。 “Martha”と”marhta”を取ってみましょう。
m = 6
t = 2/2 =1 (2 couples of non matching characters, the 4-th and 5-th) { t/h ; h/t }
|s1| = 6
|s2| = 6
数字を置き換えるだけで、次の式が得られます:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
今、私たちはJaro距離が何であるかを知っています、Jaro-Winkler距離に飛び乗ってみましょう。
Jaro-Winklerの類似性では、プレフィックス長lが設定されているため、最初から一致する文字列に有利な評価を与えるプレフィックススケールpを使用します。
pは、共通のプレフィクスを持つためにスコアを上に調整する量の一定のスケーリング係数です。 ウィンクラーの研究におけるこの定数の標準値はp=0.1です。
lは、文字列の先頭にある共通接頭辞の長さ(最大4文字まで)です。
だから、「martha」/「marhta」の例に戻って、接頭辞の長さをl=3（「mar」を参照）としましょう。 私達はに得ます:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
JaroWinklerの公式を使用して、94％の類似度でJaro距離から96％に移動します。
私たちの場合、似たようなアプリのほとんどは同じ接頭辞で始まります（”twitter v1″対”twitter v2″または”ShazamIphone”対”ShazamAndroid”など）。 上記のアルゴリズムテスト表を参照してください）。 だから、考慮に入れることが重要な基準です。
