Algorithmes pour la chaîne de similitudes (mieux que Levenshtein, et similar_text)? Php, Js

Où puis-je trouver les algorithmes que les valeurs de l'orthographe des égarés personnages avec plus de précision que levenshtein() et php similar_text() méthodes?

Exemple:

similar_text('jonas', 'xxjon', $similar); echo $similar; //returns 60
similar_text('jonas', 'asjon', $similar); echo $similar; //returns 60 <- although more similar!
echo levenshtein('jonas', 'xxjon'); //returns 4
echo levenshtein('jonas', 'asjon'); //returns 4  <- although more similar!

/Jonas

Qu'est-levenshtein vous donner pour "nojsa" et "nojxx" par rapport à "jonas"?
Même résultat, 4 et 4
Puis-je vous demander ce que votre objectif final est à la recherche d'un algorithme avec plus raffiné des dégradés? Votre exemple utilise des noms propres. Le réel les données que vous travaillez avec impliquent des noms ou des mots?
Je suis actuellement à la recherche d'un moyen de mesurer les similitudes pédagogique des situations de jeu. Disons que d'un étudiant tâche est de sélectionner des objets à partir d'un bassin, et de mettre ces objets dans un ordre précis (les trier par ordre alphabétique ou autre). J'ai alors besoin d'un moyen de mesurer la similarité entre les élèves d'y répondre et de le corriger...

OriginalL'auteur Cambiata | 2011-03-18

php

Voici une solution que j'ai trouvé. Il est basé sur Tim proposition de la comparaison de l'ordre de la suite des charachters. Quelques résultats:

jonas /jonax : 0.8
jonas /sjona : 0.68
jonas /sjonas : 0.66
jonas /asjon : 0.52
jonas /xxjon : 0.36

Je suis sûr que je n'est pas parfait, et qu'il pourrait être optimisé, mais néanmoins, il semble produire les résultats que je suis après...
Un point faible est que lorsque les cordes sont de longueur différente, il produit des résultats différents lorsque les valeurs sont inversés...

static public function string_compare($str_a, $str_b) 
{
    $length = strlen($str_a);
    $length_b = strlen($str_b);

    $i = 0;
    $segmentcount = 0;
    $segmentsinfo = array();
    $segment = '';
    while ($i < $length) 
    {
        $char = substr($str_a, $i, 1);
        if (strpos($str_b, $char) !== FALSE) 
        {               
            $segment = $segment.$char;
            if (strpos($str_b, $segment) !== FALSE) 
            {
                $segmentpos_a = $i - strlen($segment) + 1;
                $segmentpos_b = strpos($str_b, $segment);
                $positiondiff = abs($segmentpos_a - $segmentpos_b);
                $posfactor = ($length - $positiondiff) / $length_b; //<-- ?
                $lengthfactor = strlen($segment)/$length;
                $segmentsinfo[$segmentcount] = array( 'segment' => $segment, 'score' => ($posfactor * $lengthfactor));
            } 
            else 
            {
                $segment = '';
                $i--;
                $segmentcount++;
            } 
        } 
        else 
        {
            $segment = '';
            $segmentcount++;
        }
        $i++;
    }   

    //PHP 5.3 lambda in array_map      
    $totalscore = array_sum(array_map(function($v) { return $v['score'];  }, $segmentsinfo));
    return $totalscore;     
}

pouvez-vous expliquer la logique interne de votre fonction? Surtout, je ne comprends pas $segmentInfo['segment'] - est-il juste pour un débogage?

OriginalL'auteur Cambiata

5

S'il vous plaît, soyez prudent sur l'utilisation de string_compare :

ivanov ivan /ivanov ivan : 1 OK!

ivanov ivan2 /ivanov ivan : 1 o_O

ivanov ivan /ivanov i : 1.1363636363636 OMG!

OriginalL'auteur Solo.dmitry
4

En plus de levenshtein() et similar_text(), il y a aussi:

soundex(): Renvoie les quatre caractères soundex de la clé d'un mot, qui doit être la même que la clé de toute son similaire mot.

metaphone(): Similaire à soundex, et peut-être plus efficace pour vous. C'est plus précis que soundex() qu'il connaît les règles de base de la prononciation anglaise. Le metaphone clés générées sont de longueur variable.

Merci, Mark! Hmm... Ils sont tous les deux algorightms pour le calcul de similarités dans son, qui pourrait induire en erreur dans mon cas ne l'ai pas testé, mais il peut conduire à un résultat où, par exemple "chou" pourrait être assez proche de "montrer", alors que le personnage de contenu est très différent.

OriginalL'auteur Mark Baker
1

@Tim: je suis actuellement à la recherche d'un moyen
de mesure de similarités dans un
pédagogique des situations de jeu. Disons
qu'un élève de la tâche consiste à sélectionner
les objets d'une piscine, et de mettre ces
les objets dans un ordre précis (les trier
par alphabet ou quoi que ce soit). J'ai donc besoin
une façon de mesurer la similarité
entre les étudiants de répondre et de la
bon

Algorithmes pour calculer le degré d'exactitude de l'ordre des caractères dans un mot (c'est à dire son orthographe) pourrait être très différent d'un algorithme de mesure de l'ordre correct des mots dans une liste. La façon dont l'orthographe des algorithmes de gérer des omissions ou des dittography ou des transpositions peuvent ne pas s'appliquer très bien à votre cas d'utilisation.

Si vous connaissez l'ordre des éléments à l'avance, et de connaître le nombre d'éléments de trop, alors vous pouvez simplement faire une boucle par la réponse et de comparer la valeur à la position de corriger la valeur à la position et à en arriver à un pourcentage correct. Pourtant, ce serait une mesure brute, et induire en erreur, car si le but du jeu était de tester si le joueur a compris tri alphabétique, et le joueur qui s'est passé pour obtenir le premier mot mal, chaque mot peut être dans la mauvaise position, même si les mots étaient sinon corriger l'ordre alphabétique:
```
      banana
      blackberry
      blueberry
      cherry
      fig
      grapefruit
      orange
      pear
      persimmon
      raspberry
      apple
```
Donc ce que vous pourriez faire pour améliorer la précision de votre mesure dans notre situation hypothétique est-ce: en boucle par le gamer de la réponse de la liste de recherche pour voir si la valeur de la réponse est immédiatement suivi par le mot correct; à chaque fois qu'un mot est suivi par le mot correct, vous devez donner au joueur un point. Le joueur qui a produit la liste ci-dessus, serait d'obtenir 9 points sur 10 possibles et que le score serait en effet refléter avec précision le joueur à comprendre les règles de tri alphabétique.

OriginalL'auteur Tim

J'ai trouvé que Jaro-Winkler est également bon pour les fautes d'orthographe et de petites différences entre les chaînes. J'ai modifié ce code être orienté-objet:

class StringCompareJaroWinkler 
{
public function compare($str1, $str2)
{
return $this->JaroWinkler($str1, $str2, $PREFIXSCALE = 0.1 );
}
private function getCommonCharacters( $string1, $string2, $allowedDistance ){
$str1_len = mb_strlen($string1);
$str2_len = mb_strlen($string2);
$temp_string2 = $string2;
$commonCharacters='';
for( $i=0; $i < $str1_len; $i++){
$noMatch = True;
//compare if char does match inside given allowedDistance
//and if it does add it to commonCharacters
for( $j= max( 0, $i-$allowedDistance ); $noMatch && $j < min( $i + $allowedDistance + 1, $str2_len ); $j++){
if( $temp_string2[$j] == $string1[$i] ){
$noMatch = False;
$commonCharacters .= $string1[$i];
$temp_string2[$j] = '';
}
}
}
return $commonCharacters;
}
private function Jaro( $string1, $string2 ){
$str1_len = mb_strlen( $string1 );
$str2_len = mb_strlen( $string2 );
//theoretical distance
$distance = (int) floor(min( $str1_len, $str2_len ) / 2.0); 
//get common characters
$commons1 = $this->getCommonCharacters( $string1, $string2, $distance );
$commons2 = $this->getCommonCharacters( $string2, $string1, $distance );
if( ($commons1_len = mb_strlen( $commons1 )) == 0) return 0;
if( ($commons2_len = mb_strlen( $commons2 )) == 0) return 0;
//calculate transpositions
$transpositions = 0;
$upperBound = min( $commons1_len, $commons2_len );
for( $i = 0; $i < $upperBound; $i++){
if( $commons1[$i] != $commons2[$i] ) $transpositions++;
}
$transpositions /= 2.0;
//return the Jaro distance
return ($commons1_len/($str1_len) + $commons2_len/($str2_len) + ($commons1_len - $transpositions)/($commons1_len)) / 3.0;
}
private function getPrefixLength( $string1, $string2, $MINPREFIXLENGTH = 4 ){
$n = min( array( $MINPREFIXLENGTH, mb_strlen($string1), mb_strlen($string2) ) );
for($i = 0; $i < $n; $i++){
if( $string1[$i] != $string2[$i] ){
//return index of first occurrence of different characters 
return $i;
}
}
//first n characters are the same   
return $n;
}
private function JaroWinkler($string1, $string2, $PREFIXSCALE = 0.1 ){
$JaroDistance = $this->Jaro( $string1, $string2 );
$prefixLength = $this->getPrefixLength( $string1, $string2 );
return $JaroDistance + $prefixLength * $PREFIXSCALE * (1.0 - $JaroDistance);
}
}
$jw = new StringCompareJaroWinkler();
echo $jw->compare("jonas","asjon");

OriginalL'auteur joshweir

Vous devez vous connecter pour publier un commentaire.