(57)【要約】【課題】  複数ノード・ツリー構造に対する自動変更をサポートするための方法およびシステムを提供することにある。【解決手段】  各文節および各論理演算子はノードとしてツリー構造内で定義される。加えて、子ノードから親ノードに発出する各リンクは子リンクとして定義され、親ノードから子ノードに発出する各リンクは親リンクとして定義される。選択した位置に応答して、ツリー構造内の配置のための演算子の選択および位置が自動化される。【選択図】  図４
2006302254.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ・システムによる演算処理を用いて複数ノード・ツリー構造を変更する方法において、
前記コンピュータ・システムの表示装置に表示される前記ノード・ツリー構造に対して新しいノードを追加するために前記ツリー構造内における位置を受け付けるステップと、
前記位置を受け付けることに応答して、前記演算処理により前記ツリー構造内で前記新しいノードを自動的に配置するステップであって、前記新しいノードが、新しい論理演算子と論理演算子に対する文節からなるグループから選択されるステップと、
を有する方法。
【請求項２】
前記ツリー構造内の各文節および各論理演算子をノードとしてカテゴリ化するステップをさらに有する、請求項１に記載の方法。
【請求項３】
前記選択されるステップの後に、前記ツリー構造を編集するステップをさらに有する、請求項２に記載の方法。
【請求項４】
前記ツリー構造を編集する前記ステップが、
子リンク上の論理演算子の編集に応答して、新しい文節ノードと新しい論理演算子ノードとを作成するステップ
を含む、請求項３に記載の方法。
【請求項５】
前記ツリー構造を編集する前記ステップが、
親リンク上の演算子の選択に応答して、ｎ進演算子として親ノードの演算子を使用する新しい文節ノードを追加するステップを含む、請求項３に記載の方法。
【請求項６】
前記親リンク上の前記演算子が、２項演算子と論理演算子からなるグループから選択される、請求項５に記載の方法。
【請求項７】
演算処理を用いて複数ノード・ツリー構造を変更するコンピュータ・システムであり、
前記コンピュータ・システムの表示装置に表示される前記ノード・ツリー構造に対して新しいノードを追加するために前記ツリー構造内における位置を受け付ける演算マネージャと、
前記位置を受け付けることに応答して、前記演算処理により前記ツリー構造内で前記新しいノードを自動的に配置するステップであって、前記新しいノードが、新しい論理演算子と論理演算子に対する文節からなるグループから選択される自動選択マネージャと、
を有するシステム。
【請求項８】
コンピュータ・システムに演算処理を用いて複数ノード・ツリー構造を変更させるコンピュータ・プログラムであり、
前記コンピュータ・システムに、
前記コンピュータ・システムの表示装置に表示される前記ノード・ツリー構造に対して新しいノードを追加するために前記ツリー構造内における位置を受け付けるステップと、
前記位置を受け付けることに応答して、前記演算処理により前記ツリー構造内で前記新しいノードを自動的に配置するステップであって、前記新しいノードが、新しい論理演算子と論理演算子に対する文節からなるグループから選択されるステップと、
を実行させるコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理式を変更するための技術に関する。より具体的には、この技術は、少なくとも３つの接続ノードをサポートする親ノードに対する新しいノードの配置を自動化するものである。
【背景技術】
【０００２】
ツリーの形になっているデータ構造は、テーブルを構築し、既知の接頭部から始まるサーチをサポートするために効率の良いツールとして知られている。ツリーは、まずルート・ノードでアクセスされるデータ構造である。各後続ノードは、追加の後続ノードを備えた内部ノードにするか、またはそのノードの下に追加ノードがまったく存在しない外部ノードにすることができる。内部ノードは、１つまたは複数の下降または子ノード（descending or child node）へのリンクを指すかまたはそのリンクを有し、その子ノードの親と呼ばれ、外部ノードは一般にリーフと呼ばれる。ルート・ノードは通常、ツリー構造の最上部に描写され、外部ノードは最下部に描写される。
【０００３】
ツリー構造は、そのツリーの特性によって定義される場合が多い。たとえば、バイナリ・ツリーは、各ノードについてせいぜい２つの子を備えたツリーである。ディジタル・ツリーは、リーフがディジタル記号のストリングを表す、根付きツリーである。パトリシア・ツリー（Patricia Tree）は、他のブランチの厳密な接頭部であるキーを禁止する、単方向ブランチ（one way branching）の抑制を備えたディジタル・ツリーである。一般に、パトリシア・ツリーは、記号アルファベットがバイナリであるときにバイナリ・ツリーになる以外は、常にディジタル・ツリーである。内部ノードは１組のストリングに対する共通接頭部を表し、そのノードの各子は、共通接頭部に続く次の記号の選択項目に対応する。パトリシア・ツリーは、すべての内部ノードが少なくとも２つの子を有する場合に、バイナリ・ツリーおよびディジタル・ツリーの形を取ることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
問題は、ツリー構造にリーフを追加する際に発生する。各ノードについてせいぜい２つの子が存在するバイナリ・ツリーでは、そのツリーにリーフを追加することは簡単なことである。しかし、問題は、各親ノードについて３つ以上の子ノードをサポートする複数ノード・ツリー（multiple node tree）で発生する。ノードあたり３つ以上の子をサポートするツリー構造を変更するための従来技術の方法では、それが２項演算子を追加するための演算であるか、そのツリーにノードを追加するための演算であるかを指定することを必要とする。しかし、ツリー構造に追加すべき各子ノードについて位置および演算子を選択しなければならないので、この方法は時間のかかるものである。したがって、ノードあたり３つ以上の子をサポートするツリー構造内の新しいノードの配置の自動化をサポートする必要がある。
【０００５】
本発明は、新しいリーフ・ノードの追加のための位置の選択に基づいて、複数ノード・サポート・ツリー構造の変更を自動化するための方法、システムおよびコンピュータ・プログラムを含む。
【課題を解決するための手段】
【０００６】
一態様では、複数ノード・ツリー構造を変更するための方法が提供される。ツリー構造内で新しいノードを追加するための位置の決定が行われる。その決定に応答して、ツリー構造に追加すべき新しいノードの配置が自動的に選択される。新しいノードは、新しい論理演算子あるいは論理演算子に対する文節またはその両方にすることができる。
【０００７】
他の態様では、新しいノードの追加のために複数ノード・サポート・ツリー構造内で位置を決定するための演算マネージャ（operation manager）を備えたシステムが提供される。ツリー構造内で新しいノードを自動的に配置するための自動選択マネージャも提供される。自動選択マネージャは演算マネージャに応答する。新しいノードは、新しい論理演算子あるいは論理演算子に対する文節またはその両方の形にすることができる。
【０００８】
さらに他の態様では、コンピュータ・プログラムが提供される。新しいノードの配置のために複数ノード・サポート・ツリー構造内で位置を決定するための媒体内の手段が提供される。加えて、ツリー構造内で新しいノードを自動的に配置するための媒体内の手段が提供される。自動配置手段は位置決定手段に応答する。新しいノードは、新しい論理演算子あるいは論理演算子に対する文節またはその両方にすることができる。
【０００９】
本発明のその他の特徴および利点は、添付図面に関連して取り上げられた本発明の現在好ましい実施形態に関する以下の詳細な説明から明らかになるであろう。
【発明を実施するための最良の形態】
【００１０】
概要
２つの子ノードのみを有することができるノードに新しいノードを追加するという形でバイナリ・ツリー構造を変更するプロセスを自動化することは、当技術分野で知られている。しかし、各ノードが３つまたはそれ以上のノード、すなわち、Ｎ進演算子を有することができるツリー構造では、新しいノードが追加されるときにツリー構造を変更するプロセスを自動化することは複雑なものになる。本発明の一実施形態では、親ノードと子ノード、子リンクとして知られる子ノード付近の接続部、親リンクとして知られる親ノード付近の接続部との区別が行われる。
【００１１】
技術的詳細
図１は、ノードとして表された４つの文節（１２）、（１４）、（１６）、（１８）と、３つの論理演算子（２０）、（２２）、（２４）とを備えたツリー構造のブロック図（１０）である。各文節（１２）、（１４）、（１６）、（１８）は、論理演算子（２０）および（２２）の観点から子ノードとして定義される。同様に、各論理演算子（２０）、（２２）、（２４）はノードとして定義され、論理演算子1ノード（２０）および論理演算子2ノード（２２）は文節（１２）、（１４）、（１６）、（１８）に対する親ノードであり、論理演算子3ノード（２４）は論理演算子1ノード（２０）および論理演算子2ノード（２２）に対する親ノードである。論理演算子1ノード（２０）は文節1ノード（１２）および文節2ノード（１４）に対する親ノードであり、論理演算子2ノード（２２）は文節3ノード（１６）および文節4ノード（１８）に対する親ノードである。論理演算子1ノード（２０）および論理演算子2ノード（２２）はどちらも定義された子ノードに対する親ノードであるが、論理演算子3ノード（２４）に対する子ノードとして定義することができる。ある論理演算子が子ノードにもなりうることは留意すべき重要なことである。しかし、本明細書で示した例では、論理演算子ノードは定義された子ノードに対する親ノードである。文節4ノード（１８）から論理演算子2ノード（２２）への接続部は子リンク（３０）として定義され、文節3ノード（１６）から論理演算子2ノード（２２）への接続部も子リンク（３２）として定義される。同様に、文節2ノード（１４）から論理演算子1ノード（２０）への接続部は子リンク（３４）として定義され、文節1ノード（１２）から論理演算子1ノード（２０）への接続部は子リンク（３６）として定義される。定義された子リンクに加えて、親リンクは親ノードから発出する接続部である。論理演算子1ノード（２０）から子リンク（３４）および（３６）への接続部は親リンク（４０）として定義され、論理演算子2ノード（２２）から子リンク（３０）および（３２）への接続部は親リンク（４２）として定義される。したがって、各ノードおよびノード同士を接続する各リンクはツリー構造内で定義される。
【００１２】
ツリー構造内の諸要素のそれぞれが定義されると、ツリー構造の変更は自動化することができる。図２および図３は、ツリー構造内の新しいノードの選択および配置を自動化するためのプロセスを示す流れ図（１００）である。ツリー構造内の各文節はノードとして指定され（１０２）、ツリー構造内の各論理演算子はノードとして指定される（１０４）。さらに、ブランチの一部分であって、親ノードと子ノードを接続するリンクのうち、子ノード付近の各リンクは子リンクとして定義され（１０６）、トランクの一部分であって、親ノードと子ノードを接続するリンクのうち、親ノード付近の各リンクは親リンクとして定義される（１０８）。ツリー構造に対する変更を開始する前に、その変更がツリー構造への新しいノードの追加を必要とするかどうかを判定するためのテストが行われる（１１０）。ステップ（１１０）のテストに対する否定応答は、それがツリー構造内の論理演算子のうちの１つまたは複数であるか、文節のうちの１つまたは複数であるかにかかわらず、その変更が既存のノードの編集の形になる可能性があることを示している。このため、既存のツリー構造に新しいノードを追加するプロセスは終了する（１１２）。しかし、ステップ（１１０）のテストに対する応答が肯定である場合、ツリー構造に追加すべき新しいノードが、ステップ（１０６）で定義された通り、複数ノード・サポート・ツリー構造内の子リンク上に位置するかどうかを判定するための後続テストが行われる（１１４）。ステップ（１１４）のテストに対する肯定応答の結果として、複数ノード・サポート・ツリー構造内に新しい論理演算子および新しい文節が作成されることになる（１１６）。しかし、ステップ（１１４）のテストに対する否定応答の結果として、またはステップ（１１６）の完了後、ツリー構造に追加すべき新しいノードが、ステップ（１０８）で定義された通り、複数ノード・サポート・ツリー構造内の親リンク上に位置するかどうかを判定するための他のテストが行われることになる（１０８）。ステップ（１１８）のテストに対する応答が否定である場合、これは、ツリー構造の変更がツリー構造への新しいノードの追加を含まないことを示している（１２０）。しかし、ステップ（１１８）のテストに対する肯定応答の結果として、親ノードの論理演算子タイプを使用する新しい子ノードの形で新しい文節を作成することになる（１２２）。ステップ（１２２）の新しいノードの作成後、ツリー構造に対して行うべき追加の変更があるかどうかを判定するための最終テストが行われる（１２４）。ステップ（１２４）のテストに対する肯定応答の結果として、ステップ（１１０）に戻り、ツリー構造に対して行うべき変更と位置を決定することになる。同様に、ステップ（１２４）のテストに対する否定応答の結果として、ツリー構造に対する変更が終結することになる（１２６）。したがって、ツリー構造に対する変更の配置およびカテゴリを決定するプロセスは、その変更の指定の位置に基づいて自動化される。
【００１３】
図２および図３に記載した通り、各文節はノードとして定義され、各論理演算子はノードとして定義される。一実施形態では、図２および図３に示した論理は、ユーザが直観的にツリー構造を変更できるようにするためのインターフェースを含むツールとして実施することができる。このツールは、機械可読フォーマットでデータを変更するために使用するので、コンピュータ可読信号伝送媒体上に保管することができる。このツールは、ツリー構造を変更する必要性を決定し、ツリー構造の位置および変更を選択するためにマネージャと通信するためのリクエスタを含むことができる。ツール・マネージャのリクエスタおよびマネージャは、コンピュータ・システム内のハードウェア要素またはコンピュータ可読信号伝送媒体内のソフトウェア要素の形にすることができる。
【００１４】
なお、これまでの説明に基づいて、このようにＮ進演算子を有することができるツリー構造において、新しいノードが追加されるときにツリー構造を変更するプロセスを自動化する方法を、当業者であれば、コンピュータ・システム又はコンピュータ・プログラムにおいて実現可能である。すなわち、コンピュータ・システムとしては、入力装置、出力装置（表示装置を含む）、演算装置、制御装置、記憶装置を備え、上述の自動化する方法を実現することができる。また、コンピュータ・システムに上述の自動化する方法を実現させるコンピュータ・プログラムを作成することができる。
【００１５】
図４は、子リンク（３４）上の２項演算子を編集した後の図１の変更されたツリー構造のブロック図（１５０）である。図示の通り、４つの元の文節（１５２）、（１５４）、（１５６）、（１５８）と、３つの元の論理演算子ノード（１６０）、（１６２）、（１６４）が存在する。各文節ノードは、論理演算子ノードの親リンクに接続された子リンクを有する。子リンク（３４）上の２項演算子を編集するプロセス後、新しい文節NEWノード（１８０）が作成され、新しい子リンク（１８２）は新しいノードである論理演算子NEW（１８６）の新しい親リンク（１８４）と通信する。同様に、文節1ノード（１５２）は論理演算子1ノード（１６０）の親リンク（１６６）と通信する子リンク（１６８）を保持し、文節2ノード（１５４）は新しい論理演算子NEWノード（１８６）の新しいリンク（１８４）と通信する新しい子リンク（１７０）を入手し、文節3ノード（１５６）は論理演算子2ノード（１６２）の親リンク（１９４）と通信する子リンク（１９０）を保持し、文節4ノード（１５８）は論理演算子2ノード（１６２）の親リンク（１９４）と通信する子リンク（１９２）を保持する。したがって、複数ノードをサポートするツリー構造内に新しい論理演算子を追加するために子リンクを編集するプロセスの結果として、新しい文節を有する新しい子ノードと、論理演算子の形の新しい親ノードの両方が作成される。
【００１６】
図５は、親リンク（４０）上の２項演算子を編集した後の図１の変更されたツリー構造のブロック図（２５０）である。図示の通り、４つの元の文節（２５２）、（２５４）、（２５６）、（２５８）と、３つの元の論理演算子ノード（２６２）、（２６４）、（２６６）が存在する。各文節ノードは、論理演算子ノードの親リンクに接続された子リンクを有する。親リンク（２７８）上の２項演算子を編集するプロセス後、新しい文節NEWノード（２６０）が作成され、新しい子リンク（２７２）は論理演算子1ノード（２６２）の元の親リンク（２７８）と通信する。同様に、文節1ノード（２５２）は論理演算子1ノード（２６２）の親リンク（２７８）と通信する子リンク（２６８）を有し、文節2ノード（２５４）は論理演算子1ノード（２６２）の親リンク（２７８）と通信する子リンク（２７０）を有し、文節3（２５６）は論理演算子2ノード（２６４）の親リンク（２８０）と通信する子リンク（２７４）を有し、文節4（２５８）は論理演算子2ノード（２６４）の親リンク（２８０）と通信する子リンク（２７６）を有する。したがって、複数ノードをサポートするツリー構造内に新しい論理演算子を追加するために親リンクを編集するプロセスの結果として、いずれも親リンク（２７８）と通信する３つまたはそれ以上の子ノード（２５２）、（２５４）、（２６０）を備えた新しい文節が作成される。
【００１７】
従来技術を超える利点
複数ノード・サポート・ツリー構造内の各ノードおよび各接続部の分類は、ツリー構造の自動編集をサポートする。それが子リンクであるか親リンクであるかにかかわらず、あるリンクの各部は、付近のノードに関連する演算を実行する。ツリー構造に対する提案された変更の位置は、ツリー構造に追加すべきノードのタイプを自動的に選択する。編集するために選択されたリンクが複数文節演算子に関連する場合、そのノードが３つまたはそれ以上のリーフをサポートするように、そのノードに対して新しいリーフを作成することができる。したがって、このツールは、ツリー構造内のリンクの選択に基づいて、複数ノード・ツリー構造の自動編集をサポートする。
【００１８】
代替実施形態
本明細書では例証のために本発明の特定の諸実施形態について説明してきたが、本発明の精神および範囲を逸脱せずに、様々な変更を行うことができることが分かるであろう。特に、本明細書に示した方法およびツールは、ツリー構造に対する自動変更をサポートするためにバイナリ・ツリーに適用することができる。したがって、本発明の保護の範囲は、特許請求の範囲およびそれと同等のもののみによって制限される。
【図面の簡単な説明】
【００１９】
【図１】ツリー構造の従来技術の図である。
【図２】本発明の好ましい実施形態によりツリー構造を変更するためのプロセスを示す流れ図であり、発行された特許の１ページ目に印刷するために提案された流れ図である。
【図３】本発明の好ましい実施形態によりツリー構造を変更するためのプロセスを示す流れ図であり、発行された特許の１ページ目に印刷するために提案された流れ図である。
【図４】子リンクの選択後の変更されたツリー構造のブロック図である。
【図５】親リンクの選択後の変更されたツリー構造のブロック図である。
【符号の説明】
【００２０】
１５２：文節1
１５４：文節2
１５６：文節3
１５８：文節4
１６０：論理演算子1
１６２：論理演算子2
１６４：論理演算子parent
１８０：文節new
１８６：論理演算子new
【図１】
2006302254.tif 000003
【図２】
2006302254.tif 000004
【図３】
2006302254.tif 000005
【図４】
2006302254.tif 000006
【図５】
2006302254.tif 000007