(57)【要約】相互接続されたツリーの森を含むツリーベースのデータストアが生成および／またはアクセスされる。ツリーベースのデータストアは、第１のルートノードに従属して複数のブランチを含み得る第１のツリーを含む。第１のツリーのブランチの各々は、葉ノードにおいて終端をなす。各葉ノードは、以下により詳細に説明するように、エンドプロダクトを表わし得る。同じツリーベースのデータストアの第２のルートは、エンドプロダクトを表わす各葉ノードにリンクされる。したがって、第２のルートは本質的に、順序が逆になった第１のツリーへのルートであるが、第１のツリーは複製されない。最終的に、ツリーベースのデータストアは、以下により詳細に説明するように、これらのツリーの各々のルートノードが基本ノードである複数のツリーを含む。これらのツリーの各々のルートノードは、第１のツリーの１つ以上のブランチ内の１つ以上のノードにリンクされ得る。ツリーベースのデータストアのノードは、ツリーベースのデータストア内の他のノードを指すポインタのみを含む。ツリーベースのデータストアを含むツリーの森内のツリーのルートは、データにリンクされ得る。
2006522984.tif 000002
【特許請求の範囲】
【請求項１】
ツリーベースのデータストアを生成するためのシステムであって、
プロセッサと、
プロセッサに結合されたメモリと、
ツリーベースのデータストアの少なくとも１つのレベルを作成するためのツリーベースのデータストアジェネレータとを含み、ツリーベースのデータストアの少なくとも１つのレベルは、第１のルートと複数のノードの少なくとも１つのノードとを含む第１のツリー、第２のルートと第１のツリーの少なくとも１つのノードとを含む第２のツリー、および第３のルートと第１のツリーの複数のノードの少なくとも１つとを含む少なくとも第３のツリーを含む、システム。
【請求項２】
データストアのノードは、少なくとも１つの基本ノードと、１つのサブコンポーネントノードと、１つのエンドプロダクトノードとを含む、請求項１に記載のシステム。
【請求項３】
ツリーベースのデータストアは、少なくとも第１のレベルおよび第２のレベルを含み、第１のレベルのエンドプロダクトは、第２のレベルの基本ノードを含む、請求項２に記載のシステム。
【請求項４】
ツリーベースのデータストアは、少なくとも第１のレベルおよび第２のレベルを含み、第１のレベルのエンドプロダクトは、分解されて第１のレベルの基本ノードを作成する、請求項２に記載のシステム。
【請求項５】
ツリーベースのデータストアは、少なくとも第１のレベルおよび第２のレベルを含み、第２のレベルの基本ノードは、分解されて第１のレベルの基本ノードを作成する、請求項２に記載のシステム。
【請求項６】
ノードは、ツリーベースのデータストア内の他のノードを指すポインタを含む、請求項１に記載のシステム。
【請求項７】
第１のルートおよび第２のルートは、ツリーベースのデータストア内の他のノードを指すポインタを含み、非ポインタ情報を含む、請求項１に記載のシステム。
【請求項８】
第１のルートは、開始インジケータに関連付けられて、第１の階層順序でツリーベースのデータストアにアクセスする、請求項７に記載のシステム。
【請求項９】
第２のルートは、終了インジケータに関連付けられて、第１の階層順序の逆でツリーベースのデータストアにアクセスする、請求項７に記載のシステム。
【請求項１０】
第３のルートは、データセットの要素に関連付けられた非ポインタ情報を含み、データセットの要素に基づいて第３の階層順序でツリーベースのデータストアにアクセスする、請求項７に記載のシステム。
【請求項１１】
ツリーベースのデータストアから情報を検索するための、ツリーベースのデータストアアクセス機構をさらに含む、請求項１に記載のシステム。
【請求項１２】
ツリーベースのデータストアアクセス機構はさらに、
ツリーベースのデータストアから検索されるべき情報の要求を受信するための手段と、
ツリーベースのデータストアから要求した情報を検索するための手段と、
ツリーベースのデータストアから検索した情報を返却するための手段とを含む、請求項
１１に記載のシステム。
【請求項１３】
データストアを生成するためのシステムであって、
プロセッサと、
プロセッサに結合されたメモリと、
データストアを作成するためのデータストアジェネレータとを含み、データストアは、複数の接続されたツリーに組織化されるルートノードおよび非ルートノードを含み、複数の接続されたツリーは、第１のルートと複数の非ルートノードの少なくとも１つとを含む第１のタイプのツリー、および第２のタイプの複数のツリーの少なくとも１つを含み、第２のツリーのタイプは、第１のタイプのツリーのノードと共通する複数の非ルートノードおよび第２のルートノードを含む、システム。
【請求項１４】
データストアのノードは、少なくとも１つの基本ノードと、１つのサブコンポーネントノードと、１つのエンドプロダクトノードとを含む、請求項１３に記載のシステム。
【請求項１５】
第１のタイプのツリーは、サブコンポーネントノードと基本ノードとの少なくとも１つの組合せからエンドプロダクトのシーケンシャルな合成を記録し、データストア内の第１の文脈内のデータへのアクセスを提供する、請求項１４に記載のシステム。
【請求項１６】
第２のタイプの複数のツリーの少なくとも１つのツリーは、データストア内の第２の文脈内のデータへのアクセスを提供する、請求項１３に記載のシステム。
【請求項１７】
少なくとも１つの基本ノードは、第１のヌルポインタと、第２のヌルポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、それらの第２の部分として基本ノードを含むノードを含む、請求項１４に記載のシステム。
【請求項１８】
少なくとも１つのサブコンポーネントノードは、第１のノードを指す第１のポインタを含み、第１のノードは、サブコンポーネントノードの第１の部分を含み、少なくとも１つのサブコンポーネントノードはさらに、第２のノードを指す第２のポインタを含み、第２のノードは、サブコンポーネントノードの第２の部分を含み、少なくとも１つのサブコンポーネントノードはさらに、ノードを指すポインタの第１のリストを指す第３のポインタを含み、第１のリストは、それらの第１の部分としてサブコンポーネントを含むノードを含み、少なくとも１つのサブコンポーネントノードはさらに、第４のヌルポインタを含む、請求項１４に記載のシステム。
【請求項１９】
少なくとも１つのエンドプロダクトノードは、第１の部分を指す少なくとも第１のポインタと、終了インジケータの第２の部分を指す第２のポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、それらの第２の部分としてエンドプロダクトノードを含むノードを含む、請求項１４に記載のシステム。
【請求項２０】
開始インジケータを表わすルートノードは、第１のヌルポインタと、第２のヌルポインタと、ノードを指すポインタの第１のリストを指す第３のポインタとを含み、第１のリストは、第１の部分として開始インジケータを含むノードを含み、開始インジケータを表すルートノードはさらに、第４のヌルポインタを含む、請求項１３に記載のシステム。
【請求項２１】
データセット要素を表すルートノードは、第１のヌルポインタと、第２のヌルポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、第２の部分としてデータセット要素を含むノードを含む、請
求項１３に記載のシステム。
【請求項２２】
エンドプロダクトを表わすルートノードは、第１のヌルポインタと、第２のヌルポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、第２の部分としてエンドプロダクトを含む第２のレベルのノードを含む、請求項１３に記載のシステム。
【請求項２３】
インタロック状態のツリーデータストアに記憶された情報にアクセスするためのアクセス機構をさらに含む、請求項１３に記載のシステム。
【請求項２４】
アクセス機構はさらに、
ツリーベースのデータストアから検索されるべき情報の要求を受信するための手段と、
ツリーベースのデータストアから要求した情報を検索するための手段と、
ツリーベースのデータストアから検索した情報を返却するための手段とを含む、請求項２３に記載のシステム。
【請求項２５】
データストアからデータを生成してそのデータにアクセスするための方法であって、
データを受信したことに応答して、ツリーベースのデータストアの少なくとも１つのレベルを作成するステップを含み、ツリーベースのデータストアの少なくとも１つのレベルは、第１のルートと複数のノードの少なくとも１つのノードとを含む第１のツリー、第２のルートと第１のツリーの少なくとも１つのノードとを含む第２のツリー、および第３のルートと第１のツリーの複数のノードの少なくとも１つとを含む少なくとも第３のツリーを含み、前記方法はさらに、
ツリーベースのデータストアの少なくとも１つのレベルからアクセスすることのできる情報に対する情報要求を受信するステップと、
ツリーベースのデータストアの少なくとも１つのレベルから情報を検索するステップとを含む、方法。
【請求項２６】
ツリーベースのデータストアに追加すべきデータを受信したことに応答して、受信したデータに関連付けられた情報を記憶するために、ツリーベースのデータストア内に新規のノードを作成するステップと、
新規のノードの第１の部分を含む第１のノードおよび新規のノードの第２の部分を含む第２のノードまで、新規のノードからリンクを作成するステップと、
第１のノードのポインタの第１のリストに対し、新規のノードへのリンクを追加するステップと、
第２のノードのポインタの第２のリストに対し、新規のノードへのリンクを追加するステップとを含む、請求項２５に記載の方法。
【請求項２７】
ツリーベースのデータストア内に新規のノードを作成するステップは、開始インジケータを表わす第１のノードとデータセット要素を表わす第２のノードとを組合せて、不完全なプロダクトを表わす第３のノードを生成するステップを含む、請求項２６に記載の方法。
【請求項２８】
ツリーベースのデータストア内に新規のノードを作成するステップは、第１の不完全なプロダクトを表わす第１のノードと、データセット要素を表わす第２のノードとを組合せて、第２の不完全なプロダクトを表わす第３のノードを生成するステップを含む、請求項２７に記載の方法。
【請求項２９】
ツリーベースのデータストア内に新規のノードを作成するステップは、第１の不完全なプロダクトと、終了インジケータを表わす第４のノードとを組合せて、エンドプロダクト
を表わす第５のノードを生成するステップを含む、請求項２７に記載の方法。
【請求項３０】
ツリーベースのデータストア内に新規のノードを作成するステップは、第２の不完全なプロダクトと、終了インジケータを表わす第４のノードとを組合せて、エンドプロダクトを表わす第５のノードを生成するステップを含む、請求項２７に記載の方法。
【請求項３１】
新規のノードを作成するステップは、第１のポインタ、第２のポインタ、第３のポインタ、および第４のポインタに空間を割当てるステップを含む、請求項２６に記載の方法。
【請求項３２】
第３のポインタおよび第４のポインタは、ヌルポインタである、請求項２６に記載の方法。
【請求項３３】
ツリーベースのデータストアから情報にアクセスするための方法であって、
データストアから情報の要求を受信したことに応答して、情報の要求は、少なくとも１つの制約を含み、データストアは、ツリーベースのデータストアの少なくとも１つのレベルを含み、ツリーベースのデータストアの少なくとも１つのレベルは、第１のルートと複数のノードの少なくとも１つのノードとを含む第１のツリー、第２のルートと第１のツリーの少なくとも１つのノードとを含む第２のツリー、および第３のルートと第１のツリーの複数のノードの少なくとも１つとを含む少なくとも第３のツリーを含み、前記方法は、
第３のルートに関連付けられたノードのリストを検索するステップを含み、ノードのリスト内の各ノードは、第１の部分および第２の部分を含み、第３のルートは少なくとも１つの制約を含み、前記方法はさらに、
第２のツリーの少なくとも１つのノードまで、第１のツリー内の各ノードのブランチを辿るステップを含む、方法。
【請求項３４】
情報の要求は、第１の制約および第２の制約を含み、第２のツリーのノードの組の共通部分が返却される、請求項３３に記載の方法。
【請求項３５】
インタロック状態のツリーデータベースを生成するためのコンピュータ実行可能な命令を含むコンピュータ読取可能な媒体であって、
ツリーベースのデータストアに追加されるべきデータを受信したことに応答して、受信したデータに関連付けられた情報を記憶するために、ツリーベースのデータストア内に新規のノードを作成するステップと、
新規のノードの第１の部分を含む第１のノードおよび新規のノードの第２の部分を含む第２のノードまで、新規のノードからリンクを作成するステップと、
第１のノードのポインタの第１のリストに対し、新規のノードへのリンクを追加するステップと、
第２のノードのポインタの第２のリストに対し、新規のノードへのリンクを追加するステップとを行なうための命令を含む、コンピュータ読取可能な媒体。
【請求項３６】
ノードと、前記ノード間にリンクとを含む構造であって、前記ノードは複数のデータフィールドを有し、前記複数のデータフィールドの少なくとも２つはポインタを含み、前記少なくとも２つのポインタの一方はCaseポインタであり、前記少なくとも２つのポインタの他方はResultポインタであり、少なくとも１つのノードは、ポインタのリストを指す少なくとも追加のポインタを有し、ポインタの前記リストを指す前記追加のポインタの１つは、前記ノードが関連付けられたasCaseリストを有する場合、asCaseリストを指すものであり、ポインタの前記リストを指す前記追加のポインタの別のものは、前記ノードが関連付けられたasResultリストを有する場合、asResultリストを指すものであり、前記ノードは、その少なくとも１つの主ルートノードおよび少なくとも１つの基本ルートノードが存在するルートノードを含み、前記ノードは他のルートノードを含み得、前記ノードはさら
に、少なくとも１つの思考の終わりノード、少なくとも１つのサブコンポーネントノード、および少なくとも１つのエンドプロダクトノードを含み、前記asResultリンクは、ルートノードと他の任意のノードとの間を指し、前記asCaseリンクは、少なくとも１つの主ルートノードと少なくとも１つのエンドプロダクトノードとの間を指し、それらの間の経路に少なくとも１つのサブコンポーネントノードを含み、前記asResultリンクは、ルートノードまたはエンドプロダクトノードと、それらの間の前記経路上のサブコンポーネントノードまたはエンドプロダクトノードとの間を指し、前記基本ノードもまた、値を有するフィールドを有する、構造。
【請求項３７】
前記構造は、コンピュータシステム内で起動されるとコンピュータシステムを設定して前記構造を生じるプログラム命令の組で形成される、請求項３６に記載の構造。
【請求項３８】
クレーム３７に明示したプログラム命令の組を含む、コンピュータ読取可能な媒体。
【請求項３９】
クレーム３６の構造に整合するデータ構造を含む、電子システム。
【請求項４０】
前記asCaseリストおよび前記asResultリストは、前記インタロック状態のツリー構造とは別個のデータ構造に記憶され、前記別個のデータ構造は、ポインタにより、前記インタロック状態のツリー構造内の関連するノードに関連付けられる、請求項３６に記載の構造。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
この発明はコンピューティングの分野に関し、特に、データストアへのデータの記憶および当該データへのアクセスの分野に関する。
【背景技術】
【０００２】
発明の背景
ソフトウェアを開発する際に開発者が行なう１つの基本的な選択は、データの組織化および参照を容易にする適切なデータ構造の選択である。リンクされたリスト、スタック、ツリー、アレイなどを含むさまざまな種類のデータ構造が利用可能である。各データ構造は何らかの利点および制限を伴う。
【０００３】
しばしば用いられる１つのデータ構造にはツリーがある。ツリーの１つの一般的な形は、ノードと呼ばれる要素の有限集合で構成されており、これはルートから１つ以上の内部ノードまで一緒にリンクされており、その各々が１つ以上のノードにリンクされ、最終的にいくつかの葉ノードで終わる。典型的には、ルートにより近いノードは、ルートからさらに離れたノードの親ノードである。ルートからさらに離れたノードは親ノードの子ノードと呼ばれる。データは典型的にはノードに記憶され、ルートからノード、さらに葉へのリンク、親から子へのリンク等を用いて参照され得る。したがって、階層またはシーケンシャルな関係はツリー構造のノードに記憶されたデータに起因し得る。階層関係はまた、文脈関係としても理解され得るが、各ノードはその親ノードの文脈内でアクセス可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ツリーデータ構造の１つの限界は、典型的には、ツリーが１つの階層しか表わせないことである。たとえば、販売活動についてのルートノードはルートノードに従属するいくつかのノードを有し得るが、各ノードは特定の販売員を表わす。各々の販売員ノードは子ノードを有し得るが、販売員の子ノードは各々、たとえば特定の州での販売を表わしている。したがって、このツリーは、販売員の文脈内における州の情報について容易にアクセスされ得る。すなわち、このツリーを用いることにより、「販売員ボブはどの州で販売するか？」といった質問に効率的に答え得る。販売員による州のデータへのアクセスではなく、州の文脈内における販売員データが必要とされる（すなわち、「どの販売員がテキサスで販売しているか？」という質問への回答が望まれる）場合、別のツリーが作成されなければならず、そのノードはルートの販売員の活動に従属する州を表わしているが、販売員を表わす子ノードがこれに従属し得る。別のツリーを作成する代替例では、所望の情報を抽出するためにツリー全体をトラバースすることとなるだろう。
【０００５】
１つの構造がデータ内における起り得るすべての文脈関係を記録し、これにより、標準的なツリーデータ構造では不可能な効率を達成し得るのであれば有用であるだろう。
【課題を解決するための手段】
【０００６】
発明の概要
相互接続されたツリーの森のうちの１つ以上のレベルを含むツリーベースのデータストアが生成および／またはアクセスされる。ツリーベースのデータストアの各レベルは第１のツリーを含み、当該第１のツリーは第１のルートノードに従属し、複数のブランチを含
み得る。第１のルートは、レベル開始インジケータなどを含むがこれに限定されない概念を表わし得る。第１のツリーのブランチの各々は葉ノードで終わる。各々の葉ノードは、以下により十分に記載されるように、エンドプロダクトを表わし得る。ツリーベースのデータストアのうち同じレベルの第２のルートは、エンドプロダクトを表わす第１のツリーの各葉ノードにリンクされる。したがって、第２のルートは本質的に、順序が逆になった第１のツリーへのルートまたは第１のツリーのサブセットであるが、第１のツリーは複製されない。第２のルートは、レベル終了インジケータなどを含むがこれに限定されない概念を表わし得る。最後に、ツリーベースのデータストアは複数のツリーを含み、これらのツリーの各々のルートノードは、データセット要素またはデータセット要素の表現などのデータを含み得る。この種類のルートノードはこの明細書中においては基本ルートノードと称される。これらのツリーの各々の基本ルートノードは、複製されない第１のツリーのうちの１つ以上のブランチにおける１つ以上のノードにリンクされ得る。ツリーベースのデータストアの非ルートノードは、ツリーベースのデータストアにおける他のノードを指すポインタしか含まない。各レベルのツリーベースのデータストアを含むツリーの森におけるツリーのルートはまたポインタで構成されるが、ルートノードはさらに、情報を表わすデータを含み（すなわち、データセット要素などのデータまたはレベル開始もしくはレベル終了インジケータなどの概念であるかまたはこれを表わすデータを含み）得る。ツリーベースのデータストアの他のノードはすべて、他のノードを指すだけであり、データを含まない。この発明の一実施例においては、データは、文字、画素表現、開始インジケータ、終了インジケータ、フィールドの開始インジケータなどの状態に関連付けられる整数であるが、但し、この発明はそのようには限定されない。複数のレベルの上述のツリーベースのデータストアが生成およびアクセスされ得、より低いレベルのエンドプロダクトが次のレベルの基本ルートノードになる。
【０００７】
インタロック状態のツリーデータストアが生成およびアクセスされる。データストアは、この明細書中において主ルートと称される第１のルートに従属する１つのasCaseツリーを形成するasCaseブランチと、複数のルートに従属する複数のasResultツリーを形成するasResultブランチとの複数ルートのツリーを含む。asResultツリーの１つの特別な例は、上述のasCaseツリーのうちの１つ以上のエンドプロダクト葉ノードにリンクされたルートノードを含む。したがって、このasResultツリーは、エンドプロダクトで終端するasCaseツリーのブランチに逆の順序で容易にアクセスできる。このasResultツリーはまた、次のレベルのための基本ルートノードを規定するのに用いられてもよい。これらの基本ルートノードは、より低いレベルのエンドプロダクトの組で構成される、次のレベルのためのデータセット要素を表わし得る。
【０００８】
インタロック状態のツリーデータストアは、レベル開始インジケータを表わすノードとデータセット要素を表わすノードとを組合せてサブコンポーネントを表わすノードを形成することにより、入力ファイルにおいて生じるデータセット要素間の関係についての情報を取込み得る。サブコンポーネントノードは、データセット要素を表わすノードと組合されて、反復サブプロセスにおいて別のサブコンポーネントノードを生成し得る。サブコンポーネントノードを、レベル終了インジケータを表わすノードと組合せることにより、レベルエンドプロダクトノードが作成され得る。レベル開始ノードをデータセット要素ノードと組合せてサブコンポーネントを作成し、サブコンポーネントをデータセット要素ノードなどと組合せるプロセス自体が繰返されると、あるレベルにおいて複数のasCaseブランチが生成され得る。asResultツリーはまた、たとえばasCaseツリーにおける１つ以上のノードを指すasResultツリーのルートによって、asCaseツリーにおけるノードにリンクまたは接続され得る。
【０００９】
１つのレベルのエンドプロダクトノードは、次のレベルのサブコンポーネントを生成するために組合されるデータセット要素を表わす基本ルートノードであり得る。このプロセ
スは何回でも繰返されて、asCaseツリーのレベルがいくつでも作成され得る。加えて、あるレベルの基本ルートノードが分解されて、より低いレベルのノードおよびルートが生成され得る。１つのレベルのエンドプロダクトノードが、特別な場合のより低いレベルのasResultツリーにより、次のレベルの基本ルートノードになる。すなわち、より低いレベルのasResultツリーはより低いレベルの終了インジケータを表わすルートノードを有する。したがって、より低いレベルの終了インジケータを表わすルートノードを有する、より低いレベルのasResultツリーは、反転したより低いレベルのasCaseツリーへの第２のルートである。
【００１０】
この発明の一実施例においては、ノードが作成されると、asCaseおよびasResultリンクは各レベルにおいて本質的に同時に生成される。asCaseブランチは、入力が処理されると、asCaseリンクを生成することによって作成される。各レベル上のasCaseツリーのasCaseブランチは、そのレベルの各々のサブコンポーネントおよびエンドプロダクトが、データセット要素を表わすノードをサブコンポーネントおよびエンドプロダクトなどにシーケンシャルに組合せることによって如何に作成されたかを直接記録する。asCaseツリーのブランチはまた、ツリーにおけるノードの１つの起こり得る階層関係を表わす。
【００１１】
asResultリンクを生成することにより、一連のインタロック状態のツリーが作成され、その各々は別個のルートに従属する。あるレベルには、この種類の複数のルートが存在し得る。これにより、結果として、入力時に生じるデータセット要素間の他のすべての関係が記録される。上述の情報は、ツリーのノードに明確に記憶されるのではなく構築されるインタロック状態のツリーの森の構造によって取込まれ、これにより、実際には、入力として受信されるデータが、構築されるインタロック状態のツリーの森の構造を決定する。asResultツリーの森の構造により、このように記憶された情報が、所要の他のいかなる文脈においても確実にアクセス可能となる。したがって、データストアは、以下の説明から明らかとなるように、自己組織化する。
【００１２】
上述の概要、ならびにこの発明の実施例についての以下の詳細な説明は、添付の図面と関連して読まれるとより良く理解される。この発明を例示する目的で、この発明の例示的な構造が図面に示される。しかしながら、この発明は開示される特定の方法および手段に限定されない。
【発明を実施するための最良の形態】
【００１３】
具体的な実施例の詳細な説明
概観
以下に記載されるシステムおよび方法は、相互接続されたツリーの森の少なくとも１つのレベルを含むデータストアを作成する。データストアの各レベルの相互接続されたツリーの森は、レベル開始を表わすノードと（サブコンポーネントノードを作成する）データセット要素との組合せ、またはサブコンポーネントノードとデータセット要素ノードとの組合せ、またはサブコンポーネントノードとレベル終了インジケータを表わすノードとの組合せについての情報を、反復プロセスにおいて取込み、これにより、asCaseツリーブランチおよび複数のasResultツリーによってリンクされるノードで構成される単一のasCaseツリーが生成されることとなる。asCaseブランチのノードは第１のルートに従属する。たとえば、図３ａを参照すると、ノード３０２、３１２、３１４および３１６は、第１の開始インジケータルート３０２に従属する例示的なasCaseツリーである。asResultツリーは以下のツリーを含む。すなわち、ノード３０６および３１２（１つのasResultツリー）、ノード３０４および３１４（第２のasResultツリー）、ノード３０８および３１６（第３のasResultツリー）、ならびにノード３１０および３１８（第４のasResultツリー）である。第４のasResultツリーは、asResultツリーの特別な例である。というのも、ルート（ノード３１０）が終了インジケータを表わすからである。
【００１４】
所与のレベルのasCaseツリーの各ブランチは、レベル開始インジケータを表わすノードと、サブコンポーネントノードへのデータセット要素を表わすノードとの組合せで始まる。サブコンポーネントノードは、別のサブコンポーネントノードへのデータセット要素ノードと繰返し組合されてもよい。サブコンポーネントはレベル終了インジケータを表わすノードと組合されて、エンドプロダクトノードを作成し得る。このプロセスは繰返すことができ、結果として、第１のルートに従属する複数のasCaseツリーブランチを形成することとなり得る。
【００１５】
たとえば、特定のインタロック状態のツリー構造のうち分割できない基本構成要素が英数字である場合、サブコンポーネントは、語ではない文字の組合せであってもよく、エンドプロダクトは語であってもよい。代替的には、サブコンポーネントは、一部の在庫数または注文数を含む英数字の組合せであってもよく、エンドプロダクトは、この発明に適用される入力の英数字の母集団のうち多数ある中から２つの可能な用途を挙げると、全ての在庫数または注文数であってもよい。
【００１６】
１つのレベルのエンドプロダクトは次のレベルのデータセット要素であってもよい。エンドプロダクトデータセット要素を用いることにより、より低いレベルのデータセット要素がより低いレベルのサブコンポーネントおよびエンドプロダクトを作成するのに用いられるのと同じ態様で、次のレベルのサブコンポーネントが生成され得る。たとえば、上述の特定のインタロック状態のツリー構造においては、１つのレベルのエンドプロダクト（語）はデータセット要素であってもよく、そこから、より高いレベルのエンドプロダクト（文）が作成され得る。このプロセスは何回繰返されてもよく、これにより、データストアにいくつものレベルのasCaseツリーが作成され得る。
【００１７】
上述の例を続けるために、レベルデータセット要素として語を用いるより高いレベルには文が含まれ得る。文を組合せることにより段落（さらにより高いレベル）などが作成され得る。加えて、より高いレベルのデータセット要素を分解することにより、より低いレベルのインタロック状態のツリーデータストアが生成され得る。この発明の一実施例においては、レベル終了インジケータから始まるasResultツリーを用いて、次のレベルのデータセット要素を規定する。終了インジケータは、この発明の一実施例においては、asCaseツリーによって規定されるように、反転したインタロック状態のツリーデータストアへの第２のルートである。
【００１８】
ノードが作成されると、asCaseおよびasResultリンクが各レベルで同時に生成され得る。asCaseリンクは、ノードがそこから作成される２つのノードのうち第１のノードへのリンクを表わす。入力が処理されると、asCaseツリーのasCaseブランチがasCaseリンクの生成によって作成され得ることが認識されるだろう。各レベルのasCaseブランチは、そのレベルの各サブコンポーネントおよびエンドプロダクトが如何に作成されたかを直接記録する。したがって、asCaseブランチはいかなる目的で用いられてもよく、これについては、サブコンポーネントおよびエンドプロダクトが如何に作成されるかを知ることが有用である。たとえば、インタロック状態のツリージェネレータへの入力が正確に綴られた語の母集団を含む場合、生成されたインタロック状態のツリーのうち結果として得られるasCaseリンクをスペルチェッカーとして用いて、データストアの有用性の可能な限り多くの例から例を１つだけ列挙し得る。
【００１９】
加えて、asCaseツリーのブランチはまた、asCaseツリーにおけるノードの１つの起り得る階層関係を表わす。たとえば、インタロック状態のツリージェネレータが受取ったデータが「トムがペンシルヴェニア州で１００個を売った。（Tom sold 100 PA.）ビルがニュージャージー州で４０個を売った。(Bill sold 40 NJ.)」である場合、生成されたasCase
ツリーは、「販売員の文脈内の州情報」の文脈または階層にデータの視点を含む。
【００２０】
asResultリンクは、ノードがそこから作成される２つのノードのうち第２のノードへのリンクを表わす。asResultリンクの生成により一連のインタロック状態のツリーが作成され、この場合、asResultツリーの各々はデータセット要素を含むルートに従属する。これにより、結果として、データストアにおいて要素とasCaseツリーとの間に発生するすべての関係が記録されることとなる。すなわち、asResultツリーは、インタロック状態のツリーのノードの起り得るすべての文脈を取込む。asResultツリーはいかなる目的で用いられてもよく、これについては、文脈またはノード間の関係を知ることが有用である。たとえば、インタロック状態のツリーデータストアジェネレータへの入力が、販売員の名前、曜日、アイテムの数および州を含む販売データの母集団を含む場合、生成されたインタロック状態のツリーデータストアのうち結果として得られるasResultリンクを用いることにより、「特定の州においてどの販売員が販売するか？」、「月曜日にいくつのアイテムが売れたか？」、「販売員ボブは月曜日と火曜日にアイテムをいくつ売ったか？」などの情報がすべて、同じインタロック状態のツリーデータストアから、データストアの複数のコピーを作成せずに抽出され得る。
【００２１】
サブコンポーネントおよびエンドプロダクトは、asResultツリーに記憶される情報を用いて分類され得る。上述の情報が、ツリーのサブコンポーネントおよびエンドプロダクトノードに明示的に記憶されるのではなく、構築されたインタロック状態のツリーデータストアの構造によって実際に記録されることが認識されるだろう。インタロック状態のツリーデータストアのルートノードだけがデータを含み得るので、asResultリンクがルートノードまで辿られることにより、サブコンポーネントまたはエンドプロダクトがルートノードによって表わされるデータのクラスに属するかどうかが決定され得る。この特徴が以下に記載されるプロセスに従ってデータストアの自己組織化を引起すことがさらに理解されるだろう。たとえば、インタロック状態のツリーデータストアジェネレータへの入力が「CAT TAB」である場合、結果として得られるインタロック状態のツリーデータストアの構造に記憶される情報を用いることにより、エンドプロダクト「BOT-C-A-T-EOT」および「BOT-T-A-B-EOT」が共に要素「A」を含むこと、言い換えれば、「A」を含むサブコンポーネント／エンドプロダクトのクラスが「BOT-C-A-T-EOT」および「BOT-T-A-B-EOT」を含むと判断され得る。さらに、「A」を含むノードのasCaseリンクを辿ることにより、「A」を含む他のサブコンポーネントおよびエンドプロダクトがasCaseツリーのブランチに沿って見出され得る。
【００２２】
この発明の一実施例においては、ノード間のリンクは双方向である。たとえば、文字「A」を表わすルートノードはノードAのasResultListにおけるノードBOT-C-Aを指すポインタを含み得、ノードBOT-C-Aは、そのasResultポインタとしてノードAを指すポインタを含み得る、等々である。
【００２３】
この発明の別の実施例においては、ノード間のリンクは単方向である。たとえば、この実施例においては、ノードBOT-C-Aは、ノードBOT-Cを指すasCaseポインタと、Aを表わすルートノードを指すasResultポインタとを含むが、ルートノードAは、そのasResultListにおいてノードBOT-C-Aを指すポインタを含まない。どのノードがクラスAのものであるかについての情報を依然として決定することができるが、そうするには、すべてのノードの探索が必要となるかもしれないことを当業者は認識するだろう。
【００２４】
例示的なコンピューティング環境
図１は、この発明の局面が実現され得る例示的なコンピュータシステム１００を示すブロック図である。コンピュータシステム１００は、メインフレーム、ミニコンピュータ、ＩＢＭの互換性のあるパーソナルコンピュータ、Unix（登録商標）ワークステーションま
たはネットワークコンピュータなどであるがこれらに限定されない如何なる好適なシステムであってもよい。この発明の装置が、マルチユーザコンピュータシステムまたは単一のユーザコンピュータを含むがこれらに限定されない如何なるコンピュータシステムにも適用され得ることを当業者は理解するだろう。図１に図示のとおり、コンピュータシステム１００は、メインメモリ１０４、補助ストレージインターフェイス１０６、端末インターフェイス１０８およびネットワークインターフェイス１１０に接続される中央処理装置（ＣＰＵ）１０２を含む。これらのシステム構成要素はシステムバス１６０を介して接続される。補助ストレージインターフェイス１０６は、ディスク１９５などであるがこれに限定されないディスクにデータを記憶する、ＤＡＳＤ装置１９０などであるがこれらに限定されない記憶装置をコンピュータシステム１００に接続するのに用いられる。
【００２５】
コンピュータシステム１００の仮想メモリ全体を含むメインメモリ１０４はオペレーティングシステム１２２およびアプリケーション１２４を含み、インタロック状態のツリーデータストア１２６をも含み得る。インタロック状態のツリーデータストア１２６を用いることにより、データを複製する必要なしに複数の文脈モードでデータを直ちに探索することができるデータストレージが提供され得る。コンピュータシステム１００は周知の仮想アドレス指定機構を用い得るが、これにより、コンピュータシステム１００のプログラムが、メインメモリ１０４およびＤＡＳＤ装置１９０などの複数のより小さなストレージエンティティにアクセスするのではなく大きな単一のストレージエンティティにアクセスするかのように挙動することが可能となる。したがって、オペレーティングシステム１２２、アプリケーション１２４およびインタロック状態のツリーデータストア１２６はメインメモリ１０４に存在するように示されているが、当業者は、これらの要素が必ずしもすべて完全にメインメモリ１０４に同時に配置されるわけではないことを認識するだろう。
【００２６】
コンピュータシステム１００は単一のＣＰＵおよびシステムバスのみを含むよう示されているが、当業者は、この発明が複数のＣＰＵおよび／またはバスを含むシステムを用いて実現され得ることを理解するだろう。端末インターフェイス１０８は、１つ以上の端末をコンピュータシステム１００に接続するのに用いられ得る。参照される端末は簡易端末装置または完全にプログラム可能なワークステーションであってもよく、システム管理者およびユーザがコンピュータシステム１００と通信することを可能にするのに用いられてもよい。
【００２７】
ネットワークインターフェイス１１０は、他のコンピュータシステムおよび／またはワークステーションをコンピュータシステム１００に接続するのに用いられてもよい。ネットワークインターフェイス１１０がインターフェイスをとるネットワークは、ローカルエリアネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、インターネット（Internet）、エクストラネットもしくはインターネット、または他の好適なネットワークであってもよい。オペレーティングシステム１２２は、ＯＳ／２、ＷＩＮＤＯＷＳ（登録商標）、ＡＩＸ、ＵＮＩＸ（登録商標）、ＬＩＮＵＸなどのオペレーティングシステム、または他の好適なオペレーティングシステムであってもよい。
【００２８】
アプリケーションプログラム１２４は、インタロック状態のツリーデータストア１２６に記憶されるデータにアクセスする如何なる種類のアプリケーションプログラムであってもよい。したがって、当該アプリケーションは、いくつかの例を挙げると、データ解析アプリケーション、データウェアハウジングアプリケーション、侵入検出システムを含み得るが、但し、この発明はこれらには限定されない。
【００２９】
インタロック状態のツリーデータストア１２６は、ユーザが同じデータストアにアクセスして如何なる文脈にも関連付けられる情報を得ることを可能にするデータストレージ構造を提供する。この明細書中に用いられるデータという語は、数字、テキスト、グラフィ
ック、式、表、音声、映像、マルチメディアまたはその組合せなどであるがこれらに限定されない、コンピュータによって記憶された如何なる種類の情報をも含み得る。インタロック状態のツリーデータストア１２６は、アプリケーション１２４の一部として、オペレーティングシステム１２２の一部として、または、多種多様なアプリケーションにデータストレージを提供するよう適合され得る別個のデータストアプロダクトとして、実現され得る。
【００３０】
この発明は、十分に機能的なコンピュータシステムの文脈において記載されるが、当業者は、この発明がさまざまな形のプログラムプロダクトとして分散可能であり、この発明が、この分散を実行する特定の種類の信号記録媒体から独立して等しく適用されることを認識するだろう。このような信号を搬送する媒体の例は、フロッピー（登録商標）ディスク、ハードドライブ、ＣＤ−ＲＯＭ、電気媒体、光学媒体、無線媒体または他の好適な媒体に亘るデジタルおよびアナログ通信リンクを含むが、これらには限定されない。
【００３１】
インタロック状態のツリーデータストアを生成し、これにアクセスするためのシステムおよび方法
図２ａは、この発明の一実施例に従ったデータストアを含むインタロック状態のツリーの森からデータを生成しこのデータにアクセスするための例示的なシステム２００を示す。一実施例においてインタロック状態のツリーデータストアを生成するためのサブシステム２５０は、インタロック状態のツリージェネレータ２０２、データセット要素２０６の組および入力データ２０４を含み、そこから、例示的なインタロック状態のツリーデータストア２０８が生成される。代替的には、データセット要素２０６の組は入力データ２０４から得られてもよい。
【００３２】
インタロック状態のツリーデータストア２０８からの情報にアクセスするためのサブシステム２５１は、データ要求２１２を受取り、データ要求２１２を処理し、要求された情報を戻すための上述のインタロック状態のツリーデータストア２０８および／またはインタロック状態のツリーデータストアアクセス機構２１０を含み得る。
【００３３】
図２ｂは、インタロック状態のツリーデータベースから情報を生成し、この情報にアクセスするための例示的な方法を示す。ステップ２６０において、インタロック状態のツリーデータストアが、以下により十分に記載されるように生成される。ステップ２６２において、インタロック状態のツリーデータストアからの情報に対する要求が受取られる。ステップ２６４において、インタロック状態のツリーデータストアから情報が検索される。
【００３４】
インタロック状態のツリーデータストアの生成
たとえば、入力データ２０４が語（たとえば「CAT」）を表わす英数字のストリームを含むと仮定する。この場合、データセット要素２０６はアルファベットの文字の組であってもよく、デリミタまたは語の始め／語の終わり概念を表わす１つ以上の文字を含んでいてもよい。デリミタは、空白（「  」）、コンマ（「，」）およびピリオド（「．」）などであるがこれらに限定されない英数字を含み得る。
【００３５】
インタロック状態のツリーデータストア２０８は、いくつかのルート、いくつかの非ルートノード、および、非ルートノード間またはルートと非ルートノードとの間にいくつかのリンクまたは接続部を含む。インタロック状態のツリーデータストア２０８の各々のルートおよび非ルートノードは、１対のポインタ（ケースポインタおよび結果ポインタ）ならびに１対のリストポインタ（asCaseListを指すポインタおよびasResultListを指すポインタ）を含む。加えて、ルートは、値を表わすデータまたは値への参照を含み得る。
【００３６】
図３ａは例示的なインタロック状態のツリーデータストア２０８を示すより詳細な図で
ある。いくつかのノード、特に、当該例におけるルートノード３０２（BOT）および３１０（EOT）は開始インジケータまたは終了インジケータなどの概念を表わし、ルートノード３０４（A）、３０６（C）、３０８（T）はデータセット要素を表わすが、他のノード、特にノード３１２（BOT-C）、３１４（BOT-C-A）、３１６（BOT-C-A-T）および３１８（BOT-C-A-T-EOT）は、開始インジケータを表わすノードとデータセット要素を表わすノードとの、サブコンポーネントを表わすノードへのシーケンシャルな合成を表わし、当該サブコンポーネントは、サブコンポーネントが終了インジケータを表わすノードと組合されてエンドプロダクトを表わすノードが作成されるまで、データセット要素と組合わされて別のサブコンポーネントなどにされる。この場合、デリミタが後に続く一連の文字からの語のシーケンシャルな合成（すなわち、一連の文字「CAT」の後にデリミタ「  」または空白文字が続く）が取り込まれる。入力におけるデリミタはエンドプロダクトを識別するよう作用し得る。たとえば、語を区切る文字が１つの語の終わりと別の語の始めとをともに示すよう作用し得ることに留意されたい。たとえば、ストリング「CATS ARE」においては、「CATS」と「ARE」との間の空白文字は共に、語「CATS」の終わりと語「ARE」の始めとを示す。したがって、入力における空白文字などのデリミタは、作成されたノードにおける「BOT」などの開始インジケータまたは「EOT」などの終了インジケータに置換えられてもよい。これは以下により十分に記載されるとおりである。
【００３７】
ルートノード３０４、３０６および３０８などのノードはこの明細書中において基本ノードと称される。というのも、これらのノードはデータセット要素を表わし、分割可能なユニット（サブコンポーネントおよびエンドプロダクト）を構成する分割できないユニットを含むからである。３１２、３１４および３１６などのノードは、この明細書中においてはサブコンポーネントまたはサブコンポーネントノードと称される。というのも、これらのノードは、開始インジケータなどの概念インジケータとデータセット要素を表わすノードとの組合せ、またはサブコンポーネントとエンドプロダクトを含まないデータセット要素を表わすノードとの組合せ、またはサブコンポーネントとエンドプロダクトを含まない終了インジケータを表わすノードとの組合せを表わすからである。ノード３１８などのノードはエンドプロダクトを表わす。列挙された例においては、データセット要素は文字であり、サブコンポーネントは語を含まない文字の組合せを表わし、エンドプロダクトは語である。なお、ルートノードの組は、当該例においては、語の始めを示す「BOT」と、語の終わりを示す「EOT」とを含む。「BOT」および「EOT」が開始インジケータおよび終了インジケータを表わすが、この発明がこれに限定されないことが理解されるだろう。このようなインジケータのうちの一方またはその両方が無い場合、他のこのようなインジケータの使用が企図される。この発明の一実施例においては、ノードからルートノードへのリンクがEOT概念を表わしているので、エンドプロダクトはサブコンポーネントから識別可能である。
【００３８】
所与の例においては、入力の母集団が英数字の組であり、そこから語を得ることができるが、企図されたこの発明がそのようには限定されないことが理解されるだろう。たとえば、入力の母集団は、文字などのテキスト（ここから語を得ることができる）または語（ここから句または文を得ることができる）であり得るか、または代替的には、そこからゲノムを得ることができるアミノ酸、プロセスにおいて用いられる制限されたリソース、概念、画素セット、画像、音声、数、アナログ測定もしくは値、または、エンドプロダクトを生成するためにデジタル化され連続して組合され得る要素単位からなる他の如何なる好適な母集団であってもよい。典型的には、この発明の一実施例に従うと、要素単位は最適化されたシーケンスにおいて組合される。
【００３９】
上述のノードに加えて、インタロック状態のツリーデータストア２０８はまた、ノード間においてリンク３２０、３２２、３２４および３２６や、リンク３２８、３３０、３３２および３３４などのいくつかの接続またはリンクを含み得る。この発明の一実施例にお
けるリンク３２０、３２２、３２４および３２６ならびにリンク３２８、３３０、３３２および３３４は双方向であり、すなわち、ルートノード（BOT）とノード３１８（BOT-C-A-T-EOT）との間の経路はリンク３２０、３２２、３２４および３２６を介してトラバースされ得るか、または代替的には、リンク３２６、３２４、３２２および３２０を介してトラバースされ得る。リンク３２０、３２２、３２４および３２６（実線で図示）は、この明細書中においてはasCaseリンクと称される。リンク３２８、３３０、３３２および３３４（破線または点線で図示）は、この明細書中においてはasResultリンクと称される。同様に、この発明の一実施例においては、リンク３２８、３３０、３３２および３２４は、ノードC306におけるポインタがノードBOT-C３１２を指し、ノードBOT-C３１２におけるポインタがノードC306を指し、ノードA304におけるポインタがノードBOT-C-A-T314を指し、ノードBOT-C-A３１４におけるポインタがノードA３０４を指す、等々の点で、双方向である。
【００４０】
図３ｂは、インタロック状態のツリーデータストア２０８の例示的なノードに含まれる情報を示す。例示的なノード３４０はサブコンポーネントまたはエンドプロダクトを表わし得る。例示的なノード３４０は、サブコンポーネントまたはエンドプロダクト３４０の第１の部分を指すポインタ（この明細書中において「asCase」とも称されるケースを指すポインタ３４２）、サブコンポーネントまたはエンドプロダクト３４０の第２の部分を指すポインタ（この明細書中において「asResult」とも称される結果を指すポインタ３４４）、asResultList、すなわちノード３４０が第１の部分であるサブコンポーネントもしくはエンドプロダクトのリンクされたリスト、を指すポインタ３４６、および、asResultList、すなわちノード３４０が第２の部分である構成要素またはエンドプロダクトのリンクされたリスト、を指すポインタ３４８を含み得る。
【００４１】
例示的なノード３４１はルートノードを表す。例示的なノード３４１は、ヌルポインタ（この明細書中において「asCase」とも称されるケースを指すポインタ３４２）、第２のヌルポインタ（この明細書中において「asResult」とも称される結果を指すポインタ３４４）、asCaseList、すなわちルートノード３４１が第１の部分であるサブコンポーネントまたはエンドプロダクトのリンクされたリスト、を指すポインタ３４６、asResultList、すなわち、ルートノード３４１が第２の部分である構成要素またはエンドプロダクトのリンクされたリスト、を指すポインタ３４８、および、値３４９を含む。値３４９は実効値を含み得、状態または条件を表わし、値などを指すポインタまたは基準を含み得る。したがって、この発明の一実施例においては、開始インジケータが決してサブコンポーネントの第２の部分とはならないので開始インジケータ概念または条件を表わすルートノードはヌルasResultListを有することとなり、データセット要素が決してサブコンポーネントの第１の部分とはならないのでデータセット要素を表わすルートノードはヌルasCaseListを有することとなり、終了インジケータが決してサブコンポーネントの第１の部分とはならないので終了インジケータ概念または条件を表わすルートノードはヌルasCaseListを有することとなる。最後に、エンドプロダクトが次のレベルのためのデータセット要素として作用するので、より低いレベルのエンドプロダクトからなるルートノードはヌルasCaseListを有することとなる。
【００４２】
図３ｃは、インタロック状態のツリーデータストア２０８のasResultにリンクされたリストを示す。リンク３５０は、ノードC３０６のasResultList内のポインタをノードBOT-C３０２に設定することにより確立され、リンク３５２は、ノードA３０４のasResultList内のポインタをノードBOT-C-A３１４に設定することにより確立され、リンク３５４は、ノードT３０８のasResultList内のポインタをノードBOT-C-A-T３１８に設定することにより確立され、リンク３５６は、ノードEOT３１０のasResultList内のポインタをノードBOT-C-A-T-EOT３１８に設定することにより確立される。
【００４３】
図４は、メモリ１０４内の例示的なデータセット要素２０６のBOT、A〜Z、およびEOTの例示的なストレージを示す。認識できるように、この例では、BOTが位置０に記憶され、Aが位置５に記憶され、以下同様にしてEOTが位置１３５に記憶される。データセット要素の配置が単に例示的なものであり、データセット要素の任意の適切な配置が企図されることを理解されるであろう。図５ａ〜図５ｅは、インタロック状態のツリーデータストア２０８がこの発明の例示的な実施例で生成される際のインタロック状態のツリーデータストア２０８と、このインタロック状態のツリーデータストア２０８におけるノードの対応する内容とを示す。図６は、この発明の一実施例に従ってインタロック状態のツリーデータストア２０８を生成するための例示的なプロセス６００のフロー図である。
【００４４】
ここでステップ６０２において、同時に図４、図５および図６を参照すると、インタロック状態のツリーデータストアが初期化される。この発明の一実施例において、初期化は、作成されるべきインタロック状態のツリーデータストアのルートノードに「最新のポインタ」を設定するステップを含む。この発明の別の実施例において、初期化は、既存のインタロック状態のツリーデータストアのルートに「最新のポインタ」を設定するステップを含む。
【００４５】
加えて、データセット要素をメモリにロードして初期化することができる。この発明の一実施例において、ルートノード（図５ａのルートノードBOT３０２、A５３５ａ…EOT５５９ａ等）は、以下の値、すなわち、ケースポインタ＝ヌル、結果ポインタ＝ヌル、asCaseListを指すポインタ＝ヌル、asCaseList＝ヌル、asResultListを指すポインタ＝ヌル、asResultList＝ヌル、および、データセット要素か、概念／条件インジケータか、または、それに対する表現を指す値で初期化される。
【００４６】
この時点で、インタロック状態のツリーデータストア、たとえば、この発明の一実施例に従ったインタロック状態のツリーデータストア５００ａは、この場合、語の始まりを示す単一のノード３０２（BOT）を含み得る。ブロック図５０２ａのノード３０２は、１対のポインタ（ヌルに初期化されたケースポインタ５０４ａおよび結果ポインタ５０６ａ）と、１対のリストポインタ（ヌルに初期化されたasCaseListを指すポインタおよびasResultListを指すポインタ）と、値（ここではBOTと記述される、何らかの値に初期化された値５１１ａ）とを含む。図５およびブロック図５０２ａにおいて理解し易くするために、図５０２ｂ〜図５０２ｅ内および図面全体におけるセル５０８ａおよび類似のセルは、インタロック状態のツリーデータストアにおいて、関連付けられたasCaseListを指すポインタを実際には示すものの、その代わりに、関連付けられたasCaseListの最新の内容を示す。同様に、図５０２ｂ〜図５０２ｅ内のセル５１０ａおよび類似のセルは、インタロック状態のツリーデータストアにおいて、関連付けられたasResultListを指すポインタを実際には示すものの、その代わりに、関連付けられたasResultListの最新の内容を示す。
【００４７】
asCaseLists（asCaseList５０８ａ等）およびasResultLists（asResultList５１０ａ等）は、リンクされたリストして実現され得る。別の実施例において、asCaseLists（asCaseList５０８ａ等）およびasResultLists（asResultList５１０ａ等）は、以下のものに限定されないがアレイ等に対し、設定可能なサイズの連続する記憶場所のブロックとして割当てられ、asCaseListを指すポインタが、asCaseListメモリブロックの開始位置に設定され、asResultListを指すポインタが、asResultListメモリブロックの開始位置に設定される。
【００４８】
ステップ６０４において、入力が受信される。この発明の一実施例において、「最新のポインタ」の値は「以前のポインタ」に設定され、「最新のポインタ」は、この入力に設定される。所定の例において、受信した入力は「C」である。ステップ６０４において、この入力の妥当性が検査される。所定の例において、このことは、「C」が有効なデータ
セット要素であるかどうか確認するステップを含む。「C」は実際に有効な要素であり、メモリ１０４内の位置１５に位置付けられる。
【００４９】
ステップ６０６において、ノードがそれまでに存在していない場合、インタロック状態のツリーデータストア内にノードが作成されて初期化され、メモリ内の或る位置に記憶される。この例では、インタロック状態のツリーデータストア２０８内にノード３１２が作成されてBOT-Cを表わし、ノードBOT-C３１２のケースポインタ、結果ポインタ、asCaseListを指すポインタ、asCaseList、asResultListを指すポインタ、およびasResultListがヌルに初期化され、BOT-Cはメモリ１０４の位置１４０に記憶される。
【００５０】
ステップ６０８において、この発明の一実施例に従い、ステップ６０６で作成されたノードに対するリンクが形成される。新規のノードは、新規のノードのケースポインタを以前のポインタの値に設定し、かつ、新規のノードの結果ポインタを最新のポインタの値に設定することによって規定される。図５ｂのインタロック状態のツリーデータストア５００ｂは、リンクの作成後のインタロック状態のツリーデータストア２０８を示す。リンクが作成された後のノードBOT３０２、C３０６、およびBOT-C３１２の内容をブロック図５０２ｂに示す。サブコンポーネントBOT-C３１２は、ノードBOT３０２とノードC３０６とのシーケンシャルな組合せにより作成される。したがって、ケースポインタおよび結果ポインタに対して以下の値が設定される。すなわち、ノードBOT-C３１２のケースポインタ５２０ｂは０に、すなわちメモリ１０４内のノードBOT３０２の位置に設定され、ノードBOT-C３１２の結果ポインタ５２２ｂは１５に、すなわちメモリ１０４内の基本ノードC３０６の位置に設定される。
【００５１】
この発明の一実施例では、新規のノードから、この新規のノードが導出されたノードにリンクを作成することに加え、asCaseListおよびasResultListのリンクが作成される。asCaseListおよびasResultListのリンクの作成は、新規のノードが導出されたノードのリンクされたリスト、すなわちasCaseListおよびasResultListに対し、新規のノードの位置を指すポインタを追加することによって行なわれる。これらのポインタは、リストの終わりもしくはリストの始めに追加されてよく、または、リスト内のどこかに挿入されてよい。加えて、リストの数を維持することができる。たとえば、ノードのasCaseListは、最も頻繁にアクセスされる順序にポインタが維持されている、順序付けされたリストに加え、リンクされたリストの終わりにポインタが追加されるシーケンシャルなリストを含み得る。この所定の例は、１つの順序付けされたリストおよび１つのシーケンシャルなリストを例として挙げているが、この発明はそれに限定されず、リストの任意の組合せおよび数が、この発明の範囲内で企図されることが理解されるであろう。順序付けされたリストは、最後の更新、最後のアクセス、更新もしくはアクセスの頻度、または、他の任意の適切な順序付けの規則により、順序付けることができる。
【００５２】
新規のノードへのリンクが作成される。すなわち、新規のノードを指すポインタが、以前のポインタのasCaseListおよび最新のポインタのasResultListに追加される。この例では、ノードBOT-C３１２のCaseポインタ５２０ｂをノードBOT３０２の位置、すなわち位置０（ブロック図５０３ｂのリンク３２０ａ）に設定することと、ノードBOT-C３１２の位置、すなわち位置１４０を指すポインタをasCaseList５０８ｂに追加することによってノードBOT３０２のasCaseList５０８ｂ（リンク３２０ｂ）を更新することとにより、双方向リンク３２０が生成される。Caseポインタ５２０ａが設定される。なぜなら、ノードBOT３０２がノードBOT-C３１２の定義ノードの１つであるためである。asCaseList５０８ｂが更新される。なぜなら、ノードBOT３０２が、ノードBOT-C３１２がそこから作成された２つのノードのうちの第１のものである、ノードBOT-C３１２の合成で用いられるためである。asCaseList５０８ｂは現時点でヌル集合を含む（すなわち、asCaseList５０８ｂは空である）。ノードBOT-C３１２がメモリ１０４内の位置１４０に位置付けられているた
め、asCaseList５０８ｂはヌルから１４０に更新される。asCaseList５０８ｂが非ヌル集合を含んでいたならば、ノードBOT-C３１２の位置１４０は、上で論じた方法の１つにより、asCaseList５０８ｂに追加されていたであろう。
【００５３】
同様に、ノードBOT-C３１２のResultポインタ５２２ｂをノードCの位置、すなわち位置１５に設定すること（ブロック図５０３ｂのリンク３２８ａ）と、ノードBOT-C３１２の位置を指すポインタをasResultList５１８ｂに追加することによって基本ノードC３０６のasResultList５１８ｂ（リンク３２８ｂ）を更新することとにより、双方向リンク３２８が生成される。Resultポインタ５２２ｂが設定される。なぜなら、ノードC３０６がノードBOT-C３１２の定義ノードの１つであるためである。asResultList５１８ｂが更新される。なぜなら、ノードC３０６が、ノードBOT-C３１２がそこから形成された２つのノードのうちの第２のものを構成するためである（したがって、リンク３２８ｂはasResultリンクと呼ばれる）。asResultList５１８ｂは現時点でヌル集合を含む（すなわち、asResultList５１８ｂは空である）。ノードBOT-C３１２がメモリ１０４内の位置１４０に位置付けられているため、asResultList５１８ｂはヌルから１４０に更新される。asResultList５１８ｂが非ヌル集合を含んでいたならば、ノードBOT-C３１２の位置１４０は、上で論じた方法の１つにより、asResultList５１８ｂに追加されていたであろう。
【００５４】
この時点で、図５ｂに示すデータストア、すなわち、インタロック状態のツリーデータストア５００ｂが作成される。同じ構造が、図５ｂのブロック図５０３ｂにおいてより詳細に示される。リンク３２０ｂが、ノードBOT-C３１２の位置を指すポインタを表わし、asCaseList５０８ｂにおいてノードBOT３０２に対する第１の要素であることと、リンク３２８ｂがノードBOT-C３１２の位置を指すポインタを表わし、ノードC３０６のasResultList５１８ｂにおける第１の要素であることとに注目されたい。リンク３２０ａは、ノードBOT-C３１２からその第１の部分、すなわちノードBOT３０２を指すポインタを表わし、リンク３２８ａは、ノードBOT-C３１２からその第２の部分、すなわちノードC３０６を指すポインタを表わす。
【００５５】
ステップ６１０において、さらなる入力が存在するか否かが判断される。この場合、さらなる入力が存在するため、処理はステップ６０４に戻る。ステップ６０４において入力が受信される。所定の例において、受信した入力は「A」である。ステップ６０４において、入力の妥当性が検査される。所定の例において、このことは、「A」が有効かつ基本のデータセットであるかどうかを確認するステップを含む。「A」は実際に有効な要素であり、メモリ１０４内の位置５に位置付けられる。
【００５６】
ステップ６０６において、ノードがそれまでに存在していない場合、インタロック状態のツリーデータストア内にノードが作成されて初期化され、メモリ内の或る位置に記憶される。この例では、インタロック状態のツリーデータストア２０８内のノード３１４が作成されてBOT-C−Aを表わし、ノードBOT-C-A３１４のケースポインタ、結果ポインタ、asCaseListを指すポインタ、asCaseList、asResultListを指すポインタ、およびasResultListがヌルに初期化され、ノードBOT-C-A３１４がメモリ１０４内の位置１４５に記憶される。
【００５７】
ステップ６０８において、この発明の一実施例に従い、ステップ６０６で作成されたノードに対するリンクが作成される。図５ｃは、リンクが作成された後のインタロック状態のツリーデータストア５００ｃを示す。ノードBOT３０２、C３０６、A３０４、BOT-C３１２およびBOT-C-A３１４の内容をブロック図５０２ｃに示す。サブコンポーネントBOT-C-A３１４は、ノードBOT-C３１２とノードA３０４とのシーケンシャルな組合せにより作成される。したがって、ケースポインタおよび結果ポインタに対して以下の値が設定される。すなわち、ノードBOT-C-A３１４のケースポインタ５２８ｃは１４０に、すなわちメモリ
１０４内の基本ノードBOT-C３１２の位置に設定され（リンク３２２ａ）、ノードBOT-C-A３１４の結果ポインタ５３０ｃは５に、すなわちメモリ１０４内の基本ノードA３０４の位置に設定される（リンク３３０ａ）。
【００５８】
双方向リンク３２２は、Caseポインタ５２８ｃを１４０に設定し（リンク３２２ａ）、かつ、メモリ１０４内のノードBOT-C-A３１４の位置を指すポインタをノードBOT-C３１２のasCaseList５２４ｃに追加する（リンク３２２ｂ）ことにより生成される。asCaseList５２４ｃが更新される。なぜなら、ノードBOT-C３１２が、ノードBOT-C-A３１４がそこから作成された２つのノードのうちの第１のものを構成するためである。ノードBOT-C３１２のasCaseList５２４ｃは、リンク３２２ｂが作成される前にヌル集合を含んでいた（すなわち、asCaseList５２４ｃは空であった）。ノードBOT-C-A３１４がメモリ１０４内の位置１４５に見出されるため、asCaseList５２４ｃはヌルから１４５に更新される。asCaseList５２４ｃが非ヌル集合を含んでいたならば、ノードBOT-C-A３１４の位置１４５は、上で論じた方法の１つにより、asCaseList５２４ｃに追加されていたであろう。
【００５９】
同様に、ノードBOT-C-A３１４のResultポインタ５３０ｃを５に設定することと、ノードBOT-C-A３１４の位置を指すポインタをノードA３０４のasResultList５４２ｃに追加することによって基本ノードA３０４のasResultList５４２ｃを更新することとにより、双方向リンク３３０が生成される。asResultList５４２ｃが更新される。なぜなら、ノードA３０４が、ノードBOT-C-A３１４がそこから作成された２つのノードのうちの第２のものを構成するためである。asResultList５４２ｃは、リンク３３０ｂが作成される前にヌル集合を含んでいた（すなわち、asResultList５４２ｃは空であった）。ノードBOT-C-A３１４がメモリ１０４内の位置１４５に位置付けられているため、asResultList５４２ｃはヌルから１４５に更新される。asResultList５４２ｃが非ヌル集合を含んでいたならば、ノードBOT-C-A３１４の位置１４５は、上で論じた方法の１つにより、asResultList５４２ｃに追加されていたであろう。
【００６０】
この時点で、図５ｃに示すデータストア、すなわち、インタロック状態のツリーデータストア５００ｃが形成される。同じ構造が、図５ｃのブロック図５０３ｃに、より詳細に示される。リンク３２２ｂがノードBOT-C-A３１４の位置を指すポインタを表わし、位置１４５がasCaseList５２４ｃにおいてノードBOT-C３１２に対する第１の要素であることと、リンク３３０ｂがノードBOT-C-A３１４の位置を指すポインタを表わし、１４５がasResultList５４２ｃにおいてノードA３０４に対する第１の要素であることとに注目されたい。リンク３２２ａは、ノードBOT-C-A３１４からその第１の部分、すなわちノードBOT-C３１２を指すポインタを表わし、リンク３３０ａは、ノードBOT-C-A３１４からその第２の部分、すなわちノードA３０４を指すポインタを表わす。
【００６１】
ステップ６１０において、さらなる入力が存在するか否かが判定される。この場合、さらなる入力が存在するため、処理はステップ６０４に戻る。ステップ６０４において、入力が受信される。所定の例において、受信された入力は「T」である。ステップ６０４において入力の妥当性が検査される。所定の例において、このことは、「T」が有効なデータセット要素であるかどうかを確認するステップを含む。「T」は実際に有効なデータセット要素であり、メモリ１０４内の位置１００に位置付けられる。
【００６２】
ステップ６０６において、ノードがこれまでに存在していない場合、インタロック状態のツリーデータストア内にノードが作成されてメモリ内の或る位置に初期化され、記憶される。この例では、インタロック状態のツリーデータストア２０８内にノード３１６が作成されてノードBOT-C-A-T３１６を表わし、ケースポインタ、結果ポインタ、asCaseListを指すポインタ、asCaseList、asResultListを指すポインタ、およびasResultListがヌルに初期化され、ノードBOT-C-A-T３１６がメモリ１０４内の位置１５０に記憶される。
【００６３】
ステップ６０８において、ステップ６０６で作成されたノードに対するリンクが作成される。図５ｄは、リンクが作成された後のインタロック状態のツリーデータストア５００ｄを示す。ノードBOT３０２、C３０６、A３０４、T３０８、BOT-C３１２、BOT-C-A３１４、およびBOT-C-A-T３１６の内容をブロック図５０２ｄに示す。サブコンポーネントBOT-C-A-T３１６は、ノードBOT-C-A３１４とノードT３０８とのシーケンシャルな組合せにより作成される。したがって、ケースポインタおよび結果ポインタに対する以下の値が、ノードBOT-C-A-T３１６に対して設定される。すなわち、ケースポインタ５４４ｄは１４５に、すなわちメモリ１０４内のノードBOT-C-A３１４の位置に設定され、結果ポインタ５４６ｄは１００に、すなわちメモリ１０４内の基本ノードT３０８の位置に設定される。
【００６４】
ケースポインタ５４４ｄを１４５に設定し、かつ、メモリ１０４内のノードBOT-C-A３１４（位置１５０）の位置を指すポインタをノードBOT-C-A３１４のasCaseList５３２ｄに追加することにより、双方向リンク３２４が生成される。asCaseList５３２ｄが更新される。なぜなら、ノードBOT-C-A３１４が、ノードBOT-C-A-T３１６がそこから作成された２つのノードのうちの第１のものを構成するためである。ノードBOT-C-A３１４のasCaseList５３２ｄは、リンク３２４が作成される前にヌル集合を含んでいた。BOT-C-A-Tがメモリ１０４内の位置１５０に見出されるため、asCaseList５３２ｄは、ヌルから１５０に更新される。ノードBOT-C-A３１４のasCaseList５３２ｄがデータを含んでいたならば、１５０は、上で概略的に説明した方法の１つにより、リストに追加されていたであろう。
【００６５】
同様に、結果ポインタ５４６ｄを１００に設定することと、ノードBOT-C-A-T３１６の位置を指すポインタをasResultList５５８ｄに追加することによって基本ノードT３０８のasResultList５５８ｄを更新することとにより、双方向リンク３３２が生成される。asResult List５５８ｄが更新される。なぜなら、ノードT３０８が、ノードBOT-C-A-T３１６がそこから作成された２つのノードのうちの第２のものを構成するためである。基本ノードT３０８のasResultList５５８は、リンク３３２が作成される前にヌル集合を含んでいたため、このヌル集合は１５０に、すなわちメモリ１０４内のノードBOT-C-A-T３１６の位置に置き換えられる。asResultList５５８ｄがデータを含んでいたならば、１５０は、上で概略的に説明した方法の１つにより、リストに追加されていたであろう。
【００６６】
この時点で、図５ｄに示すデータストア、すなわち、インタロック状態のツリーデータストア５００ｄが作成される。インタロック状態のツリーデータストア５００ｄのより詳細な表示、図５ｃに示されるその類似物、インタロック状態のツリーデータストア５００ｃに対するブロック図５０３ｃが示され得ることを、当業者は認識するであろう。
【００６７】
ステップ６１０において、さらなる入力が存在するか否かが判定される。この場合、さらなる入力が存在するため、プロセスはステップ６０４に戻る。ステップ６０４において入力が受信される。所定の例において、受信された入力は「  」または空白文字である。ステップ６０４において、入力の妥当性が検査される。所定の例において、このことは、空白文字が有効かつ基本のデータセットであるかどうかを確認するステップを含む。空白文字は実際に有効な要素であり、この場合、語「CAT」の終わりを示すデリミタである。したがって、この発明の一実施例において、位置１３５に位置付けられたノードEOT３１０はサブコンポーネントBOT-C-A-T３１６に追加され、この場合は語であるエンドプロダクトまたはモナドを作成する。
【００６８】
ステップ６０６において、ノードがこれまでに存在していない場合、インタロック状態のツリーデータストア内にノードが作成されて初期化され、メモリ内の或る位置に記憶される。この例において、インタロック状態のツリーデータストア２０８内のノード３１８が作成されてノードBOT-C-A-T-EOT３１８を表わし、ノードBOT-C-A-T-EOT３１８のケース
ポインタ、結果ポインタ、asCaseListを指すポインタ、asCaseList、asResultListを指すポインタ、およびasResultListがヌルに初期化され、ノードBOT-C-A-T-EOT３１８は、たとえばメモリ１０４内の位置１５５に記憶される。
【００６９】
ステップ６０８では、ステップ６０６において作成されたノードに対するリンクが作成される。図５ｅは、リンクが作成された後のインタロック状態のツリーデータストア５００ｅを示す。リンクが作成された後のノードBOT３０２、C３０６、A３０４、T３０８、EOT３１０、BOT-C３１２、BOT-C-A３１４、BOT-C-A-T３１６、およびBOT-C-A-T-EOT３１８の内容を、ブロック図５０２ｅに示す。エンドプロダクト３１８（BOT-C-A-T-EOT）は、ノードBOT-C-A-T３１６とノードEOT３１０とのシーケンシャルな組合せにより作成される。したがって、ノードBOT-C-A-T-EOT３１８に対するケースポインタおよび結果ポインタに対する以下の値が設定される。すなわち、エンドプロダクトBOT-C-A-T-EOT３１８のケースポインタ５６８ｅは１５０に、すなわち、メモリ１０４内のノードBOT-C-A-T３１６の位置に設定され、エンドプロダクトBOT-C-A-T-EOT３１８の結果ポインタ５７０ｅは１３５に、すなわちメモリ１０４内の基本ノードEOT１３５の位置に設定される。
【００７０】
エンドプロダクトBOT-C-A-T-EOT３１８のCaseポインタ５６８ｅを１５０に設定することと、メモリ１０４内のノードBOT-C-A-T３１６の位置を指すポインタを、ノードBOT-C-A-T３１６のasCaseList５４８ｅに追加することとにより、双方向リンク３２６が生成される。asCaseList５４８ｅが更新される。なぜなら、ノードBOT-C-A３１４が、ノードBOT-C-A-T３１６がそこから形成された２つのノードのうちの第１のものを構成するためである。ノードBOT-C-A-T３１６のasCaseList５４８ｅは、リンク３３４が作成される前にヌル集合を含んでいた（すなわち、asCaseList５４８ｅは空であった）。ノードBOT-C-A-T３１６がメモリ１０４内の位置１５５に見出されるため、ノードBOT-C-A-T３１６のasCaseList５４８ｅは、ヌルから１５５に更新される。asCaseList５４８ｅが非ヌル集合を含んでいたならば、ノードBOT-C-A-Tの位置１５５は、上で論じた方法の１つにより、asCasseList５４８ｅに追加されていたであろう。
【００７１】
同様に、エンドプロダクトBOT-C-A-T-EOT３１８のResultポインタ５７０ｅを１３５に設定することと、ノードBOT-C-A-T-EOT３１８の位置を指すポインタをノードEOT３１０のasResult List５６６ｅに追加することによってノードEOT３１０のasResultList５６６ｅを更新することとにより、双方向リンク３３４が生成される。asResultList５６６ｅが更新される。なぜなら、ノードEOT３１０が、ノードBOT-C-A-T-EOT３１８がそこから作成された２つのノードのうちの第２のノードを構成するためである（したがって、リンク３３４はasResultリンクと呼ばれる）。asResultList５６６ｅは、リンク３３４が作成される前にヌル集合を含んでいた（すなわち、asResultList５６６ｅは空であった）。ノードBOT-C-A-T-EOT３１８がメモリ１０４内の位置１５５に位置付けられているため、asResultList５６６ｅはヌルから１５５に更新される。asResultList５６６ｅが非ヌル集合を含んでいたならば、ノードBOT-C-A-T-EOT３１８の位置１５５は、上で論じた方法の１つにより、asResultList５６６ｅに追加されていたであろう。
【００７２】
この時点で、図５ｅに示すデータストア、すなわちインタロック状態のツリーデータストア５００ｅが作成される。インタロック状態のツリーデータストア５００ｅのより詳細な表示、図５ｃに示されるその類似物、およびインタロック状態のツリーデータストア５００ｃに対するブロック図５０３ｃが示され得ることを、当業者は認識するであろう。
【００７３】
ステップ６１０において、さらなる入力が存在するか否かが判定される。この場合、さらなる入力が存在しないため、プロセスはステップ６１２で終了する。
【００７４】
次に、入力２０４が「CAT」ではなく「CAT TAB」を含むものと考えられたい。上述のプ
ロセスが辿られる。「CAT」までの入力が処理されると、図５ｅのインタロック状態のツリーデータストア５００ｅが作成される。しかしながら、ステップ６１０においてさらなる入力が存在するためにプロセスは続行し、結果的に図７ａのインタロック状態のツリーデータストア７００ａを生じる。対応するノードBOT３０２、C３０６、A３０４、T３０８、B７１８、EOT３１０、BOT-C３１２、BOT-C-A３１４、BOT-C-A-T３１６、BOT-C-A-T-EOT３１８、BOT-T７０３、BOT-T-A７０５、BOT-T-A-B７０７、およびBOT-T-A-B-EOT７０９の内容を、ブロック図７０２ａに示す。ノードBOT-T７０３、BOT-T-A７０５、BOT-T-A-B７０７、およびBOT-T-A-B-EOT７０９がインタロック状態のツリーデータストア５００ｅに追加され、インタロック状態のツリーデータストア７００ａを作成することに注目されたい。
【００７５】
このプロセスにおいて、asCaseリンク７０１、７０４、７０６、および７０８が作成され、asResultリンク７１０、７１２、７１４、および７１６が作成された。ノードBOT-T７０３のasCaseポインタ７２０ｆは０に、すなわちノードBOT３０２の位置に設定される。ノードBOT-T７０３のasResultポインタ７２２ｆは１００に、すなわちノードT３０８の位置に設定される。ノードBOT-T-A７０５のasCaseポインタ７２８ｆは１７０に、すなわちノードBOT-T７０３の位置に設定される。ノードBOT-T-A７０５のasResultポインタ７３０ｆは５に、すなわちノードA３０４の位置に設定され、以下同様である。
【００７６】
asCaseリンク７０１は、ノードBOT３０２のasCaseList５０８ｆに１７０を、すなわちBOT-T７０３の位置を追加することによって作成され、それによってasCaseList５０８ｆは、１４０、すなわちBOT-C３１２の位置と、１７０、すなわちBOT-T７０３の位置との両方を含む。asCaseリンク７０４は、ノードBOT-T７０３のasCaseList７２４ｆに１７５を、すなわちBOT-T-Aの位置を追加することによって作成される。asCaseリンク７０６は、ノードBOT-T-A７０５のasCaseList７３２ｆに１８０を、すなわちBOT-T-A-Bの位置を追加することによって作成され、以下同様である。
【００７７】
asResultリンク７１０は、ノードT３０８のasResultList５５８ｆに１７０を、すなわちBOT-T７０３の位置を追加することによって作成され、それによってasResultList５５８ｆは、１５０、すなわちノードBOT-C-A-Tの位置と、１７０、すなわちBOT-T７０３の位置との両方を含む。asResultリンク７１２は、ノードA３０４のasResultList５４２ｆに１７５を、すなわちBOT-T-Aの位置を追加することによって作成され、それによってasResultList５４２ｆは、１４５、すなわちノードBOT-C-A３１４の位置と、１７５、すなわちBOT-T-Aの位置との両方を含む。asResultリンク７１４は、ノードB７１８のasResultList７４２ｆに１８０を、すなわちノードBOT-T-A-B７０７の位置を追加することによって作成される。ノードB７１８のasResultList７４２ｆが以前にヌルであったため、ノードB７１８のasResultList７４２ｆは、１８０、すなわちノードBOT-T-A-B７０７の位置のみを含む。asResultリンク７１６は、ノードEOT３１０のasResultList５６６ｆに１８５を、すなわちBOT-T-A-B−EOT７０９の位置を追加することによって作成され、それによってasResultList５６６ｆは、１５５、すなわちノードBOT-C-A-T-EOT３１８の位置と、１８５、すなわちBOT-T-A-B-EOT１８５の位置との両方を含む。
【００７８】
次に、入力２０４が「CAT」ではなく「CATS CATHODE」を含むものと考えられたい。上述のプロセスが辿られる。入力「CAT」が処理されると、図５ｄのインタロック状態のツリーデータストアが作成される。ステップ６１０において、さらなる入力が見出されるため、プロセスは続行する。入力「CATS」を処理した後に、図８のインタロック状態のツリーデータストア８００ａが生成される。さらなる入力が見出される。「CATHODE」が処理されるのに伴い、BOT-C、BOT-C-A、およびBOT-C-Aに対する新規のノードは作成されない。なぜなら、それらが既に存在しているためである。さらなる入力「SCATHODE」が処理され、図８のインタロック状態のツリーデータストア８００ｂを生じる。結果的に得られた
ツリーが自己組織化しているため、生じるインタロック状態のツリーデータストアの構造が、受信した入力によって規定され、受信した入力に従属することを、当業者は認識するであろう。
【００７９】
次に、入力２０４が、「CAT」ではなく「CATS ARE FURRY.」を含むものと考えられたい。図９ａは、この発明の一実施例において生成されたインタロック状態のツリーデータストア９００を示す。入力内にインジケータ、たとえばこの例では、句の終わりまたは文の終わりのインジケータ（「FURRY」の後のピリオド等）が存在することにより、１つのレベルのエンドプロダクト（BOT-C-A-T-EOT９０８、BOT-A-R-E-EOT９０６、BOT-F-U-R-R-Y-EOT９０４）が組合さって次のレベルのサブコンポーネントになり得る。すなわち、１つのレベル（レベル１  ９１０等）のエンドプロダクトノード（「CATS」、「ARE」、および「FURRY」等の語）が、次のレベル（レベル２  ９１２等）のデータセット要素を表わすルートノードとなり得る。したがって、ノード「BOT-CATS-ARE-FURRY-EOT」９０２は、文「CATS ARE FURRY.」を表わす単一のノードである。
【００８０】
この発明の一実施例において、より高いレベルのデータセット要素を表わすノードは、データか、またはデータもしくは概念の表現を含まない。すなわち、より高いレベルのデータセット要素を表わす基本ルートノードは、より低いレベルのノードを指すポインタのみを含む。たとえば図９ｂは、図９ａにおけるいくつかのノードの内容を示す。レベル１
９１０のノードBOT-C-A-T-S-EOTが、レベル２  ９１２の基本ルートノードとして使用されていること（ノード９０８のasResultList９１４が３００を、すなわちノードBOT-CATS９１６の位置を含み、ノードBOS-CATS９１６のasResultポインタ９１８が２００を、すなわちノードBOT-C-A-T-S-EOT９０８の位置を含む）、そして以下同様であることに注目されたい。
【００８１】
任意の適切な数のレベルが生成され得る。たとえば、テキストの場合、レベルは、文字、語、文、段落、章、本、ライブラリ等を表わし得る。例示的な図面では２つのレベルのインタロック状態のツリーデータストア（レベル１  ９１０およびレベル２  ９１２）が示されているが、この発明がそれに限定されないことが理解されるであろう。任意の数のレベルのインタロック状態のツリーデータストアを構築することができる。この例の母集団がテキストであり、すなわち、文字の組合せが語（１つのレベルのエンドプロダクト）を形成するため、この発明のこの実施例における語の組合せの結果は、句または文（別のレベルのエンドプロダクト）である。文を組合せて段落を形成することができ、段落を組合せて章または節等を形成することができる。
【００８２】
入力の母集団に依存して、エンドプロダクトが、語、句、文等以外のエンティティを表わし得ることが、さらに認識されるであろう。多くの例の中から１つを提示すると、入力が、染色体を構成するアミノ酸の配列である場合、１つのエンドプロダクトは、遺伝子または対立遺伝子を表わし得る。
【００８３】
次に、入力２０４が以下のもの、すなわち、
ビル  火曜日  ４０  販売  PA（Bill Tuesday 40 sold PA）
ビル  月曜日  １０３  販売  NJ（Bill Monday 103 sold NJ）
ビル  月曜日  １００  試用  PA（Bill Monday 100 trial PA）
トム  月曜日  ８０  販売  PA（Tom Monday 80 sold PA）
トム  月曜日  １３  試用  NJ（Tom Monday 13 trial NJ）
等のデータ記録を含むものと考えられたい。
【００８４】
この発明の一実施例において、データセット要素は、以下のものに限定されないが空白文字等のデリミタにより分離された情報のフィールドで構成される。一実施例において、
データセット要素は入力から導出されるが、上述のとおり、この発明がそれに限定されないことを理解されるであろう。これまでに入力データ内に生じるデータセット要素は、販売員の名前（ビルおよびトム）、曜日（月曜日、火曜日）、品目数（４０、１０３、１００、８０、１３）、状況（販売、試用）、および州（PA、NJ）である。この発明の一実施例において、図１０のインタロック状態のツリーデータストア１０００は、この入力から生じる。図１０では、空間上の理由から、ノードの第１の部分を示していない。たとえば、ノード１００２は「ビル」と表記されているが、ノード１００２は実際に「BOT-Bill」を表わす。ノード１００２は「火曜日」と表記されているが、ノード１００４は実際に「BOT−ビル−火曜日」を表わし、以下同様である。
【００８５】
インタロック状態のツリーデータストアからの情報へのアクセス
インタロック状態のツリーデータストア内に記憶された情報にアクセスするための方法を図１１に示す。ステップ１１０２において、インタロック状態のツリーデータストアから検索されるべき情報の要求が受信される。検索されるべき情報の要求は、インタロック状態のツリーアクセス機構により処理され得る形に変換され得る。ステップ１１０４では、示されたノードにアクセスする。ステップ１１０６では、適切なasCaseListおよび／またはasResultListを検索する。ステップ１１０８では、適切なasCaseListまたはasResultList内のポインタを辿り、所望の情報を検索する。ステップ１１１０では、要求された情報が収集されて返却される。
【００８６】
たとえば、図７ａを再び参照すると、asResultリンク３２８、３３０、３３２、３３４、７１０、７１２、７１４、および７１６を含むデータストア７００ａを用いて、たとえば「どのノードが文字「A」を含むか？」、「どの文字が「A」に先行する／後行するか？」、「どの（またはいくつの）語が文字「A」を含むか？」、「どの語が文字「A」および「T」の両方を含むか？」、「どの語が、「T」が先行する「A」を含むか？」、および他の無数の質問等の、内容の質問に対する答えを求めることができる（理解し易くするために、この例示的な質問では特定の文字が指定されているが、その代わりに任意のデータセット要素または単位群を用いてよいことが理解されるであろう）。
【００８７】
たとえば、この発明の一実施例において、所望のデータセット要素を含むノードおよびエンドプロダクトは、そのデータセット要素を表わす特定のノードのasResultListに含まれるポインタを辿ることによって求めることができる。asResultListにアクセスし、リスト内の各ポインタを辿り、そのノードに関連付けられたasCaseブランチに至る。エンドプロダクトが所望される場合、asCaseブランチツリーを辿ってブランチの葉ノードに至る。
【００８８】
この発明の一実施例において、情報の要求は、制約および／または焦点を指定する形をとる。たとえば、情報の要求は、制約のリストの形をとり得る。制約のリストは、入れ子状にされるか、または別個にされ得る。この発明の一実施例では、列挙された各制約のasResultListが見出され、各制約についての各asResultList内の各ノードに対するブランチが見出され、これらのブランチを辿ってそれらのエンドプロダクトに至り、各制約についての各asResultList内の各ブランチに対するエンドプロダクトの共通部分が選択される。入れ子状の制約はまず、データストアを制約して１組のデータを検索することによって見出される。この１組のデータは、さらに制約されるべきデータの組として次に用いられ、以下同様である。
【００８９】
この発明の一実施例において、焦点は、返却される情報を決定する。データセット要素が文字であり、レベル１のエンドプロダクトが語を含み、レベル２のエンドプロダクトが文を含み、指定された制約が特定の文字である２レベルのデータストアの場合、焦点を「語」に指定することによって語のみが返却されることになり、焦点を「文」に指定することによって文のみが返却されることになる。第１のレベルからエンドプロダクトを検索す
ることにより、語が返却される。第２のレベルからエンドプロダクトを検索することにより、文が返却される。一実施例では、文を検索するために、各語のasResultListを次のレベルまで辿り、指定されたブランチを辿ってそのエンドプロダクトに至り、指定された文字を含む文を検索する。
【００９０】
一実施例では、レベル開始インジケータをそのルートとして有するツリーを辿ることにより、制約で始まるすべてのエンドプロダクトを見出すことができる（たとえば、指定された文字で始まるすべての語を見出すことができる）。同様に、指定された制約か、または指定された位置内の指定された制約を有するすべてのエンドプロダクト（たとえば、それらの中に特定の文字を有するすべての語、または指定された列内に指定された文字を有するすべての語）を見出すことができる。同様に、レベル終了インジケータをルートとして有するツリーを辿ることにより、指定された制約で終了するすべてのエンドプロダクト（たとえば、指定された文字で終了するすべての語）を見出すことができる。複数の制約および／または焦点を指定することができる。
【００９１】
たとえば、文字（文字「B」等）のデータセット要素を含むツリーのasCaseブランチの第１のノードが所望されているものと仮定されたい。一実施例では、このデータ要素を表わす基本ルートノード（ノードB７１８等）をメモリから検索し、そのasResultList（asResultList７４２ｆ等）にアクセスし、いくつかのサブコンポーネントと基本ルートノード（ノードB７１８等）との組合せにより作成されたノードの位置が返却される。asResultList内のノードがアクセスされる。この例では、位置１８０がアクセスされる。この位置１８０は、ノードBOT-T-A-B７０７を保持する。したがって、ノードBOT-T-A-B７０７は、文字「B」の表示を含むインタロック状態のツリーデータストア７００ａ内のノードである。形成されたエンドプロダクトを見出すために、asCaseブランチ（たとえばこの例において、ノードBOT-T７０３、ノードBOT-T-A７０５、ノードBOT-T-A-B７０７、およびノードBOT-T-A-B−EOT７０９を含むブランチ）は、検索されたasCaseListがヌルになるまで、アクセスしたノードのasCaseListを繰り返し検索することにより辿られる。たとえば、データセット要素B７１８を含む語が「TAB」であることを判定するために、ノードBOT-T-A-B７０７のasCaseList７４０ｆにアクセスして位置１８５を検索する。位置１８５の内容にアクセスし、asCaseList７４８ｆを検索する。asCaseList７４８ｆがヌルポインタであるため、エンドプロダクトに到達した。
【００９２】
やはり図７ａを参照して、文字「A」を含むすべてのasCaseブランチの第１のノードが所望されているものと仮定されたい。基本ルートノードA３０４をメモリから検索し、そのasResultList５４２ｆにアクセスして、位置１４５および１７５を返却する。第１の位置１４５にアクセスする。この第１の位置１４５は、ノードBOT-C-A３１４を含む。ノードBOT-C-A３１４は、文字「A」を含むデータ構造７００ａの第１のブランチ内の第１のノードである。形成されたエンドプロダクトを見出すために、asCaseブランチ（たとえばこの例において、ノードBOT-C３１２、ノードBOT-C-A３１４、ノードBOT-C-A-T３１６、およびノードBOT-C-A-T-EOT３１８を含むブランチ）と、このブランチのasCaseリンクとが、検索されたasCaseListがヌルになるまでノードのasCaseListを繰り返し検索することによって辿られる。たとえば、データセット要素A３０４を含む第１の語が「CAT」であることを判定するために、ノードBOT-C-A３１４のasCaseList７４０ｆにアクセスし、位置１４５を検索する。位置１４５（ノードBOT-C-A３１４）の内容にアクセスし、asCaseList５３２ｆ、すなわち１５０を検索する。位置１５０（ノードBOT-C-A-T３１６）の内容にアクセスし、asCaseList５４８ｆ、すなわち１５５を検索する。位置１５５（ノードBOT-C-A-T-EOT３１８）の内容にアクセスし、asCaseList５７２ｆを検索する。asCaseList５７２ｆがヌルポインタであるため、エンドプロダクトに到達した。
【００９３】
次の位置１７５にアクセスする。この位置１７５は、ノードBOT-T-A７０５を含む。ノ
ードBOT-T-A７０５は、文字「A」を含むインタロック状態のツリーデータストア７００ａの第２のブランチ内の第１のノードである。形成されたエンドプロダクトを見出すために、asCaseブランチ（たとえばこの例において、ノードBOT-T７０３、ノードBOT-T-A７０５、ノードBOT-T-A-B７０７、およびノードBOT-T-A-B-EOT７０９を含むブランチ）と、このブランチのasCaseリンクとが、検索されたasCaseListがヌルになるまでノードのasCaseListを繰り返し検索することによって辿られる。たとえば、データセット要素A３０４を含む第２の語が「TAB」であると判定するために、ノードBOT-T-A-B７０７のasCaseList７４０ｆにアクセスして、位置１８５を検索する。位置１８５の内容にアクセスして、asCaseList７４８ｆを検索する。asCaseList７４８ｆがヌルポインタであるため、エンドプロダクトに到達した。
【００９４】
再び図７ａを参照し、文字「A」および「T」を含むすべてのasCaseブランチの第１のノードが所望されているものと仮定されたい。上述のように、基本ルートノードA３０４をメモリから検索し、そのasResultList５４２ｆにアクセスして、位置１４５および１７５を返却する。第１の位置１４５にアクセスする。この位置１４５は、ノードBOT-C-A３１４を含む。ノードBOT-C-A３１４は、文字「A」を含むインタロック状態のツリーデータストア７００ａの第１のブランチ内の第１のノードである。形成されたエンドプロダクトを見出すために、asCaseブランチ（たとえばこの例において、ノードBOT-C３１２、ノードBOT-C-A３１４、ノードBOT-C-A-T３１６、およびノードBOT-C-A-T-EOT３１８を含むブランチ）と、このブランチのasCaseリンクとが、検索されたasCaseListがヌルになるまでノードのasCaseListを繰り返し検索することによって辿られる。たとえば、データセット要素A３０４を含む第１の語が「CAT」であると判定するために、ノードBOT-C-A３１４のasCaseList７４０ｆにアクセスして位置１４５を検索する。位置１４５（ノードBOT-C-A３１４）の内容にアクセスして、asCaseList５３２ｆ、すなわち１５０を検索する。位置１５０（ノードBOT-C-A-T３１６）の内容にアクセスして、asCaseList５４８ｆ、すなわち１５５を検索する。位置１５５（ノードBOT-C-A-T-EOT３１８）の内容にアクセスして、asCaseList５７２ｆを検索する。asCaseList５７２ｆがヌルポインタであるため、エンドプロダクトに到達した。エンドプロダクトノードBOT-C-A-T-EOT３１８は、データセット要素Aを含む。
【００９５】
次の位置１７５にアクセスする。この位置１７５は、ノードBOT-T-A７０５を含む。ノードBOT-T-A７０５は、文字「A」を含むインタロック状態のツリーデータストア７００ａの第２のブランチ内の第１のノードである。形成されたエンドプロダクトを見出すために、asCaseブランチ（たとえばこの例において、ノードBOT-T７０３、ノードBOT-T-A７０５、ノードBOT-T-A-B７０７、およびノードBOT-T-A-B−EOT７０９を含むブランチ）と、このブランチのasCaseリンクとが、検索されたasCaseListがヌルになるまでノードのasCaseListを繰り返し検索することによって辿られる。たとえば、データセット要素A３０４を含む第２の語が「TAB」であると判定するために、ノードBOT-T-A-B７０７のasCaseList７４０ｆにアクセスして、位置１８５を検索する。位置１８５の内容にアクセスして、asCaseList７４８ｆを検索する。asCaseList７４８ｆがヌルポインタであるため、エンドプロダクトに到達した。エンドプロダクトノードBOT-T-A-B−EOT７０９は、データセット要素Aを含む。
【００９６】
次に、基本ルートノードT３０８をメモリから検索し、そのasResultList５５８ｆにアクセスして、値１５０および１７０を返却する。第１の位置１５０にアクセスする。この位置１５０は、ノードBOT-C-A-T３１６を含む。ノードBOT-C-A-T３１６は、文字「T」を含むインタロック状態のツリーデータストア７００ａの第１のブランチ内の第１のノードである。形成されたエンドプロダクトを見出すために、asCaseブランチ（たとえばこの例において、ノードBOT-C３１２、ノードBOT-C-A３１４、ノードBOT-C-A-T３１６、およびノードBOT-C-A-T-EOT３１８を含むブランチ）と、このブランチのasCaseリンクとが、検
索されたasCaseListがヌルになるまでノードのasCaseListを繰り返し検索することによって辿られる。たとえば、分割できない基本単位T３０８を含む第１の語が「CAT」であると判定するために、ノードBOT-C-A３１４のasCaseList５３２ｆにアクセスして、位置１４５を検索する。位置１４５の内容（ノードBOT-C-A３１４）にアクセスして、asCaseList５３２ｆ、すなわち１５０を検索する。位置１５０（ノードBOT-C-A-T３１６）の内容にアクセスしてasCaseList５４８ｆ、すなわち１５５を検索する。位置１５５（ノードBOT-C-A-T-EOT３１８）の内容にアクセスして、asCaseList５７２ｆを検索する。asCaseList５７２ｆがヌルポインタであるため、エンドプロダクトに到達した。エンドプロダクトノードBOT-C-A-T-EOT３１８は、データセット要素Tを含む。
【００９７】
次の位置１７０にアクセスする。この位置１７０は、ノードBOT-T７０３を含む。ノードBOT-T７０３は、文字「T」を含むインタロック状態のツリーデータストア７００ａの第２のブランチ内の第１のノードである。形成されたエンドプロダクトを見出すために、asCaseブランチ（たとえばこの例において、ノードBOT-T７０３、ノードBOT-T-A７０５、ノードBOT-T-A-B７０７、およびノードBOT-T-A-B-EOT７０９を含むブランチ）と、このブランチのasCaseリンクとが、検索されたasCaseListがヌルになるまでノードのasCaseListを繰り返し検索することによって辿られる。たとえば、データセット要素T３０８を含む第２の語が「TAB」であると判定するために、ノードBOT-T-A-B７０７のasCaseList７４０ｆにアクセスして、位置１８５を検索する。位置１８５の内容にアクセスして、asCaseList７４８ｆを検索する。asCaseList７４８ｆがヌルポインタであるため、エンドプロダクトに到達した。エンドプロダクトノードBOT-T-A-B-EOT７０９は、データセット要素Tを含む。したがって、AおよびTの両方を含むエンドプロダクトは、Aを含むエンドプロダクトの組とTを含むエンドプロダクトの組との共通部分、すなわちこの場合、BOT-C-A-T-EOT３１８およびBOT-T-A-B-EOT７０９を含む。
【００９８】
この発明の一実施例において、検索された情報は、表示または印刷される。検索された情報を表示または印刷するために、asCaseツリーがエンドプロダクトから開始部分（BOT）まで逆方向に辿られる。asCaseツリーに沿った各ノードにおいてResultポインタ（ノードが導出された第２の部分を指す）を用いて、基本ルートノードが何を表すかを判断する。インタロック状態のツリーデータストアが２つ以上のレベルを含む場合、Resultポインタは、より低いレベルのエンドプロダクトを指し、最下位のレベルの基本ルートノードが検索されるまで同じプロセスが辿られなければならない。
【００９９】
次に、図１０を参照して、火曜日に販売されたユニットの総数が所望されるものと仮定されたい。全データストア内の全ノードをトラバースする代わりに、この発明の一実施例において、この情報を検索することにより、基本ルートノード１００６および１００８のasResultListの検索のみが必要になることが、当業者には明らかであろう。ブランチ５  １０１０がトラバースされる。なぜなら、ノード１００４が、火曜日１００６を表わす基本ノードにより指されており、かつ、ノード１０２６が、販売１００８を表わす基本ノードにより指されているためである。そして、ブランチ４  １０１２がトラバースされる。なぜなら、ノード１０２８が、販売１００８を表わす基本ノードにより指されているためである。ブランチ１  １０１５、ブランチ２  １０１４、およびブランチ３  １０１３は、トラバースされなくてよい。基本ノード１００６および１００８により指された以下のブランチから返却されたエンドプロダクトの組の共通部分は、ビルが火曜日にPAで４０台販売したことを表わすノード１０３０を含む。
【０１００】
販売されたユニット数は、ノード１０２４から、数４０（図示せず）を表わすルートノードまでポインタを辿ることによって求めることができる。このステップが、エンドプロダクトの共通部分が見出された後に実行され得ること、または、ブランチがトラバースされるのに伴ってこの情報が検索および記憶され得ることが理解されるであろう。
【０１０１】
上述の方法およびシステムは、コンピュータ読取可能な媒体、たとえばフロッピー（登録商標）ディスケット、CD-ROM、DVD-ROM、DVD-RAM、ハードディスクドライブ、または他の任意の機械読取可能な記憶媒体に記憶されたプログラムコード（すなわち命令）の形で実現され得る。ここでは、プログラムコードがコンピュータ等の機械にロードされて、この機械により実行されると、この機械が、この発明を実施するための装置となる。この発明は、何らかの伝送媒体を介して、たとえば電気配線もしくは布線を介して、光ファイバ経由で、インターネットもしくはイントラネットを含むネットワークを介して、または、他の任意の形の伝送を介して伝送されるプログラムコードの形で実施することもでき、この場合、プログラムコードがコンピュータ等の機械により受信され、この機械にロードされてこの機械により実行されると、この機械が、この発明を実施するための装置となる。プログラムコードが汎用プロセッサで実行されると、プロセッサと組合さって、特定の論理回路と同様に作動する一意の装置を提供する。プログラムコードは、高水準のプログラミング言語、たとえばC、C＋＋、またはJAVA（登録商標）で実行され得る。代替的に、プログラムコードは、アセンブリ言語またはマシン言語で実行され得る。いずれの場合も、この言語はコンパイル型言語か、またはインタプリタ型言語であり得る。
【０１０２】
上述の例が単に説明のために提示されており、この発明の限定として考えられるべきではないことに注意されたい。たとえば、インタロック状態のツリーデータストアは、オブジェクト指向の技術、手続き技術、それらの混成技術、または他の任意の適切な手法を用いて実施され得る。さらに、示した実施例は、メモリ内に記憶されたデータセット要素を示しているが、この機能が多くの異なる方法で実施され得ることを、当業者は理解するであろう。たとえばこの発明は、遠隔に配置された複数の機械に記憶された多くの異なる母集団のデータセット要素の、多くの異なる組を用いることを企図する。
【図面の簡単な説明】
【０１０３】
【図１】この発明の局面が実現され得る例示的なコンピューティング環境を示す図である。
【図２ａ】この発明の一実施例に従ったインタロック状態のツリーデータストアからデータを生成し、かつこれにアクセスするための例示的なシステムを示す図である。
【図２ｂ】インタロック状態のツリーデータベースから情報を生成しかつこれにアクセスするための例示的な方法を示す図である。
【図３ａ】この発明の一実施例に従った、図３ａの例示的なインタロック状態のツリーデータストアを示すより詳細な図である。
【図３ｂ】この発明の一実施例に従った、図３ａのインタロック状態のツリーデータストアの例示的なノードを示すより詳細な図である。
【図３ｃ】この発明の一局面に従った、図３ａのインタロック状態のツリーデータストアのリンクされたリストを示す図である。
【図４】この発明の一実施例に従ったメモリに記憶される図２の例示的なデータセット要素の組を示す図である。
【図５ａ】図２のインタロック状態のツリーと、インタロック状態のツリーがこの発明の一実施例に従って生成される場合のインタロック状態のツリーのノードの対応する内容とを示す図である。
【図５ｂ】図２のインタロック状態のツリーと、インタロック状態のツリーがこの発明の一実施例に従って生成される場合のインタロック状態のツリーのノードの対応する内容とを示す図である。
【図５ｃ】図２のインタロック状態のツリーと、インタロック状態のツリーがこの発明の一実施例に従って生成される場合のインタロック状態のツリーのノードの対応する内容とを示す図である。
【図５ｄ】図２のインタロック状態のツリーと、インタロック状態のツリーがこの発明の一実施例に従って生成される場合のインタロック状態のツリーのノードの対応する内容とを示す図である。
【図５ｅ】図２のインタロック状態のツリーと、インタロック状態のツリーがこの発明の一実施例に従って生成される場合のインタロック状態のツリーのノードの対応する内容とを示す図である。
【図６】この発明の一局面に従ったインタロック状態のツリーを生成する例示的なプロセスを示すフロー図である。
【図７ａ】この発明の一実施例に従った別のインタロック状態のツリーデータストアおよび対応するノードを示す図である。
【図７ｂ】この発明の一局面に従った図７ａのインタロック状態のツリーデータストアのリンクされたリストを示す図である。
【図８】この発明の実施例に従った他のインタロック状態のツリーデータストアを示す図である。
【図９ａ】この発明の一実施例に従った別のインタロック状態のツリーデータストアを示す図である。
【図９ｂ】この発明の一実施例に従った図９ａのインタロック状態のツリーデータストアのノードの例示的な内容を示す図である。
【図１０】この発明の一実施例に従った別のインタロック状態のツリーデータストアを示す図である。
【図１１】この発明の一実施例に従ったインタロック状態のツリーデータストアからのデータにアクセスする例示的なプロセスを示すフロー図である。
【図１】
2006522984.tif 000003
【図２ａ】
2006522984.tif 000004
【図２ｂ】
2006522984.tif 000005
2006522984.tif 000006
【図３ｂ】
2006522984.tif 000007
2006522984.tif 000008
【図４】
2006522984.tif 000009
【図５ａ】
2006522984.tif 000010
【図５ｂ】
2006522984.tif 000011
【図５ｃ】
2006522984.tif 000012
【図５ｄ】
2006522984.tif 000013
【図５ｅ】
2006522984.tif 000014
【図６】
2006522984.tif 000015
【図７ａ】
2006522984.tif 000016
2006522984.tif 000017
【図８】
2006522984.tif 000018
【図９ａ】
2006522984.tif 000019
【図９ｂ】
2006522984.tif 000020
【図１０】
2006522984.tif 000021
【図１１】
2006522984.tif 000022
【手続補正書】
【提出日】平成17年11月21日(2005.11.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ツリーベースのデータストアを生成するためのシステムであって、
プロセッサと、
プロセッサに結合されたメモリと、
ツリーベースのデータストアの少なくとも１つのレベルを作成するためのツリーベースのデータストアジェネレータとを含み、ツリーベースのデータストアの少なくとも１つのレベルは、第１のルートと複数のノードの少なくとも１つのノードとを含む第１のツリー、第２のルートと第１のツリーの少なくとも１つのノードとを含む第２のツリー、および第３のルートと第１のツリーの複数のノードの少なくとも１つとを含む少なくとも第３のツリーを含む、システム。
【請求項２】
データストアのノードは、少なくとも１つの基本ノードと、１つのサブコンポーネントノードと、１つのエンドプロダクトノードとを含む、請求項１に記載のシステム。
【請求項３】
ツリーベースのデータストアは、少なくとも第１のレベルおよび第２のレベルを含み、第１のレベルのエンドプロダクトは、第２のレベルの基本ノードを含む、請求項２に記載のシステム。
【請求項４】
ツリーベースのデータストアは、少なくとも第１のレベルおよび第２のレベルを含み、第１のレベルのエンドプロダクトは、分解されて第１のレベルの基本ノードを作成する、請求項２に記載のシステム。
【請求項５】
ツリーベースのデータストアは、少なくとも第１のレベルおよび第２のレベルを含み、第２のレベルの基本ノードは、分解されて第１のレベルの基本ノードを作成する、請求項２に記載のシステム。
【請求項６】
ノードは、ツリーベースのデータストア内の他のノードを指すポインタを含み、前記ポインタは双方向性である、請求項１に記載のシステム。
【請求項７】
第１のルートおよび第２のルートは、ツリーベースのデータストア内の他のノードを指すポインタを含み、非ポインタ情報を含む、請求項１に記載のシステム。
【請求項８】
第１のルートは、開始インジケータに関連付けられて、第１の階層順序でツリーベースのデータストアにアクセスする、請求項７に記載のシステム。
【請求項９】
第２のルートは、終了インジケータに関連付けられて、第１の階層順序の逆でツリーベースのデータストアにアクセスする、請求項７に記載のシステム。
【請求項１０】
第３のルートは、データセットの要素に関連付けられた非ポインタ情報を含み、データセットの要素に基づいて第３の階層順序でツリーベースのデータストアにアクセスする、請求項７に記載のシステム。
【請求項１１】
ツリーベースのデータストアから情報を検索するための、ツリーベースのデータストアアクセス機構をさらに含む、請求項１に記載のシステム。
【請求項１２】
ツリーベースのデータストアアクセス機構はさらに、
ツリーベースのデータストアから検索されるべき情報の要求を受信するための手段と、
ツリーベースのデータストアから要求した情報を検索するための手段と、
ツリーベースのデータストアから検索した情報を返却するための手段とを含む、請求項１１に記載のシステム。
【請求項１３】
データストアを生成するためのシステムであって、
プロセッサと、
プロセッサに結合されたメモリと、
データストアを作成するためのデータストアジェネレータとを含み、データストアは、複数の接続されたツリーに組織化されるルートノードおよび非ルートノードを含み、複数の接続されたツリーは、第１のルートと複数の非ルートノードの少なくとも１つとを含む第１のタイプのツリー、および第２のタイプの複数のツリーの少なくとも１つを含み、第２のツリーのタイプは、第１のタイプのツリーのノードと共通する複数の非ルートノードおよび第２のルートノードを含む、システム。
【請求項１４】
データストアのノードは、少なくとも１つの基本ノードと、１つのサブコンポーネントノードと、１つのエンドプロダクトノードとを含む、請求項１３に記載のシステム。
【請求項１５】
第１のタイプのツリーは、サブコンポーネントノードと基本ノードとの少なくとも１つの組合せからエンドプロダクトのシーケンシャルな合成を記録し、データストア内の第１の文脈内のデータへのアクセスを提供する、請求項１４に記載のシステム。
【請求項１６】
第２のタイプの複数のツリーの少なくとも１つのツリーは、データストア内の第２の文脈内のデータへのアクセスを提供する、請求項１３に記載のシステム。
【請求項１７】
少なくとも１つの基本ノードは、第１のヌルポインタと、第２のヌルポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、それらの第２の部分として基本ノードを含むノードを含む、請求項１４に記載のシステム。
【請求項１８】
少なくとも１つのサブコンポーネントノードは、第１のノードを指す第１のポインタを含み、第１のノードは、サブコンポーネントノードの第１の部分を含み、少なくとも１つのサブコンポーネントノードはさらに、第２のノードを指す第２のポインタを含み、第２
のノードは、サブコンポーネントノードの第２の部分を含み、少なくとも１つのサブコンポーネントノードはさらに、ノードを指すポインタの第１のリストを指す第３のポインタを含み、第１のリストは、それらの第１の部分としてサブコンポーネントを含むノードを含み、少なくとも１つのサブコンポーネントノードはさらに、第４のヌルポインタを含む、請求項１４に記載のシステム。
【請求項１９】
少なくとも１つのエンドプロダクトノードは、第１の部分を指す少なくとも第１のポインタと、終了インジケータの第２の部分を指す第２のポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、それらの第２の部分としてエンドプロダクトノードを含むノードを含む、請求項１４に記載のシステム。
【請求項２０】
開始インジケータを表わすルートノードは、第１のヌルポインタと、第２のヌルポインタと、ノードを指すポインタの第１のリストを指す第３のポインタとを含み、第１のリストは、第１の部分として開始インジケータを含むノードを含み、開始インジケータを表すルートノードはさらに、第４のヌルポインタを含む、請求項１３に記載のシステム。
【請求項２１】
データセット要素を表すルートノードは、第１のヌルポインタと、第２のヌルポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、第２の部分としてデータセット要素を含むノードを含む、請求項１３に記載のシステム。
【請求項２２】
エンドプロダクトを表わすルートノードは、第１のヌルポインタと、第２のヌルポインタと、第３のヌルポインタと、ノードを指すポインタの第２のリストを指す第４のポインタとを含み、第２のリストは、第２の部分としてエンドプロダクトを含む第２のレベルのノードを含む、請求項１３に記載のシステム。
【請求項２３】
インタロック状態のツリーデータストアに記憶された情報にアクセスするためのアクセス機構をさらに含む、請求項１３に記載のシステム。
【請求項２４】
アクセス機構はさらに、
ツリーベースのデータストアから検索されるべき情報の要求を受信するための手段と、
ツリーベースのデータストアから要求した情報を検索するための手段と、
ツリーベースのデータストアから検索した情報を返却するための手段とを含む、請求項２３に記載のシステム。
【請求項２５】
データストアからデータを生成してそのデータにアクセスするための方法であって、
データを受信したことに応答して、ツリーベースのデータストアの少なくとも１つのレベルを作成するステップを含み、ツリーベースのデータストアの少なくとも１つのレベルは、第１のルートと複数のノードの少なくとも１つのノードとを含む第１のツリー、第２のルートと第１のツリーの少なくとも１つのノードとを含む第２のツリー、および第３のルートと第１のツリーの複数のノードの少なくとも１つとを含む少なくとも第３のツリーを含み、前記方法はさらに、
ツリーベースのデータストアの少なくとも１つのレベルからアクセスすることのできる情報に対する情報要求を受信するステップと、
ツリーベースのデータストアの少なくとも１つのレベルから情報を検索するステップとを含む、方法。
【請求項２６】
ツリーベースのデータストアに追加すべきデータを受信したことに応答して、受信したデータに関連付けられた情報を記憶するために、ツリーベースのデータストア内に新規の
ノードを作成するステップと、
新規のノードの第１の部分を含む第１のノードおよび新規のノードの第２の部分を含む第２のノードまで、新規のノードからリンクを作成するステップと、
第１のノードのポインタの第１のリストに対し、新規のノードに戻るリンクを追加するステップと、
第２のノードのポインタの第２のリストに対し、新規のノードに戻るリンクを追加するステップとを含む、請求項２５に記載の方法。
【請求項２７】
ツリーベースのデータストア内に新規のノードを作成するステップは、開始インジケータを表わす第１のノードとデータセット要素を表わす第２のノードとを組合せて、不完全なプロダクトを表わす第３のノードを生成するステップを含む、請求項２６に記載の方法。
【請求項２８】
ツリーベースのデータストア内に新規のノードを作成するステップは、第１の不完全なプロダクトを表わす第１のノードと、データセット要素を表わす第２のノードとを組合せて、第２の不完全なプロダクトを表わす第３のノードを生成するステップを含む、請求項２７に記載の方法。
【請求項２９】
ツリーベースのデータストア内に新規のノードを作成するステップは、第１の不完全なプロダクトと、終了インジケータを表わす第４のノードとを組合せて、エンドプロダクトを表わす第５のノードを生成するステップを含む、請求項２７に記載の方法。
【請求項３０】
ツリーベースのデータストア内に新規のノードを作成するステップは、第２の不完全なプロダクトと、終了インジケータを表わす第４のノードとを組合せて、エンドプロダクトを表わす第５のノードを生成するステップを含む、請求項２７に記載の方法。
【請求項３１】
新規のノードを作成するステップは、第１のポインタ、第２のポインタ、第３のポインタ、および第４のポインタに空間を割当てるステップを含む、請求項２６に記載の方法。
【請求項３２】
第３のポインタおよび第４のポインタは、ヌルポインタである、請求項２６に記載の方法。
【請求項３３】
ツリーベースのデータストアから情報にアクセスするための方法であって、
データストアから情報の要求を受信したことに応答して、情報の要求は、少なくとも１つの制約を含み、データストアは、ツリーベースのデータストアの少なくとも１つのレベルを含み、ツリーベースのデータストアの少なくとも１つのレベルは、第１のルートと複数のノードの少なくとも１つのノードとを含む第１のツリー、第２のルートと第１のツリーの少なくとも１つのノードとを含む第２のツリー、および第３のルートと第１のツリーの複数のノードの少なくとも１つとを含む少なくとも第３のツリーを含み、前記方法は、
第３のルートに関連付けられたノードのリストを検索するステップを含み、ノードのリスト内の各ノードは、第１の部分および第２の部分を含み、第３のルートは少なくとも１つの制約を含み、前記方法はさらに、
第２のツリーの少なくとも１つのノードまで、第１のツリー内の各ノードのブランチを辿るステップを含む、方法。
【請求項３４】
情報の要求は、第１の制約および第２の制約を含み、第２のツリーのノードの組の共通部分が返却される、請求項３３に記載の方法。
【請求項３５】
インタロック状態のツリーデータベースを生成するためのコンピュータ実行可能な命令を含むコンピュータ読取可能な媒体であって、
ツリーベースのデータストアに追加されるべきデータを受信したことに応答して、受信したデータに関連付けられた情報を記憶するために、ツリーベースのデータストア内に新規のノードを作成するステップと、
新規のノードの第１の部分を含む第１のノードおよび新規のノードの第２の部分を含む第２のノードまで、新規のノードからリンクを作成するステップと、
第１のノードのポインタの第１のリストに対し、新規のノードに戻るリンクを追加するステップと、
第２のノードのポインタの第２のリストに対し、新規のノードに戻るリンクを追加するステップとを行なうための命令を含む、コンピュータ読取可能な媒体。
【請求項３６】
ノードと、前記ノード間にリンクとを含む構造であって、前記ノードは複数のデータフィールドを有し、前記複数のデータフィールドの少なくとも２つはポインタを含み、前記少なくとも２つのポインタの一方はCaseポインタであり、前記少なくとも２つのポインタの他方はResultポインタであり、少なくとも１つのノードは、ポインタのリストを指す少なくとも追加のポインタを有し、ポインタの前記リストを指す前記追加のポインタの１つは、前記ノードが関連付けられたasCaseリストを有する場合、asCaseリストを指すものであり、ポインタの前記リストを指す前記追加のポインタの別のものは、前記ノードが関連付けられたasResultリストを有する場合、asResultリストを指すものであり、前記ノードは、その少なくとも１つの主ルートノードおよび少なくとも１つの基本ルートノードが存在するルートノードを含み、前記ノードは他のルートノードを含み得、前記ノードはさらに、少なくとも１つの思考の終わりノード、少なくとも１つのサブコンポーネントノード、および少なくとも１つのエンドプロダクトノードを含み、前記asResultリンクは、ルートノードと他の任意のノードとの間を指し、前記asCaseリンクは、少なくとも１つの主ルートノードと少なくとも１つのエンドプロダクトノードとの間を指し、それらの間の経路に少なくとも１つのサブコンポーネントノードを含み、前記asResultリンクは、ルートノードまたはエンドプロダクトノードと、それらの間の前記経路上のサブコンポーネントノードまたはエンドプロダクトノードとの間を指し、前記基本ノードもまた、値を有するフィールドを有する、構造。
【請求項３７】
前記構造は、コンピュータシステム内で起動されるとコンピュータシステムを設定して前記構造を生じるプログラム命令の組で形成される、請求項３６に記載の構造。
【請求項３８】
クレーム３７に明示したプログラム命令の組を含む、コンピュータ読取可能な媒体。
【請求項３９】
クレーム３６の構造に整合するデータ構造を含む、電子システム。
【請求項４０】
前記asCaseリストおよび前記asResultリストは、前記インタロック状態のツリー構造とは別個のデータ構造に記憶され、前記別個のデータ構造は、ポインタにより、前記インタロック状態のツリー構造内の関連するノードに関連付けられる、請求項３６に記載の構造。
【国際調査報告】
2006522984.tif 000023