Gornアドレスは、ツリーデータ構造内の任意のノードを識別し、アドレス指定する方法であり、1967年にアメリカの計算機科学者ソール・ゴーンによって導入された。これは、慣例的にドットで区切られた0個以上の整数の列であり、例えば0や1.0.1のような形式である。この表記法は、句構造規則によって定義された構文解析木内のノードを識別するためによく使用され、各アドレスはルートから特定のノードへの経路を一意に符号化する。
ツリーのルートは、ゴーンが*と呼んだもので、空の列と見なされる。アドレスiを持つ任意のノードについて、そのj番目の子（0から数える）はアドレスi.jを持つ。例えば、ルートに子0、1、2があるツリーでは、アドレス1.0はルートの2番目の子の最初の子を指す。この再帰的な定義により、ツリーが深くなるにつれてアドレスは任意に長くなり、列内の各整数は対応するレベルでの子のインデックスを示す。
形式的定義
形式的には、Gornアドレスは非負整数の有限列であり、多くの場合a1.a2....anと記述され、各aiは整数である。空の列は*または空文字列で表され、ルートを表す。ノードのアドレスは、その親のアドレスと子のインデックスをドットで区切って連結することで構築される。この方式は曖昧さがない。ツリーが有限で、各ノードが明確に定義された数の子を持つ場合、ツリー内の各ノードは正確に1つのGornアドレスを持ち、有効な各アドレスは正確に1つのノードに対応する。
この表記法は、形式言語理論や計算言語学で特に有用であり、そこでは句構造文法によって構文解析木が生成される。そのようなツリーでは、各内部ノードは非終端記号に対応し、その子は生成規則内の記号に対応する。Gornアドレスは、特定の部分木や葉を参照するためのコンパクトな方法を提供し、明示的なポインタなしでツリー構造を走査または操作するアルゴリズムを可能にする。
コンピュータ科学における応用
Gornアドレスの主な応用は、構文ツリーの表現と処理であり、特に自然言語処理やコンパイラ設計においてである。コンパイラでは、抽象構文木（AST）にGornアドレスを注釈として付けることが多く、エラー報告、デバッグ、コード生成を容易にする。例えば、コンパイラはアドレス2.1.0でエラーを報告し、AST内の特定の葉ノードを示すことがある。
Gornアドレスはまた、人工知能や機械学習の研究、特に記号的AIや知識表現にも登場する。これらは決定木や文法内のノードをインデックス付けするために使用され、ルートから葉への各経路は一意の規則または分類を表す。深層学習では、ツリーLSTMなどのツリー構造ニューラルネットワークが、出力をツリー位置と整合させるためにGornアドレスを使用することがある。
他のツリーアドレス指定方式との関係
Gornアドレスは、ツリー内のノードを識別するいくつかの方法の1つである。代替案には、ヒープインデックス（バイナリヒープで使用され、ルートは1で、ノードiの子は2iと2i+1）、XPathパス（要素名と述語を使用）、LispのS式（ネストしたリストを使用）がある。ヒープインデックスとは異なり、Gornアドレスは固定のアリティに依存せず、ノードが可変数の子を持つツリーで機能する。XPathとは異なり、Gornアドレスは純粋に位置ベースであり、ノードラベルに依存しないため、より単純であるが、記述性は低い。
この表記法は、Unixファイルパスにも関連しており、両方とも階層的な識別子の列を使用するが、Gornアドレスは整数とドット区切り文字のみを使用するのに対し、ファイルパスは名前とスラッシュを使用する。この整数ベースの方式は、構造が既知であるがラベルが不明な場合、またはラベルが冗長な場合に有利である。
歴史的背景と影響
ソール・ゴーンは、1967年の論文「Explicit definitions and linguistic dominoes」でアドレス表記法を導入し、これはトロント大学でのシステムとコンピュータ科学に関するシンポジウムの議事録に掲載された。ゴーンはコンピュータ科学教育とプログラミング言語の先駆者であり、ツリーアドレス指定に関する彼の研究は、データ構造と形式言語理論のその後の発展に影響を与えた。「Gornアドレス」という用語は、現在ではコンパイラ設計と構文解析に関する教科書で標準的であり、単に「ツリーアドレス」または「パス文字列」と呼ばれることもある。
その古さにもかかわらず、この表記法は現代のシステムでも関連性を保っている。例えば、XMLやJSON処理ツールは、デバッグに同様の位置ベースのアドレス指定を使用することが多く、一部のデータベースは階層データのインデックス付けにGorn風のアドレスを使用する。プログラミング言語理論では、Gornアドレスは属性文法で属性が計算される場所を指定するために使用される。
制限と拡張
Gornアドレスの1つの制限は、固定の子順序を前提としていることであり、これは構文解析木には自然であるが、順序付けられていないツリーには当てはまらない場合がある。そのような場合、アドレスは依然として有効であるが、異なる順序では安定しない可能性がある。もう1つの制限は、深いツリーではアドレスが長くなる可能性があることだが、これは実際にはほとんど問題にならない。
Gornアドレスの拡張には、特別なノード（例えば仮想ルート）を表すための負の整数の使用や、読みやすさのための異なる区切り文字の使用が含まれる。一部のシステムでは、ルートを空の列ではなく0とする変種を使用するが、これは標準的ではない。この表記法は、NP.0.1のようにラベルと組み合わせられることもあり、NPはノードラベルであるが、これは非公式な拡張である。
要約すると、Gornアドレスはコンピュータ科学における基礎的な概念であり、ツリー内のノードを参照するための単純で曖昧さのない方法を提供する。構文解析木やコンパイラでの使用により、これは永続的なツールとなっており、階層データを含む現代の研究や応用にも引き続き登場している。