›

Fuzzy search

muqaddarmuqaddar Administrateur
dans Objective-C, Swift, C, C++ #1
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.
Mots clés:

Réponses

  • AliGatorAliGator Membre, Modérateur
    #2
    J'avais implémenté une catégorie de NSString pour calculer la distance de Levenshtein entre 2 chaà®nes.

    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 ?)...
  • MalaMala Membre, Modérateur
    #3
    J'ai fait de même qu'Ali en repartant de l'article de ce blog...

    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.
  • SystemSystem
    #4
    Quid des perfs? image/ohmy.png' class='bbc_emoticon' alt=':o' />
  • AliGatorAliGator Membre, Modérateur
    #5
    Tel que le code est implémenté dans le lien de Mala, pas terrible (créer une méthode ObjC pour calculer le min entre 2 et 3 nombres... WTF ?!)

    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.
  • muqaddarmuqaddar Administrateur
    #6
    'Mala' a écrit:


    J'ai fait de même qu'Ali en repartant de l'article de ce blog...

    http://weblog.wander...ses?commented=0



    Par contre c'est moins évolué en terme de finesse.




    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.
  • muqaddarmuqaddar Administrateur
    #7
    Sur mon Mac, la comparaison d'une chaà®ne avec 180 records prend 14 ms, avec 500 records 21 ms, avec 3500 records 170ms.



    Je parle de la requête SQL qui compare avec les trigrams déjà  pré-découpés.
  • MalaMala Membre, Modérateur
    mars 2012 modifié #8
    Si cela peut aider, je te mets ma catégorie en pièce jointe.


    NSArray *strings = [NSArray arrayWithObjects:@&quot;sebastian&quot;,@&quot;sebastn&quot;,@&quot;seb&quot;,@&quot;pierre&quot;,@&quot;seabstine&quot;,@&quot;sbastien&quot;,@&quot;paul&quot;,@&quot;jacouille&quot;,nil];<br />
NSLog(@&quot;%@&quot;,[strings description]);<br />
NSLog(@&quot;%@&quot;,[[NSString sortStrings:strings byFuzzyStringMatching:@&quot;sebastien&quot;] description]);<br />




    Donnes le résultat suivant:


    2012-03-14 10:23:07.073 test[19494:a0f] (

    sebastian,

    sebastn,

    seb,

    pierre,

    seabstine,

    sbastien,

    paul,

    jacouille

    )



    2012-03-14 10:15:40.406 test[19407:a0f] (

    sbastien,

    sebastian,

    seabstine,

    sebastn

    )




    Tu noteras que c'est moins évolué que ton système. Cela compense des fautes de frappe mais pas la dyslexie... image/rolleyes.gif' class='bbc_emoticon' alt='::)' />



    Je ne me suis pas foulé à  l'optimiser. Il y a moyen d'améliorer.
  • muqaddarmuqaddar Administrateur
    #9
    Ah merci, c'est super sympa, je vais regarder ça ! image/thumbsup.gif' class='bbc_emoticon' alt='' />
  • muqaddarmuqaddar Administrateur
    #10
    Bon, j'avais utilisé en premier ta catégorie modifiée pour mes besoins.

    ç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)
  • AliGatorAliGator Membre, Modérateur
    #11
    Heu tu veux dire qu'à  la base tu avais prévu de faire ta reconstruction de base de données sur chaque device client ?!

    Donc de refaire faire le boulot par chaque iPhone/iPad ?



    Quitte à  consolider ta base, autant le faire une fois pour toutes, non ?
  • muqaddarmuqaddar Administrateur
    #12
    Non. Pas du tout.



    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).
  • MonsieurPaulMonsieurPaul Membre
    mars 2012 modifié #13
    Super intéressant comme topic. On peut trouver une fonction C pour calculer la distance de Levenshtein ici.

    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?
  • muqaddarmuqaddar Administrateur
    mars 2012 modifié #14
    Oui.

    Je reprends du début. image/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:




    SELECT (((count(*)*100.0)/6) + ((count(*)*100.0)/(SELECT count(*) FROM country_trigrams WHERE country_id = countries.id)))/2.0 AS fuzzy_weight, countries.id, countries.name_en, countries.name_fr, countries.name_it, countries.name_es, countries.name_de, countries.name_nl, countries.name_pt, countries.name_zh, countries.image, countries.updated_at, countries.status

    FROM `countries`

    LEFT OUTER JOIN country_trigrams ON country_trigrams.country_id = countries.id

    WHERE (country_trigrams.token IN (' fr','fra','ran','anc','nce','ce '))

    GROUP BY countries.id, countries.name_en, countries.name_fr, countries.name_it, countries.name_es, countries.name_de, countries.name_nl, countries.name_pt, countries.name_zh, countries.image, countries.updated_at, countries.status

    HAVING (((count(*)*100.0)/6) + ((count(*)*100.0)/(SELECT count(*) FROM country_trigrams WHERE country_id = countries.id)))/2.0 >= 5

    ORDER BY fuzzy_weight DESC




    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.
Connectez-vous ou Inscrivez-vous pour répondre.