Quelqu'un sait comment adapter un arbre de recherche pour gérer des expressions régulières limitées? La tâche est, avec un nom de fichier, de trouver tous les nœuds correspondant à ce nom de fichier. Les noeuds peuvent contenir les globs de nom de fichier habituels (* et?). Évidemment, puisqu'il s'agit d'un arbre de recherche, la vitesse est essentielle.Arbre de recherche d'expressions régulières (glob)
EDIT: Je devrais ajouter que le cas le plus important pour la vitesse est le temps moyen pour écarter une correspondance. C'est-à-dire que dans la plupart des cas l'appariement échouera.
Un exemple: Dire l'arbre contenait les nœuds suivants:
foo, bar, foo *, * bar, foo bar
Recherche de foo renverrait noeuds 1 et 3. Recherche de bar? renverrait les nœuds 2 et 4. La recherche de fob ne retournerait aucun nœud. La recherche de fooxbar renvoie le nœud 5. La recherche de foobar renverrait les nœuds 3 et 4.
Est-ce un problème inverse (de regex): correspondance si une chaîne appartient à une langue régulière ou pas? – dirkgently
Pouvez-vous nous donner un échantillon d'E/S? – dirkgently
Un exemple: Dites que l'arbre contenait les nœuds suivants: foo, bar, foo *, * bar, foo? Bar Étant donné une chaîne (par exemple foo, foobar, fooxbar, fob, etc.), trouvez rapidement le nœud (s), le cas échéant, qui correspondent à cette chaîne. –