Algorithmes efficaces pour rechercher une collection d'arbres

9

J'ai un grand ensemble de données d'arbres et je voudrais le rechercher en spécifiant un treelet (sous-graphe connecté). La requête doit renvoyer toutes les occurrences du treelet dans l'ensemble de données.

Existe-t-il des algorithmes efficaces pour le faire?

Je pensais à quelque chose comme des tableaux de suffixes, cependant, encoder naïvement les arbres comme des chaînes (par un ordre de traversée fixe de leurs nœuds) ne fonctionnera pas, car le treelet de recherche peut avoir n'importe quelle forme arbitraire.

MISE À JOUR:

Quelques détails sur les cas typiques que j'attends:

L'ensemble de données comprendra au moins des dizaines de milliers d'arbres, chacun composé d'environ vingt à trente nœuds. Les arbres ne seront pas binaires, mais le nombre typique d'enfants par nœud sera petit (généralement pas plus grand que quatre ou cinq, bien que dans certains cas dégénérés il puisse atteindre une trentaine). Le nombre d'étiquettes sera de plusieurs dizaines de milliers.

J'en ai besoin pour les applications PNL: chaque arbre sera l'analyse de dépendance d'une phrase, chaque nœud représentant une occurrence de mot et chaque étiquette un mot de dictionnaire (avec une certaine décoration).

graph-algorithms ds.data-structures tree graph-isomorphism string-search Antonio Valerio Miceli-Barone
la source
1
Ce volume présente une discussion des algorithmes parallèles pour l'isomorphisme des sous-arbres.
Anthony Labarre
1
Désolé, je pensais que vous cherchiez un sous-graphe connecté, qui sera nécessairement un arbre, apparaissant dans un ensemble d'arbres donné. Pourriez-vous préciser sous quels aspects votre problème diffère de cette description?
Anthony Labarre
1
Connaissez-vous à l'avance les arbres? Binaire? Combien de labels de nœuds différents attendez-vous? Des limites sur l'efficacité de l'espace? Je demande parce que si vous exécutez une tonne de requêtes sur le même ensemble de données, une solution pourrait impliquer un certain type d'indexation agressive.
Eli
1
Connaissez-vous l'appariement de brindilles XML? Votre problème semble être un cas spécial, vous pouvez donc simplement utiliser l'un des algorithmes et logiciels existants.
Marek Chrobak
2
Je suppose qu'il serait préférable d'ignorer la structure du graphique. Étant donné une requête typique, si vous jetez la structure, combien d'arbres prévoyez-vous avoir tous ces mots? Vos requêtes contiennent-elles des caractères génériques ou sont-elles exactes? Si les mots d'une requête sont comme "Le chat a mangé le chapeau", combien de graphiques auront en fait les mots "chat" et "chapeau"? Si vous indexez simplement chaque mot sur un ensemble d'arbres, puis coupez tous les ensembles, vous pourriez potentiellement naïvement rechercher le résultat sans encourir trop de coûts.
Eli

Réponses:

3

Bien qu'elle ne soit pas spécifiquement destinée aux arbres (enracinés), je pense que la structure de données G-trie pourrait fonctionner assez bien dans votre environnement. C'est une adaptation du trie (pour rechercher des ensembles de chaînes) aux graphiques.

Joshua Grochow
la source
1

Il y a quelque temps, j'ai rédigé l'algorithme de canonisation de l'arbre de Ronald Read et je l'ai mis sur wikipedia .

Je créerais une table de hachage pour chaque signature de nœud interne et les étiqueterais avec une liste de pointeurs vers les sous-arbres dont ils sont issus. Cependant, cela ne fonctionnera que pour les treelets avec de vraies feuilles.

Chad Brewbaker
la source