J'ai besoin d'une application iPhone / iPad pour pouvoir rechercher rapidement environ 10 000 enregistrements (environ un paragraphe de texte, chacun), pour toute sous-chaîne contenue dans l'enregistrement. Donc, si l'enregistrement contient le mot "flamme", interroger "boiteux" doit correspondre.
Je suis actuellement en train d'utiliser SQLite, mais "Comme% Term%%" Les recherches sont trop lentes pour ces nombreux enregistrements. L'activation de la recherche en texte intégral ne semble pas que cela répondra pleinement à mes besoins, car SQLite prend uniquement en charge les caractères génériques de préfixes (par exemple, «flam *», pas «* boiteux»).
J'ai expérimenté avec un blob géant de texte (~ 350K) et faire [Nstring RangeFstring: ...], que je pense utilise un algorithme Boyer-Moore. Ceci est plus rapide que "comme%% du terme%" des recherches, mais ce n'est toujours pas le genre de vitesse que j'espère.
Toute suggestion pour les approches ou les bibliothèques qui permettrait de réaliser ce type de recherche de sous-chaîne évolutive et qui fonctionnerait sur un iPhone?
3 Réponses :
Voici un certain nombre d'options différentes. Je ne suis pas au courant des beckmarks pour chacun, vous devrez donc faire des tests.
premier est l'extension FTS3 à SQLite. Cela devrait vous donner une recherche de texte complète rapide et indexée: http://regularradeandrythm.com/regular-rate- Rhythm-blog / sqlite3-fts-in-ios4.html
Alors, que des expressions régulières ont été introduites dans iOS 4:
http://developer.apple.com /Library/ios/#documentation/foundation/reference/nsregularexpression_class/reference/reference.html
Pour Pre-iOS 4, vous pouvez utiliser Regexkitlite:
http://regexkit.sourceforge.net/regexkitlite/index.html
Si vous décidez d'utiliser des expressions régulières, jetez un coup d'œil à cette entrée sur la manière d'optimiser ces:
Comment accélérer les expressions régulières iPhone avec nsregularexpression?
Les expressions régulières sont assez lentes ... je suis sûr que vous voulez une sorte de solution indexée O (1). J'aimerais entendre si vous roulez le vôtre ou trouvé une bonne solution via SQLite ...
Oui, les regex sont strictement plus lents que les recherches de texte régulières. Et la recherche en texte intégral dans SQLite, comme je l'ai écrit à l'origine, ne fait pas ce que je cherche.
envisagez peut-être de combiner votre deuxième approche avec l'approche asynchrone. Divisez votre gros bloc de texte en 5,10, quelle que soit sa taille et recherchez-les séparément avec le même nombre de fils. Ensuite, combinez des résultats à l'aide d'un système de coordonnées qui sait comment positionner correctement les correspondances (E.G. thread 5 Recherche de la région 5 et a trouvé une correspondance à la position 337 qui est corrélée au document X, position Y). Vous constaterez qu'il y a une limite où l'ajout de plus de threads ne fait pas de bien, donc ce serait la première chose à comprendre.
Si vous ne pouvez pas goverser le texte (divisé en mots), vous ne pouvez pas l'indexer. C'est pourquoi comme une recherche séquentielle. À moins que votre sous-chaîne ne puisse être contrainte d'une manière ou d'une autre (supprimez toujours la première lettre ou une longueur fixe pour la sous-chaîne, par exemple) Votre texte ne peut pas être stocké comme une liste de tous les jetons possibles et que ces jetons ne peuvent pas être indexés. La clé (jeu de mots) est de trouver un algorithme qui produit une liste suffisamment petite de jetons que le coût de leur indexation est inférieur au coût d'une recherche linéaire.
J'ai eu un problème de jeu de données / de requêtes similaire que j'ai trouvé que je devais utiliser des astuces d'interface utilisateur et de filetage pour que cela se sente réactive. J'ai fait toute la recherche dans un fil de travailleur qui annulerait / relancerait la recherche en tant qu'utilisateur saisi. Je n'ai trouvé aucune balle magique.
Merci Nwcoder. J'ai également envisagé ce genre d'approche asynchrone. Cela de côté, quelle approche avez-vous réglé pour chercher? Comme des requêtes?
Oui, je ne pouvais obtenir que les résultats corrects avec comme. Une note supplémentaire, j'ai fini par créer un objet simple avec uniquement le texte recherché et une carte d'identité référençant les attributs étendus de l'objet. Dans la version spécifique de recherche, j'ai normalisé le texte (toutes minuscules de ponctuation non minuscules, etc.) et cela a aidé un peu, mais pas beaucoup. (Peut-être une augmentation de 5 à 10% de vitesse.)