エンフィレード（ザナドゥ）

エンフィレードは、コンピュータ科学者のテッド・ネルソンによって発明され、 1970 年代と 1980 年代のプロジェクト ザナドゥの「グリーン」設計で使用されたツリー データ構造のクラスです。エンフィレードを使用すると、大規模な相互リンクされたハイパーテキストデータベースで、編集、バージョン管理、検索、および相互比較の操作を迅速に行うことができます。1990 年代に開始されたザナドゥの「ゴールド」設計では、 Entと呼ばれる関連データ構造が使用されました。

エンフィレードの原理は、あらゆるツリー データ構造に適用できますが、Xanadu システムで使用される特定の構造は、B ツリーによく似ています。エンフィレードの特徴は、ツリー ノード内のインデックス情報に DSPとWIDを使用することです。

DSP は変位、オフセット、または相対キーです。DSP は、包含ノードとサブツリーまたはリーフのキーの差です。たとえば、マップのグリッド スクエアのリーフは、そのリーフが属するサブツリーによって表されるより大きなグリッドに対して、特定の経度と緯度のオフセットを持つ場合があります。エンフィレードのリーフのキーは、そのリーフまでのツリーのパスにあるすべての DSP を組み合わせることで見つかります。DSP は、サブツリー全体またはコンテンツの範囲に一度にトップダウンで適用されるその他のコンテキスト情報にも使用できます。

ウィドは、幅、範囲、または境界ボックスです。ウィドはサブツリーまたはリーフのキーに相対的ですが、サブツリー内のすべての項目をカバーするアドレスの範囲を指定します。ウィドは、まばらに配置されているアドレス空間の重要な部分を識別します。一部のエンフィレードでは、特定のノードの下にあるサブツリーのウィドが重複することがあり、いずれの場合も、アドレス範囲内のデータの検索では、検索範囲と交差するウィドを持つサブツリーをすべて訪問する必要があります。ウィドは、ツリーのリーフからすべてのレイヤーを経由してルートまで結合されます (ただし、増分的に維持されます)。ウィドには、データの合計や最大値などの他の要約も含めることができます。

wid と dsp の相対的な性質により、エンフィレード内でサブツリーを再配置できます。サブツリーの最上部の dsp を変更すると、その下にあるすべてのデータのキーが暗黙的に変更されます。エンフィレードでの編集操作は、ツリーを関連するアクセス パスに分割する「カット」、サブツリーの挿入、削除、または再配置、およびそれらの部分の接合によって実行されます。カット操作と接合操作のコストは、1-D ツリーでは一般に対数に近く、2-D ツリーでは対数と平方根の中間です。

サブツリーはツリー間で共有することも、ツリー内の複数の場所からリンクすることもできます。これにより、エンフィレードはコンテンツの仮想コピーとバージョン管理を備えた完全に永続的なデータ構造になります。サブツリーの各使用は、そのサブツリーまでの DSP のチェーンから異なるコンテキストを継承します。コピーに変更を加えると、カット パスに沿ってのみ新しいノードが作成され、元のツリー全体がそのまま残ります。バージョンのオーバーヘッドは非常に小さく、新しいバージョンのツリーはバランスが取れていて高速で、そのストレージ コストは元のツリーからの変更にのみ関連します。

1 次元エンフィレードは、配列の直接アドレス指定可能性と、リンク リストの挿入、削除、再配置の容易さの中間に位置します。多次元エンフィレードは、緩やかで再配置可能、バージョン管理可能なQuad ツリー、Oct ツリー、またはk -d ツリーに似ています。

1979 年以前の Xanadu 設計で使用されていたModel -Tエンフィレードは、ロープに非常によく似たデータ構造です。文字の線形シーケンスを保存し、挿入、削除、並べ替え、バージョン管理は簡単ですが、リンクやバージョン間の比較は容易ではありません。テキストはエンフィレードの葉に直接保存されます。

後期の Xanadu の設計はより間接的になりました。istream (不変ストリーム) と呼ばれる共有可能なコンテンツ ピースのプールは増え続け、ユーザーが表示および操作するドキュメント、リンク、バージョン (すべて仮想アドレス付き) に整理されます。一連の enfilade 型は、仮想アドレスと istream アドレス間の双方向マッピングを管理します。ドキュメント間の対応とリンクのトレースは、仮想アドレスから不変アドレスへ、そして再び仮想アドレスへマッピングすることで可能になります。ID を記憶し、すべての出現をトレースできる共有コンテンツ ピースを使用してドキュメントを保存することを、トランスクルージョンと呼びます。

POOMfilade (順序行列の順列)は、順列行列を表す 2D のエンフィレードです。これは、ドキュメント内の仮想位置を、そのドキュメントが構築されているプールされたコンテンツ内の istream 位置にマップします。POOM は単位行列から始まり、ドキュメントの各編集によってマップの水平ストリップがスライスされ、再配置されます。POOM は、低くて広いアドレス範囲または高くて狭いアドレス範囲を検索することにより、V->I または I->V 方向でクエリできます。

Spanfiladeは、ドキュメントまたはドキュメント セットで使用される istream コンテンツのすべてのスパンの結合を収集します。2 つのドキュメントまたはドキュメントのバージョンからスパン セットの共通部分を取得すると、ドキュメントの比較が高速化されます。この同じメカニズムは、ドキュメントからのリンクまたはドキュメントへのリンクの検索にも使用されます。

Granfiladeは、このすべての情報をディスクとサーバーのネットワーク上に保存します。

エンフィレード（内部データ構造）とistreamアドレスは、Xanaduの外部インターフェースには公開されません。エンフィレードは、1999年にXanaduコードがオープンソースになるまで企業秘密情報であり、それ以前のいくつかの出版物では言及されていましたが、説明されていませんでした。^[1]

Xanadu システムにおけるクライアント サーバー通信では、タンブラーと呼ばれる形式の vstream アドレスが使用されます。

したがって、Enfilade という用語は FeBe (フロントエンド - バックエンド プロトコル) ドキュメントでは明示的には言及されていませんが、Xanalogical Structure やその他のいくつかのドキュメントでは間接的に言及されています。前述のドキュメントでは、xu88 が「General Enfilade Theory」に基づいていたことが言及されています。

1972 年、xu72 は Enfilade の概念を導入しました。これは「Model T Enfilade」と呼ばれ、ワードプロセッサタイプのインターフェイスで使用されました。1976 年、xu76 は「密結合 Enfilade」を実装しました。1980 年、xu80 システムはバージョン管理 Enfilade として説明される「ent」を導入しました。1988 年、xu88 システムは、Mark S. Miller、Stuart Greene、Roger Gregoryの「一般 Enfilade 理論」の概念を利用しました。これは「上向きに伝播する検索特性と同時に下向きに強制可能な構造特性を持つデータ管理ツリーを生成する」と説明されています。xu88 はまた、分散ネットワーク上で Enfilade の概念を拡張し、2 次元 Enfilade を導入し、ドキュメント バース全体で重複する Enfilade スパンを検索するアルゴリズムを実装しました。1992 年、xu92 は ent の最新の概念を実装しました。^[2]

• ハイパーメディア
• 一般化検索ツリー

• エンフィラードの紹介
• ザナドゥテクノロジーズ：紹介
• http://xanadu.com
• udanax.com - エンフィラディック ハイパーテキスト
• http://hyperworlds.com
• サイバースペースの漫画史
• 耳鼻咽喉科に関する論文
• ザナロジカル構造（ミラー）