Comment fonctionne similar_text?

Question

J'ai juste trouvé la similar_text fonction et a joué avec elle, mais le pourcentage de sortie toujours des surprises moi. Voir les exemples ci-dessous.

J'ai essayé de trouver des informations sur l'algorithme utilisé comme mentionné sur php: similar_text()^Docs:

<?php
$p = 0;
similar_text('aaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>";
//66.666666666667
//Since 5 out of 10 chars match, I would expect a 50% match

similar_text('aaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>";
//40
//5 out of 20 > not 25% ?

similar_text('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>"; 
//9.5238095238095 
//5 out of 100 > not 5% ?


//Example from PHP.net
//Why is turning the strings around changing the result?

similar_text('PHP IS GREAT', 'WITH MYSQL', $p);
echo $p . "<hr>"; //27.272727272727

similar_text('WITH MYSQL', 'PHP IS GREAT', $p);
echo $p . "<hr>"; //18.181818181818

?>

Quelqu'un peut-il expliquer comment cela fonctionne réellement?

Mise à jour:

Merci pour les commentaires, j'ai trouvé que le pourcentage est en fait calculé en utilisant le nombre de semblable charactors * 200 / length1 + longueur 2

Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);

Cela explique pourquoi la percenatges sont plus élevés que prévu. Avec une chaîne avec 5 de 95, il s'avère 10, de sorte que je peux utiliser.

similar_text('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>"; 
//10
//5 out of 95 = 5 * 200 / (5 + 95) = 10

Mais je ne peux pas comprendre pourquoi le PHP renvoie un résultat différent en tournant les cordes autour de. Le code JS fournis par dfsq ne pas le faire. En regardant le code source en PHP je ne peux que trouver une différence dans la ligne suivante, mais je ne suis pas un programmeur c. Un aperçu de ce qu'est la différence, serait appréciée.

En JS:

for (l = 0;(p + l < firstLength) && (q + l < secondLength) && (first.charAt(p + l) === second.charAt(q + l)); l++);

En PHP: (php_similar_str fonction)

for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);

Source:

/* {{{ proto int similar_text(string str1, string str2 [, float percent])
   Calculates the similarity between two strings */
PHP_FUNCTION(similar_text)
{
  char *t1, *t2;
  zval **percent = NULL;
  int ac = ZEND_NUM_ARGS();
  int sim;
  int t1_len, t2_len;

  if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|Z", &t1, &t1_len, &t2, &t2_len, &percent) == FAILURE) {
    return;
  }

  if (ac > 2) {
    convert_to_double_ex(percent);
  }

  if (t1_len + t2_len == 0) {
    if (ac > 2) {
      Z_DVAL_PP(percent) = 0;
    }

    RETURN_LONG(0);
  }

  sim = php_similar_char(t1, t1_len, t2, t2_len);

  if (ac > 2) {
    Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
  }

  RETURN_LONG(sim);
}
/* }}} */ 


/* {{{ php_similar_str
 */
static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
  char *p, *q;
  char *end1 = (char *) txt1 + len1;
  char *end2 = (char *) txt2 + len2;
  int l;

  *max = 0;
  for (p = (char *) txt1; p < end1; p++) {
    for (q = (char *) txt2; q < end2; q++) {
      for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
      if (l > *max) {
        *max = l;
        *pos1 = p - txt1;
        *pos2 = q - txt2;
      }
    }
  }
}
/* }}} */


/* {{{ php_similar_char
 */
static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
{
  int sum;
  int pos1, pos2, max;

  php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);

  if ((sum = max)) {
    if (pos1 && pos2) {
      sum += php_similar_char(txt1, pos1,
                  txt2, pos2);
    }
    if ((pos1 + max < len1) && (pos2 + max < len2)) {
      sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
                  txt2 + pos2 + max, len2 - pos2 - max);
    }
  }

  return sum;
}
/* }}} */

Source en Javascript: texte similaire port de javascript

Answer 1

En fait, c'était une question très intéressante, merci de me donner un puzzle qui s'est avéré être très enrichissante.

Permettez-moi de commencer par vous expliquer comment similar_text fonctionne réellement.

---

Texte Similaire: L'Algorithme

C'est une récursivité en fonction de division et de conquête de l'algorithme. Il fonctionne par trouver la plus longue de la commune de chaîne entre les deux entrées et de rompre le problème en sous-ensembles autour de cette chaîne.

Les exemples que vous avez utilisé dans votre question, en fait tous d'effectuer une seule itération de l'algorithme. Les seuls à ne pas en utilisant une itération et ceux donnant des résultats différents sont à partir de la php.net commentaires.

Voici un exemple simple pour comprendre le problème principal derrière simple_text et nous espérons donner un aperçu de la façon dont il fonctionne.

---

Texte Similaire: La Faille

eeeefaaaaafddddd
ddddgaaaaagbeeee

Iteration 1:
Max    = 5
String = aaaaa
Left : eeeef and ddddg
Right: fddddd and geeeee

J'espère que la faille est déjà apparent. Il ne fera que vérifier directement vers la gauche et vers la droite de la plus longue chaîne trouvée dans les deux chaînes d'entrée. Cet exemple

$s1='eeeefaaaaafddddd';
$s2='ddddgaaaaagbeeee';

echo similar_text($s1, $s2).'|'.similar_text($s2, $s1);
// outputs 5|5, this is due to Iteration 2 of the algorithm
// it will fail to find a matching string in both left and right subsets

Pour être honnête, je suis pas sûr de savoir comment cette affaire devrait être traitée. Il peut être vu que seulement 2 caractères sont différents dans la chaîne. Mais les deux eeee et dddd sont sur les extrémités opposées des deux chaînes, incertain de ce que la PNL amateurs ou autre littéraire experts ont à dire à propos de cette situation spécifique.

---

Texte similaire: des résultats contradictoires sur l'argument de permutation

Les différents résultats que vous étiez confrontés basé sur l'entrée de commande est due à la façon dont le alogirthm se comporte effectivement (comme mentionné ci-dessus). Je vais vous donner une dernière explination sur ce qui se passe.

echo similar_text('test','wert'); // 1
echo similar_text('wert','test'); // 2

Sur le premier cas, il n'y a qu'une seule Itération:

test
wert

Iteration 1:
Max    = 1
String = t
Left :  and wer
Right: est and 

Nous n'avons qu'une seule itération, car vide/null chaînes de retourner la valeur 0 sur la récursivité. Alors, ceci termine l'algorithme et nous avons notre résultat: 1

Sur le deuxième cas, cependant, nous sommes confrontés à de multiples Itérations:

wert
test

Iteration 1:
Max    = 1
String = e
Left : w and t
Right: rt and st

Nous avons déjà une commune de chaîne de longueur 1. L'algorithme sur la gauche sous-ensemble prendra fin en 0 matches, mais sur la droite:

rt
st

Iteration 1:
Max    = 1
String = t
Left : r and s
Right:  and 

Cela conduira à notre nouveau et résultat final: 2

Je vous remercie pour ce très instructif question et la possibilité de se mêler en C++ de nouveau.

---

Texte Similaire: JavaScript Édition

La réponse courte est: Le code javascript n'est pas la mise en œuvre de l'algorithme correct

sum += this.similar_text(first.substr(0, pos2), second.substr(0, pos2));

Évidemment, il doit être first.substr(0,pos1)

Remarque: Le code JavaScript a été fixé par sie dans une précédente livraison. Merci @eie

Démystifiée!

Answer 2

En effet, il semblerait que la fonction utilise une logique différente en fonction du paramètre d'ordre. Je pense qu'il y a deux choses à jouer.

Tout d'abord, voir cet exemple:

echo similar_text('test','wert'); // 1
echo similar_text('wert','test'); // 2

Il me semble que c'est un test "combien de fois distincts char sur param1 est trouvé dans param2", et donc le résultat serait différent si vous permutez les params autour. Il a été rapporté comme un bug, qui n'a pas été confirmée par n'importe qui.

Maintenant, le ci-dessus est le même pour les deux PHP et le javascript les implémentations - paremeter commande a un impact, donc en disant que le code JS ne le ferais pas, c'est faux. Je pense qu'il est possible d'argumenter que, comme prévu comportement. Vous ne savez pas si il est.

Seconde - ce qui ne semble pas correcte est MYSQL/PHP word exemple. Avec qui, javascript version 3 de pertinence de l'ordre de paramètres, alors que PHP donne 2 et 3 (et de ce fait, le pourcentage est également différent). Maintenant, les expressions "PHP EST GRAND" et "MYSQL" devrait avoir 5 personnages en commun, indépendamment de la façon dont vous comparer: H, I, S et T, une de chaque, plus un pour l'espace vide. Dans l'ordre, ils ont 3 caractères, 'H', '' et 'S', donc, si vous regardez les commandes, la bonne réponse devrait être de 3 dans les deux sens. J'ai modifié le code en C pour un exécutable de la version, et ajouté un peu de sortie, on peut donc voir ce qui s'y passe (codepad lien):

#include<stdio.h>

/* {{{ php_similar_str
 */
static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
  char *p, *q;
  char *end1 = (char *) txt1 + len1;
  char *end2 = (char *) txt2 + len2;
  int l;

  *max = 0;
  for (p = (char *) txt1; p < end1; p++) {
    for (q = (char *) txt2; q < end2; q++) {
      for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
      if (l > *max) {
        *max = l;
        *pos1 = p - txt1;
        *pos2 = q - txt2;
      }
    }
  }
}
/* }}} */


/* {{{ php_similar_char
 */
static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
{
  int sum;
  int pos1, pos2, max;

  php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);

  if ((sum = max)) {
    if (pos1 && pos2) {
      printf("txt here %s,%s\n", txt1, txt2);
      sum += php_similar_char(txt1, pos1,
                  txt2, pos2);
    }
    if ((pos1 + max < len1) && (pos2 + max < len2)) {
      printf("txt here %s,%s\n", txt1+ pos1 + max, txt2+ pos2 + max);
      sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
                  txt2 + pos2 + max, len2 - pos2 - max);
    }
  }

  return sum;
}
/* }}} */
int main(void)
{
    printf("Found %d similar chars\n",
        php_similar_char("PHP IS GREAT", 12, "WITH MYSQL", 10));
    printf("Found %d similar chars\n",
        php_similar_char("WITH MYSQL", 10,"PHP IS GREAT", 12));
    return 0;
}

le résultat est sortie:

txt here PHP IS GREAT,WITH MYSQL
txt here P IS GREAT, MYSQL
txt here IS GREAT,MYSQL
txt here IS GREAT,MYSQL
txt here  GREAT,QL
Found 3 similar chars
txt here WITH MYSQL,PHP IS GREAT
txt here TH MYSQL,S GREAT
Found 2 similar chars

Donc, on peut voir que sur la première comparaison, la fonction 'H', '' et 'S', mais pas 'T', et a obtenu le résultat de 3. La deuxième comparaison a trouvé " I " et "T", mais pas de 'H', '' ou 'S', et donc obtenu le résultat de 2.

La raison de ces résultats peut être vu à partir de la sortie: algorithme prend la première lettre de la première chaîne de la deuxième chaîne contient, comtes, et jette les chars avant qu'à partir de la deuxième chaîne. C'est pourquoi il manque les personnages dans un entre-deux, et c'est la chose à l'origine de la différence lorsque vous modifiez l'ordre des caractères.

Ce qui s'y passe peut être intentionnelle ou non. Cependant, ce n'est pas comment la version javascript fonctionne. Si vous imprimez les mêmes choses dans la version javascript, vous obtenez ceci:

txt here: PHP, WIT
txt here: P IS GREAT,  MYSQL
txt here: IS GREAT, MYSQL
txt here: IS, MY
txt here:  GREAT, QL
Found 3 similar chars
txt here: WITH, PHP 
txt here: W, P
txt here: TH MYSQL, S GREAT
Found 3 similar chars

montrant que la version javascript t-il d'une manière différente. Ce que la version javascript n'est qu'il trouve 'H', '' et 'S' étant dans le même ordre dans la première comparaison, et même 'H', '' et 'S' est également sur le second - dans ce cas, l'ordre des paramètres n'a pas d'importance.

Je dirais que la version javascript est plus bonne façon de le faire, mais c'est pour la spéculation. En tout cas, comme le javascript est destinée à dupliquer le code de la fonction PHP, il doit se comporter de manière identique, c'est pourquoi j'ai soumis de rapport de bug sur la base d'analyse de @Khez et le correctif. Bravo il.

Answer 3

first String = aaaaaaaaaa = 10 letters
second String = aaaaa = 5 letters

first five letters are similar
a+a
a+a
a+a
a+a
a+a
a
a
a
a
a


( <similar_letters> * 200 ) / (<letter_count_first_string> + <letter_count_second_string>)

( 5 * 200 ) / (10 + 5);
= 66.6666666667

Answer 4

Description int similar_text ( string $premier , $string deuxième [, float &$pour cent ] )

Permet de calculer la similarité entre deux chaînes de caractères, comme décrit dans Oliver [1993]. Notez que cette mise en oeuvre ne pas utiliser une pile à Oliver de pseudo-code, mais les appels récursifs qui peut ou peut ne pas accélérer l'ensemble du processus. Notez également que la complexité de cet algorithme est O(N**3) où N est la longueur de la chaîne la plus longue. Paramètres

première

The first string.

deuxième

The second string.

pour cent

By passing a reference as third argument, similar_text() will calculate the similarity in percent for you.