Um endereço de Gorn é um método de identificar e endereçar qualquer nó dentro de uma estrutura de dados em árvore, introduzido pelo cientista da computação americano Saul Gorn em 1967. É uma sequência de zero ou mais inteiros convencionalmente separados por pontos, como 0 ou 1.0.1. A notação é frequentemente usada para identificar nós em uma árvore de análise definida por regras de estrutura de frase, onde cada endereço codifica de forma única o caminho da raiz até um nó específico.
A raiz da árvore, que Gorn chamou de *, é considerada a sequência vazia. Para qualquer nó com endereço i, seu j-ésimo filho (contando a partir de 0) tem o endereço i.j. Por exemplo, em uma árvore onde a raiz tem filhos 0, 1 e 2, o endereço 1.0 refere-se ao primeiro filho do segundo filho da raiz. Esta definição recursiva permite que os endereços cresçam arbitrariamente longos conforme a árvore se aprofunda, com cada inteiro na sequência indicando o índice do filho no nível correspondente.
Definição Formal
Formalmente, um endereço de Gorn é uma sequência finita de inteiros não negativos, frequentemente escrita como a1.a2....an onde cada ai é um inteiro. A sequência vazia, denotada por * ou uma string vazia, representa a raiz. O endereço de um nó é construído concatenando o endereço de seu pai com o índice do filho, separados por um ponto. Este esquema é inequívoco: cada nó em uma árvore tem exatamente um endereço de Gorn, e cada endereço válido corresponde a exatamente um nó, desde que a árvore seja finita e cada nó tenha um número bem definido de filhos.
A notação é particularmente útil na teoria das linguagens formais e na linguística computacional, onde árvores de análise são geradas por gramáticas de estrutura de frase. Em tais árvores, cada nó interno corresponde a um símbolo não terminal, e seus filhos correspondem aos símbolos em uma regra de produção. Endereços de Gorn fornecem uma maneira compacta de referir-se a subárvores ou folhas específicas, permitindo que algoritmos percorram ou manipulem estruturas de árvore sem ponteiros explícitos.
Aplicações em Ciência da Computação
A principal aplicação dos endereços de Gorn está na representação e processamento de árvores de sintaxe, especialmente em processamento de linguagem natural e design de compiladores. Em compiladores, árvores de sintaxe abstrata (ASTs) são frequentemente anotadas com endereços de Gorn para facilitar relatórios de erro, depuração e geração de código. Por exemplo, um compilador pode relatar um erro no endereço 2.1.0, indicando um nó folha específico na AST.
Endereços de Gorn também aparecem em pesquisa de inteligência artificial e aprendizado de máquina, particularmente em IA simbólica e representação do conhecimento. Eles são usados para indexar nós em árvores de decisão e gramáticas, onde cada caminho da raiz até uma folha representa uma regra ou classificação única. Em aprendizado profundo, redes neurais estruturadas em árvore, como LSTMs de árvore, às vezes usam endereços de Gorn para alinhar saídas com posições na árvore.
Relação com Outros Esquemas de Endereçamento de Árvores
Endereços de Gorn são uma das várias maneiras de identificar nós em uma árvore. Alternativas incluem índices de heap (usados em heaps binários, onde a raiz é 1 e filhos do nó i são 2i e 2i+1), caminhos XPath (que usam nomes de elementos e predicados) e expressões S de Lisp (que usam listas aninhadas). Ao contrário dos índices de heap, os endereços de Gorn não estão vinculados a uma aridade fixa; eles funcionam para árvores onde os nós têm números variados de filhos. Ao contrário do XPath, os endereços de Gorn são puramente posicionais e não dependem de rótulos de nós, tornando-os mais simples, mas menos descritivos.
A notação também está relacionada a caminhos de arquivo Unix, pois ambos usam uma sequência hierárquica de identificadores, mas endereços de Gorn usam apenas inteiros e um separador de ponto, enquanto caminhos de arquivo usam nomes e barras. Este esquema baseado em inteiros é vantajoso quando a estrutura é conhecida, mas os rótulos não são, ou quando os rótulos são redundantes.
Contexto Histórico e Influência
Saul Gorn introduziu a notação de endereço em seu artigo de 1967 "Explicit definitions and linguistic dominoes", publicado nos anais de um simpósio sobre sistemas e ciência da computação na Universidade de Toronto. Gorn foi um pioneiro na educação em ciência da computação e em linguagens de programação, e seu trabalho em endereçamento de árvores influenciou desenvolvimentos posteriores em estruturas de dados e teoria das linguagens formais. O termo "endereço de Gorn" agora é padrão em livros didáticos sobre projeto de compiladores e análise sintática, embora às vezes seja referido simplesmente como "endereço de árvore" ou "string de caminho".
Apesar de sua idade, a notação permanece relevante em sistemas modernos. Por exemplo, ferramentas de processamento de XML e JSON frequentemente usam endereçamento posicional semelhante para depuração, e alguns bancos de dados usam endereços semelhantes aos de Gorn para indexar dados hierárquicos. Na teoria de linguagens de programação, endereços de Gorn são usados em gramáticas de atributos para especificar onde os atributos são computados.
Limitações e Extensões
Uma limitação dos endereços de Gorn é que eles assumem uma ordenação fixa de filhos, o que é natural para árvores de análise, mas pode não ser válido para árvores não ordenadas. Em tais casos, os endereços ainda são válidos, mas podem não ser estáveis entre diferentes ordenações. Outra limitação é que os endereços podem se tornar longos para árvores profundas, mas isso raramente é um problema prático.
Extensões aos endereços de Gorn incluem o uso de inteiros negativos para denotar nós especiais (por exemplo, uma raiz virtual) ou o uso de um separador diferente para legibilidade. Alguns sistemas usam uma variante onde a raiz é 0 em vez da sequência vazia, mas isso não é padrão. A notação também é às vezes combinada com rótulos, como em NP.0.1, onde NP é um rótulo de nó, mas isso é uma extensão informal.
Em resumo, o endereço de Gorn é um conceito fundamental na ciência da computação, fornecendo uma maneira simples e inequívoca de referenciar nós em uma árvore. Seu uso em árvores de análise e compiladores o tornou uma ferramenta duradoura, e ele continua a aparecer em pesquisas e aplicações modernas envolvendo dados hierárquicos.