Quali sono alcuni algoritmi per confrontare come sono simili due stringhe?

Question

Ho bisogno di confrontare le stringhe per decidere se rappresentano la stessa cosa. Si tratta di titoli di casi inseriti da esseri umani in cui le abbreviazioni e altri piccoli dettagli possono essere diversi. Ad esempio, considerare i seguenti due titoli:

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP"; 

in contrapposizione a:

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP"; 

un essere umano può misurare rapidamente che questi sono molto probabilmente la stessa cosa. L'attuale approccio che ho preso è di normalizzare le stringhe da caratteri minuscoli tutte le lettere e la rimozione di tutta la punteggiatura e gli spazi dando:

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp"; 

E:

std::string secondNormalized = "harpervthelawofficesofhueylueyllp"; 

Confrontando in questo caso, uno è un sotto-sequenza dell'altro, ma puoi immaginare altre variazioni più complesse in cui ciò non si verifica necessariamente, ma hanno in comune sequenze significative. Potrebbero anche esserci occasionali errori di immissione umana come lettere trasposte e errori di ortografia.

Forse un qualche tipo di programma diff potrebbe aiutare? Ho visto programmi di buona linea diff per confrontare le differenze nel codice da verificare, c'è qualcosa del genere a livello di personaggio, forse in boost? Se potessi contare il numero di caratteri consecutivi in ​​comune e prendere il rapporto con i caratteri non condivisi, forse sarebbe un buon euristico?

Alla fine, ho bisogno di una decisione booleana se considerarli uguali o meno. Non deve essere perfetto, ma idealmente dovrebbe essere raramente sbagliato.

Quale algoritmo posso usare per darmi una sorta di quantificazione di quanto le due stringhe siano simili tra loro e quindi posso convertirle in una risposta sì/no per mezzo di un certo euristico?

Answer 1

Quello che stai cercando sono chiamati algoritmi String Metric. C'è un numero di significativo di loro, molti con caratteristiche simili. Tra i più popolari:

• Levenshtein Distance: il numero minimo di modifiche a carattere singolo necessarie per modificare una parola nell'altra. Le stringhe non devono essere della stessa lunghezza
• Hamming Distance: il numero di caratteri che sono diversi in due stringhe di uguale lunghezza.
• Smith–Waterman: Una famiglia di algoritmi per il calcolo delle somiglianze a sequenza secondaria variabile.
• Sørensen–Dice Coefficient: un algoritmo di somiglianza che calcola i coefficienti di differenza delle coppie di caratteri adiacenti.

Dai uno sguardo a questi e ad altri sullo wiki page sull'argomento.

Answer 2

Damerau Levenshtein distance è un altro algoritmo per il confronto di due stringhe ed è simile all'algoritmo di distanza Levenshtein. La differenza tra i due è che può anche controllare le trasposizioni tra caratteri e quindi può dare un risultato migliore per la correzione degli errori.

Ad esempio: La distanza tra Levenshtein night e nigth è 2 ma Damerau Levenshtein distanza tra night e nigth sarà 1 perché è solo uno scambio di una coppia di caratteri.

Answer 3

È possibile utilizzare ngram per questo. Ad esempio, trasforma le due stringhe in trigrammi di parole (in genere in minuscolo) e confronta la percentuale di esse che sono uguali tra loro.

La tua sfida è definire una percentuale minima per la somiglianza.

http://en.wikipedia.org/wiki/N-gram