Similarité des cordes - > distance de Levenshtein

je pense que cela peut être facilement résolu en utilisant les Substrat Commun Le Plus Long/Subsequence algorithme sur l'une des chaînes (par exemple "conair") et l'autre chaîne qui s'est ajoutée une seule fois (par exemple "aircon" -> "airconaircon").

exemple de code en C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Returns the length of the longest common substring (LCS)
// between two given strings.
//
// This recursive implementation can be replaced by a
// more performant dynamic programming implementation.
size_t llcs(const char* s1, const char* s2)
{
  size_t len[3];

  if (*s1 == '' || *s2 == '') return 0;

  len[0] = (*s1 == *s2) + llcs(s1 + 1, s2 + 1);
  len[1] = llcs(s1 + 1, s2);
  len[2] = llcs(s1, s2 + 1);

  if (len[0] < len[1]) len[0] = len[1];
  if (len[0] < len[2]) len[0] = len[2];

  return len[0];
}

// Returns similarity of two given strings in the range
// from 0.0 to 1.0 (1.0 for equal strings).
double similarity(const char* s1, const char* s2)
{
  size_t s1len = strlen(s1);
  size_t s2len = strlen(s2);
  double sim;

  if (s1len == 0 && s2len == 0)
  {
    // Two empty strings are equal
    sim = 1;
  }
  else
  {
    size_t len;
    // Append s1 to itself in s1s1 (e.g. "aircon" -> "airconaircon")
    char* s1s1 = malloc(s1len * 2 + 1);
    strcpy(s1s1, s1);
    strcpy(s1s1 + s1len, s1);

    // Find the length of the LCS between s1s1 and s2
    // (e.g. between "airconaircon" and "conair")
    len = llcs(s1s1, s2);
    // We need it not longer than s1 (e.g. "aircon")
    // since we're actually comparing s1 and s2
    if (len > s1len) len = s1len;

    len *= 2;

    // Prevent 100% similarity between a string and its
    // cyclically shifted version (e.g. "aircon" and "conair")
    if (len == s1len + s2len && strcmp(s1, s2) != 0) len--;

    // Get the final measure of the similarity
    sim = (double)len / (s1len + s2len);

    free(s1s1);
  }

  return sim;
}

int main(int argc, char** argv)
{
  if (argc == 3)
    printf("Similarity of \"%s\" and \"%s\" is %.2f%%\n",
           argv[1], argv[2], 100 * similarity(argv[1], argv[2]));
  else
    printf("Usage:\n  %s string1 string2\n",
           argv[0]);
  return 0;
}

sortie de L'échantillon:

Similarity of "123" and "123" is 100.00%
Similarity of "123" and "1234" is 85.71%
Similarity of "0123" and "123" is 85.71%
Similarity of "a" and "aa" is 66.67%
Similarity of "aa" and "a" is 66.67%
Similarity of "aaaaaaa" and "aaaaaa" is 92.31%
Similarity of "aaaaaa" and "aaaaaaa" is 92.31%
Similarity of "aircon" and "conair" is 91.67%
Similarity of "spit" and "pits" is 87.50%
Similarity of "pits" and "spit" is 87.50%
Similarity of "spits" and "pits" is 88.89%
Similarity of "pits" and "spits" is 88.89%

il semble que vous pourriez vouloir essayer de faire la distance Levenshtein en utilisant des syllabes ou des phonèmes au lieu de lettres.

en Théorie, l'approche que vous utilisez est correct pour le problème que vous essayez de résoudre. Mais Levenstein ne considérerait que les caractères individuels des deux ensembles.

la similarité de la chaîne peut aussi être trouvée en utilisant La Plus Longue Sous-Suite Commune méthode et ensuite vous pouvez voir Levenstein sur le reste de l'incomparable.

Dans le cas où vous voulez faire une approche en cluster, la réponse suivante semble avoir quelques détails, mais évidemment il est plus difficile à mettre en œuvre.

trier les mots et trouver Levenshtein donnerait une correspondance de 100% pour votre exemple mais cela donnerait aussi une correspondance de 100% pour, par exemple

CONAIR
RCIAON

ce qui n'est peut-être pas ce que vous voulez.

l'autre façon de définir la similarité serait de trouver des substrats communs pour 2 chaînes. Vous pouvez créer un Suffix Tree et trouver tous les substrats communs et essayer de déterminer comment ils sont similaires. Donc pour votre exemple l'arbre de suffixe donnerait des substrats communs comme CON & AIR qui couvre le mot entier (pour vos 2 cordes) et les conclut ainsi comme similaires.

essayez d'utiliser d'autres mesures de similarité comme sorenson,jaccard et jaro_winkler

personnellement je suis un grand fan de jaro winkler car il a servi mon but de nombreuses fois.

from Levenshtein import jaro_winkler
In [2]: jaro_winkler("conair","aircon")
Out[2]: 0.8333333333333334

jetez un coup d'oeil aux algorithmes Needleman-Wunsch ou Smith-Waterman. Ils sont utilisés pour gérer l'appariement des chaînes de caractères par le biais d'une distance d'édition adaptée pour les séquences D'ADN, où toute sorte d'insertions, d'inversions, de transposons peuvent se produire, à n'importe quelle longueur, à n'importe quel endroit. Ceci dit, je dois ajouter que pour une corde suffisamment longue il n'y a pas de solution optimale. Et n'oubliez pas que le coût d'édition dépend du contexte d'utilisation de l'algorithme (un problème de sémantique), alors que tout algorithme est toujours syntaxique. machine.