Calcolo della distanza minima di hamming tra una stringa e un set di stringhe
-
21-12-2019 - |
Domanda
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ò.
Soluzione
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