Calcolo di una distanza relativa di Levenshtein - ha senso?

Question

Sto usando sia il soundexing di Daitch-Mokotoff che Damerau-Levenshtein per scoprire se una voce utente e un valore nell'applicazione sono "uguali".

La distanza di Levenshtein dovrebbe essere utilizzata come valore assoluto? Se ho una parola di 20 lettere, una distanza di 4 non è così male. Se la parola ha 4 lettere ...

Quello che sto facendo ora è prendere la distanza/lunghezza per ottenere una distanza che rispecchi meglio la percentuale della parola è stata cambiata.

È un approccio valido/comprovato? O è semplicemente stupido?

Answer 1

La distanza di Levenshtein dovrebbe essere utilizzata come valore assoluto?

Sembra che dipenderebbe dalle vostre esigenze. (Per chiarire: la distanza di Levenshtein è un valore assoluto, ma come indicato dall'OP, il valore grezzo potrebbe non essere così utile come per una determinata applicazione come una misura che tiene conto della lunghezza della parola. sono in realtà più interessati a somiglianza della distanza di per sé.)

sto usando sia Daitch-Mokotoff soundexing e Damerau-Levenshtein per scoprire se una voce utente e un valore nell'applicazione sono "lo stesso ".

Suona come si sta cercando di determinare se l'utente destinato il loro ingresso per essere lo stesso di un determinato valore di dati?

Stai facendo il controllo ortografico? o conforme input non valido a un set noto di valori? Quali sono le tue priorità?

• minimizzare i falsi positivi (Proviamo a assicurarci che tutte le parole suggerite sono molto "simili", e la lista dei suggerimenti è breve)
• minimizzare i falsi negativi (cercano di fare in modo che la stringa l'utente previsto è nella elenco di suggerimenti, anche se si fa la lista lunga)
• massimizzare l'accuratezza corrispondente media

si potrebbe finire utilizzando la distanza Levenshtein in un modo per determinare se una parola dovrebbe essere offerto in un elenco di suggerimenti; e un altro modo per determinare come ordinare l'elenco dei suggerimenti.

Mi sembra, se ho dedotto correttamente il tuo scopo, che la cosa principale che vuoi misurare è somiglianza piuttosto che la differenza tra due stringhe. Come tale, è possibile utilizzare Jaro or Jaro-Winkler distance, che tiene conto della lunghezza delle corde e il numero di caratteri in comune:

Il Jaro distanza dj di due date stringhe s1 e s2 è

(m/|s1| + m/|s2| + (m - t)/m)/3 

dove:

• m è il numero di caratteri corrispondenti
• t è il numero di trasposizioni

Jaro-Winkler distanza usa un prefisso scala p che dà più favorevoli feedback per le stringhe che corrispondono dalla inizio per una lunghezza prestabilita del prefisso l.

Answer 2

La distanza di levenshtein è un valore relativo tra due parole. Confrontando il LD alla lunghezza non è rilevante per es

cat -> scat = 1 (75% simile ??)

differenza -> differenze = 1 (90% simile ??)

Entrambi questi le parole hanno una differenza di lev di 1, cioè differiscono di un carattere, ma se confrontate con le loro lunghezze, il secondo set sembra essere "più" simile.

che uso soundexing classificare parole che hanno lo es stessa distanza lev

cat e fat entrambi hanno un LD di 1 rispetto al kat, ma la parola è più probabile che sia kat di grasso quando utilizza soundex (supponendo la parola è scritta in modo non corretto, non digitata in modo errato!)

Quindi la risposta breve è semplicemente utilizzare la distanza di lev per determinare la somiglianza.