Um algoritmo de sorting de similaridade melhor para cadeias de comprimento variável

Eu estou procurando um algoritmo de similaridade de seqüência de caracteres que produz melhores resultados em seqüências de comprimento variável do que os que são geralmente sugeridos (distância levenshtein, soundex, etc).

Por exemplo,

Dada a string A: “Robert”,

Em seguida, a cadeia B: “Amy Robertson”

seria um jogo melhor do que

Cadeia C: “Richard”

Além disso, preferencialmente, esse algoritmo deve ser agnóstico de idioma (também funciona em idiomas diferentes do inglês).

    Simon White, da Catalysoft, escreveu um artigo sobre um algoritmo muito inteligente que compara pares de caracteres adjacentes que funciona muito bem para os meus propósitos:

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

    Simon tem uma versão Java do algoritmo e abaixo escrevi uma versão PL / Ruby (tirada da versão em ruby ​​simples feita no comentário de input do fórum relacionado por Mark Wong-VanHaren) para que eu possa usá-la em minhas consultas do PostgreSQL:

    CREATE FUNCTION string_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'; 

    Funciona como um encanto!

    A resposta de marzagao é ótima. Eu converti para C #, então pensei em postar aqui:

    Link Pastebin

     ///  /// This class implements string comparison algorithm /// based on character pair similarity /// Source: http://www.catalysoft.com/articles/StrikeAMatch.html ///  public class SimilarityTool { ///  /// Compares the two strings based on letter pair matches ///  ///  ///  /// The percentage match from 0.0 to 1.0 where 1.0 is 100% public double CompareStrings(string str1, string 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 string ///  ///  ///  private List WordLetterPairs(string str) { List AllPairs = new List(); // Tokenize the string and put the tokens/words into an array string[] 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 string ///  ///  ///  private string[] LetterPairs(string str) { int numPairs = str.Length - 1; string[] pairs = new string[numPairs]; for (int i = 0; i < numPairs; i++) { pairs[i] = str.Substring(i, 2); } return pairs; } } 

    Aqui está outra versão da resposta de marzagao , esta escrita em Python:

     def get_bigrams(string): """ Take a string and return a list of bigrams. """ s = string.lower() return [s[i:i+2] for i in list(range(len(s) - 1))] def string_similarity(str1, str2): """ Perform bigram comparison between two strings 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/StrikeAMatch.html """ w1 = 'Healed' words = ['Heard', 'Healthy', 'Help', 'Herded', 'Sealed', 'Sold'] for w2 in words: print('Healed --- ' + w2) print(string_similarity(w1, w2)) print() 

    Aqui está minha implementação PHP do algoritmo StrikeAMatch sugerido, por Simon White. as vantagens (como diz no link) são:

    • Um verdadeiro reflexo da semelhança lexical – strings com pequenas diferenças devem ser reconhecidas como sendo semelhantes. Em particular, uma sobreposição de substring significativa deve apontar para um alto nível de similaridade entre as strings.

    • Uma robustez para alterações de ordem de palavras – duas cadeias que contêm as mesmas palavras, mas numa ordem diferente, devem ser reconhecidas como sendo semelhantes. Por outro lado, se uma string é apenas um anagrama random dos caracteres contidos na outra, ela deve (geralmente) ser reconhecida como diferente.

    • Independência de Linguagem – o algoritmo deve funcionar não apenas em inglês, mas em muitos idiomas diferentes.

     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; } } 

    Uma versão mais curta da resposta de John Rutledge :

     def get_bigrams(string): ''' Takes a string and returns a list of bigrams ''' s = string.lower() return {s[i:i+2] for i in xrange(len(s) - 1)} def string_similarity(str1, str2): ''' Perform bigram comparison between two strings 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)) 

    Esta discussão foi realmente útil, obrigado. Eu converti o algoritmo para VBA para uso com o Excel e escrevi algumas versões de uma function de planilha, uma para comparação simples de um par de strings, a outra para comparar uma string com um intervalo / array de strings. A versão strSimLookup retorna a última melhor correspondência como string, índice de matriz ou métrica de similaridade.

    Esta implementação produz os mesmos resultados listados no exemplo da Amazon no site do Simon White com algumas pequenas exceções em partidas de baixa pontuação; Não tenho certeza onde a diferença se insere, poderia ser a function Split do VBA, mas eu não investiguei, pois está funcionando bem para os meus propósitos.

     'Implements functions to rate how similar two strings are on 'a scale of 0.0 (completely dissimilar) to 1.0 (exactly similar) 'Source:  http://www.catalysoft.com/articles/StrikeAMatch.html 'Author: Bob Chatham, bob.chatham at gmail.com '9/12/2010 Option Explicit Public Function stringSimilarity(str1 As String, str2 As String) As Variant 'Simple version of the algorithm that computes the similiarity metric 'between two strings. 'NOTE: This verision is not efficient to use if you're comparing one string 'with a range of other values as it will needlessly calculate the pairs for the 'first string 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 stringSimilarity = SimilarityMetric(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 string similarity indexes for str1 vs every string 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) = SimilarityMetric(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 strings in rRng) ' returnType = 0 or omitted: returns the best matching string ' returnType = 1 : returns the index of the best matching string ' returnType = 2 : returns the similarity metric Dim sPairs1 As Collection Dim sPairs2 As Collection Dim metric, bestMetric 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 bestMetric = -1 iBest = -1 For i = 1 To rRng.Count Set sPairs2 = New Collection WordLetterPairs CStr(rRng(i)), sPairs2 metric = SimilarityMetric(sPairs1, sPairs2) If metric > bestMetric Then bestMetric = metric 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 = bestMetric End Select End Function Public Function strSim(str1 As String, str2 As String) As Variant Dim ilen, iLen1, ilen2 As Integer iLen1 = Len(str1) ilen2 = Len(str2) If iLen1 >= ilen2 Then ilen = ilen2 Else ilen = iLen1 strSim = stringSimilarity(Left(str1, ilen), Left(str2, ilen)) End Function Sub WordLetterPairs(str As String, pairColl As Collection) 'Tokenize str into words, then add all letter pairs to pairColl Dim Words() As String 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 SimilarityMetric(sPairs1 As Collection, sPairs2 As Collection) As Variant 'Helper function to calculate similarity metric 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 SimilarityMetric = 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 SimilarityMetric = (2 * Intersect) / Union End Function 

    Desculpe, a resposta não foi inventada pelo autor. Este é um algoritmo bem conhecido que foi apresentado pela primeira vez pela Digital Equipment Corporation e é muitas vezes referido como shingling.

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

    Eu traduzi o algoritmo do Simon White para PL / pgSQL. Esta é minha contribuição.

      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.comparestrings(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'; 

    Uma versão mais rápida do algoritmo no PHP:

     /** * * @param $str * @return mixed */ private static function wordLetterPairs ($str) { $allPairs = array(); // Tokenize the string 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; } 

    Para os dados que eu tinha (aproximadamente 2300 comparações), eu tinha um tempo de execução de 0,58sec com a solução Igal Alkon versus 0,35sec com a minha.

    Uma versão na bela Scala:

      def pairDistance(s1: String, s2: String): Double = { def strToPairs(s: String, acc: List[String]): List[String] = { 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) } 

    As métricas de similaridade de string contêm uma visão geral de muitas métricas diferentes usadas na comparação de strings (a Wikipedia também tem uma visão geral). Muitas dessas métricas são implementadas em uma biblioteca simétrica .

    Ainda outro exemplo de métrica, não incluído na visão geral dada é por exemplo a distância de compression (tentando aproximar a complexidade de Kolmogorov ), que pode ser usada para textos um pouco mais longos do que o que você apresentou.

    Você também pode considerar um assunto muito mais amplo do Processamento de Linguagem Natural . Esses pacotes R podem ajudar você a começar rapidamente (ou pelo menos dar algumas ideias).

    E uma última edição – pesquise as outras questões sobre este assunto no SO, existem algumas relacionadas.

    Aqui está a versão 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) } 

    Postando a resposta de marzagao em C99, inspirada por esses algoritmos

     double dice_match(const char *string1, const char *string2) { //check fast cases if (((string1 != NULL) && (string1[0] == '\0')) || ((string2 != NULL) && (string2[0] == '\0'))) { return 0; } if (string1 == string2) { return 1; } size_t strlen1 = strlen(string1); size_t strlen2 = strlen(string2); 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); } 

    Alguns testes baseados no artigo original :

     #include  void article_test1() { char *string1 = "FRANCE"; char *string2 = "FRENCH"; printf("====%s====\n", __func__); printf("%2.f%% == 40%%\n", dice_match(string1, string2) * 100); } void article_test2() { printf("====%s====\n", __func__); char *string = "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; } 

    Com base na versão c # impressionante de Michael La Voie, conforme o pedido para torná-lo um método de extensão, aqui está o que eu criei. O principal benefício de fazer isso dessa maneira é que você pode classificar uma Lista Genérica pela correspondência percentual. Por exemplo, considere que você tem um campo de string chamado “City” em seu object. Um usuário procura por “Chester” e você deseja retornar resultados em ordem decrescente de correspondência. Por exemplo, você quer que as correspondências literais de Chester apareçam antes de Rochester. Para fazer isso, adicione duas novas propriedades ao seu object:

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

    Em seguida, em cada object, defina o SearchText para o que o usuário pesquisou. Então você pode classificá-lo facilmente com algo como:

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

    Aqui está a pequena modificação para torná-lo um método de extensão:

      ///  /// This class implements string comparison algorithm /// based on character pair similarity /// Source: http://www.catalysoft.com/articles/StrikeAMatch.html ///  public static double PercentMatchTo(this string str1, string 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 string ///  ///  ///  private static List WordLetterPairs(string str) { List AllPairs = new List(); // Tokenize the string and put the tokens/words into an array string[] 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 string ///  ///  ///  private static string[] LetterPairs(string str) { int numPairs = str.Length - 1; string[] pairs = new string[numPairs]; for (int i = 0; i < numPairs; i++) { pairs[i] = str.Substring(i, 2); } return pairs; } 

    Minha implementação JavaScript usa uma string ou uma matriz de strings e um floor opcional (o andar padrão é 0.5). Se você passar uma string para ela, ela retornará true ou false, dependendo se a pontuação de similaridade da string for maior ou igual ao floor. Se você passar um array de strings, ele retornará uma matriz dessas strings cuja pontuação de similaridade é maior ou igual ao floor, classificada por score.

    Exemplos:

     '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"] 

    Aqui está:

     (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 && strings.length > 1 && similarity(pairs1, pairs(strings)) >= floor || str1.toLowerCase() == strings.toLowerCase(); }else if(strings instanceof Array){ var scolors = {}; strings.map(function(str2){ scolors[str2] = str1.length > 1 ? similarity(pairs1, pairs(str2)) : 1*(str1.toLowerCase() == str2.toLowerCase()); }); return strings.filter(function(str){ return scolors[str] >= floor; }).sort(function(a, b){ return scolors[b] - scolors[a]; }); } }; })(); 

    E aqui está uma versão reduzida para sua conveniência:

     (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]})}}})(); 

    O algoritmo do coeficiente de dados (resposta de Simon White / marzagao) é implementado em Ruby no método pair_distance_similar na gem do amatch

    https://github.com/flori/amatch

    Esta gem também contém implementações de um número aproximado de algoritmos de comparação e string: Levenshtein edita a distância, Sellers edita a distância, a distância de Hamming, a maior extensão de subsequência comum, o maior comprimento de substring comum, a métrica de distância de par, a métrica Jaro-Winkler .

    Uma versão do Haskell – sinta-se livre para sugerir edições porque eu não fiz muito Haskell.

     import Data.Char import Data.List -- Convert a string into words, then get the pairs of words from that phrase wordLetterPairs :: String -> [String] wordLetterPairs s1 = concat $ map pairs $ words s1 -- Converts a String into a list of letter pairs. pairs :: String -> [String] pairs [] = [] pairs (x:[]) = [] pairs (x:ys) = [x, head ys]:(pairs ys) -- Calculates the match rating for two strings matchRating :: String -> String -> 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 string-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)) 

    E quanto à distância de Levenshtein, dividida pelo comprimento da primeira string (ou, alternativamente, dividida meu comprimento min / max / avg de ambas as strings)? Isso funcionou para mim até agora.

    Ei pessoal eu tentei isso em javascript, mas eu sou novo nisso, alguém sabe maneiras mais rápidas de fazer isso?

     function get_bigrams(string) { // Takes a string and returns a list of bigrams var s = string.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])); } 

    Aqui está outra versão da similaridade baseada no índice Sørensen – Dice (a resposta de marzagao), esta escrita em C ++ 11:

     /* * Similarity based in Sørensen–Dice index. * * Returns the Similarity between _str1 and _str2. */ double similarity_sorensen_dice(const std::string& _str1, const std::string& _str2) { // Base case: if some string is empty. if (_str1.empty() || _str2.empty()) { return 1.0; } auto str1 = upper_string(_str1); auto str2 = upper_string(_str2); // Base case: if the strings are equals. if (str1 == str2) { return 0.0; } // Base case: if some string 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.