Imaginez que vous avez une énorme cache de données à rechercher de 4 façons:
J'utilise Trie pour les 3 premiers types de recherche, mais je peux ' t déterminer comment aborder le quatrième d'autre que le traitement séquentiel d'énormes numéros d'éléments.
3 Réponses :
Vous pouvez construire une carte navigable ou un ensemble (p. Ex. Treemap ou Arbreset) pour les 2 (avec des touches en ordre normal) et 3 (touches inverse)
Pour option 4, vous pouvez construire une collection avec une clé pour chaque lettre de départ. Vous pouvez simplifier cela en fonction de vos besoins. Cela peut conduire à plus d'espace utilisé mais obtenez des heures de recherche O (log n).
Essayer de comprendre votre recommandation pour 4: Si la chaîne existante est "cas" correspondrait-il à tous les A, B, C et E?
Pour "Abcae", l'ensemble ressemblerait à {AE, AAE, ABCAAE, BCAAE, CAAE, E} Vous recherchez avec Etage (TOFDIND) .Startswith (tofind)
Si votre ensemble de données est énorme COSIDER utilisant une plate-forme de recherche comme Apache Solr afin que vous ne finissez pas de finir dans un désordre de performance.
Nous parlons de collections de chaînes avec la taille moyenne. 5000. Lucene est surchargée ici
J'aurais juste besoin de l'algorithme et de la structure de données Lucene utilise pour ce dont j'ai besoin. Peut-être que je pourrais y jeter un coup d'oeil. Le problème est que ce type de recherche de modèle n'a pas vraiment de nom ...
Je lisais à travers ce page sur la recherche de texte intégral.
S'il ne s'agit que d'environ 5000 chaînes, pourquoi ne pas essayer de correspondre à l'aide de regex.
Pour # 4 Je pense que si vous calculez le nombre de surveurs de chaque personnage, vous pouvez rechercher ce tableau pour les entrées qui ont au moins autant de survie des caractères de la chaîne de recherche.
Quelle est la fonctionnalité de cet algorithme dépendra probablement de la nature des données et de la chaîne de recherche. Il pourrait être utile de donner quelques exemples de la fois ici pour obtenir de meilleures réponses.
Juste un commentaire rapide. Pour 1 & 2, vous pouvez utiliser des conditions d'inclusion sargable telles que
= etcomme '%' . Celles-ci permettent généralement à l'optimiseur d'utiliser l'index sur la colonne. Combien de temps le
myquestion être? Plus de 10 caractères?@Sloin Vous mentionnez dans un autre commentaire que la taille moyenne de votre collection est de 5000 (pas gros). Pourquoi ne pas itération (pour 100 000+ je comprendrais)?
Avez-vous envisagé d'utiliser l'indexation complète du texte? Ceci est disponible dans la plupart des bases de données. Sinon, stockez les données dans une machine avec suffisamment de RAM pour la mettre en mémoire, et vous n'avez pas à vous soucier de la numérisation de tout.
@anymeric: Cela dépend, les petites entreprises auraient 5000, mais nous le déploiions ensuite au grand et il y aurait 50 000
Quel SGBD utilisez-vous? PostgreSQL peut utiliser un index régulier pour 3) et 4)
@A_HORSE_WITH_NO_NAME: SQL a été mentionné simplement pour signaler quel type de carte sauvage assortie partielle nous parlons. On pourrait appeler la correspondance partielle des infixes.