Une adresse de Gorn est une méthode permettant d'identifier et d'adresser tout nœud dans une structure de données arborescente, introduite par l'informaticien américain Saul Gorn en 1967. Il s'agit d'une séquence de zéro ou plus entiers conventionnellement séparés par des points, comme 0 ou 1.0.1. La notation est souvent utilisée pour identifier les nœuds dans un arbre syntaxique défini par des règles de structure de phrase, où chaque adresse encode de manière unique le chemin de la racine à un nœud spécifique.
La racine de l'arbre, que Gorn a appelée *, est considérée comme la séquence vide. Pour tout nœud avec une adresse i, son j-ième enfant (compté à partir de 0) a l'adresse i.j. Par exemple, dans un arbre où la racine a des enfants 0, 1, et 2, l'adresse 1.0 se réfère au premier enfant du deuxième enfant de la racine. Cette définition récursive permet aux adresses de devenir arbitrairement longues à mesure que l'arbre s'approfondit, avec chaque entier dans la séquence indiquant l'indice de l'enfant au niveau correspondant
Définition formelle
Formellement, une adresse de Gorn est une séquence finie d'entiers non négatifs, souvent écrite comme a1.a2....an où chaque ai est un entier. La séquence vide, désignée par * ou une chaîne vide, représente la racine. L'adresse d'un nœud est construite en concaténant l'adresse de son parent avec l'indice de l'enfant, séparés par un point. Ce schéma est sans ambiguïté : chaque nœud dans un arbre a exactement une adresse de Gorn, et chaque adresse valide correspond à exactement un nœud, à condition que l'arbre soit fini et que chaque nœud ait un nombre bien défini d'enfants
La notation est particulièrement utile dans la théorie des langages formels et la linguistique computationnelle, où les arbres syntaxiques sont générés par des grammaires de structure de phrase. Dans de tels arbres, chaque nœud interne correspond à un symbole non terminal, et ses enfants correspondent aux symboles dans une règle de production. Les adresses de Gorn fournissent un moyen compact de se référer à des sous-arbres ou des feuilles spécifiques, permettant aux algorithmes de parcourir ou de manipuler des structures arborescentes sans pointeurs explicites
Applications en informatique
L'application principale des adresses de Gorn est dans la représentation et le traitement des arbres syntaxiques, surtout dans traitement du langage naturel et la conception de compilateurs. Dans les compilateurs, les arbres syntaxiques abstraits (ASTs) sont souvent annotés avec des adresses de Gorn pour faciliter le rapport d'erreurs, le débogage, et la génération de code. Par exemple, un compilateur pourrait signaler une erreur à l'adresse 2.1.0, indiquant un nœud feuille spécifique dans l'AST
Les adresses de Gorn apparaissent également dans la recherche en intelligence artificielle et en apprentissage automatique, particulièrement dans IA symbolique et la représentation des connaissances. Elles sont utilisées pour indexer les nœuds dans arbres de décision et les grammaires, où chaque chemin de la racine à une feuille représente une règle ou une classification unique. Dans apprentissage profond, les réseaux de neurones structurés en arbre, comme les LSTM arborescents, utilisent parfois des adresses de Gorn pour aligner les sorties avec les positions dans l'arbre
Relation avec d'autres schémas d'adressage d'arbres
Les adresses de Gorn sont l'une des plusieurs façons d'identifier les nœuds dans un arbre. Les alternatives incluent les indices de tas(utilisés dans les tas binaires, où la racine est 1 et les enfants du nœud i sont 2i et 2i+1), les chemins XPath(qui utilisent des noms d'éléments et des prédicats), et les S-expressions Lisp(qui utilisent des listes imbriquées). Contrairement aux indices de tas, les adresses de Gorn ne sont pas liées à une arité fixe ; elles fonctionnent pour des arbres où les nœuds ont des nombres variables d'enfants. Contrairement à XPath, les adresses de Gorn sont purement positionnelles et ne dépendent pas des étiquettes de nœuds, ce qui les rend plus simples mais moins descriptives
La notation est également liée aux chemins de fichiers Unix dans ce sens que les deux utilisent une séquence hiérarchique d'identifiants, mais les adresses de Gorn utilisent uniquement des entiers et un séparateur de points, tandis que les chemins de fichiers utilisent des noms et des barres obliques. Ce schéma basé sur des entiers est avantageux lorsque la structure est connue mais que les étiquettes ne le sont pas, ou lorsque les étiquettes sont redondantes
Contexte historique et influence
Saul Gorn a introduit la notation d'adresse dans son article de 1967 "Explicit definitions and linguistic dominoes," publié dans les actes d'un symposium sur les systèmes et l'informatique à l'Université de Toronto. Gorn était un pionnier dans l'éducation en informatique et les langages de programmation, et son travail sur l'adressage d'arbres a influencé les développements ultérieurs dans les structures de données et la théorie des langages formels. Le terme "adresse de Gorn" est maintenant standard dans les manuels sur la conception de compilateurs et l'analyse syntaxique, bien qu'il soit parfois simplement appelé "adresse d'arbre" ou "chaîne de chemin."
Malgré son âge, la notation reste pertinente dans les systèmes modernes. Par exemple, les outils de traitement XML et JSON utilisent souvent un adressage positionnel similaire pour le débogage, et certaines bases de données utilisent des adresses de type Gorn pour indexer des données hiérarchiques. Dans la théorie des langages de programmation, les adresses de Gorn sont utilisées dans les grammaires attribuées pour spécifier où les attributs sont calculés
Limitations et extensions
Une limitation des adresses de Gorn est qu'elles supposent un ordre fixe des enfants, ce qui est naturel pour les arbres syntaxiques mais peut ne pas tenir pour des arbres non ordonnés. Dans de tels cas, les adresses restent valides mais peuvent ne pas être stables à travers différents ordres. Une autre limitation est que les adresses peuvent devenir longues pour des arbres profonds, mais cela est rarement un problème pratique
Les extensions aux adresses de Gorn incluent l'utilisation d'entiers négatifs pour désigner des nœuds spéciaux(par exemple, une racine virtuelle) ou l'utilisation d'un séparateur différent pour la lisibilité. Certains systèmes utilisent une variante où la racine est 0 au lieu de la séquence vide, mais cela n'est pas standard. La notation est également parfois combinée avec des étiquettes, comme dans NP.0.1, où NP est une étiquette de nœud, mais cela est une extension informelle
En résumé, l'adresse de Gorn est un concept fondamental en informatique, fournissant un moyen simple et sans ambiguïté de référencer les nœuds dans un arbre. Son utilisation dans les arbres syntaxiques et les compilateurs en a fait un outil durable, et il continue d'apparaître dans la recherche moderne et les applications impliquant des données hiérarchiques