Un meilleur algorithme de classement par similarité pour les chaînes de longueur variable

Je cherche un algorithme de similarité de chaîne qui donne de meilleurs résultats sur les chaînes de longueur variable que celles qui sont habituellement suggérées (distance levenshtein, soundex, etc.).

Par exemple,

Chaîne de caractères A: “Robert”,

Puis la chaîne B: “Amy Robertson”

serait un meilleur match que

Chaîne C: “Richard”

De plus, de préférence, cet algorithme doit être indépendant de la langue (fonctionne également dans des langues autres que l’anglais).

Simon White de Catalysoft a écrit un article sur un algorithme très intelligent qui compare les paires de caractères adjacentes qui fonctionnent très bien pour mes besoins:

http://www.catalysoft.com/articles/SsortingkeAMatch.html

Simon a une version Java de l’algorithme et ci-dessous j’en ai écrit une version PL / Ruby (extraite de la version en ruby ​​de Mark Wong-VanHaren) afin de pouvoir l’utiliser dans mes requêtes PostgreSQL:

CREATE FUNCTION ssortingng_similarity(str1 varchar, str2 varchar) RETURNS float8 AS ' str1.downcase! pairs1 = (0..str1.length-2).collect {|i| str1[i,2]}.reject { |pair| pair.include? " "} str2.downcase! pairs2 = (0..str2.length-2).collect {|i| str2[i,2]}.reject { |pair| pair.include? " "} union = pairs1.size + pairs2.size intersection = 0 pairs1.each do |p1| 0.upto(pairs2.size-1) do |i| if p1 == pairs2[i] intersection += 1 pairs2.slice!(i) break end end end (2.0 * intersection) / union ' LANGUAGE 'plruby'; 

Fonctionne comme un charme!

La réponse de marzagao est géniale. Je l’ai converti en C #, alors j’ai pensé le poster ici:

Lien Pastebin

 ///  /// This class implements ssortingng comparison algorithm /// based on character pair similarity /// Source: http://www.catalysoft.com/articles/SsortingkeAMatch.html ///  public class SimilarityTool { ///  /// Compares the two ssortingngs based on letter pair matches ///  ///  ///  /// The percentage match from 0.0 to 1.0 where 1.0 is 100% public double CompareSsortingngs(ssortingng str1, ssortingng str2) { List pairs1 = WordLetterPairs(str1.ToUpper()); List pairs2 = WordLetterPairs(str2.ToUpper()); int intersection = 0; int union = pairs1.Count + pairs2.Count; for (int i = 0; i < pairs1.Count; i++) { for (int j = 0; j < pairs2.Count; j++) { if (pairs1[i] == pairs2[j]) { intersection++; pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success break; } } } return (2.0 * intersection) / union; } ///  /// Gets all letter pairs for each /// individual word in the ssortingng ///  ///  ///  private List WordLetterPairs(ssortingng str) { List AllPairs = new List(); // Tokenize the ssortingng and put the tokens/words into an array ssortingng[] Words = Regex.Split(str, @"\s"); // For each word for (int w = 0; w < Words.Length; w++) { if (!string.IsNullOrEmpty(Words[w])) { // Find the pairs of characters String[] PairsInWord = LetterPairs(Words[w]); for (int p = 0; p < PairsInWord.Length; p++) { AllPairs.Add(PairsInWord[p]); } } } return AllPairs; } ///  /// Generates an array containing every /// two consecutive letters in the input ssortingng ///  ///  ///  private ssortingng[] LetterPairs(ssortingng str) { int numPairs = str.Length - 1; ssortingng[] pairs = new ssortingng[numPairs]; for (int i = 0; i < numPairs; i++) { pairs[i] = str.Substring(i, 2); } return pairs; } } 

Voici une autre version de la réponse de marzagao , celle-ci écrite en Python:

 def get_bigrams(ssortingng): """ Take a ssortingng and return a list of bigrams. """ s = ssortingng.lower() return [s[i:i+2] for i in list(range(len(s) - 1))] def ssortingng_similarity(str1, str2): """ Perform bigram comparison between two ssortingngs and return a percentage match in decimal form. """ pairs1 = get_bigrams(str1) pairs2 = get_bigrams(str2) union = len(pairs1) + len(pairs2) hit_count = 0 for x in pairs1: for y in pairs2: if x == y: hit_count += 1 break return (2.0 * hit_count) / union if __name__ == "__main__": """ Run a test using the example taken from: http://www.catalysoft.com/articles/SsortingkeAMatch.html """ w1 = 'Healed' words = ['Heard', 'Healthy', 'Help', 'Herded', 'Sealed', 'Sold'] for w2 in words: print('Healed --- ' + w2) print(ssortingng_similarity(w1, w2)) print() 

Voici mon implémentation PHP de l’algorithme SsortingkeAMatch suggéré, par Simon White. les avantages (comme il est dit dans le lien) sont les suivants:

  • Un reflet fidèle de la similarité lexicale – les chaînes avec de petites différences doivent être reconnues comme étant similaires. En particulier, un chevauchement significatif de la sous-chaîne devrait indiquer un niveau élevé de similarité entre les chaînes.

  • Une robustesse aux changements d’ordre des mots – deux chaînes contenant les mêmes mots, mais dans un ordre différent, doivent être reconnues comme étant similaires. D’un autre côté, si une chaîne est simplement une anagramme aléatoire des caractères contenus dans l’autre, alors elle devrait (généralement) être reconnue comme étant différente.

  • Indépendance linguistique – l’algorithme devrait fonctionner non seulement en anglais, mais dans de nombreuses langues différentes.

 letterPairs($words[$w]); for ($p = 0; $p < count($pairsInWord); $p++) { $allPairs[] = $pairsInWord[$p]; } } return $allPairs; } /** * @param $str * @return array */ private function letterPairs($str) { $numPairs = mb_strlen($str)-1; $pairs = array(); for ($i = 0; $i < $numPairs; $i++) { $pairs[$i] = mb_substr($str,$i,2); } return $pairs; } /** * @param $str1 * @param $str2 * @return float */ public function compareStrings($str1, $str2) { $pairs1 = $this->wordLetterPairs(strtoupper($str1)); $pairs2 = $this->wordLetterPairs(strtoupper($str2)); $intersection = 0; $union = count($pairs1) + count($pairs2); for ($i=0; $i < count($pairs1); $i++) { $pair1 = $pairs1[$i]; $pairs2 = array_values($pairs2); for($j = 0; $j < count($pairs2); $j++) { $pair2 = $pairs2[$j]; if ($pair1 === $pair2) { $intersection++; unset($pairs2[$j]); break; } } } return (2.0*$intersection)/$union; } } 

Une version plus courte de la réponse de John Rutledge :

 def get_bigrams(ssortingng): ''' Takes a ssortingng and returns a list of bigrams ''' s = ssortingng.lower() return {s[i:i+2] for i in xrange(len(s) - 1)} def ssortingng_similarity(str1, str2): ''' Perform bigram comparison between two ssortingngs and return a percentage match in decimal form ''' pairs1 = get_bigrams(str1) pairs2 = get_bigrams(str2) return (2.0 * len(pairs1 & pairs2)) / (len(pairs1) + len(pairs2)) 

Cette discussion a été très utile, merci. J’ai converti l’algorithme en VBA pour l’utiliser avec Excel et j’ai écrit quelques versions d’une fonction de feuille de calcul, l’une pour comparer une paire de chaînes, l’autre pour comparer une chaîne à une plage / un tableau de chaînes. La version strSimLookup renvoie soit la dernière meilleure correspondance sous forme de chaîne, d’index de tableau ou de mésortingque de similarité.

Cette implémentation produit les mêmes résultats que ceux figurant dans l’exemple d’Amazon sur le site Web de Simon White, à quelques exceptions mineures sur les correspondances à faible score; Je ne suis pas sûr de savoir où se situe la différence, ce pourrait être la fonction Split de VBA, mais je n’ai pas enquêté car cela fonctionne bien pour mes besoins.

 'Implements functions to rate how similar two ssortingngs are on 'a scale of 0.0 (completely dissimilar) to 1.0 (exactly similar) 'Source:  http://www.catalysoft.com/articles/SsortingkeAMatch.html 'Author: Bob Chatham, bob.chatham at gmail.com '9/12/2010 Option Explicit Public Function ssortingngSimilarity(str1 As Ssortingng, str2 As Ssortingng) As Variant 'Simple version of the algorithm that computes the similiarity mesortingc 'between two ssortingngs. 'NOTE: This verision is not efficient to use if you're comparing one ssortingng 'with a range of other values as it will needlessly calculate the pairs for the 'first ssortingng over an over again; use the array-optimized version for this case. Dim sPairs1 As Collection Dim sPairs2 As Collection Set sPairs1 = New Collection Set sPairs2 = New Collection WordLetterPairs str1, sPairs1 WordLetterPairs str2, sPairs2 ssortingngSimilarity = SimilarityMesortingc(sPairs1, sPairs2) Set sPairs1 = Nothing Set sPairs2 = Nothing End Function Public Function strSimA(str1 As Variant, rRng As Range) As Variant 'Return an array of ssortingng similarity indexes for str1 vs every ssortingng in input range rRng Dim sPairs1 As Collection Dim sPairs2 As Collection Dim arrOut As Variant Dim l As Long, j As Long Set sPairs1 = New Collection WordLetterPairs CStr(str1), sPairs1 l = rRng.Count ReDim arrOut(1 To l) For j = 1 To l Set sPairs2 = New Collection WordLetterPairs CStr(rRng(j)), sPairs2 arrOut(j) = SimilarityMesortingc(sPairs1, sPairs2) Set sPairs2 = Nothing Next j strSimA = Application.Transpose(arrOut) End Function Public Function strSimLookup(str1 As Variant, rRng As Range, Optional returnType) As Variant 'Return either the best match or the index of the best match 'depending on returnTYype parameter) between str1 and ssortingngs in rRng) ' returnType = 0 or omitted: returns the best matching ssortingng ' returnType = 1 : returns the index of the best matching ssortingng ' returnType = 2 : returns the similarity mesortingc Dim sPairs1 As Collection Dim sPairs2 As Collection Dim mesortingc, bestMesortingc As Double Dim i, iBest As Long Const RETURN_STRING As Integer = 0 Const RETURN_INDEX As Integer = 1 Const RETURN_METRIC As Integer = 2 If IsMissing(returnType) Then returnType = RETURN_STRING Set sPairs1 = New Collection WordLetterPairs CStr(str1), sPairs1 bestMesortingc = -1 iBest = -1 For i = 1 To rRng.Count Set sPairs2 = New Collection WordLetterPairs CStr(rRng(i)), sPairs2 mesortingc = SimilarityMesortingc(sPairs1, sPairs2) If mesortingc > bestMesortingc Then bestMesortingc = mesortingc iBest = i End If Set sPairs2 = Nothing Next i If iBest = -1 Then strSimLookup = CVErr(xlErrValue) Exit Function End If Select Case returnType Case RETURN_STRING strSimLookup = CStr(rRng(iBest)) Case RETURN_INDEX strSimLookup = iBest Case Else strSimLookup = bestMesortingc End Select End Function Public Function strSim(str1 As Ssortingng, str2 As Ssortingng) As Variant Dim ilen, iLen1, ilen2 As Integer iLen1 = Len(str1) ilen2 = Len(str2) If iLen1 >= ilen2 Then ilen = ilen2 Else ilen = iLen1 strSim = ssortingngSimilarity(Left(str1, ilen), Left(str2, ilen)) End Function Sub WordLetterPairs(str As Ssortingng, pairColl As Collection) 'Tokenize str into words, then add all letter pairs to pairColl Dim Words() As Ssortingng Dim word, nPairs, pair As Integer Words = Split(str) If UBound(Words) < 0 Then Set pairColl = Nothing Exit Sub End If For word = 0 To UBound(Words) nPairs = Len(Words(word)) - 1 If nPairs > 0 Then For pair = 1 To nPairs pairColl.Add Mid(Words(word), pair, 2) Next pair End If Next word End Sub Private Function SimilarityMesortingc(sPairs1 As Collection, sPairs2 As Collection) As Variant 'Helper function to calculate similarity mesortingc given two collections of letter pairs. 'This function is designed to allow the pair collections to be set up separately as needed. 'NOTE: sPairs2 collection will be altered as pairs are removed; copy the collection 'if this is not the desired behavior. 'Also assumes that collections will be deallocated somewhere else Dim Intersect As Double Dim Union As Double Dim i, j As Long If sPairs1.Count = 0 Or sPairs2.Count = 0 Then SimilarityMesortingc = CVErr(xlErrNA) Exit Function End If Union = sPairs1.Count + sPairs2.Count Intersect = 0 For i = 1 To sPairs1.Count For j = 1 To sPairs2.Count If StrComp(sPairs1(i), sPairs2(j)) = 0 Then Intersect = Intersect + 1 sPairs2.Remove j Exit For End If Next j Next i SimilarityMesortingc = (2 * Intersect) / Union End Function 

Je suis désolé, la réponse n’a pas été inventée par l’auteur. Il s’agit d’un algorithme bien connu qui a été présenté pour la première fois par Digital Equipment Corporation et qui est souvent appelé «shingling».

http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-TN-1997-015.pdf

J’ai traduit l’algorithme de Simon White en PL / pgSQL. Ceci est ma consortingbution.

  create or replace function spt1.letterpairs(in p_str varchar) returns varchar as $$ declare v_numpairs integer := length(p_str)-1; v_pairs varchar[]; begin for i in 1 .. v_numpairs loop v_pairs[i] := substr(p_str, i, 2); end loop; return v_pairs; end; $$ language 'plpgsql'; --=================================================================== create or replace function spt1.wordletterpairs(in p_str varchar) returns varchar as $$ declare v_allpairs varchar[]; v_words varchar[]; v_pairsinword varchar[]; begin v_words := regexp_split_to_array(p_str, '[[:space:]]'); for i in 1 .. array_length(v_words, 1) loop v_pairsinword := spt1.letterpairs(v_words[i]); if v_pairsinword is not null then for j in 1 .. array_length(v_pairsinword, 1) loop v_allpairs := v_allpairs || v_pairsinword[j]; end loop; end if; end loop; return v_allpairs; end; $$ language 'plpgsql'; --=================================================================== create or replace function spt1.arrayintersect(ANYARRAY, ANYARRAY) returns anyarray as $$ select array(select unnest($1) intersect select unnest($2)) $$ language 'sql'; --=================================================================== create or replace function spt1.comparessortingngs(in p_str1 varchar, in p_str2 varchar) returns float as $$ declare v_pairs1 varchar[]; v_pairs2 varchar[]; v_intersection integer; v_union integer; begin v_pairs1 := wordletterpairs(upper(p_str1)); v_pairs2 := wordletterpairs(upper(p_str2)); v_union := array_length(v_pairs1, 1) + array_length(v_pairs2, 1); v_intersection := array_length(arrayintersect(v_pairs1, v_pairs2), 1); return (2.0 * v_intersection / v_union); end; $$ language 'plpgsql'; 

Une version PHP plus rapide de l’algorithme:

 /** * * @param $str * @return mixed */ private static function wordLetterPairs ($str) { $allPairs = array(); // Tokenize the ssortingng and put the tokens/words into an array $words = explode(' ', $str); // For each word for ($w = 0; $w < count($words); $w ++) { // Find the pairs of characters $pairsInWord = self::letterPairs($words[$w]); for ($p = 0; $p < count($pairsInWord); $p ++) { $allPairs[$pairsInWord[$p]] = $pairsInWord[$p]; } } return array_values($allPairs); } /** * * @param $str * @return array */ private static function letterPairs ($str) { $numPairs = mb_strlen($str) - 1; $pairs = array(); for ($i = 0; $i < $numPairs; $i ++) { $pairs[$i] = mb_substr($str, $i, 2); } return $pairs; } /** * * @param $str1 * @param $str2 * @return float */ public static function compareStrings ($str1, $str2) { $pairs1 = self::wordLetterPairs(mb_strtolower($str1)); $pairs2 = self::wordLetterPairs(mb_strtolower($str2)); $union = count($pairs1) + count($pairs2); $intersection = count(array_intersect($pairs1, $pairs2)); return (2.0 * $intersection) / $union; } 

Pour les données que j'avais (environ 2300 comparaisons), j'avais un temps de fonctionnement de 0,58 sec avec une solution d' Igal Alkon contre 0,35 sec avec le mien.

Une version dans la belle Scala:

  def pairDistance(s1: Ssortingng, s2: Ssortingng): Double = { def strToPairs(s: Ssortingng, acc: List[Ssortingng]): List[Ssortingng] = { if (s.size < 2) acc else strToPairs(s.drop(1), if (s.take(2).contains(" ")) acc else acc ::: List(s.take(2))) } val lst1 = strToPairs(s1.toUpperCase, List()) val lst2 = strToPairs(s2.toUpperCase, List()) (2.0 * lst2.intersect(lst1).size) / (lst1.size + lst2.size) } 

Les mésortingques de similarité de chaîne contiennent une vue d’ensemble de nombreuses mésortingques différentes utilisées dans la comparaison de chaînes ( Wikipedia a également une vue d’ensemble). Une grande partie de ces mésortingques est implémentée dans une bibliothèque simmesortingcs .

Un autre exemple de mésortingque, non inclus dans la vue d’ensemble donnée, est par exemple la distance de compression (en essayant de se rapprocher de la complexité de Kolmogorov ), qui peut être utilisée pour des textes un peu plus longs que celui présenté.

Vous pourriez également envisager d’aborder un sujet beaucoup plus large du traitement automatique du langage naturel . Ces packages R peuvent vous permettre de démarrer rapidement (ou du moins de donner quelques idées).

Et une dernière édition – recherchez les autres questions sur ce sujet à SO, il y en a pas mal d’autres.

Voici la version R:

 get_bigrams <- function(str) { lstr = tolower(str) bigramlst = list() for(i in 1:(nchar(str)-1)) { bigramlst[[i]] = substr(str, i, i+1) } return(bigramlst) } str_similarity <- function(str1, str2) { pairs1 = get_bigrams(str1) pairs2 = get_bigrams(str2) unionlen = length(pairs1) + length(pairs2) hit_count = 0 for(x in 1:length(pairs1)){ for(y in 1:length(pairs2)){ if (pairs1[[x]] == pairs2[[y]]) hit_count = hit_count + 1 } } return ((2.0 * hit_count) / unionlen) } 

Affichage de la réponse de marzagao en C99, inspirée par ces algorithmes

 double dice_match(const char *ssortingng1, const char *ssortingng2) { //check fast cases if (((ssortingng1 != NULL) && (ssortingng1[0] == '\0')) || ((ssortingng2 != NULL) && (ssortingng2[0] == '\0'))) { return 0; } if (ssortingng1 == ssortingng2) { return 1; } size_t strlen1 = strlen(ssortingng1); size_t strlen2 = strlen(ssortingng2); if (strlen1 < 2 || strlen2 < 2) { return 0; } size_t length1 = strlen1 - 1; size_t length2 = strlen2 - 1; double matches = 0; int i = 0, j = 0; //get bigrams and compare while (i < length1 && j < length2) { char a[3] = {string1[i], string1[i + 1], '\0'}; char b[3] = {string2[j], string2[j + 1], '\0'}; int cmp = strcmpi(a, b); if (cmp == 0) { matches += 2; } i++; j++; } return matches / (length1 + length2); } 

Quelques tests basés sur l' article original :

 #include  void article_test1() { char *ssortingng1 = "FRANCE"; char *ssortingng2 = "FRENCH"; printf("====%s====\n", __func__); printf("%2.f%% == 40%%\n", dice_match(ssortingng1, ssortingng2) * 100); } void article_test2() { printf("====%s====\n", __func__); char *ssortingng = "Healed"; char *ss[] = {"Heard", "Healthy", "Help", "Herded", "Sealed", "Sold"}; int correct[] = {44, 55, 25, 40, 80, 0}; for (int i = 0; i < 6; ++i) { printf("%2.f%% == %d%%\n", dice_match(string, ss[i]) * 100, correct[i]); } } void multicase_test() { char *string1 = "FRaNcE"; char *string2 = "fREnCh"; printf("====%s====\n", __func__); printf("%2.f%% == 40%%\n", dice_match(string1, string2) * 100); } void gg_test() { char *string1 = "GG"; char *string2 = "GGGGG"; printf("====%s====\n", __func__); printf("%2.f%% != 100%%\n", dice_match(string1, string2) * 100); } int main() { article_test1(); article_test2(); multicase_test(); gg_test(); return 0; } 

En me basant sur la version impressionnante de Michael La Voie, telle que demandée pour en faire une méthode d’extension, voici ce que j’ai trouvé. Le principal avantage de cette méthode est que vous pouvez sortinger une liste générique en fonction du pourcentage correspondant. Par exemple, considérez que vous avez un champ de chaîne nommé “City” dans votre object. Un utilisateur recherche “Chester” et vous souhaitez retourner les résultats par ordre décroissant de correspondance. Par exemple, vous voulez que les correspondances littérales de Chester apparaissent avant Rochester. Pour ce faire, ajoutez deux nouvelles propriétés à votre object:

  public ssortingng SearchText { get; set; } public double PercentMatch { get { return City.ToUpper().PercentMatchTo(this.SearchText.ToUpper()); } } 

Ensuite, sur chaque object, définissez le SearchText sur ce que l’utilisateur a recherché. Ensuite, vous pouvez sortinger facilement avec quelque chose comme:

  zipcodes = zipcodes.OrderByDescending(x => x.PercentMatch); 

Voici la légère modification pour en faire une méthode d’extension:

  ///  /// This class implements ssortingng comparison algorithm /// based on character pair similarity /// Source: http://www.catalysoft.com/articles/SsortingkeAMatch.html ///  public static double PercentMatchTo(this ssortingng str1, ssortingng str2) { List pairs1 = WordLetterPairs(str1.ToUpper()); List pairs2 = WordLetterPairs(str2.ToUpper()); int intersection = 0; int union = pairs1.Count + pairs2.Count; for (int i = 0; i < pairs1.Count; i++) { for (int j = 0; j < pairs2.Count; j++) { if (pairs1[i] == pairs2[j]) { intersection++; pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success break; } } } return (2.0 * intersection) / union; } ///  /// Gets all letter pairs for each /// individual word in the ssortingng ///  ///  ///  private static List WordLetterPairs(ssortingng str) { List AllPairs = new List(); // Tokenize the ssortingng and put the tokens/words into an array ssortingng[] Words = Regex.Split(str, @"\s"); // For each word for (int w = 0; w < Words.Length; w++) { if (!string.IsNullOrEmpty(Words[w])) { // Find the pairs of characters String[] PairsInWord = LetterPairs(Words[w]); for (int p = 0; p < PairsInWord.Length; p++) { AllPairs.Add(PairsInWord[p]); } } } return AllPairs; } ///  /// Generates an array containing every /// two consecutive letters in the input ssortingng ///  ///  ///  private static ssortingng[] LetterPairs(ssortingng str) { int numPairs = str.Length - 1; ssortingng[] pairs = new ssortingng[numPairs]; for (int i = 0; i < numPairs; i++) { pairs[i] = str.Substring(i, 2); } return pairs; } 

Mon implémentation JavaScript prend une chaîne ou un tableau de chaînes et un étage facultatif (le niveau par défaut est 0.5). Si vous lui passez une chaîne, elle retournera true ou false selon que le score de similarité de la chaîne est supérieur ou égal à celui du sol. Si vous lui passez un tableau de chaînes, il retournera un tableau de ces chaînes dont le score de similarité est supérieur ou égal au sol, sortingé par score.

Exemples:

 'Healed'.fuzzy('Sealed'); // returns true 'Healed'.fuzzy('Help'); // returns false 'Healed'.fuzzy('Help', 0.25); // returns true 'Healed'.fuzzy(['Sold', 'Herded', 'Heard', 'Help', 'Sealed', 'Healthy']); // returns ["Sealed", "Healthy"] 'Healed'.fuzzy(['Sold', 'Herded', 'Heard', 'Help', 'Sealed', 'Healthy'], 0); // returns ["Sealed", "Healthy", "Heard", "Herded", "Help", "Sold"] 

C’est ici:

 (function(){ var default_floor = 0.5; function pairs(str){ var pairs = [] , length = str.length - 1 , pair; str = str.toLowerCase(); for(var i = 0; i < length; i++){ pair = str.substr(i, 2); if(!/\s/.test(pair)){ pairs.push(pair); } } return pairs; } function similarity(pairs1, pairs2){ var union = pairs1.length + pairs2.length , hits = 0; for(var i = 0; i < pairs1.length; i++){ for(var j = 0; j < pairs1.length; j++){ if(pairs1[i] == pairs2[j]){ pairs2.splice(j--, 1); hits++; break; } } } return 2*hits/union || 0; } String.prototype.fuzzy = function(strings, floor){ var str1 = this , pairs1 = pairs(this); floor = typeof floor == 'number' ? floor : default_floor; if(typeof(strings) == 'string'){ return str1.length > 1 && ssortingngs.length > 1 && similarity(pairs1, pairs(ssortingngs)) >= floor || str1.toLowerCase() == ssortingngs.toLowerCase(); }else if(ssortingngs instanceof Array){ var scores = {}; ssortingngs.map(function(str2){ scores[str2] = str1.length > 1 ? similarity(pairs1, pairs(str2)) : 1*(str1.toLowerCase() == str2.toLowerCase()); }); return ssortingngs.filter(function(str){ return scores[str] >= floor; }).sort(function(a, b){ return scores[b] - scores[a]; }); } }; })(); 

Et voici une version réduite pour votre commodité:

 (function(){function g(a){var b=[],e=a.length-1,d;a=a.toLowerCase();for(var c=0;c=b||e.toLowerCase()==a.toLowerCase();if(a instanceof Array){var c={};a.map(function(a){c[a]=1=b}).sort(function(a,b){return c[b]-c[a]})}}})(); 

L’algorithme de coefficient de dés (réponse de Simon White / marzagao) est implémenté dans Ruby dans la méthode pair_distance_similar dans la gem amatch

https://github.com/flori/amatch

Ce bijou contient également des implémentations d’un certain nombre d’algorithmes d’appariement et de comparaison de chaînes: distance d’édition de Levenshtein, distance d’édition de Sellers, distance de Hamming, longueur de sous-séquence commune la plus longue, longueur de chaîne commune, mésortingque Jaro-Winkler .

Une version Haskell – n’hésitez pas à suggérer des modifications car je n’ai pas fait beaucoup de Haskell.

 import Data.Char import Data.List -- Convert a ssortingng into words, then get the pairs of words from that phrase wordLetterPairs :: Ssortingng -> [Ssortingng] wordLetterPairs s1 = concat $ map pairs $ words s1 -- Converts a Ssortingng into a list of letter pairs. pairs :: Ssortingng -> [Ssortingng] pairs [] = [] pairs (x:[]) = [] pairs (x:ys) = [x, head ys]:(pairs ys) -- Calculates the match rating for two ssortingngs matchRating :: Ssortingng -> Ssortingng -> Double matchRating s1 s2 = (numberOfMatches * 2) / totalLength where pairsS1 = wordLetterPairs $ map toLower s1 pairsS2 = wordLetterPairs $ map toLower s2 numberOfMatches = fromIntegral $ length $ pairsS1 `intersect` pairsS2 totalLength = fromIntegral $ length pairsS1 + length pairsS2 

Clojure:

 (require '[clojure.set :refer [intersection]]) (defn bigrams [s] (->> (split s #"\s+") (mapcat #(partition 2 1 %)) (set))) (defn ssortingng-similarity [ab] (let [a-pairs (bigrams a) b-pairs (bigrams b) total-count (+ (count a-pairs) (count b-pairs)) match-count (count (intersection a-pairs b-pairs)) similarity (/ (* 2 match-count) total-count)] similarity)) 

Qu’en est-il de la distance Levenshtein, divisée par la longueur de la première chaîne (ou bien divisée par la longueur min / max / moyenne des deux chaînes)? Cela a fonctionné pour moi jusqu’à présent.

Hey les gars j’ai essayé ceci en javascript, mais je suis nouveau, tout le monde sait des moyens plus rapides pour le faire?

 function get_bigrams(ssortingng) { // Takes a ssortingng and returns a list of bigrams var s = ssortingng.toLowerCase(); var v = new Array(s.length-1); for (i = 0; i< v.length; i++){ v[i] =s.slice(i,i+2); } return v; } function string_similarity(str1, str2){ /* Perform bigram comparison between two strings and return a percentage match in decimal form */ var pairs1 = get_bigrams(str1); var pairs2 = get_bigrams(str2); var union = pairs1.length + pairs2.length; var hit_count = 0; for (x in pairs1){ for (y in pairs2){ if (pairs1[x] == pairs2[y]){ hit_count++; } } } return ((2.0 * hit_count) / union); } var w1 = 'Healed'; var word =['Heard','Healthy','Help','Herded','Sealed','Sold'] for (w2 in word){ console.log('Healed --- ' + word[w2]) console.log(string_similarity(w1,word[w2])); } 

Voici une autre version de Similarity basée sur l’index Sørensen – Dice (la réponse de marzagao), celle-ci écrite en C ++ 11:

 /* * Similarity based in Sørensen–Dice index. * * Returns the Similarity between _str1 and _str2. */ double similarity_sorensen_dice(const std::ssortingng& _str1, const std::ssortingng& _str2) { // Base case: if some ssortingng is empty. if (_str1.empty() || _str2.empty()) { return 1.0; } auto str1 = upper_ssortingng(_str1); auto str2 = upper_ssortingng(_str2); // Base case: if the ssortingngs are equals. if (str1 == str2) { return 0.0; } // Base case: if some ssortingng does not have bigrams. if (str1.size() < 2 || str2.size() < 2) { return 1.0; } // Extract bigrams from str1 auto num_pairs1 = str1.size() - 1; std::unordered_set str1_bigrams; str1_bigrams.reserve(num_pairs1); for (unsigned i = 0; i < num_pairs1; ++i) { str1_bigrams.insert(str1.substr(i, 2)); } // Extract bigrams from str2 auto num_pairs2 = str2.size() - 1; std::unordered_set str2_bigrams; str2_bigrams.reserve(num_pairs2); for (unsigned int i = 0; i < num_pairs2; ++i) { str2_bigrams.insert(str2.substr(i, 2)); } // Find the intersection between the two sets. int intersection = 0; if (str1_bigrams.size() < str2_bigrams.size()) { const auto it_e = str2_bigrams.end(); for (const auto& bigram : str1_bigrams) { intersection += str2_bigrams.find(bigram) != it_e; } } else { const auto it_e = str1_bigrams.end(); for (const auto& bigram : str2_bigrams) { intersection += str1_bigrams.find(bigram) != it_e; } } // Returns similarity coefficient. return (2.0 * intersection) / (num_pairs1 + num_pairs2); } 

I was looking for pure ruby implementation of the algorithm indicated by @marzagao’s answer. Unfortunately, link indicated by @marzagao is broken. In @s01ipsist answer, he indicated ruby gem amatch where implementation is not in pure ruby. So I searchd a little and found gem fuzzy_match which has pure ruby implementation (though this gem use amatch ) at here . I hope this will help someone like me.