Algorithmes de recherche dans un flux XML

Question

Je recherche des suggestions d'algorithmes/techniques pour effectuer une première recherche dans un document XML en continu.

<foo> 
    <bar name="aaa" > 
     <grah name="aab" /> 
     .. 
    </bar> 
    <bar name="bbb" /> 
    <bar name="ccc" /> 
    <bar name="ddd" /> 
    <bar name="eee" /> 
... up to 10,000 entries 
</foo> 

Le nombre d'éléments de 1er niveau est hors de mon contrôle. L'utilisation de xml est également hors de mon contrôle. Je peux pré-traiter le xml, je peux indexer le xml mais je ne peux pas (pour l'avenir prévisible) charger le document xml entier dans la mémoire sur une base par demande.

Je suis actuellement à la recherche séquentielle en utilisant la capacité de lecture de flux de libxml pour effectuer cette tâche. Il consomme une quantité plus ou moins fixe de RAM/requête et est très réactif généralement pour tout moins de 3k lignes, et la mise en cache des résultats les plus populaires aide mais presque tous les éléments de haut niveau sont touchés à un moment donné.

Récemment, nous avons eu à traiter un certain nombre de fichiers vraiment volumineux où les éléments de niveau 1 avaient jusqu'à 10 000 éléments et une correspondance plus proche de la fin est inacceptable en ce qui concerne la réponse du serveur. Jusqu'ici j'ai vu Introselect et Quickselect qui peuvent réduire l'espace de recherche, à quelque chose de raisonnable. J'ai pensé que je verrais s'il y a d'autres idées ou algorithmes que j'ai oubliés avant de commencer à écrire du code.

Answer 1

Vous n'expliquez pas en détail quelles sont les exigences de recherche ou à quoi ressemble le texte qui sera recherché. Je suppose que le XML en soi n'est pas intéressant et que l'analyse de flux que vous faites avec libxml peut être faite pour construire continuellement des objets où les données du XML ont été affinées et rendues plus facilement consultables.

Vous pouvez bien sûr simplement insérer le document XML dans une base de données XML telle que eXist. C'est très flexible si vous voulez préserver le XML original, mais si vous pouvez le jeter, je chercherais d'autres moyens de stocker juste l'essence du document XML; les données à rechercher.

Puisque vous écrivez que le XML peut être pré-processus, je suppose également que le XML ne change pas très souvent. Si ces hypothèses sont correctes, vous pouvez indexer le texte que vous souhaitez rechercher dans une base de données axée sur la recherche, telle que Lucene. Vous pouvez bien sûr créer vous-même l'algorithme de recherche, mais comme il existe des solutions open source (avec la mise en cache des requêtes et autres éléments en place), je vous recommande d'examiner certaines des solutions existantes.

Si les recherches elles-mêmes ne varient pas beaucoup, vous pouvez également créer des objets JSON à partir des données dans le fichier XML et de les stocker dans une base de données de documents (comme MongoDB ou CouchDB) avec des indices prédéfinis qui contient à peu près la réponse aux recherches que vous voulez effectuer en mémoire.

La solution que vous devriez choisir est un peu difficile à donner des recommandations claires puisque je ne connais pas toutes vos exigences, mais ce sont au moins quelques idées que vous pouvez explorer.