Comparaison ultra rapide floue de deux chaines / phrases

Une petite étude sans prétention: Une méthode de comparaison ultra rapide et floue de deux chaines.

Les fonctions de la bibliothèque string.h : strcmp(s1,s2) et strncmp(s1,s2) permettent de comparer facilement deux chaines de caractères. L'inconvénient de strcmp() est d'être couteuse en temps de calcul, surtout si on ne cherche qu'à détecter une égalité ou non-égalité.  En outre strcmp n'est fait une comparaison "floue" de deux chaines.

L'utilisation de la distance de Levenshtein permet une comparaison floue de deux chaines, mais au prix d'un temps de calcul important ( 0(m.n) ).

La solution que j'ai expérimenté dans texlexan est de convertir les deux chaines de caractères (en fait deux phrases que je veux comparer) en une valeur entière codée sur 32 bits.  La méthode n'a rien d'originale puisque ce n'est que le principe d'une fonction de hachage. La seule différence avec la majorité des fonctions de hachage est que j'ai essayé d'extraire les informations caractériques de la phrases pour obtenir une valeur numérique.

La méthode retenue:

- Compter le nombre de mots dans la phrase.

- Compter le nombre de syllabes.

- Compter le nombre de certaines lettres.

- Juxtaposer les valeurs sans dépasser 32 bits.

- Le nombre de mots et le nombre de syllabes sont limités à 99.

- 5 lettres différentes sont comptabilisés et chacunes limitées à 9.

Donc la valeur maximal est 999999999   =>   [99][99][9][9][9][9][9]

Les 5 lettres comptabilisées sont: d,g,j,k,r

- J'ai exclu les voyelles car elles changent en fin de mots avec le masculin et le féminin des mots pour certaines langues latines.

- J'ai exclu le s et le x pour ne pas avoir de distinction singulier / pluriel.

- Ensuite dans le but d'avoir une bonne discrimination des phrases qu'elles soient courtes ou longues , j'ai essayé d'avoir un mixte de lettres assez fréquentes et assez rares pour l'anglais et le français. J'ai indiqué ci-dessous les fréquences approximatives des 5 lettres retenues en anglais et en français.

  r (6.5% F / 6% GB)   d (3.7% F / 4.2% GB)  g (0.9% F /  2% GB)   j (0.5% F / 0.15% GB)  k (0.05% F / 0.8% GB)

La méthode bien qu'empirique donne pour l'instant de bons résultats, je l'utilise dans le résumé automatique pour comparer deux phrases consécutives et supprimer la phrase qui est en double. Ce type de répétition arrive de temps en temps dans les pages webs.

Le code que vous trouverez ici: http://sourceforge.net/projects/texlexan/  ( dans utils.c )

int syllablescount(char *strpt, char efinal) {
/*
Count syllable in a word
it is approximate because e accent is simple e
*/
  char ch,prevch;
  int n=0;
  int i=0;
  int j=0;
  if (strpt == '\0') {
    ERRPOS
    fprintf(stderr,"Syllablescount->empty word\n");
    return 0;
  }
  while ((ch=*strpt++) != '\0') {
    if (isalpha(ch)) {
      if (strchr("aeiouy",ch) != NULL) {
        i=1;
        if (i != j) n++;
      }
      else i=0;
      j=i;
      prevch=ch;
    }
  }
  if ((efinal) && (n>1) && ('e'==prevch)) n--;
  return n;
}

int countword(char *s) {
/*count separator/space (continuous separator are counted as one)
nb of word = nb of separator + 1 */
int prev_sep=1; //want the first char not a separator
int cnt_sep=0;

  while (*s != '\0') {
    if (*s == ' ') {
      if (!prev_sep) { //don't count continuous separator
        cnt_sep++;
        prev_sep=1;
      }
    } else prev_sep=0;
    s++;
  }
  if (!prev_sep) cnt_sep++; //count the last word
  return cnt_sep;
}

long int hashsentence(char *s) {
/*
* Return a value enough characterisc of the sentence
* 2000000000
*/
long int v1=0,v2=0,v3=0,v4=0,v5=0,v6=0,v7=0;
  if (*s=='\0') return 0;
  v1=countword(s);
  if (v1>99) { v1=99; fprintf(stderr,"\nhashsentence, v1 err.\n"); }
  v2=syllablescount(s,0);
  if (v2>99) { v2=99; fprintf(stderr,"\nhashsentence, v2 err.\n"); }
  v3=countchar(s,'r');
  if (v3>9) { v3=9; fprintf(stderr,"\nhashsentence, v3 err.\n"); }
  v4=countchar(s,'k');
  if (v4>9) { v4=9; fprintf(stderr,"\nhashsentence, v4 err.\n"); }
  v5=countchar(s,'j');
  if (v5>9) { v5=9; fprintf(stderr,"\nhashsentence, v5 err.\n"); }
  v5=countchar(s,'g');
  if (v6>9) { v5=9; fprintf(stderr,"\nhashsentence, v6 err.\n"); }
  v5=countchar(s,'d');
  if (v7>9) { v5=9; fprintf(stderr,"\nhashsentence, v7 err.\n"); }
  /* |v1 2 digits|v2 2 digits|v3 1 digit|v4 1 digit|v5 1 digit|v6 1 digit|v7 1 digit| */
  return 10*(10*(10*(10*(10*(100*v1+v2)+v3)+v4)+v5)+v6)+v7;
}