从python中的前缀树返回最相似的位签名

Question

我以前从来没有用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

编辑：

我将给出一个“我在”期望代码做什么的例子。我不知道代码是否真的做到了，也不知道它是如何做到的。这就是为什么我要求解释代码，特别是遍历前缀树。在

假设我有以下前缀树，其中包含三个字符串/签名： s1=1110号 s2=1100秒 s3=1001

假设输入签名s=1000。现在我想知道前缀/trie中的哪个向量与输入向量s最相似，因为s3的hamming距离最小（1），所以我希望代码返回向量s3。在

我需要的是有人向我解释代码是否在做我期望的事情，如果是的话，它是如何得到最相似的签名的，也就是说，它是如何遍历树的。在

如果代码没有达到我期望的效果，有人能解释一下它做了什么吗？在

Answer 1

class SignatureTrie:

    @staticmethod
    def getNearestSignatureKey(trie, signature):

        digitReplacement = {'0': '1', '1': '0'}
        targetKey = signature.to01() # string with 0 and 1
        iteratingKey = '' # empty string

        for i in range(len(targetKey)): # loop through targetKey string (i being an index)
            iteratingKey += targetKey[i] # append char at position i
            if not trie.has_prefix(iteratingKey): # if iteratingKey is not the trie
                # flip last digit (0 if 1, 1 if 0) of iteratingKey
                iteratingKey = iteratingKey[:-1]+digitReplacement[targetKey[i]]

        return iteratingKey

Answer 2

您发布的代码片段不执行任何Trie搜索。完全。在

您正在查看的函数将对给定的签名密钥（一个由零和一组成的字符串）进行置换，以找到最接近的匹配项；如果没有找到以签名的第一个字符开头的匹配项，则它将查找具有反值的项。在

对于示例数据，如果要查找签名1101，则没有完全匹配的内容。但是trie前缀搜索将返回搜索1、11和{}的结果。搜索1101失败，因此digitReplacement将最后一个1替换为匹配的0，因此1100是{}函数的结果。。在

为了找到匹配项，前缀匹配被委托给trie对象。此数据类型取自Biopython project，编码为entirely in C；如果您愿意，请研究^{} function，看看该类型如何搜索匹配的前缀。在

关于该数据类型的文档是稀疏的；最好的是this autogenerated module page：

This module implements a trie data structure. This allows an O(M) lookup of a string in a dictionary, where M is the length of the string. It also supports approximate matches.