Performances SQLite sur full text search
rubijn
Membre
Bonjour,
Je réalise actuellement une application de Dictionnaire classique, proposant une recherche de mot et l affichage de la définition.
Mais malheureusement je n ai pas encore trouve de méthode efficace en terme de performance lors de la recherche.
Ma première approche a été sqlite. J ai une table avec 150k mots. j effectue une recherche via un LIKE
ex : si je cherche les mots contenant "avoi"
SELECT word FROM word WHERE word LIKE '%avoi%' LIMIT 0,50;
Naturellement ce type de commande prends bcp de temps 2-5s sur un 3GS. Ce qui n est pas satisfaisant pour l utilisateur
Ma seconde approche a été d' utiliser l extension fts3 de sqlite pour accéder a la méthode MATCH
Ex : SELECT word FROM word WHERE word MATCH 'avoi*' LIMIT 0,50;
Ici c est bcp mieux 0.10-0.15s sur un 3GS mais le problème vient du fait que je ne cherche plus que les mots commencent par "avoi"... "Avoir" remonte mais pas "savoir". Ce qui est ici aussi une solution non satisfaisante.
Est-ce que quelqu'un aurais une piste pour ce type de problème? Je pensais a Core data mais vu qu il s articule autour de sqlite je ne vois pas comment ça l optimiserai....
Je résume : quelle est la meilleure méthode en terme de performance pour faire une recherche pour trouver les mots contenant les caractère de la recherche sur une base de 150k mots
Merci d' avance si vous avez des pistes
Je réalise actuellement une application de Dictionnaire classique, proposant une recherche de mot et l affichage de la définition.
Mais malheureusement je n ai pas encore trouve de méthode efficace en terme de performance lors de la recherche.
Ma première approche a été sqlite. J ai une table avec 150k mots. j effectue une recherche via un LIKE
ex : si je cherche les mots contenant "avoi"
SELECT word FROM word WHERE word LIKE '%avoi%' LIMIT 0,50;
Naturellement ce type de commande prends bcp de temps 2-5s sur un 3GS. Ce qui n est pas satisfaisant pour l utilisateur
Ma seconde approche a été d' utiliser l extension fts3 de sqlite pour accéder a la méthode MATCH
Ex : SELECT word FROM word WHERE word MATCH 'avoi*' LIMIT 0,50;
Ici c est bcp mieux 0.10-0.15s sur un 3GS mais le problème vient du fait que je ne cherche plus que les mots commencent par "avoi"... "Avoir" remonte mais pas "savoir". Ce qui est ici aussi une solution non satisfaisante.
Est-ce que quelqu'un aurais une piste pour ce type de problème? Je pensais a Core data mais vu qu il s articule autour de sqlite je ne vois pas comment ça l optimiserai....
Je résume : quelle est la meilleure méthode en terme de performance pour faire une recherche pour trouver les mots contenant les caractère de la recherche sur une base de 150k mots
Merci d' avance si vous avez des pistes
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Sinon, pense à regarder ce que tu peux utiliser comme optimisations sur ta table elle-même. Créer une clé d'indexation sur ton champ "word" peut drastiquement accélérer la recherche, ou regarde du côté du "Full Text Search".
Je ne connais plus exactement la syntaxe SQL à utiliser comme ça de tête, mais en rajoutant ce genre d'index à ta table ça devrait beaucoup aider en terme de perfs.
Concernant la commande MAKE on ne peut pas faire de *avoi* sinon ma solution était toute trouvée.
Concernant l index de la table j ai déjà un index sur le champ word mais en sqlite la commande LIKE n utilise pas l indexation d' ou sa lenteur....
Toujours en manque de solution
J'ai fait une recherche google, et j'ai trouvé les mêmes résultats que toi. ???
Avec les avantages et inconvénients de chacun.
Mais bon, tu crois vraiment que bcp de monde cherche des mots sans connaà®tre la première lettre ?
C'est le minimum quand-même non ? ::)
http://www.mail-archive.com/sqlite-users@sqlite.org/msg29559.html
http://www.sqlite.org/vtab.html
Par contre, ça a l'air assez coton à implémenter.
Je ne vois pas de solution facile pour l'instant... J'ai essayé hier soir en faisant un fichier texte ne contenant que les mots et ensuite les parser via regex..., c'est plus rapide que la commande LIKE de sqlite mais ça reste très long.... sans compter le fait que je met en mémoire une string issue de mon fichier de 1.5Mo....
J'ai regardé quelques app de dictionnaire notamment Dixel je ne sais vraiment pas comment il font. La base de mot doit être à peu de chose près de la même taille mais la recherche est quasi instantannée sur un 3GS et elle propose en plus des mots s'approchant en tenant compte de fautes éventuelles d'orthographe.... J'ai récupéré l'ipa depuis itunes pour le dezipper et regarder la tête des sources de données mais c'est des fichiers dont je ne reconnais pas le header.
Merci en tout cas pour la réponse.
Je continue les recherches...
Sinon, je vois pas comment CoreData pourrait être plus rapide... (dans le cas où tu puisses migrer la base)
Je peux faire ce que je veux au niveau de la bdd car je pars au départ de fichiers textes et de xml pour les définitions. J'ai fait ensuite une moulinette qui me créer la BDD que je veux en fonction des besoins (sqlite, mysql etc...)
Pour mon test en regex (via RegExLite) j'ai même généré un fichier texte simple.
J'ai vu ton poste (supprimer depuis) sur le length je pense que c'est quand même une bonne idée non pas en l'utilisant avec = mais avec >= qui permet de ne pas tester sur les mot plus petit que la recherche (je vais tester pour voir si je gagne quelque chose en terme de perf).
Merci en tout cas pour les réponses... mes recherches continuent
Oui c'est pour ça que je l'avais supprimé !
Evidemment qu'il fallait pouvoir chercher des mots avec plus de caractères que ceux tapés (suis-je bête ?). Si tu utilises >= au niveau de la condition, ça devrait améliorer "un peu" les choses.
Tu autorises la recherche à partir de 2 caractères je suppose ? C'est clair que dans ce cas, ça aidera pas bcp...
Sinon, une clause LIMIT ne pourrait pas améliorer les choses aussi ? (surtout donc quand il y a peu de caractères tapés et donc beaucoup de mots trouvés) ou la LIMIT n'est-elle appliquée qu'en fin de requête dans tous les cas (c'est plus probable je pense) ?
Autant que possible, éviter les recherche avec LIKE, MATCHES, CONTAINS etc... Très consommateur comme tu as pu le constater.
Préférer l'implémentation du genre : @avoi <= AND < @avoj
Attention aussi aux caractères spéciaux ("ç" par exemple).
K.
Je suis d'accord mais je veux trouver les mots approchant
ex : je tappe 'avoi' je veux que ça remonte 'avoir' et 'savoir' pas possible avec les conditions proposées ci dessus.
La clause MATCH marche très bien avec FTS3, c'est extrêmement rapide < 0,2s pour 145K mots mais elle ne permet que de remonter 'avoir' elle ne s'occuper pas des mots contenant 'avoi'.
Dans le cas de recherche sur moins de 3 caractères j'utilise le MATCH (rapide) je ne prend que les mots commencant par ces 1-3 caractères. La tout va bien
J'ai une limit à 50 dans toutes mes requêtes mais malheureusement il arrive souvent que les mots trouvés soient en fin de liste donc il parcours tout de même une grande parti de la table
ex : 'abaiss' -> le 33ème résultat est 'rabaisser' il a du parcourir la table de a-r pour le trouver
Je creuse, je creuse, mais je suis surtout épater par Dixel qui marche super bien et rapidement... Mon client veut la même chose évidemment (marque concurrente du Robert...)
Je vous donnerais la suite de mes recherches et si il y a des pros de Core Data est-ce que vous auriez une idée de la diffences de rapidité sqlite vs Core Data pour ce type de problèmatique.
Merci en tout cas
Mais même si CoreData était plus rapide, on ne sait pas ce qu'il utilise dans sa boà®te noire pour optimiser la recherche.
Des témoignages d'utilisateurs CoreData avec de grosses bases sont les bienvenus du coup.
Déjà , ça te permettra d'utiliser des méthodes comme -rangeOfString: au lieu d'une regex de type "*truc*".
Et si tu as vraiment besoin d'une regex, elle pourra être compilée et exécutée efficacement sur tes 150000 chaà®nes (vive regexkitlite).
Et dans ce cas, un predicate est-il mauvais niveau performances ?
EDIT : apple n'a pas sorti une toute nouvelle API sur les regexp y'a pas longtemps ?
Si, dans iOS 4.
Et du coup il parait que les applications qui utilisent RegExLite sont maintenant rejetées...
Oui, ça a fait du foin y'a pas longtemps.
J'ai déjà fait le test avec RegExLite sur une string contenant toute la liste (1,5Mo). Mais les perfs sont terribles.
Je n'ai pas testé de mettre chaque mots dans un tableau puis faire une boucle sur le tableau avec un rangeOfString de ma recherche... Mais je doutes de la rapidité de la chose (je vais quand même tester de ce pas)
Effectivement je peux essayer avec un NSArray de NSString pour voir les perfs. Je n'ai aucune idée de la rapidité de predicate.
Pour le rejet éventuel de RegExLite, je n'ai pas encore regarder l'api Apple mais si c'est une api regex correcte tant mieux je me passerais de RegExLite
J'ai du mal à croire que sqlite puisse être plus efficace qu'une recherche en mémoire. Peut-être regexlite est-il plus lent que le fts3, mais dans ce cas il faut juste changer de "filtrage".
Attendons les résultats de rangeOfString: ou NSPredicate ! (je suis plutôt confiant).
ex : recherche de 'abaissaien' sur un iphone 3GS, 3.1.3
150K words dans une NSArray, lecture lors de la recherche en brut force.
Recherche via rangeOfString :
2 mots en 0.679s
abaissaient
rababaissent
150K Words dans un fichier txt, lue à l'exécution
Recherche via RegExLite sur l'ensemble du fichier
2 mots en 4.297s
abaissaient
rababaissent
150K words dans une bdd SQLIte classique (pas de table virtuelle)
Recherche 'SELECT word FROM words WHERE word LIKE '%abaissaien%' LIMIT 0,50;'
2 mots en 4.380s
abaissaient
rababaissent
150K words dans une bdd SQLite FTS3 (table virtuelle)
Recherche 'SELECT word FROM words WHERE word MATCH 'abaissaien*' LIMIT 0,50;'
1 mots en 0.023s
abaissaient
Je ne penses pas qu'il y ai de solution simple, mais je commence à avoir une piste modéliser ma table différemment avec les mots voisins orthographiquement, et rester avec une méthode FTS3
ex : la table pourrait etre
word|lemme|size|neighbors
word : le mot
lemme : l'entrée dans le dictionnaire ex : les formes conjugués des verbes n'étant pas des entrées dans un dictionnaire, on veut que lorsque l'utilisateur tape 'avait' le résultat soit 'avoir'
length:la taille du mot
neighbors: une liste de mots voisins orthographiquement (j'ai trouvé des méthode, et même une BDD avec ces éléments)
Je continue les recherches....
Ce problème m'intéresse... tu peux m'envoyer la liste des mots en message privé ?
Pour me simplifier la vie, en petit NSKeyedArchiver sur ton NSArray de NSString et tu m'envoies le data résultant :-)
(mon dieu, ma propre phrase me fait peur... quel jargon!)
Pour ceux qui veulent la liste pour l'instant je me base sur la base Lexique3 de http://www.lexique.org/.
Elle est plus volumineuse que la bdd que j'aurais à traiter au finale (90K words), mais je cherchais une bdd la plus étoffée possible (qui peut le plus...)
http://lab.display-interactive.com/public/words.data (NSArray contenant tous les mots)
-utiliser NSPredicate avec LIKE est moins efficace que rangeOfString avec NSCaseInsensitiveSearch|NSDiacriticInsensitiveSearch
-utiliser NSPredicate avec un block encapsulant rangeOfString: n'est pas aussi efficace que d'appeler directement rangeOfString:
-j'ai utilisé le IMP caching, mais je n'ai pas l'impression que ça change grand chose (je le laisse dans le code suivant pour l'exemple).
-je n'indique pas mes timings, ils ne correspondent sûrement à rien par rapport aux tiens. Par contre, si tu essayes un code comme celui ci-dessous, tu obtiens quoi ?
[edit]
On peut encore un peu grappiller en utilisant CoreFoundation directement :
[edit]
Et encore mieux avec GrandCentralDispatch
[edit]
Je viens de tester sur iPod Touch (iOS 4), les timings diffèrent pas mal. GCD est moins efficace, par exemple.
Les temps sont fournis par l'instrument Time Profiler, ils comprennent l'exécution de la requête et l'affichage de la vue résultat (chargement UITableView, calcul des sections...). Je n'ai pas cherché à optimiser. La recherche est lancée en dure (pas de saisie) avant l'affichage de la vue.
J'oscille entre 1,4 sec et 1,5 sec pour les 2 mots trouvés sur la base des mots qui tu as donné.
L'utilisation mémoire est de 695,45 KB après recherche (Overall Bytes de 2,35 MB).
Faudrait que je fasse un test en saisissant un autre mot à rechercher et en optimisant le truc.
K.
Je viens de tester en passant par CoreFondation et je gagne un peu 0,65 -> 0,55 (-18%) c'est déjà pas mal. Je pense qu'un mixte memory et sqlite avec MATCH (avec une bdd repensée) les perfs sont pas loin de celles que je cherche
http://www.mikeash.com/pyblog/friday-qa-2009-02-06-profiling-with-shark.html
La version dictfind4 est coûteuse en mémoire mais elle pourra peut-être t'aider.
Pour diminuer son coût, tu pourrais ne l'appliquer que sur les mots de taille < 8, et faire une recherche normale pour les mots plus grands.
D'ailleurs, pour optimiser, tu peux aussi créer des tableaux contenant les mots de taille >=1, >=2, >=3, etc. Comme ça, pour un motif donné, tu peux limiter ta recherche.
Le process pour récupérer les données.
words.data -> NSArray -> char* words(l'étape NSArray me permet de garder mes bench sur les autres méthodes NSRange, CF, etc..). je fais en sorte que tous les mots des datas soient dans leur forme sans accent, en minuscule encodés en ASCII
là je passe par un automate à état
states[MAX_WORD_SIZE][26] = {{0,0,0,0,0,..},{..}};
et je boucle sur tous les mots de words pour trouver la chaà®ne cherchée.
Résultats sur un iPhone 4, de la recherche 'abaissaien', sur 146K mots
comparaison dans la NSArray avec un NSRange : 0,62s
comparaison dans la NSArray avec CFStringFind (CFramework) : 0,47s
comparaison avec automate C.... : 0,12s
La dernière étant parfait en terme de perf.
Je vais donc mixer deux techniques pour le dictionnaire
1) un travail sur la modélisation de la base et de pré-calcul sur les mots pour trouver les voisins évidents, calculer les formes diacritiques, les forme inversés, les synonymes etc.. pour avoir un max d'infos dans ma bdd sur les mots.
La recherche se fera via l'extension FTS3 de Sqlite, avec une forme 'abaissaien*'
Cette recherche (la plus rapide) sera effectuée quand l'utilisateur voudra un mot commençant ou finissant par sa recherche.
2) je générais une listes de mots pour une indexations plus fine (peut-être tous les mots). Quand l'utilisateur voudra un mot qui contient sa recherche. Cette méthode utilisera l'automate pour parser la char* et trouver les occurrences.
Dans les deux cas la recherche ne devra jamais dépasser 0,2s
Voilà merci en tout cas pour toutes les pistes que vous m'avez donné.
@bientôt sur le forum
J'ai l'impression qu'il n'y a pas de secret quand on veut de la performance, il faut aller voir du côté du C... 8--)
J'espère que ton client sera content !
Qui fait ce travail ? ça ne va pas être fastidieux ??
Le premier travail effectué a été de mettre toutes mes sources de données dans une BDD Mysql en utf8, pour pouvoir faire des traitements rapide, et ensuite générer les fichiers dont j'ai besoin : sqlite, fichier txt, nsdata etc....
Ensuite à partir de ma base il est facile (mais long
Pour les synonymes j'ai une bdd publique qu'il faut que je merge avec ma bdd de mots
Du travail en effet, mais les sources de données sont là . Donc c'est surtout mon MacBookPro qui va faire le travail