Recherche d'arbres similaires

a marqué ce sujet comme résolu.

Bonjour,

Je viens vers vous suite à un problème qui me semble quelque peu difficile et auquel je ne trouve pratiquement pas de réponses ou tout du moins pas sous une forme qui me satisfait.

Mon problème est le suivant:

  • Je possède des expressions algébriques (ex: ax² + bx + c) que je convertis vers une représentation canonique (type AST).
  • Je souhaiterais les stocker dans une base de données.
  • Mais j’aimerais être capable de faire une recherche dessus. C’est-à-dire, que si je recherche une expression, la base de données me retourne les arbres les plus similaires (au sens de l’AST). Donc, ceux possédant la structure la plus proche, ceux partageant les plus grands sous-arbres communs ou au moins le plus grand nombre de noeuds similaires.

Un exemple serait que la base de données contienne:

  • 1) (ax² + bx + c)*(dx + e) et 2) (dx+e).
  • Si je cherche: (ax² + bx + c) + (dx + e). Il me retourne 1) puis 2) car 1) partage deux sous-arbres et 2) un seul.
  • Inversement, si je cherche (dx+e). Il me retourne 2) puis 1).

Je pense me tourner vers le module ltree de postgres (comme je possède également des données relationnelles classiques) mais est-ce vraiment une solution optimale ? Connaissez-vous des outils spécialement conçus pour ce type de requêtes ? Avez-vous des meilleures idées ?

Un tout grand merci d’avance pour vos réponses !

+0 -0

Je ne sais pas bien. Une version simple, du type: noeud + avec deux enfants x et 3 -> (+.x et +.3) pour symboliser: x + 3. Mais je ne suis pas certain que cela convienne finalement à mes besoins :/

Je crois que je vais devoir implémenter (malheureusement) une solution maison. Pour le moment, je ne dois faire uniquement que des requêtes et il y aura très peu de données (< 1000). J’aurais aussi un peu plus de flexibilité au niveau de la préférence des nœuds que ce que peut me proposer ltree.

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte