Comment trouver des résultats similaires et sortinger par similarité?

Comment puis-je interroger des enregistrements classés par similarité?

Par exemple. la recherche de “Stock Overflow” reviendrait

  1. Débordement de stack
  2. Dépassement de SharePoint
  3. Débordement mathématique
  4. Débordement politique
  5. VFX Overflow

Par exemple. la recherche de “LO” reviendrait:

  1. Pablo Picasso
  2. MichelangeLO
  3. jackson polLOck

Ce dont j’ai besoin d’aide avec:

  1. Utiliser un moteur de recherche pour indexer et rechercher une table MySQL, pour de meilleurs résultats

    • Utilisation du moteur de recherche Sphinx , avec PHP

    • Utiliser le moteur Lucene avec PHP

  2. Utilisation de l’indexation de texte intégral pour rechercher des chaînes similaires / contenant


Ce qui ne fonctionne pas bien

  • La distance de Levenshtein est très irrégulière. ( UDF , Requête )
    La recherche de “chien” me donne:
    1. chien
    2. tourbière
    3. depuis
    4. gros
    5. écho
  • LIKE renvoie de meilleurs résultats, mais ne retourne rien pour les requêtes longues, bien qu’il existe des chaînes similaires
    1. chien
    2. dogid
    3. dogaral
    4. dogme

J’ai découvert que la distance Levenshtein peut être bonne lorsque vous recherchez une chaîne complète sur une autre chaîne complète, mais lorsque vous recherchez des mots-clés dans une chaîne, cette méthode ne renvoie pas (parfois) les résultats souhaités. De plus, la fonction SOUNDEX ne convient pas aux langues autres que l’anglais, elle est donc assez limitée. Vous pouvez vous en tirer avec LIKE, mais c’est vraiment pour les recherches de base. Vous voudrez peut-être examiner d’autres méthodes de recherche pour déterminer ce que vous voulez réaliser. Par exemple:

Vous pouvez utiliser Lucene comme base de recherche pour vos projets. Il est implémenté dans la plupart des grands langages de programmation et il serait assez rapide et polyvalent. Cette méthode est probablement la meilleure car elle recherche non seulement des sous-chaînes, mais également la transposition de lettres, les préfixes et les suffixes (tous combinés). Cependant, vous devez conserver un index distinct (en utilisant CRON pour le mettre à jour à partir d’un script indépendant, mais de temps en temps).

Ou, si vous voulez une solution MySQL, la fonctionnalité fulltext est plutôt bonne et certainement plus rapide qu’une procédure stockée. Si vos tables ne sont pas MyISAM, vous pouvez créer une table temporaire, puis effectuer votre recherche de texte intégral:

 CREATE TABLE IF NOT EXISTS `tests`.`data_table` ( `id` int(10) unsigned NOT NULL AUTO_INCREMENT, `title` varchar(2000) CHARACTER SET latin1 NOT NULL, `description` text CHARACTER SET latin1 NOT NULL, PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin AUTO_INCREMENT=1 ; 

Utilisez un générateur de données pour générer des données aléatoires si vous ne souhaitez pas en créer vous-même …

** NOTE **: le type de colonne doit être latin1_bin pour effectuer une recherche sensible à la casse au lieu de la casse avec latin1 . Pour les chaînes Unicode, je recommanderais utf8_bin pour sensible à la casse et utf8_general_ci pour les recherches insensibles à la casse.

 DROP TABLE IF EXISTS `tests`.`data_table_temp`; CREATE TEMPORARY TABLE `tests`.`data_table_temp` SELECT * FROM `tests`.`data_table`; ALTER TABLE `tests`.`data_table_temp` ENGINE = MYISAM; ALTER TABLE `tests`.`data_table_temp` ADD FULLTEXT `FTK_title_description` ( `title` , `description` ); SELECT *, MATCH (`title`,`description`) AGAINST ('+so* +nullam lorem' IN BOOLEAN MODE) as `score` FROM `tests`.`data_table_temp` WHERE MATCH (`title`,`description`) AGAINST ('+so* +nullam lorem' IN BOOLEAN MODE) ORDER BY `score` DESC; DROP TABLE `tests`.`data_table_temp`; 

En savoir plus à partir de la page de référence de l’API MySQL

L’inconvénient de ceci est qu’il ne cherchera pas la transposition de lettre ou les mots “semblables, sonne comme”.

** MISE À JOUR **

En utilisant Lucene pour votre recherche, vous devrez simplement créer un travail cron (tous les hôtes Web ont cette “fonctionnalité”) où ce travail exécutera simplement un script PHP (ig “cd / path / to / script; php searchindexer.php”). ) qui mettra à jour les index. La raison en est que l’indexation de milliers de «documents» (lignes, données, etc.) peut prendre plusieurs secondes, voire des minutes, mais cela permet de s’assurer que toutes les recherches sont effectuées le plus rapidement possible. Par conséquent, vous souhaiterez peut-être créer un travail de délai à exécuter par le serveur. Il se peut que ce soit la nuit ou dans l’heure suivante, cela dépend de vous. Le script PHP devrait ressembler à ceci:

 $indexer = Zend_Search_Lucene::create('/path/to/lucene/data'); Zend_Search_Lucene_Analysis_Analyzer::setDefault( // change this option for your need new Zend_Search_Lucene_Analysis_Analyzer_Common_Utf8Num_CaseInsensitive() ); $rowSet = getDataRowSet(); // perform your SQL query to fetch whatever you need to index foreach ($rowSet as $row) { $doc = new Zend_Search_Lucene_Document(); $doc->addField(Zend_Search_Lucene_Field::text('field1', $row->field1, 'utf-8')) ->addField(Zend_Search_Lucene_Field::text('field2', $row->field2, 'utf-8')) ->addField(Zend_Search_Lucene_Field::unIndexed('someValue', $someVariable)) ->addField(Zend_Search_Lucene_Field::unIndexed('someObj', serialize($obj), 'utf-8')) ; $indexer->addDocument($doc); } // ... you can get as many $rowSet as you want and create as many documents // as you wish... each document doesn't necessarily need the same fields... // Lucene is pretty flexible on this $indexer->optimize(); // do this every time you add more data to you indexer... $indexer->commit(); // finalize the process 

Ensuite, il s’agit essentiellement de la recherche (recherche de base):

 $index = Zend_Search_Lucene::open('/path/to/lucene/data'); // same search options Zend_Search_Lucene_Analysis_Analyzer::setDefault( new Zend_Search_Lucene_Analysis_Analyzer_Common_Utf8Num_CaseInsensitive() ); Zend_Search_Lucene_Search_QueryParser::setDefaultEncoding('utf-8'); $query = 'php +field1:foo'; // search for the word 'php' in any field, // +search for 'foo' in field 'field1' $hits = $index->find($query); $numHits = count($hits); foreach ($hits as $hit) { $score = $hit->score; // the hit weight $field1 = $hit->field1; // etc. } 

Voici d’excellents sites sur Lucene en Java , PHP et .Net .

En conclusion, chaque méthode de recherche a ses avantages et ses inconvénients:

  • Vous avez mentionné la recherche Sphinx et elle semble très bonne, à condition que vous puissiez faire fonctionner le démon sur votre hébergeur.
  • Zend Lucene nécessite un travail cron pour réindexer la firebase database. Bien qu’il soit assez transparent pour l’utilisateur, cela signifie que toute nouvelle donnée (ou donnée supprimée!) N’est pas toujours synchronisée avec les données de votre firebase database et ne s’affiche donc pas immédiatement lors de la recherche par l’utilisateur.
  • La recherche MySQL FULLTEXT est rapide et efficace, mais ne vous donnera pas toute la puissance et la flexibilité des deux premiers.

N’hésitez pas à commenter si j’ai oublié / oublié quelque chose.

1. similarité

Pour Levenshtein en MySQL, j’ai trouvé ceci sur http://www.codejanitor.com/wp/2007/02/10/levenshtein-distance-as-a-mysql-stored-function

 SELECT column, LEVENSHTEIN(column, 'search_ssortingng') AS distance FROM table WHERE LEVENSHTEIN(column, 'search_ssortingng') < distance_limit ORDER BY distance DESC 

2. contenant, insensible à la casse

Utilisez l'instruction LIKE de MySQL, qui est insensible à la casse par défaut. Le % est un caractère générique, il peut donc y avoir une chaîne avant et après search_ssortingng .

 SELECT * FROM table WHERE column_name LIKE "%search_ssortingng%" 

3. Contenant, sensible à la casse

Le manuel MySQL aide à:

Le jeu de caractères et le classement par défaut étant latin1 et latin1_swedish_ci, les comparaisons de chaînes non binarys sont insensibles à la casse par défaut. Cela signifie que si vous effectuez une recherche avec col_name LIKE 'a%', vous obtenez toutes les valeurs de colonne commençant par A ou a. Pour rendre cette recherche sensible à la casse, assurez-vous que l'un des opérandes a un classement sensible à la casse ou binary. Par exemple, si vous comparez une colonne et une chaîne ayant toutes les deux le jeu de caractères latin1, vous pouvez utiliser l'opérateur COLLATE pour que l'un des opérandes ait le classement latin1_general_cs ou latin1_bin ...

Ma configuration MySQL ne supporte pas latin1_general_cs ou latin1_bin , mais cela a bien fonctionné pour moi d'utiliser la collation utf8_bin car binary utf8 est sensible à la casse:

 SELECT * FROM table WHERE column_name LIKE "%search_ssortingng%" COLLATE utf8_bin 

2. / 3. sortingés par Levenshtein Distance

 SELECT column, LEVENSHTEIN(column, 'search_ssortingng') AS distance // for sorting FROM table WHERE column_name LIKE "%search_ssortingng%" COLLATE utf8_bin // for case sensitivity, just leave out for CI ORDER BY distance DESC 

Il semble que votre définition de la similarité soit la similarité sémantique. Donc, pour construire une telle fonction de similarité, vous devez utiliser des mesures de similarité sémantique. Notez que la scope du travail sur le problème peut varier de quelques heures à plusieurs années, il est donc recommandé de décider de la scope avant d’entrer dans le travail. Je n’ai pas compris quelles données vous avez pour construire la relation de similarité. Je suppose que vous avez access à un dataset et à un dataset. Vous pouvez commencer par la cooccurrence des mots (par exemple, la probabilité conditionnelle). Vous découvrirez rapidement que la liste des mots vides est la plus associée aux mots simplement parce qu’ils sont très populaires. L’utilisation de la probabilité conditionnelle prendra en compte les mots vides mais rendra la relation sujette à des erreurs en petit nombre (la plupart de vos cas). Vous pourriez essayer Jacard mais comme il est symésortingque, il y aura beaucoup de relations qu’il ne trouvera pas. Ensuite, vous pouvez envisager des relations qui apparaissent seulement à courte distance du mot de base. Vous pouvez (et devriez) considérer les relations basées sur des corpus généraux (par exemple, Wikipedia) et spécifiques à l’utilisateur (par exemple, ses emails).

Très bientôt, vous aurez beaucoup de mesures de similitude, lorsque toutes les mesures sont bonnes et ont un avantage sur les autres.

Afin de combiner ces mesures, j’aime réduire le problème en un problème de classification.

Vous devez construire un dataset de paris de mots et les étiqueter comme “est lié”. Pour créer un dataset étiqueté important, vous pouvez:

  • Utilisez des sources de mots apparentés connus (par exemple, les bonnes anciennes catégories Wikipedia) pour les points positifs
  • La plupart des mots non connus ne sont pas liés.

Ensuite, utilisez toutes les mesures que vous avez comme caractéristiques des paires. Maintenant, vous êtes dans le domaine du problème de la classification supervisée. Construisez un classificateur sur le jeu de données, évalué en fonction de vos besoins et obtenez une mesure de similarité adaptée à vos besoins.