Distanza di Hamming vs. Levenshtein Distanza

Question

Per il problema che sto lavorando su, trovando distanze tra due sequenze per determinare la loro somiglianza, l'ordine di sequenza è molto importante. Tuttavia, le sequenze che ho non sono tutte la stessa lunghezza, in modo che il rilievo di tutte le stringhe carenti con punti vuoti tale che entrambe le sequenze della stessa lunghezza per soddisfare il requisito di distanza di Hamming. C'è qualche grosso problema con me a fare questo, dal momento che tutto ciò che interessa sono il numero di trasposizioni (non inserzioni o delezioni come Levenshtein fa)?

Ho trovato che la distanza di Hamming è molto, molto più veloce di Levenshtein come distanza metrica per sequenze di lunghezza maggiore. Quando si dovrebbe usare Levenshtein distanza (o derivati ??di Levenshtein a distanza) al posto del molto più economico distanza di Hamming? Hamming distanza può essere considerato il limite superiore per distanze possibili Levenshtein tra due sequenze, quindi se sto paragonando le due sequenze per una somiglianza ordine polarizzato metrica piuttosto che il numero minimo assoluto di mosse per abbinare le sequenze, non v'è un apparente motivo per me di scegliere Levenshtein sopra Hamming come metrica, è lì?

Answer 1

Questa domanda dipende molto dal tipo di sequenze che si sono corrispondenti, e che cosa risultato desiderato.

Se non è un problema che "1234567890" e "0123456789" sono considerati totalmente diverso, anzi Hamming distanza è bene.

Answer 2

In aggiunta alla risposta Johan destra, l'imbottitura può essere problematico.

Ad esempio, quando si confronta 123 per 123456 è diverso se si pad o alla fine della stringa o all'inizio della stringa. La somiglianza di ___123 con 123456 è 0, ma la somiglianza di 123___ con 123456 è 3.