Calcolo della distanza minima di hamming tra una stringa e un set di stringhe

Question

ex: Se ho la stringa "Asdf" e il set di stringhe ("Qwer", "ASWR", "ASDV"). La distanza di hamming tra il set e la stringa sarebbe 1 come "Asdv" e "Asdf" hanno una distanza di hamming uno.

È facile da brutare forza con qualcosa come questo

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

.

Penso che questo abbia o (n * k) dove n= len (stringa) e k= len (set). Tuttavia, la dimensione massima della dimensione impostata con N ^ 2, il che significa che ci occupiamo essenzialmente con o (n ^ 3). I set piuttosto statici, quindi se la pre-elaborazione avrebbe aiutato che sia sicuramente un'opzione.

Infine, dovrei menzionare che l'applicazione qui è determinare quali set (i) sono più vicini alla stringa in questione, ma ho ridotto il problema perché la lunghezza della stringa è un fattore molto più limitante del numero di set . Se c'è un altro modo per avvicinarsi guardando lo spazio nel suo insieme anziché i singoli sottoinsiemi sarei tutte le orecchie. Quando ho preso per la prima volta quell'approccio sembrava che la complessità spaziale sarebbe stata completamente ridicolo però.

Answer 1

Prima di tutto, la distanza di hamming tra le stringhe è una metrica. Quindi, stai cercando di trovare i vicini K-più vicini in uno spazio metrico (dove k= 1).

Di conseguenza, potresti prendere in considerazione un albero simile alla struttura dei dati M-Tree: (vedi http://en.wikipedia.org/wiki/m-tree e http : //www.vldb.org/conf/1997/p426.pdf ). Questo albero è progettato per ridurre i confronti del numero di distanza che devono essere eseguiti per trovare "vicini più vicini".

Personalmente, non riuscivo a trovare un'implementazione di un M-Tree online con cui sono stato soddisfatto (vedi il mio filo chiuso alla ricerca di un'implementazione M-Tree Mature) quindi ho rotolato il mio.

La mia implementazione è qui: https://github.com/jon1van/mtreemaprepo

L'unica altra implementazione che ho trovato è stata questa: https://github.com/erdavila/m -Tree Non mi è piaciuta questa implementazione perché non aveva rimozione funzionalità (e molti altri problemi) (ma era libero quindi ... è buono).

Potrebbe voler considerare di utilizzare il mio codice (che risolve la ricerca KNO in uno spazio metrico generico) con una metrica di distanza di Levinsthtein ( http://en.wikipedia.org/wiki/levenshtein_distance ). Trovare un Levenshtein Distance METRIC interamente implementato La metrica online dovrebbe essere piuttosto facile

Aggiunto LevenSein Distance Function ** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distances/levensteintance.java?R= 181