5

現在、 difflibのメソッド get_close_matches メソッドを使用して、15,000 文字列のリストを反復処理し、約 15,000 文字列の別のリストに対して最も近い一致を取得しています。

a=['blah','pie','apple'...]
b=['jimbo','zomg','pie'...]

for value in a:
    difflib.get_close_matches(value,b,n=1,cutoff=.85)

値ごとに 0.58 秒かかります。これは、ループを完了するのに 8,714 秒または 145 分かかることを意味します。より高速な別のライブラリ/メソッド、またはこのメソッドの速度を向上させる方法はありますか? 両方の配列を小文字に変換しようとしましたが、速度がわずかに向上しただけでした。

4

5 に答える 5

5

fuzzysetバイグラムとトライグラムで文字列にインデックスを付けるため、 O(log(N))O(N)の近似一致を見つけますdifflib。私の 100 万以上の単語と単語ペアのファジー セットでは、約 20 秒でインデックスを計算し、100 ミリ秒未満で最も近い一致を見つけることができます。

于 2016-07-11T22:46:09.270 に答える
3

おそらく、各リストに表示されるトライグラム (3 つの連続する文字) のインデックスを作成できます。トライグラムを共有する文字列aに対してのみ文字列をチェックします。b

BLAST バイオインフォマティクス ツールを参照してください。配列データベースに対して配列アラインメントを近似します。

于 2014-01-28T15:59:01.403 に答える
1

これを試して

https://code.google.com/p/pylevenshtein/

レーベンシュタイン Python C 拡張モジュールには、次の高速計算のための関数が含まれています - レーベンシュタイン (編集) 距離、および編集操作 - 文字列の類似度 - 文字列の中央値の近似値、および一般的な文字列の平均化 - 文字列のシーケンスとセットの類似度 通常の文字列と Unicode 文字列の両方をサポートします。

于 2014-01-28T15:13:27.150 に答える