この問題を O(n^2) から時間の複雑さを軽減するために、いくつかのレベルの最適化が可能です。
前処理: 最初のパスでリストを並べ替え、各文字列の出力マップを作成します。マップのキーは正規化された文字列にすることができます。正規化には次のものが含まれる場合があります。
これにより"Andrew H Smith"、、、同じキーが生成"andrew h. smith"され、数百万の名前のセットが、一意/類似のグループ化された名前のより小さなセットに削減されます。"ándréw h. smith""andrewhsmith"
このユーティリティ メソッドを使用して、文字列を正規化できます (ただし、Unicode 部分は含まれません)。
def process_str_for_similarity_cmp(input_str, normalized=False, ignore_list=[]):
""" Processes string for similarity comparisons , cleans special characters and extra whitespaces
if normalized is True and removes the substrings which are in ignore_list)
Args:
input_str (str) : input string to be processed
normalized (bool) : if True , method removes special characters and extra whitespace from string,
and converts to lowercase
ignore_list (list) : the substrings which need to be removed from the input string
Returns:
str : returns processed string
"""
for ignore_str in ignore_list:
input_str = re.sub(r'{0}'.format(ignore_str), "", input_str, flags=re.IGNORECASE)
if normalized is True:
input_str = input_str.strip().lower()
#clean special chars and extra whitespace
input_str = re.sub("\W", "", input_str).strip()
return input_str
正規化されたキーが同じであれば、同様の文字列はすでに同じバケットにあります。
さらに比較するには、名前ではなくキーのみを比較する必要があります。たとえば
andrewhsmithとandrewhsmeeth。この名前の類似性には、上記で行った正規化された比較とは別に、あいまいな文字列の一致が必要になるためです。
バケット化: 5 文字のキーと 9 文字のキーを比較して、それが 95% 一致しているかどうかを確認する必要がありますか? いいえ、ありません。したがって、一致する文字列のバケットを作成できます。たとえば、5 文字の名前は 4 ～ 6 文字の名前と一致し、6 文字の名前は 5 ～ 7 文字の名前と一致します。文字キーの n+1、n-1 文字の制限は、ほとんどの実際の一致に適したバケットです。
開始一致: 名前のほとんどのバリエーションは、正規化された形式で同じ最初の文字を持ちます (例: Andrew H Smith、ándréw h. smith、Andrew H. Smeeth生成キーandrewhsmith、andrewhsmith、およびandrewhsmeethそれぞれ。通常、最初の文字に違いはないため、 で始まるキーのマッチングaを他のキーと実行できます。これは で始まりa、長さのバケット内に収まります. これにより、マッチング時間が大幅に短縮されます.最初の文字で名前のバリエーションが存在することはめったにないため、キーandrewhsmithをにマッチングする必要はありません.bndrewhsmith
次に、このメソッド(または FuzzyWuzzy モジュール)の行で何かを使用して、文字列の類似性のパーセンテージを見つけることができます。速度と結果の品質を最適化するために、 jaro_winklerまたは difflib のいずれかを除外できます。
def find_string_similarity(first_str, second_str, normalized=False, ignore_list=[]):
""" Calculates matching ratio between two strings
Args:
first_str (str) : First String
second_str (str) : Second String
normalized (bool) : if True ,method removes special characters and extra whitespace
from strings then calculates matching ratio
ignore_list (list) : list has some characters which has to be substituted with "" in string
Returns:
Float Value : Returns a matching ratio between 1.0 ( most matching ) and 0.0 ( not matching )
using difflib's SequenceMatcher and and jellyfish's jaro_winkler algorithms with
equal weightage to each
Examples:
>>> find_string_similarity("hello world","Hello,World!",normalized=True)
1.0
>>> find_string_similarity("entrepreneurship","entreprenaurship")
0.95625
>>> find_string_similarity("Taj-Mahal","The Taj Mahal",normalized= True,ignore_list=["the","of"])
1.0
"""
first_str = process_str_for_similarity_cmp(first_str, normalized=normalized, ignore_list=ignore_list)
second_str = process_str_for_similarity_cmp(second_str, normalized=normalized, ignore_list=ignore_list)
match_ratio = (difflib.SequenceMatcher(None, first_str, second_str).ratio() + jellyfish.jaro_winkler(unicode(first_str), unicode(second_str)))/2.0
return match_ratio