長い文字列に存在するファジー/近似部分文字列をPythonでチェックしていますか？

Question

leveinstein（leveinsteinまたはdifflib）のようなアルゴリズムを使用すると、おおよそのmatches.egを簡単に見つけることができます。

>>> import difflib 
>>> difflib.SequenceMatcher(None,"amazing","amaging").ratio() 
0.8571428571428571 

ファジーマッチは、必要に応じて閾値を決定することによって検出することができる。

現在の要件：より大きな文字列のしきい値に基づいてファジー部分文字列を検索する。

例えば、

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 
#result = "manhatan","manhattin" and their indexes in large_string 

つブルートフォース溶液は、長さのすべてのサブストリングを生成することであるN-1 Nは、それらに一方と参照ずつQUERY_STRINGの長さ、及び使用levensteinであるN + 1（または他の一致長）に閾値。

より良い解決策は、Pythonで利用できます。好ましくは、Python 2.7に含まれるモジュール、または外部から利用可能なモジュールです。

UPDATE：それが原因の余分な操作には明白な結果であるファジーストリングの例のための作り付けのreモジュール、より少し遅いものの、Pythonの正規表現モジュールは、かなりうまく動作します。 希望の出力が良好で、ぼやけの大きさに対する制御を簡単に定義できます。

>>> import regex 
>>> input = "Monalisa was painted by Leonrdo da Vinchi" 
>>> regex.search(r'\b(leonardo){e<3}\s+(da)\s+(vinci){e<2}\b',input,flags=regex.IGNORECASE) 
<regex.Match object; span=(23, 41), match=' Leonrdo da Vinchi', fuzzy_counts=(0, 2, 1)> 

Answer 1

すぐにreと置き換えられるはずの新しいregexライブラリには、ファジーマッチングが含まれています。

https://pypi.python.org/pypi/regex/

ファジー・マッチング構文はかなり表情豊かに見えますが、これはあなたに1つまたは少数の挿入/追加/削除との一致を与えるだろう。私は試合からファジィ抽出ワードに対する閾値とfuzzysearchに基づいて、ファジーマッチにfuzzywuzzyを使用

import regex 
regex.match('(amazing){e<=1}', 'amaging') 

Answer 2

difflib.SequenceMatcher.get_matching_blocksはどうですか？

コード印刷の上

>>> import difflib 
>>> large_string = "thelargemanhatanproject" 
>>> query_string = "manhattan" 
>>> s = difflib.SequenceMatcher(None, large_string, query_string) 
>>> sum(n for i,j,n in s.get_matching_blocks())/float(len(query_string)) 
0.8888888888888888 

>>> query_string = "banana" 
>>> s = difflib.SequenceMatcher(None, large_string, query_string) 
>>> sum(n for i,j,n in s.get_matching_blocks())/float(len(query_string)) 
0.6666666666666666 

---

UPDATE

import difflib 

def matches(large_string, query_string, threshold): 
    words = large_string.split() 
    for word in words: 
     s = difflib.SequenceMatcher(None, word, query_string) 
     match = ''.join(word[i:i+n] for i, j, n in s.get_matching_blocks() if n) 
     if len(match)/float(len(query_string)) >= threshold: 
      yield match 

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 
print list(matches(large_string, query_string, 0.8)) 

：['manhatan', 'manhattn']

Answer 3

最近、私は、Python用のアライメントライブラリを書いた：それを使用してhttps://github.com/eseraygun/python-alignment

、することができます両方ともグローバルに実行する任意のスコアリング戦略を用いた局所的アライメントを任意のシーケンスのペアに適用します。実際には、query_stringの部分文字列を気にしないので、あなたの場合は準ローカル整列が必要です。私は、次のコードでローカル整列といくつかのヒューリスティックを使用して準ローカルアルゴリズムをシミュレートしましたが、適切な実装のためにライブラリを拡張するのは簡単です。

あなたのケースで変更されたREADMEファイルのコード例です。

from alignment.sequence import Sequence, GAP_ELEMENT 
from alignment.vocabulary import Vocabulary 
from alignment.sequencealigner import SimpleScoring, LocalSequenceAligner 

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 

# Create sequences to be aligned. 
a = Sequence(large_string) 
b = Sequence(query_string) 

# Create a vocabulary and encode the sequences. 
v = Vocabulary() 
aEncoded = v.encodeSequence(a) 
bEncoded = v.encodeSequence(b) 

# Create a scoring and align the sequences using local aligner. 
scoring = SimpleScoring(1, -1) 
aligner = LocalSequenceAligner(scoring, -1, minScore=5) 
score, encodeds = aligner.align(aEncoded, bEncoded, backtrace=True) 

# Iterate over optimal alignments and print them. 
for encoded in encodeds: 
    alignment = v.decodeSequenceAlignment(encoded) 

    # Simulate a semi-local alignment. 
    if len(filter(lambda e: e != GAP_ELEMENT, alignment.second)) != len(b): 
     continue 
    if alignment.first[0] == GAP_ELEMENT or alignment.first[-1] == GAP_ELEMENT: 
     continue 
    if alignment.second[0] == GAP_ELEMENT or alignment.second[-1] == GAP_ELEMENT: 
     continue 

    print alignment 
    print 'Alignment score:', alignment.score 
    print 'Percent identity:', alignment.percentIdentity() 
    print 

minScore=5の出力は次のとおりです。

m a n h a - t a n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

m a n h a t t - i 
m a n h a t t a n 
Alignment score: 5 
Percent identity: 77.7777777778 

m a n h a t t i n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

minScore引数を削除すると、最も良い得点マッチが得られます。ライブラリ内のすべてのアルゴリズムはO(n * m)時間計算、nとmは、配列の長さを有する

m a n h a - t a n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

m a n h a t t i n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

注意。

Answer 4

。

process.extractBestsは、クエリ、単語リスト、およびカットオフスコアを取り、カットオフスコアより上の一致およびスコアのタプルのリストを返します。

find_near_matchesは、結果がprocess.extractBestsで、単語の開始インデックスと終了インデックスを返します。私は索引を使用して単語を作成し、作成した単語を使用して大きな文字列の索引を検索します。​​3210がfind_near_matchesの場合、必要に応じて調整する必要がある「レーベンシュタイン距離」です。

from fuzzysearch import find_near_matches 
from fuzzywuzzy import process 

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 

def fuzzy_extract(qs, ls, threshold): 
    '''fuzzy matches 'qs' in 'ls' and returns list of 
    tuples of (word,index) 
    ''' 
    for word, _ in process.extractBests(qs, (ls,), score_cutoff=threshold): 
     print('word {}'.format(word)) 
     for match in find_near_matches(qs, word, max_l_dist=1): 
      match = word[match.start:match.end] 
      print('match {}'.format(match)) 
      index = ls.find(match) 
      yield (match, index) 

テスト;

print('query: {}\nstring: {}'.format(query_string, large_string)) 
for match,index in fuzzy_extract(query_string, large_string, 70): 
    print('match: {}\nindex: {}'.format(match, index)) 

query_string = "citi" 
print('query: {}\nstring: {}'.format(query_string, large_string)) 
for match,index in fuzzy_extract(query_string, large_string, 30): 
    print('match: {}\nindex: {}'.format(match, index)) 

query_string = "greet" 
print('query: {}\nstring: {}'.format(query_string, large_string)) 
for match,index in fuzzy_extract(query_string, large_string, 30): 
    print('match: {}\nindex: {}'.format(match, index)) 

出力;
クエリ：マンハッタン
文字列：manhatan
インデックス：8
試合：manhattin
指数：49

クエリ：シティ
文字列：thelargemanhatanprojectがあるthelargemanhatanprojectがthemanhattincity
試合で素晴らしいプロジェクトです大成功の素晴らしいプロジェクト
都市：
インデックス：58

クエリ：
文字列を迎える：偉大
インデックス：thelargemanhatanprojectはthemanhattincity
試合で大きなプロジェクトである上記29の

Answer 5

アプローチは良いですが、私は干し草の多くの小さな針を見つける必要があり、そう

0.72972972973 this string is the one we wanted to find