6

私は Python を使用しています (そして pandas、numpy、scipy にアクセスできます)。

セット A とセット B の 2 つのセットの文字列があります。各セット A と B には c が含まれています。2000 要素 (各要素は文字列)。文字列の長さは約 50 ～ 100 文字で、最大 c. 20 ワード (これらのセットはさらに大きくなる可能性があります)。

セットAのメンバーがセットBのメンバーでもあるかどうかを確認したい.

今、単純な実装は、A と B のメンバーが互いに比較される行列として視覚化できると考えています (たとえば、A1 == B1、A1 == B2、A1 == B3 など...) とブール値比較からの (0, 1) は、行列の要素を構成します。

これを効率的に実装するための最良の方法は何ですか?

さらに2つの詳細：

(i) 大きなセットの場合は、ブルーム フィルター (PyBloom、pybloomfilter など) を使用して各文字列をハッシュすることも考えています (つまり、fasle ポジティブはそれほど気にしません...)。これは良いアプローチですか、それとも考慮すべき他の戦略はありますか?

（ii）ファジーマッチが必要になる可能性があるため、文字列間のレーベンシュタイン距離マッチ（遅い可能性があることはわかっています）を含めることを考えています-これを（i）のアプローチと組み合わせる方法、またはそれ以外の方法でより効率的にする方法はありますか？

助けてくれてありがとう！

4

3 に答える 3

5

まず、2000 * 100 文字はそれほど大きくないため、セットを直接使用できます。

第二に、あなたの文字列がソートされている場合、次のようにそれらを比較する簡単な方法があります（私はここで見つけました）：

def compare(E1, E2):
    i, j = 0, 0
    I, J = len(E1), len(E2)
    while i < I:
        if j >= J or E1[i] < E2[j]:
            print(E1[i], "is not in E2")
            i += 1
        elif E1[i] == E2[j]:
            print(E1[i], "is in E2")
            i, j = i + 1, j + 1
        else:
            j += 1

セットを使用するよりも確かに遅くなりますが、文字列をメモリに保持する必要はありません (同時に必要なのは 2 つだけです)。

レーベンシュタインについては、Pypi で見つけることができ、非常に高速な C モジュールがあります。

于 2013-06-23T18:51:38.030 に答える
1

コメントで述べたように：

def compare(A, B):
    return list(set(A).intersection(B))
于 2014-09-11T13:19:41.747 に答える