Algorithme de recherche de tableaux PHP / mysql

Question

J'aimerais pouvoir utiliser la recherche php dans un tableau (ou mieux encore, une colonne d'une table mysql) pour une chaîne particulière. Cependant, mon objectif est de renvoyer la chaîne trouvée et le nombre de caractères correspondants (dans le bon ordre) ou un autre moyen de voir dans quelle mesure les résultats de la recherche sont raisonnables. Je peux donc utiliser ces informations pour décider si Je veux afficher le premier résultat par défaut ou donner aux utilisateurs les options parmi les premiers. Je sais que je peux faire quelque chose comme

$citysearch = mysql_query("  SELECT city FROM $table WHERE city LIKE '$city' ");

mais je n'arrive pas à trouver un moyen de déterminer sa précision.

L'objectif serait:
a) trouver " Milwaukee " si le terme recherché était " milwakee " ou quelque chose de similaire.
b) si le terme de recherche était "ouest", renvoyer des choses comme "West Bend" et "Westmont".

Quelqu'un connaît-il un bon moyen de le faire?

Answer 1

Plus de recherches m'ont conduit à la distance de Levenshtein, puis à similar_text, ce qui s'est avéré être le meilleur moyen de le faire.

similar_text("input string", "match against this", $pct_accuracy);

compare les chaînes, puis enregistre la précision sous forme de variable. La distance de Levenshtein détermine le nombre de fonctions de suppression, d’insertion ou de remplacement d’un même caractère à effectuer pour passer d’une chaîne à l’autre, en tenant compte du fait que chaque fonction est pondérée différemment (par exemple, il est plus coûteux de remplacer un caractère que pour supprimer un caractère). C'est apparemment plus rapide mais moins précis que similar_text. D'autres articles que j'ai lus ailleurs ont mentionné que pour les chaînes de moins de 10 000 caractères, il n'y a pas de différence fonctionnelle de vitesse.

J'ai fini par utiliser une version modifiée de quelque chose que j'ai trouvé pour que cela fonctionne. Ceci finit par sauvegarder les 3 meilleurs résultats (sauf en cas de correspondance exacte).

$input = 
 Plus de recherches m'ont conduit à la distance de Levenshtein, puis à similar_text, ce qui s'est avéré être le meilleur moyen de le faire. 

similar_text("input string", "match against this", $pct_accuracy);


 compare les chaînes, puis enregistre la précision sous forme de variable. La distance de Levenshtein détermine le nombre de fonctions de suppression, d’insertion ou de remplacement d’un même caractère à effectuer pour passer d’une chaîne à l’autre, en tenant compte du fait que chaque fonction est pondérée différemment (par exemple, il est plus coûteux de remplacer un caractère que pour supprimer un caractère). C'est apparemment plus rapide mais moins précis que similar_text. D'autres articles que j'ai lus ailleurs ont mentionné que pour les chaînes de moins de 10 000 caractères, il n'y a pas de différence fonctionnelle de vitesse. 

 J'ai fini par utiliser une version modifiée de quelque chose que j'ai trouvé pour que cela fonctionne. Ceci finit par sauvegarder les 3 meilleurs résultats (sauf en cas de correspondance exacte). 

<*>POST["searchcity"];
$accuracy = 0;
$runner1acc = 0;
$runner2acc = 0;
while ($cityarr = mysql_fetch_row($allcities)) {
  $cityname = $cityarr[1];
  $cityid = $cityarr[0];
  $city = strtolower($cityname);
  $diff = similar_text($input, $city, $tempacc);

  // check for an exact match
  if ($tempacc == '100') {

    // closest word is this one (exact match)
    $closest = $cityname;
    $closestid = $cityid;
    $accuracy = 100;

    break;
  }

  if ($tempacc >= $accuracy) { // more accurate than current leader
    $runner2 = $runner1;
    $runner2id = $runner1id;
    $runner2acc = $runner1acc;
    $runner1 = $closest;
    $runner1id = $closestid;
    $runner1acc = $accuracy;
    $closest  = $cityname;
    $closestid = $cityid;
    $accuracy = $tempacc;
  }
  if (($tempacc < $accuracy)&&($tempacc >= $runner1acc)) { // new 2nd place
    $runner2 = $runner1;
    $runner2id = $runner1id;
    $runner2acc = $runner1acc;
    $runner1 = $cityname;
    $runner1id = $cityid;
    $runner1acc = $tempacc;
  }
  if (($tempacc < $runner1acc)&&($tempacc >= $runner2acc)) { // new 3rd place
    $runner2 = $cityname;
    $runner2id = $cityid;
    $runner2acc = $tempacc;
  }
}

echo "Input word: $input\n<BR>";
if ($accuracy == 100) {
  echo "Exact match found: $closestid $closest\n";
} elseif ($accuracy > 70) { // for high accuracies, assumes that it's correct
  echo "We think you meant $closestid $closest ($accuracy)\n";
} else {
  echo "Did you mean:<BR>";
  echo "$closestid $closest? ($accuracy)<BR>\n";
  echo "$runner1id $runner1 ($runner1acc)<BR>\n";
  echo "$runner2id $runner2 ($runner2acc)<BR>\n";
}

Answer 2

Vous devriez vérifier la recherche en texte intégral . en MySQL. Consultez également le port Zend du projet Apache Lucene, Zend_Search_Lucene . .

Answer 3

Cela peut être très compliqué, et je ne suis pas personnellement au courant de bonnes bibliothèques tierces bien que je sois sûr qu'elles existent. D’autres pourront peut-être suggérer des solutions en conserve.

J'ai écrit quelque chose de similaire à plusieurs reprises dans le passé. Si vous suivez cette voie, ce n’est probablement pas quelque chose que vous voudriez faire en PHP, car chaque requête impliquerait d’obtenir tous les enregistrements et d’effectuer vos calculs. Cela impliquera presque certainement de créer un ensemble de tables d'index conformes à vos spécifications.

Par exemple, il vous faudrait définir des règles pour imaginer que "Milwaukee" pourrait finir par être orthographié "milwakee". Ma solution à cela était de faire la compression de voyelle et la compression de duplication (pas sûr si ce sont réellement des termes de recherche). Ainsi, milwaukee serait indexé comme suit:

• milwaukee
• m_lw__k __
• m_lw_k _

Lorsque la requête de recherche est entrée pour "milwaukee", je voudrais exécuter le même processus pour la saisie de texte, puis lancer une recherche dans la table d'index pour:

SELECT cityId,
       COUNT(*)
  FROM myCityIndexTable
 WHERE term IN ('milwaukee', 'm_lw__k__', 'm_lw_k_')

Lorsque la requête de recherche est entrée pour "milwakee", je voudrais exécuter le même processus sur la saisie de texte, puis lancer une recherche sur la table d'index pour:

SELECT cityId,
       COUNT(*)
  FROM myCityIndexTable
 WHERE term IN ('milwaukee', 'm_lw_k__', 'm_lw_k_')

Dans le cas de Milwaukee (orthographié correctement), le résultat serait "3". pour le compte.

Dans le cas de Milwakee (orthographié de manière incorrecte), il renverrait "2". pour le compte (car il ne correspondrait pas au modèle m_lw__k __ car il ne comportait qu'une seule voyelle au milieu).

Si vous triez les résultats en fonction du nombre, vous rencontrerez l'une de vos règles, celle de "Milwaukee". finirait par être trié plus haut comme une correspondance possible que "Milwakee".

Si vous voulez construire ce système de manière générique (comme l'indique votre utilisation de $ table dans la requête), vous aurez probablement besoin d'une autre table de mappage quelque part pour mapper vos termes. à la table appropriée.

Je ne dis pas que c'est la meilleure (ou même une bonne) façon de procéder, mais une chose que j'ai faite dans le passé et qui pourrait vous être utile si vous prévoyez d'essayer de le faire sans tiers. solution de parti.

Answer 4

Le résultat le plus accablant avec LIKE est celui-ci "% man". cela retournera toutes les femmes dans le fichier! Dans le cas d'une inscription, une solution pas trop mauvaise consiste peut-être à continuer à raccourcir l'aiguille de recherche. Dans votre cas, une correspondance sera trouvée lorsque votre recherche $ sera aussi courte que "milwa".