Cálculo de la distancia mínima de la hamamización entre una cadena y un conjunto de cadenas

Question

ex: Si tengo la cadena "asdf" y el conjunto de cuerdas ("QWER", "ASWR", "ASDV"). La distancia de hamaming entre el set y la cadena serían 1 como el "ASDV" y "ASDF" tienen la distancia de la distancia.

Es fácil de forzar la fuerza con algo así

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

Creo que esto tiene O (n * k) donde n= len (cadena) y k= len (conjunto). Sin embargo, las escalas de tamaño máximo de tamaño con N ^ 2, lo que significa que estamos esencialmente tratando con O (n ^ 3). Los sets bastante estáticos, por lo que si el preprocesamiento ayudaría a que es definitivamente una opción.

Finalmente, debería mencionar que la aplicación aquí es determinar qué se establece (s) están más cerca de la cadena en cuestión, pero he reducido el problema porque la longitud de cadena es un factor mucho más limitante que el número de conjuntos . Si hay otra manera de acercarse a esto mirando el espacio en su totalidad en lugar de los subconjuntos individuales, sería todos los oídos. Cuando tomé por primera vez ese enfoque, parecía que la complejidad del espacio iba a ser completamente ridícula, aunque.

Answer 1

En primer lugar, la distancia de hamaming entre las cuerdas es una métrica. Por lo tanto, está tratando de encontrar los vecinos más cercanos a K en un espacio métrico (donde K= 1).

En consecuencia, es posible que desee considerar un árbol similar a la estructura de datos del árbol M: (consulte > http://en.wikipedia.org/wiki/m-tree y http : //www.vldb.org/conf/1997/p426.pdf ). Este árbol está diseñado para reducir las comparaciones de la distancia número que deben realizarse para encontrar "vecinos más cercanos".

Personalmente, no pude encontrar una implementación de un árbol en línea en línea con la que estaba satisfecho (consulte mi hilo cerrado en busca de una implementación madura de árbol maduro), así que giré a mi cuenta.

Mi implementación está aquí: https://github.com/jon1van/mTremAprepo

La única otra implementación que pude encontrar fue esta: https://github.com/erdavila/m -Tree No me gustó esta implementación porque no tenía la funcionalidad del eliminación (y varios otros problemas) (pero era gratis, así que ... eso es bueno).

Es posible que desee considerar el uso de mi código (que resuelve búsquedas en un espacio métrico genérico) con una métrica de distancia de levensthtein ( http://en.wikipedia.org/wiki/levenshtein_distance ). Encontrar una métrica de distancia Levenshtein completamente implementada en línea debería ser bastante fácil

agregó la función de distancia de levenstein ** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distance/levensteindistance.java?r= 181