2

私は以前にPythonでコーディングしたことはありません（私はJavaプログラマーです）。プレフィックスツリーで最も類似したビット署名/ベクトルを返すというコードを見ています。署名は、たとえばこの「1001」のようになります。誰かがコードの仕組みを説明してもらえますか? ツリー内のクエリ署名に最も類似した/最も近い署名を見つけるために、プレフィックスツリーをどのように反復しますか? 類似度はハミング距離に基づいています。

コードは次のとおりです。

class SignatureTrie:
    @staticmethod
    def getNearestSignatureKey(trie, signature):
        digitReplacement = {'0': '1', '1': '0'}
        targetKey, iteratingKey = signature.to01(), ''
        for i in range(len(targetKey)):
            iteratingKey+=targetKey[i]
            if not trie.has_prefix(iteratingKey): iteratingKey=iteratingKey[:-1]+digitReplacement[targetKey[i]]
        return iteratingKey

ソース ファイルは次のとおりです: https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

編集：

「私」がコードに期待していることの例を挙げます。コードが実際にそれを行っているのか、どのように行っているのかはわかりません。そのため、コードの解釈、特にプレフィックス ツリーのトラバースを求めています。

3 つの文字列/署名を含む次のプレフィックス ツリーがあるとします: s1 = 1110 s2 = 1100 s3 = 1001

ここに画像の説明を入力

入力シグネチャ s = 1000 があるとします。ここで、プレフィックス/トライのどのベクトルが入力ベクトル s に最も類似しているかを知りたいと考えています。s3 は最小のハミング距離 (1) であるため、コードがベクトル s3 を返すことを期待しています。

私が必要としているのは、コードが私が期待していることを実行しているかどうか、もしそうなら、どのように最も類似した署名を取得しているか、つまりどのようにツリーをトラバースしているかを説明してくれる人です。

コードが私が期待していることをしていない場合、誰かが私が提供した例を挙げてそれが何をするのか説明してもらえますか?

4

2 に答える 2

1

投稿したコード スニペットは、Trie 検索を一切行いません。まったく。

あなたが見ている関数は、指定された署名キー (0 と 1 の文字列) を並べ替えて、最も近い一致を見つけます。署名の最初の文字で始まる一致が見つからない場合は、代わりに逆の値を持つアイテムを探します。

サンプル データの場合、署名を探す場合、1101完全に一致するものはありません。ただし、プレフィックス検索では、 、 for 、 fortrieの検索結果が返されます。の検索は失敗するため、最後をに置き換えるために使用されます。これは一致し、関数の結果も同様です。1111101101digitReplacement101100getNearestSignatureKey()

一致を見つけるために、プレフィックスの一致がtrieオブジェクトに委任されます。このデータ型はBiopython プロジェクトから取得され、完全に Cでコーディングされています。興味がある場合は、Trie_has_prefix関数を調べて、そのタイプが一致するプレフィックスを検索する方法を確認してください。

そのデータ型に関するドキュメントはまばらです。私たちが持っている最高のものは、この自動生成されたモジュールページです:

このモジュールは、トライ データ構造を実装します。これにより、辞書内の文字列の O(M) ルックアップが可能になります。ここで、M は文字列の長さです。おおよその一致もサポートします。

于 2013-08-02T16:57:18.627 に答える