Fuzzy search
muqaddar
Administrateur
Salut,
Dans mon appli web, j'utilise un plugin terrible qui compare des chaà®nes à l'aide de "trigrams". Par exemple, si l'utilisateur tape "ustraallia", il va être capable de me retrouver les enregistrements correspondants au maximum à la chaà®ne, et de les classer par ordre de pertinence, ce qui donnerait pour ce cas : "Australia", "Austria"...etc. Et donc de prendre la première occurrence.
C'est assez magique je dois dire.
Auparavant, il a découpé les enregistrements à comparer dans une autre table. Par exemple: "Australia" est découpée en "Au", "ust", "tra", "ali", "ia"... en gros.
Ensuite, il génère une requête SQL assez complexe lors de la comparaison des chaà®nes, en découpant aussi la chaà®ne à comparer, avec celles pré-découpées dans la base.
Je souhaite faire la même chose en Cocoa et l'interfacer avec SQL.
Je pense être en mesure d'adapter le fonctionnement de ce plugin pour cocoa (j'ai déjà tes tables contenant les trigrams, il me resterait à générer la grosse requête et découper la chaà®ne à comparer intelligemment).
Simplement, j'aimerais savoir si il existe d'autres solutions en Cocoa. Je n'ai pas trouvé grand chose sur le web. Apparemment il y a des choses similaires sur Mac OS X (fonction de recherche), mais pas iOS. Je veux que ça marche sur les 2 plateformes.
Dans mon appli web, j'utilise un plugin terrible qui compare des chaà®nes à l'aide de "trigrams". Par exemple, si l'utilisateur tape "ustraallia", il va être capable de me retrouver les enregistrements correspondants au maximum à la chaà®ne, et de les classer par ordre de pertinence, ce qui donnerait pour ce cas : "Australia", "Austria"...etc. Et donc de prendre la première occurrence.
C'est assez magique je dois dire.
Auparavant, il a découpé les enregistrements à comparer dans une autre table. Par exemple: "Australia" est découpée en "Au", "ust", "tra", "ali", "ia"... en gros.
Ensuite, il génère une requête SQL assez complexe lors de la comparaison des chaà®nes, en découpant aussi la chaà®ne à comparer, avec celles pré-découpées dans la base.
Je souhaite faire la même chose en Cocoa et l'interfacer avec SQL.
Je pense être en mesure d'adapter le fonctionnement de ce plugin pour cocoa (j'ai déjà tes tables contenant les trigrams, il me resterait à générer la grosse requête et découper la chaà®ne à comparer intelligemment).
Simplement, j'aimerais savoir si il existe d'autres solutions en Cocoa. Je n'ai pas trouvé grand chose sur le web. Apparemment il y a des choses similaires sur Mac OS X (fonction de recherche), mais pas iOS. Je veux que ça marche sur les 2 plateformes.
Mots clés:
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ce qui me permettait de calculer pour chaque élément d'un tableau de chaà®ne quelle était la chaà®ne avec la plus petite distance avec celle recherchée, et donc la chaà®ne qui ressemblait le plus au terme recherché.
Donc faire ça en pur Cocoa pour rechercher dans un NSArray c'est assez simple. Par contre, le transposer pour une recherche dans une base SQL, à moins de rajouter dynamiquement une fonction à sqlite3 (il me semble que la lib C le permet ?)...
http://weblog.wanderingmango.com/articles/14/fuzzy-string-matching-and-the-principle-of-pleasant-surprises?commented=0
Par contre c'est moins évolué en terme de finesse.
En adaptant le code pour l'optimiser et donc implémenter l'algo uniquement en C (ce que j'avais fait, de mémoire), perfs bien plus concluantes.
Après, vu que c'est de la Fuzzy Search, c'est forcément un peu moins rapide qu'une recherche "classique", c'est normal, on ne peut pas tout avoir.
Oui, ça se rapproche de ça.
En fait, pour mon cas, avoir déjà les chaà®nes à comparer découpées dans la base est certainement un avantage un terme de performances.
Il faudrait que je teste les 2 solutions, la Cocoa et la SQL.
Je parle de la requête SQL qui compare avec les trigrams déjà pré-découpés.
Donnes le résultat suivant:
Tu noteras que c'est moins évolué que ton système. Cela compense des fautes de frappe mais pas la dyslexie... /rolleyes.gif' class='bbc_emoticon' alt='::)' />
Je ne me suis pas foulé à l'optimiser. Il y a moyen d'améliorer.
ça marchait plutôt bien, mais j'ai environ 10 termes à comparer sur on va dire 3000 records de BDD chacun... et ceci fois environ 20 occurrences encore... Donc, ça pompait pas mal.
Comme j'ai pas envie de charger mes trigrams en BDD en local pour plusieurs raisons, et de réinventer la roue au niveau du code, j'ai opté pour cette solution:
- mon serveur récupère le JSON du serveur source
- c'est lui qui parse et cherche les occurrences ressemblantes
- il me renvoie du JSON formatté pour mon modèle de données
C'est donc le serveur qui supporte la charge. Je pense que c'est la meilleure approche. (sauf à avoir 3000 users qui font ça en même temps, ce qui ne sera pas le cas)
Donc de refaire faire le boulot par chaque iPhone/iPad ?
Quitte à consolider ta base, autant le faire une fois pour toutes, non ?
L'ago de Mala ne se base pas sur une préconstruction de trigrams dans la base. Il fait tout en temps réel.
Côté serveur, j'ai déjà toutes les tables sources MAIS AUSSI mes enregistrements éclatés dans les tables secondaires, des tables de trigrams. C'est beaucoup plus rapide à comparer. En gros, France est déjà découpé en "Fr", fra", "an", "anc" "ce".
Il y avait 3 solutions:
1) Utiliser la classe de Mala qui marche bien et compare tout en temps réel. Sachant que j'ai les tables d'origines des pays en local.
2) Copier les tables de trigrams en local puisqu'elle ne bougent pratiquement pas (c'est pas tous les jours qu'on a un nouveau pays hein...)
3) Attaquer sur le serveur directement, mon serveur jouant de pont avec le flux d'origine, et de comparaisons avec les tables trigrams.
J'ai donc opté pour le 3).
Je suis intéressé par la méthode des trigrammes, d'un point de vue théorique en tout cas. Est-ce que vous auriez de liens/explications là dessus?
EDIT: C'est bon, je pense avoir compris: la distance entre 2 strings est évaluée par le nombre de trigrammes communs aux 2. L'avantage est que l'on peut évaluer cette distance directement en SQL et que l'on peut construire en avance la base de trigrammes pour la cible. Je me coucherais moins con ce soir tiens.
EDIT2: Je continue sur ma lancée, est-ce que SearchKit ne pourrait pas être une piste à explorer aussi?
Je reprends du début. /smile.png' class='bbc_emoticon' alt=':)' />
Au départ, j'ai une table countries de 190 pays.
Une seconde table country_trigrams va être générée à partir de la première une seule fois.
En gros, elle découpe tous les pays en sous-sections.
On aura donc par exemple pour France et Espagne:
1- Fr
2- ran
3- an
4- nce
5- ce
6- Es
7- spa
8- pag
9- gne
En fait, c'est plus finement découpé. C'est un plugin Rails qui me génère ceci. Il choisit de découper les pays en 3, 4, 5, 6, 7... sections suivant le nombre de lettres.
Ensuite, c'est là que ça devient intéressant.
Imaginons qu'on trouve le pays "Epagnee" ou "spagnne", il faut le faire correspondre au bon pays: Espagne.
Pour cela, on va:
1) Découper la chaà®ne source en sections de la même façon que les trigrams pré-générées, ce qui donnera grosso-modo avec "Epagnee":
1- "Ep"
2- "Epa"
3- "pag"
4- "gne"
5- "nee"
2) Comparer nos 5 sections avec celles se trouvant dans la table de données des trigrams grâce, dans mon cas, à une belle requête SQL de ce genre, pour le terme "france" pour le coup:
Sachant que fuzzy_weight classe les résultats par pertinence. Plus ce nombre est gros, plus la ressemblance entre les 2 chaà®nes est frappante.
Voilà en gros comment ça marche.