Calculando a distância mínima de hamming entre uma corda e um conjunto de cordas

Question

Ex:Se eu tiver a string "asdf" e o conjunto de strings ("qwer", "aswr", "asdv").A distância de hamming entre o conjunto e a corda seria 1, pois "asdv" e "asdf" têm distância de hamming um.

É fácil usar força bruta com algo assim

def hamming_distance(string, set):
    min = len(string)
    for element in set:
        element_distance = sum(ch1 != ch2 for ch1, ch2 in zip(string, element))
        if min > element_distance:
            min = element_distance
        if min == 0:
            break
    return min

Acho que tem O(n*k) onde n = len(string) e k = len(set).No entanto, o tamanho máximo do conjunto é dimensionado com n ^ 2, o que significa que estamos lidando essencialmente com O (n ^ 3).Os conjuntos são bastante estáticos, portanto, se o pré-processamento ajudar, isso é definitivamente uma opção.

Finalmente, devo mencionar que a aplicação aqui é determinar quais conjuntos estão mais próximos da string em questão, mas reduzi o problema porque o comprimento da string é um fator muito mais limitante do que o número de conjuntos.Se houver outra maneira de abordar isso, olhando para o espaço como um todo, em vez dos subconjuntos individuais, eu seria todo ouvidos.Quando adotei essa abordagem pela primeira vez, parecia que a complexidade do espaço ficaria completamente ridícula.

Answer 1

Em primeiro lugar, a distância entre as cordas é uma métrica.Assim, você está tentando encontrar os k vizinhos mais próximos em um espaço métrico (onde k = 1).

Conseqüentemente, você pode considerar uma árvore semelhante à estrutura de dados M-Tree:(ver http://en.wikipedia.org/wiki/M-tree e http://www.vldb.org/conf/1997/P426.PDF ).Esta árvore foi projetada para reduzir o número de comparações de distância que precisam ser realizadas para encontrar os "vizinhos mais próximos".

Pessoalmente, não consegui encontrar uma implementação on-line de um M-Tree que me deixasse satisfeito (veja meu tópico fechado Procurando por uma implementação madura de M-Tree), então criei o meu próprio.

Minha implementação está aqui: https://github.com/jon1van/MTreeMapRepo

A ÚNICA outra implementação que consegui encontrar foi esta: https://github.com/erdavila/M-Tree Não gostei dessa implementação porque ela não tinha funcionalidade de remoção (e vários outros problemas) (mas era gratuita, então... isso é bom).

Você pode considerar usar meu código (que resolve pesquisas kNN em um espaço métrico genérico) com uma métrica de distância Levensthtein (http://en.wikipedia.org/wiki/Levenshtein_distance).Encontrar online uma métrica de distância de Levenshtein totalmente implementada deve ser muito fácil

Adicionada função de distância Levenstein ** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distances/LevensteinDistance.java?r=181