Comment trouver des résultats similaires et les trier par similarité ?

Question

Comment faire une recherche d'enregistrements classés par similarité ?

Par exemple, la recherche de "Stock Overflow" renverrait aux résultats suivants

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

Par exemple, si vous cherchez "LO", vous obtiendrez des résultats :

1. pabLO picasso
2. michelangeLO
3. jackson pollock

---

Ce pour quoi j'ai besoin d'aide :

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

   • Utilisation de la Sphinx moteur de recherche, avec PHP

   • Utilisation de la Lucene avec PHP

2. Utilisation de l'indexation en texte intégral pour trouver des chaînes similaires/contenantes.

---

Ce qui ne fonctionne pas bien

• distance de Levenshtein est très erratique. ( UDF , Requête )
  La recherche de "chien" me donne :
  1. chien
  2. tourbière
  3. il y a un an
  4. grand
  5. echo
• LIKE renvoie de meilleurs résultats, mais ne renvoie rien pour les longues requêtes bien que des chaînes similaires existent.
  1. chien
  2. dogid
  3. dogaral
  4. dogme

Answer 1

J'ai découvert que la distance de Levenshtein peut être bonne lorsque vous recherchez une chaîne complète par rapport à 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 n'est pas adaptée aux langues autres que l'anglais, elle est donc assez limitée. Vous pourriez vous en sortir avec LIKE, mais c'est vraiment pour les recherches de base. Vous pouvez envisager d'autres méthodes de recherche pour ce que vous voulez obtenir. Par exemple :

Vous pouvez utiliser Lucene comme base de recherche pour vos projets. Elle est mise en œuvre dans la plupart des principaux langages de programmation et elle est assez rapide et polyvalente. Cette méthode est probablement la meilleure, car elle ne recherche pas seulement les sous-chaînes, mais aussi la transposition des lettres, les préfixes et les suffixes (tous combinés). Cependant, vous devez conserver un index séparé (l'utilisation de CRON pour le mettre à jour à partir d'un script indépendant de temps en temps fonctionne cependant).

Ou, si vous voulez une solution MySQL, la fonctionnalité de texte intégral est assez 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 plein texte :

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 voulez pas prendre la peine de les créer vous-même...

** NOTE ** : le type de colonne doit être latin1_bin pour effectuer une recherche sensible à la casse au lieu d'une recherche insensible à la casse avec latin1 . Pour les chaînes unicode, je recommande utf8_bin pour la casse et utf8_general_ci pour les recherches sans distinction de 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`;

Pour en savoir plus, consultez le site Page de référence de l'API MySQL

L'inconvénient de cette méthode est qu'elle ne recherche pas la transposition des lettres ou les mots "similaires, ressemblant à".

** UPDATE **

En utilisant Lucene pour votre recherche, vous devrez simplement créer une tâche cron (tous les hôtes web ont cette "fonctionnalité") où cette tâche exécutera simplement un script PHP (c'est-à-dire "cd /path/to/script ; php searchindexer.php") qui mettra à jour les index. La raison étant que l'indexation de milliers de "documents" (lignes, données, etc.) peut prendre plusieurs secondes, voire des minutes, mais il s'agit de s'assurer que toutes les recherches sont effectuées aussi rapidement que possible. Par conséquent, vous pouvez créer une tâche de retardement qui sera exécutée par le serveur. Cela peut être pendant la nuit, ou dans l'heure qui suit, cela dépend de vous. Le script PHP devrait ressembler à quelque chose comme 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, c'est en gros la façon dont vous effectuez une 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 dans Java , PHP et .Net .

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

• Vous avez mentionné Recherche de Sphynx et ça a l'air très bien, tant que vous pouvez faire fonctionner le deamon sur votre hôte web.
• Zend Lucene nécessite une tâche cron pour réindexer la base de données. Bien que cela 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 base de données et n'apparaîtra donc pas immédiatement lors d'une recherche utilisateur.
• La recherche MySQL FULLTEXT est bonne et rapide, mais ne vous donnera pas toute la puissance et la flexibilité des deux premières.

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

Answer 2

1. Similitude

Pour Levenshtein dans MySQL, j'ai trouvé ceci : Mise en œuvre de SQL Levenshtein . Cela fonctionne bien pour moi !

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

2. Contenant, insensible à la casse

Utilisez le LIKE de MySQL, qui est insensible à la casse par défaut. L'adresse % est un joker, donc n'importe quelle chaîne de caractères peut se trouver avant et après search_string .

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

3. Contenant, sensible à la casse

Le site Manuel MySQL aide :

Le jeu de caractères et la collation par défaut sont latin1 et latin1_swedish_ci, les comparaisons de chaînes non binaires sont donc 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 qui commencent par A ou a. Pour que cette recherche soit sensible à la casse, assurez-vous que l'un des opérandes a une collation sensible à la casse ou binaire. Par exemple, si vous comparez une colonne et une chaîne de caractères qui ont toutes deux le jeu de caractères latin1, vous pouvez utiliser l'opérateur COLLATE pour que l'un des opérandes ait la collation latin1_general_cs ou latin1_bin...

Ma configuration MySQL ne prend pas en charge latin1_general_cs ou latin1_bin mais l'utilisation de la collation fonctionne bien pour moi. utf8_bin car l'utf8 binaire est sensible à la casse :

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

2. / 3. triés par la distance de Levenshtein

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

Answer 3

Il semble que votre définition de la similarité soit la similarité sémantique. Ainsi, pour construire une telle fonction de similarité, vous devez utiliser des mesures de similarité sémantique. Notez que la portée du travail sur la question peut varier de quelques heures à des années, il est donc recommandé de décider de la portée avant de se mettre au travail. Je n'ai pas compris de quelles données vous disposez pour construire la relation de similarité. Je suppose que vous avez accès à un jeu de données de documents et à un jeu de données de requêtes. Vous pouvez commencer par la co-occurrence des mots (par exemple, la probabilité conditionnelle). Vous découvrirez rapidement que vous obtenez la liste de mots vides comme étant liés la plupart des mots simplement parce qu'ils sont très populaires. L'utilisation de l'ascenseur de la probabilité conditionnelle prendra en charge les mots vides mais rendra la relation sujette à erreur dans un petit nombre (la plupart de vos cas). Vous pouvez essayer Jacard mais comme elle est symétrique, il y aura beaucoup de relations qu'elle ne trouvera pas. Vous pouvez alors considérer les relations qui n'apparaissent qu'à une 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 vite, vous disposerez d'une multitude de mesures de similarité, lorsque toutes les mesures seront bonnes et auront un avantage sur les autres.

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

Vous devez construire un ensemble de données de paris de mots et les étiqueter comme "est lié". Pour construire un grand ensemble de données étiquetées, vous pouvez.. :

• Utiliser des sources de mots apparentés connus (par exemple, les bonnes vieilles catégories de Wikipedia) pour les positifs.
• La plupart des mots qui ne sont pas connus comme apparentés ne le sont pas.

Utilisez ensuite toutes les mesures dont vous disposez comme caractéristiques des paires. Vous êtes maintenant dans le domaine des problèmes de classification supervisée. Construisez un classificateur sur l'ensemble des données, évalué selon vos besoins et obtenez une mesure de similarité qui correspond à vos besoins.