(57)【特許請求の範囲】
【請求項１】
状態の組を符号化する方法であって、
電子コンピュータ装置を用いて、一組の状態空間の２進プレフィックス木表示を水平順序エッジシーケンス（ＬＯＥＳ）符号化するステップであって、葉ノードではないノードを、最初に上から下の順序で、次いで左から右の順序で符号化するとともに、前記葉ノードではないノードの各々を、偽の枝のみを有する場合、真の枝のみを有する場合、並びに偽及び真の枝を有する場合を含むノードから出る２つの枝の有無を示す２つのビットを用いて符号化することによって前記２進プレフィックス木表示を水平順序エッジシーケンス（ＬＯＥＳ）符号化するステップと、
前記電子コンピュータ装置を用いて、ある識別子によってプレフィックス木の葉の存在を識別するステップと、
前記電子コンピュータ装置を用いて、他の識別子によってプレフィックス木の葉の不在を識別するステップと、を含む方法。
【請求項２】
サンプルの状態空間の組を生成するステップと、
サンプリングした状態空間の順序を上から順に検査するステップと、
前記葉ノードではないノードを、上から下の順序で前記２つのビットを用いて符号化する順序である符号化ビット順序の置換を通して共通のプレフィックスの平均長さを最大にする２進プレフィックス木の表示を作るステップと、をさらに含む請求項１に記載の方法。
【請求項３】
あるオフセット及びこのオフセットに至るオフセットのシークエンスのビットの組の数により、前記オフセットのランクを判定するステップをさらに含む請求項１に記載の方法。
【請求項４】
ＬＯＥＳ符号化された２進プレフィックス木について、ある状態に対応する根から葉までの経路の存在、不存在を判定するステップであって、
ＬＯＥＳを構成する各ビットの組について、前記ビットの組に対応するノードにおける枝の有無を判定し、
あるノードにおいて枝がないと判定された場合は、前記状態に対応する経路が存在しないと判定し、
最後のノードまで枝が存在すると判定された場合には、前記状態に対応する経路が存在すると判定する
ステップをさらに含む請求項１の方法。
【請求項５】
有効経路は前記ＬＯＥＳ内で表示される状態を含む、請求項４に記載の方法。
【請求項６】
正規化された前記経路のオフセットのランクを用いて、少なくとも１つの要素に対する補助データに対する全単射の要素指数を決定するステップをさらに含む請求項４に記載の方法。
【請求項７】
前記ＬＯＥＳ符号化内の各レベル上を平行検索することにより状態の設定を反復するステップであって、各レベルにおいて、各レベル上の最初のビットの組で表示される最初の要素から検索が開始され、平行探査は最も低いレベルから始まり、ある設定ビットから別のビットへと、全ての設定ビットが反復されるまで、各ビットの組内を進み、同様に次のレベルでも進行する、ステップをさらに含む請求項１の方法。
【請求項８】
少なくとも１つの要素を前記ＬＯＥＳ符号化に加えるステップであって、
前記設定が空の場合は前記組を追加し又は空でない場合は前記適切なビットを設定して、各レベルで前記ビットの組を加えられる全ての要素を構築し、
前記レベルを第２のＬＯＥＳ符号化へ連結し、
両方のＬＯＥＳ符号化を同時に反復させ辞書式順序の状態設定を供給し、
前記ＬＯＥＳ符号化を結合して前記追加された要素を含むＬＯＥＳ符号化を形成するステップをさらに含む請求項７に記載の方法。
【請求項９】
状態の組を符号化するよう構成されたシステムであって、
メモリ及び電子プロセッサを有する電子コンピュータ装置を含み、
前記電子プロセッサが、
一組の状態空間の２進プレフィックス木表示を、葉ノードではないノードを、最初に上から下の順序で、次いで左から右の順序で符号化するとともに、前記葉ノードではないノードの各々を、偽の枝のみを有する場合、真の枝のみを有する場合、並びに偽及び真の枝を有する場合を含むノードから出る２つの枝の有無を示す２つのビットを用いて符号化することによって、水平順序エッジシーケンス（ＬＯＥＳ）として符号化し、
ある識別子によって前記プレフィックス木の葉の存在を識別し、
他の識別子によって前記プレフィックス木の葉の不在を識別するよう構成される、システム。
【請求項１０】
前記電子プロセッサが、
サンプルした状態空間の順序を上から順に検査し、
前記葉ノードでないノードを、上から下の順序で前記２つのビットを用いて符号化する順序である符号化ビット順序の置換を通して共通のプレフィックスの長さを最大にする２進プレフィックス木の表示を作るようさらに構成される、請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は検索に関し、より詳細にはコンピュータベースの状態空間の検索に関する。状態空間の検索を行うコンピュータのプログラムにおいて具体的な課題は、コンピュータの有効なメモリを効率的に使用することである。Ａ＊等の最良優先検索アルゴリズムは一般に、全ての抽象的な状態の抽象的結論までの距離を格納する参照テーブル（又は「パターン」）であるパターンデータベース（ＰＤＢ）を含んだフロンティアの検索（オープンリスト）、前もって拡張された状態（クローズリスト）、及びメモリベースのヒューリスティックの状態設定を表示するために使用されるメモリの容量により規制される。
【背景技術】
【０００２】
ＩＤＡ＊（反復深化深さ優先検索）等の線形空間の検索アルゴリズムにより、このＡ＊に関するメモリの課題を解決しているが、一般に線形空間の検索では後続要素が生成されたとき複製物をチェックせず、これが冗長な作業に繋がる恐れがあるため、追加ノードを拡張して最適なソリューションを見出さなければならない。基本的に、これらのアルゴリズムでは、時間を空間に変換し、検索空間で遭遇する複製物の数によりその効率は著しく変動する。スライディングブロックパズル等の複製物がほとんど無いドメインでは、ＩＤＡ＊はＡ＊よりも断然優れている。複数の配列アラインメント等その他のドメインがなければ、単純に線形空間の検索は非常に時間がかかる。ＳＴＲＩＰＳ（スタンフォード研究所問題解決プログラム）プランニグに関しては、置換表を使用したとしてもＩＤＡ＊は、Ａ＊よりもはるかに多くのノードを拡張しなければならない。結果として、ファーストダウンワード（ＦＤ）等の最先端のヒューリスティック検索プランナは、サブ検索アルゴリズムとして、ＩＤＡ＊の代わりにＡ＊を使用している。
【０００３】
Ａ＊の格納効率を改善する典型的なアプローチでは、二分決定グラフ（ＢＤＤ）を用いて、状態の設定（又は複数の設定）をコンパクトに表示する。同じ形式の部分グラフを結合することにより、同等な明示状態の表示よりもＢＤＤをかなり簡素にすることができる。例えば、ＢＤＤが明示状態の格納より幾何学的にコンパクトなグリッパのようなドメイン上では、ＭＩＰＳ（モデル検査統合プランニングシステム）等のＢＤＤベースのプランナは非常に良好に動作する。しかし、このようにＢＤＤを際立たせてみせることができるドメインは、プランニングにおいて見出されるベンチマーク課題の氷山の一角にすぎず、全てのヒューリスティック検索のプランナは状態設定に関する簡素な格納からメリットを得られるにもかかわらず、そのほとんどがいまだに明示状態表示を用いている。
【発明の概要】
【課題を解決するための手段】
【０００４】
水平順序付けエッジシーケンス（ＬＯＥＳ）として２進プレフィックス木による表示を符号化する状態設定を符号化するための方法及びシステムを開示する。その２進プレフィックス木では、内側の木のノードが左から右、及び上から下の順番で順位付けされ、葉節点の存在を表示するビットの組として符号化される。
【図面の簡単な説明】
【０００５】
【図１】図１は、３つのビットシーケンス及びそれらに対応して導かれたプレフィックス木を示す説明図である。
【図２】図２は、状態空間の設定においてビットの最順序付けを行い、その結果縮小したプレフィックス木の例を示す説明図である。
【図３】図３は、ＬＯＥＳ符号化を行うときの例示のプレフィックス木の符号化を示す説明図である。
【図４】図４は、状態空間がＬＯＥＳ符号化の要素かどうかを判断する一例を示す説明図である。
【図５】図５は、補助データに対する指数どのように計算するのかの一例を示す説明図である。
【図６】図６は、設定の反復がどのように行われかの一例を示す説明図である。
【図７】図７は、ＬＯＥＳ構造として、ＬＯＥＳ符号化に加えられる要素が最初に符号化され次に結合するかの一例を示す説明図である。
【図８】図８は、本出願のコンセプトが用いられたシステムの説明図である。
【発明を実施するための形態】
【０００６】
続く議論では、検索課題の符号化のサイズを前もって（例えば、検索開始前）決定することができるものと仮定する。さらに、一般論からかけ離れることなく、ｍを所与の課題に関する全ての状態を符号化するために必要なビット数と仮定する。これらの理解のもと、偽と真で表示された、ｍの深さのラベル付きの２進木として、このような全ての状態の設定を表示することができる。この木の根から葉までの全ての経路は、そこでの設定の一意の状態に対応（そして、その逆も同様である）し、根から葉までのラベル付きのシーケンスにより再構築することができる。このような仕事の関連で、これらの木をプレフィックス木と呼ぶ。いくつかの内側のノードに根付いた木の枝により表示される全ての要素は、根からそのノードまでの経路により示される表示において、共通のプレフィックスを共有する。
【０００７】
上記のことを考慮し、メモリ要求を最小にするこのようなプレフィックス木を符号化する方法及びシステムを続く議論でより詳細に供述し、本明細書で開示することになる。既知のサイズ及び各状態の状態設定は、２進シーケンスである。状態設定はプレフィックス木として表示される。状態空間設定のビットを再順序付けすることにより、プレフィックス木はそのサイズ小さくする。次いで、縮小したプレフィックス木は、本明細書で開示される水平順序付けエッジシーケンス（ＬＯＥＳ）と呼ばれる方法により符号化される。ＬＯＥＳ符号化は、縮小したプレフィックス木の内側のノード毎に記録する２ビットのエッジの組の水平順序の連結であり、これらのビットにより各ノードでの偽と真のエッジの有無が符号化される。
【０００８】
図１に目を移すと、ビットシーケンス「１１０」、「０００」、「１００」から導かれるプレフィックス木１００が示される。より具体的には、シーケンス「１１０」は経路１０２経由でプレフィックス木１００を横断する。シーケンス「０００」は経路１０４経由でプレフィックス木１００を横断する。そしてシーケンス「１００」は経路１０６経由でプレフィックス木１００を横断する。本出願のコンセプトの開示を補助するために、このプレフィックス木を続く議論で使用する。しかし、このプレフィックス木は、例として使用されているだけで、このコンセプトをその他の検索構成のなかでも使用できることは言うまでもない。
【０００９】
図２には、好ましくは最小化したプレフィックス木２００に変換されるプレフィックス木１００が示される。このプレフィックス木１００は、状態空間ビット設定の表示の再順序付けを通してサイズが縮小する。
【００１０】
格納効率は表示された設定の要素間で共有された共通のプレフィックスの平均の長さに依存し、次にこの表示された設定は、状態符号化において使用されたビットの順序に依存することが分かる。図２には、状態設定におけるビット順序の置換が示され、プレフィックス木１００のサイズが縮小している。元の状態２１０の「１１０」、「０００」、及び「１００」は、並び替え、即ち、再順序付けされて、それぞれ状態２２０の「０１１」、「０００」、及び「０１０」となる。元の状態設定の要素と、並び替えられる状態設定の要素とは一対一で対応する。
【００１１】
一実施形態では、効率よく最小化したプレフィックス木の表示２００に近づけるため、元のビット順序に対する置換を通して貪欲法タイプの検索を行って、共通のプレフィックスの平均の長さを最大にする要素を見出す。これに関して、第１工程として最初の状態を構成するシングルトン状態から状態のサンプル設定が生成される。各反復で、設定から１つの状態がランダムに選択され、その後続要素が生成され、この設定に戻される。設定が特定なサイズまで成長するか、又は所定の数の反復が実行されかのうちのどちらであっても最初に発生した場合、処理は終了する。ランダムな選択は異なる検索の深さでの有効な状態の良好なサンプルの生成を目的とする。
【００１２】
次いで、これらのサンプル状態の上にプレフィックス木を欲張って上から下に構築することにより好適なビット順序が推定され、これは下記に示すアルゴリズム１により実現される。アルゴリズム１で、Ｓは「木の枝」の要素であり、ｓはＳのビットシーケンスであり、Ｈは情報理論エントロピーである。
【表１】
0006029867.tif 000002
【００１３】
この処理では、サンプル設定内で定数に近い値のビットを、並び替えられた、即ち、再順序付けされた最も重要なビットの位置に移動させる。この例では、この処理により高い順序のビットは共通で、したがって分離した経路よりむしろ根からの共有する経路を表示したために、サイズが縮小されたプレフィックス木２００が作り出された。状態空間の設定に割り当てられるビットの順序は、再順序付けされた状態空間の設定２２０（「０１１」、「０００」、「０１０」）である。一対一の対応関係を用いることで、再順序付けされた状態２２０から元の状態２１０（例えば、「１１０」、「０００」、「１００」）を構築することや元の状態から再順序付けされた状態を構築することも可能である。
【００１４】
各反復は、その時点での木の葉節点毎の設定で始まり、根から葉節点までの経路に対応するプレフィックスを有するサブ設定を保持する。全てのサンプル状態を含む単一の葉の設定、空のビット順序、及び候補として指定された全てのビット位置と共に、この処理は開始される。反復の間、割り当てられていない、残された各候補のビットは再検査され、その状態の中のこのビットの値によって各設定を分割することにより一時的な新しい木の層が作り出される。平均のプレフィックス長さを最長にするために、その葉の設定内で最も少ないエントロピーを有する候補がビット順序内で次に選択される。ｍ回の反復の後、全ての候補が割り当てられたときに、この処理は終了する。
【００１５】
全ての足にわたりエントロピーの計算が行われる。つまり全サンプル設定が、その時点でのビット位置のシーケンスにより分割される（即ち２つより多い（選択された位置の数）の論理分割があり、そのうちのいくつかは空でもよい）。各サブ設定は、木の足を分割するサンプルの設定を表示する。これを分配として解釈することができ、それに関してエントロピーが計算されえる。各反復で、これは全ての長さ＋１のシーケンスに関して論理的に行われ、結果として候補（即ちまだ割り当てられていない）のビット位置のうちの添付される１つから前回の反復で既に固定されたシーケンスまでとなる。次いで、最も少ないエントロピーを有するシーケンスが選択される（情報理論では、エントロピーとは、直観的なランダムな変数のサンプリングを行ために予想される情報獲得の尺度である、即ちそれは予想不可能である。つまり、このようなサンプリングの結果最大エントロピーを有する変数に関して極めて不確定であり、最小エントロピーを有する変数に関しては極めて確実である）。ＬＯＥＳに関して、課題は平均のプレフィックスの長さを最大化することにある。したがって、挿入されたあらゆるシーケンスに関しては、個別に大きな分割が、確率の高い小さなサブ設定（ゆえに極めて予想可能な、低いエントロピーのランダム変数）に落ち着くことが望まれる。
【００１６】
上記の処理により得られる木の表示により設定要素間のプレフィックスの冗長性は排除されるが、直線的な実装では簡単に要素のビット文字列のシンプルな連結のサイズを超えることができる。その原因は、その時点においてマシン上で８バイトまでの記憶容量を使用可能なポインタである。代替物としては、２分ヒープによる系図表示等のポインタを使わない構造がある。履歴の系図では、文書内のそれらの位置を通して個々の世代の順序が単独で表示される。最初は位置が対象である。順序付けの規則では、位置ｉのあらゆる個人に対して、位置２ｉで男性の祖先を見出すことができ、位置２ｉ＋１で女性の祖先を見出すことができ、そして位置（ｉ／２）で子孫見出すことができる。より一般的には、その要素（例えば、個人）と、水平順序（例えば、彼らの世代順序）内の配列における位置と、をマップ化する全単射を行って、２分木を配列の中に格納する。この技術は、完全な２分木（２分ヒープ等の）に対して非常に適しているが、一般の２分木に関しては比較的コストがかかる。しかし、下記に説明する通り、この技術を本方法及びシステムのコンセプトに適用することができる。
【００１７】
最初に、２分木の符号化に対する情報理論的な図を提供する。それらのノードの数に関する異なる２分木の数は、下記のカタラン数により与えられる。
【数１】
0006029867.tif 000003
【００１８】
スターリングの近似によりｌｏｇ２  Ｃｎを２ｎ＋Ｏ（ｎ）として得ることができ、ｎノードを有する一般的な２分木を表示するのに必要な情報理論的なビットの最小数の考えを提供している。数多くの既知の符号化が存在し（例えばＪａｃｏｂｓｏｎ，Ｐｈ．Ｄ．Ｄｉｓｓｅｒｔａｔｉｏｎ  Ｃａｒｎｅｇｉｅ  Ｍｅｌｌｏｎ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｉｔｔｓｂｕｒｇｈ，ＰＡ  １９８８，Ｓｕｃｃｉｎｃｔ  ｓｔａｔｉｃ  ｄａｔａ  ｓｔｒｕｃｔｕｒｅ及びＭｕｎｒｏ  ａｎｄ  Ｒａｍａｎ，ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｎ  Ｃｏｍｐｕｔｉｎｇ  ２００１，３１：７６２，Ｓｕｃｃｃｔ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｏｆ  ｂａｌａｎｃｅｄ  ｐａｒｅｎｔｈｅｓｅｓ  ａｎｄ  ｓｔａｔｉｃ  ｔｒｅｅｓ）それらは木のノード毎に２ビットを使用するこのような木を格納することができ、オーバーヘッド空間をほとんど追加することなく基本的な木のナビゲーションをサポートしている。本出願によるプレフィックス木は、全ての葉がｍ−１の深さで規制されている。
【００１９】
本出願では、上記の特性を活用しより短い符号と、よりシンプルでより速いアルゴリズムと、を実現する符号化が記述されている。この符号化を本明細書では、水平順序付けエッジシーケンス符号化又はＬＯＥＳ符号化と呼ぶ。これは、木の内側のノード毎に記録する２ビットのエッジの組の水平順序連結（そのノード偽と真のエッジの存在に対応するビット）として定義される。
【００２０】
図３には、単一のバイト、即ち、より一般的な符号化の長さの半分より少し長いバイト内で再順序付けされた上記の状態２２０の「０００」、「０１０」及び「０１１」の提案された例示の設定の符号化を可能にするＬＯＥＳ符号化の一実施形態が示されている。
【００２１】
図３では、０等の特定な識別子で符号化された状態のビットを表示するノードの左側３００から偽が出る。１等の別の識別子で符号化された状態のビットを表示するノードの右側３１０から真が出る。再順序付けされた状態のビット２２０が表示され、その順序では各ビットがノード３２０と同じで、状態シーケンスの次のビットがそのノードの子供と同じ順序である。根のノード３３０から始まり各ノードの葉が、葉節点（例えば、３００又は３１０）が存在することを示す「１」と、表示する葉節点が存在しないことを示す「０」との組として符号化される。
【００２２】
混同する可能性を避けるため、上記の偽（エッジ）の葉節点を表示する「０」の使用は、葉節点が無いことを表示する「０」の使用とは根本的に異なる、即ち、それが偽の葉節点か真の葉節点かを示す。同様に、真（エッジ）の葉節点を表示する「１」の使用は、葉節点が存在することを表示する「１」の使用とは異なる、即ち、同様に偽のノードか真のノードかを示す。
【００２３】
符号化は、内側のノード毎に左から右、上から下の順序で進められる。符号化される状態をｍビットと仮定すると、符号化されたｍ−１のレベルの３４０、３５０、３６０が存在し、プレフィックス木２００は全ての葉がｍ−１の深さで規制される。プレフィックス木２００の各レベル３４０、３５０、３６０は、横断され２−ビットの組で符号化される。例えば、「１０」のビットの組は、偽の葉節点３００だけの存在を示し、「０１」のビット組は、真の葉節点３１０だけの存在を示す。「１１」のビットの組は、偽３００及び真３１０葉節点が両方存在することを示す。２−ビットの組は、左から右の順序の各レベルで連結され、各レベルのビットの文字列は上から下の順序で連結されて、水平順序エッジシーケンス３７０全体を形成し、このビットは、各ノードでの偽のエッジ３００及び真のエッジの３１０存在に対応する。
【００２４】
ｎ個の一意の状態設定に関して、状態の共通プレフィックスの長さの平均が最小であれば、プレフィックス木は最大となる。直観的に、これは、深さｋ＝（ｌｏｇ２ｎ）までの完全な２分木に類似する構造をもたらし、木を深さｋの各ノードから退化させる。ゆえに設定する木は、最悪でも、２ｎ＋ｎ（ｍ−ｋ）個のノードを含む。長い状態の大きな設定に関して（即ちｌｏｇ２ｎ≪ｍ≪ｎ）、これは（２＋ｍ）ｎ≒ｎｍ個のノードより少ない。各ノード（木の根を除いて）１つの（到着する）エッジ、及び少なくとも１つのエッジを保持するＬＯＥＳ内の各記録をきっちりと有していれば、この符号は悪くても設定内に詰め込まれた状態の連結長さの２倍より少しだけ長くなるだけである。
【００２５】
この構造が退化した木を深さｊ＝ｍ−ｌｏｇ２ｎ］まで表示し、より低いレベルで完全な２分木がこれに続くときに、最良のケースはこの反対の状況から発生する。このような木は、２ｎ＋（ｍ−ｊ）個のノードと、２つのエッジを表示する２分木内の各記録で構成される。ゆえに、大きな設定（即ちｍ≪ｎ）に関して、２ビットがＬＯＥＳ符号の最小の長さに対する厳しい下限となる。
【００２６】
状態空間検索又はプランニングにおける使用に関して、下記の３つの異なる操作を時間及び空間的に効率よく実行可能でなければならない。（１）設定要素のクエリ、（２）補助データと状態とを効率的に関連付けさせるための設定のｎ個の要素と、整数０・・・ｎ−１と、の全単射のマップ化及び、（３）設定要素に関する反復。これらの全ての操作には、ＬＯＥＳを介する効率的なナビゲーションが必要である。あるオフセットｏでのシーケンス内の全てのエッジに関する、ノードの偽と真のエッジに関する入力値を例に挙げると、それらは２ランクの（ｏ）のオフセット及び２ランクの（ｏ）＋１のオフセットで見出すことができる。但し、ランク（ｏ）はオフセット「ｏ」までの（及び含んだ）シーケンス内の設定のビット数を得る関数である。これは、ＬＯＥＳ符号内の各設定のビット（現在のエッジ）が、次のレベル上の対象ノードに関するエッジの組の記録をもたらす（葉レベルは除いて）ためである。これらの記録が水平順序で格納されると、（ＬＯＥＳ）エッジより先行し、結果として子供の記録より先行する。したがって、オフセットｏにおけるあるエッジに関する子供の記録は、そのシーケンス内のランク（ｏ）＋１番目の記録となる（根のノードには到着するエッジがないため）。これを２ビットの記録でオフセットに変換することで、次いで２ランク（ｏ）及び２ランク（ｏ）＋１の対象ノードの偽と真のエッジの現在のビットを有する各オフセットを提供する。
【００２７】
これを実行するときは、論理的にＬＯＥＳを２１６ビットのブロックと５１２（２９）ビットのサブブロックに分ける２つのレベル指数を使用する。きめの細かい時間と空間のトレードオフを可能にするドメインの必要性に応じて、これらのサブ区分を変えることができるこの指数はブロック毎にシーケンスの開始から、ブロックの開始までの設定のビット数を示す８バイトの符号なしの整数を保持する。サブブロックレベル上で、２バイトの符号化されていない値には、対応するブロック始まりからサブブロックの始まりまでの設定ビット数が格納される。したがって、ブロックの中の上記の指数は下記の通りである。
【数２】
0006029867.tif 000004
【００２８】
これらの指数を用いて、このランクの関数ではブロック指数及びサブブロック指数の簡単な検索と、サブブロック内の設定ビット数のカウントと、を行う。
【００２９】
一実施形態では、経路のオフセット関数が、下記のアルゴリズム２により実現可能である。
【表２】
0006029867.tif 000005
【００３０】
具体的には、経路オフセット関数は、ＬＯＥＳを通して状態の経路解釈によりナビゲートする。状態が木の根からある葉までの有効な経路を表示した場合、この関数は経路の最後のエッジの対応するビットのオフセットを戻す。さもなければ⊥に戻す。図４を参照して、このようなナビゲーションの例を説明する。
【００３１】
次に図４に目を移すと、縮小したプレフィックス木に関して、経路オフセットを有効な経路及び／又は有効な状態毎に計算することができる。具体的には、図４にはＬＯＥＳ符号化「１０、１１、１０、１１」（図３の３７０）をナビゲートして、状態＝００１が存在するかどうかを判定する工程が示されている。この簡単な例では、例示のＬＯＥＳ符号化に関して有効な状態が状態０００、０１０、及び０１１となることが分かれば、ｓ＝００１は無効であることが分かる。しかし、教育的な目的に関して、処理ｓ＝００１が無効であることを証明するプロセスは有効である。このプロセスではランク関数を用い、この関数はそのオフセットまでの、及びそのオフセットを含む、１と設定されるビット数として規定される（０で始まる）。あるオフセットのあらゆるエッジに関して、そのノードの偽及び真のエッジの入力値を例に挙げると、それらはオフセット偽のエッジに関する２＊ランクの（オフセット）及び真のエッジに関する２＊ランクの（オフセット）＋１で見出すことができる。
【００３２】
このランクは、時間を改善して特定のオフセットに関するランクを計算する指数内の設定ビット数を含んで、そのオフセットまで及そのオフセットを含む設定のビット数をカウントするため、先行するブロック及びサブブロックの指数の中に格納される値を合計することにより、検査されるサブブロック内の個々のビットシーケンスまでの値を得ることができ、次いでそれをビットごとに検査する。
【００３３】
経路オフセットはランク関数を用いてＬＯＥＳ符号化３７０をナビゲートする。０のオフセット（即ち、図４のｉ０で）の根３３０で始まり、０の状態ビットに関する２＊ランクの（オフセット）又は１の状態ビットに関する２＊ランクの（オフセット）のどちらかが計算されて新しいオフセットが得られ、次いでその場所のＬＯＥＳのビットがテストされる。値が１（この場合で図４のｉ１）ならば、それは葉が存在し、したがってのここまでの経路有効であることを示す。値が０ならば、それは葉が存在せず、経路は無効であることを示す。経路が有効ならば、次いで状態のビットが検査され、新しいオフセットが計算される。この処理は状態各ビットが検査され、ＬＯＥＳの最も下のレベルに到達するまで行われる。最終ビットがオフセットを通して位置し、検査により１ビットにより葉が存在したとき、この状態は有効な状態である。経路のいずれのポイントが無効の場合、例（即ち、図４のｉ２）のように、この状態はＬＯＥＳ符号化の中で示される要素ではない。
【００３４】
オフセット関数に基づくと、要素のテストは簡単である。状態、その経路解釈がプレフィックス木を通す有効な経路の場合に及びその場合でのみ、設定は状態を含む。
【００３５】
ＬＯＥＳ符号化内の状態に関する要素のテストは、図１の１０２、１０４、及び１０６等の有効な経路等の所与の状態に関するＬＯＥＳ符号化内の有効な経路の存在によって判定することである。
【００３６】
一実施形態では、要素指数の関数は下記のアルゴリズム３の中の工程により実行することができる。
【表３】
0006029867.tif 000006
【００３７】
要素指数の関数とは、状態と値｛⊥、０、…、ｎ−１｝をマップ化することである。そのマップは、設定の全ての要素状態に関する全単射型であり、したがってポインタを必要としないで各要素に関する補助データを関連付けることができる。この考えは、各設定要素の経路がこの木の葉レベルでの一意のエッジに対応することである。経路オフセットの関数により、そのビットのアドレスを得ることができる。アドレスのランクを計算することで、各状態が連続する範囲の一意の整数に割り当てられる。これらの値は、最後の１つ前の層＋１の最後のオフセットランクを減算することにより正規化されて間隔（０：ｎ）となる。これらのコンセプトは図５に示される。
【００３８】
図５に目を移すと、例示の設定２２０内の全ての状態に関する補助データに対する指数のマップ５００が示されている。指数マップ５００は、ＬＯＥＳ符号化３７０「１０１１１０１１」の指数ブロック及びサブブロックに対して使用される指数から分離される。状態空間から補助データ構造への指数のマップ化５００は、全単射であり、そのため、記述した通り、ポインタを使用する必要がない、即ちポインタによる付加的なメモリは必要ない。
【００３９】
指数マップ５００は正規化されて間隔（０；ｎ）となる。但し、ｎは状態空間の数である。この例では、各状態空間２２０（０００、０１０、及び０１１）に関する指数を見出すために、上記に説明したランク関数が用いられている。各状態空間に関するオフセットは、上記に議論された経路オフセット又は最終オフセットを用いて見出される。そのオフセットのランクを見出すことで値を導き出すことができ、この導き出された値は、この例では、状態空間毎に４、５、及び６として示されている。前のレベル内の最後のエッジのランクに１を加算し、次いでその値を、状態経路のオフセットのランクより得た値から減算して正規化された指数を導き出す。これを次のように表すこともできる。ランク（オフセット）−（ランク（前のレベル最後のエッジ）＋１）又はランク（オフセット）−ランク（前のレベルの最後のエッジ）−１。この例では、ランク（前のレベル最後のエッジ）は３であり、それはＬＯＥＳ符号化３７０「１０１１１０１１」の０から３までの位置内の設定ビットのカウントである。
【００４０】
レベルの境（即ちそれらの指数）を、予め計算しておき、レベルのシーケンスを加えられるとき格納する（メモリをほとんど使わない）、又は続く特性の上誘導的にオンディマンドベースで計算してもよい。最初のレベルは、絶えず２ビットの単一の記録からなる。以前の全てのレベルの長さを考慮してレベルｌ＋１の長さを計算するために、レベル内の設定ビットの数ｋ（その長さ：そのシーケンスの開始及び終了はこの時点で分かる）を、ランクを用いて計算する。したがって層ｌ＋１の長さは、２ｋビットとなる。
【００４１】
木の異なるレベルを表示するＬＯＥＳのサブ範囲上を平行検索することにより設定の反復は機能する。最初の要素は、各レベル上の最初の設定ビットにより示される。葉のオフセットが増加してＬＯＥＳ内の最後の設定ビットを超えた後、この反復は終了する。アルゴリズム４により、設定内のある要素から次の要素に状態の反復を進めるための疑似コードが得られる。
【表４】
0006029867.tif 000007
【００４２】
概念的に、葉のレベルからスタートし、対応するオフセットが設定のビット位置に対応するまで増加する。オフセットが進み記録境界（２ビット毎の）を超えた場合、処理が次に高いレベルへと続く。各記録は少なくとも１つの設定ビットを含んでいるため、次の設定ビットへ進むことで、多くても１つの記録の境界しか超えない。図６はこの例に関する異なる状態の反復を示し、ＬＯＥＳの数「１０１１１０１１」は、木のレベル０（３４０）で「１０」、木のレベル１（３５０）で「１１」、木のレベル２（３６０）で「１０１１」から成る。ＬＯＥＳ内の偶数のオフセットは偽のレベル（「０」）に対応し、奇数のオフセットは真レベル（「１」）に対応する。したがって、オフセット配列から要素を簡単に再構築することができる。但し、反復は常に辞書式順序の要素に戻る。この特性は、設定の構築の間使用される。
【００４３】
引き続き図６を参照して、この例の設定に関する設定の反復について説明する。この図の第１列は、黒のポインタ６００、灰色のポインタ６０２、及び白のポインタ６０４によりそれぞれ示された木レベル０、１、及び２（３４０、３５０、３６０）に対応するＬＯＥＳのオフセットを示す。第２列は、これらのオフセット（ｍｏｄ２）からどのようにしてＬＯＥＳ３７０「１０１１１０１１」により示される状態２２０（０００、０１０、０１１）が得られるかを示している。この状態の設定は、ＬＯＥＳ符号化内の各レベルに対する平行検索を行うことにより繰り返され、第１の要素は各レベル（３４０、３５０、３６０）の第１の設定ビットにより示される。このスイープは最も低いレベルで始まり１設定ビットから次へと進む。ビット組内の前進では、次に高いレベルのポインタが同じように全ての設定ビットが繰り返されるまで前進する。但し、反復は常に辞書式順序の要素に戻る。
【００４４】
ＬＯＥＳは静的構造を有する。一般に必要な要素を加えることにより、局所的に限定されていないビットの文字列に変化する、したがって単純な反復のコストはＯ（ｎ）である。このトピックスについて詳しく説明するために、最初に辞書的順序の状態のシーケンスが、どのようにＬＯＥＳへ変換されるかについて考察する。まず、空のビットシーケンスが、木の各層毎に初期化される。アルゴリズム５は、新しい状態を加えたときこれらのシーケンスがどのように操作されるかを示す。
【表５】
0006029867.tif 000008
【００４５】
具体的には、設定が空の場合、対応する記録が全てのレベルに追加される。それ以外では、最初に異なるビットｓとｓ’の間の位置、即ち、深さｄが決められる。シーケンスｄの最後のビットが真と設定され、ｓによる記録がそれより低い全てのレベルに追加される。複製物（即ちｓ＝ｓ’）は、単に無視される。最後の状態が追加された後、全てのシーケンスは水平順序で連結されてＬＯＥＳを形成する。
【００４６】
図７は、実行例に関するこの処理を示す。ＬＯＥＳの静的性質により、バッチ内の状態を追加することが好ましい。ＬＯＥＳの設定に対する反復は、辞書式順序内の要素に戻る。このようなやり方で、初期設定、及び辞書式に順序付けられた状態のバッチに対して同時に反復し、新しいＬＯＥＳに要求された順序で供給することが可能となる。バッチがほぼ設定のサイズと同じ場合、挿入の償却原価Ｏ（ｌｏｇｎ）である。辞書式に順序付けされたバッチを有する必要からこのログは付けられていが、但し、最適な時間性能を得るためには、ＬＯＥＳに基づく検索、即ち、プランニングシステムはこの特性を避けて設計されなければならない。
【００４７】
さらに図７を参照すると、ＬＯＥＳ符号化に加えられる要素に対する符号化が示されている。各要素はビットの組を用いて符号化され、符号化される状態の各ビットが、各レベル（木のレベル０、木のレベル１、木のレベル２）内のビットの組の１ビットを示す。状態０００に関して、各ビットは０であり、したがって１０で示され、最初のビットが１に設定されて０、即ち、偽の葉の存在を示し、２番目のビットが１、即ち、真の葉が存在していないため、０で示される。２番目の要素を追加するとき、ビットの組は既に存在し、したがって各レベル内の適切なビットだけを設定する必要がある。設定０１０の例では、２番目のレベル内でビットが設定されて１即ち真の葉が存在していることを示し、ビット組が、真の葉の存在又は２番目のレベル内の設定ビットとして３番目のレベル内に追加される。３番目の要素である設定０１１を追加するとき、ビット組は存在し最初と２番目のレベル内に設定される。最後のレベル内のビットの組の適切なビットだけを設定する必要がある。各要素が追加された後、シーケンスは水平順序で連結されてＬＯＥＳ符号化を形成する。次いで、この追加される要素のＬＯＥＳ符号化を、元のＬＯＥＳ符号化と結合することができる。バッチ内の新しい状態を加えることが好ましい。
【００４８】
このＬＯＥＳ符号化の結合は、設定の反復を通して同時に行われる。設定の反復により、辞書式順序の状態が作り出される。したがって、これらの状態は比較され、それに対応するシーケンスが追加又は変更され、次いで組み合わせた状態の設定の新しいＬＯＥＳの構造に統合される。複製された状態は単に無視される。
【００４９】
ＬＯＥＳ符号化結合に必要なメモリ容量を最小にするため、ビットシーケンスを同じサイズメモリ空間内に保持することができ、このメモリ空間は破壊読込をサポートする。これにより、この構造を横断する間必要のないメモリ空間を自由にすることができ、結合動作に関するピークメモリ要求を著しく削減することができる。
【００５０】
本明細書に記載されたコンセプトが、種々のコンピュータシステム上で実行され得ることを理解されたい。一例として、このようなコンピュータシステム（即ち電子コンピュータ装置）８００を図８に示す。このコンピュータシステムは、その他の構成部品と共に、モニタ８０２、キーボード８０４、演算部８０６、及び外部メモリディスク８０８等の外部メモリを含む。演算部８０６は、ＣＰＵ、電子プロセッサ、グラフィック処理ユニット（ＧＰＵ）又はその他のコンピュータ部品８１０、及びＲＡＭ等の内部メモリ８１２を含む。演算部８０６はその他の構成部品を含み、本明細書に示す以外の構成で設計できることも、もちろん言うまでもない。外部メモリ８０８は外付けと考えられ、実際には演算部８０６の外側であり、これにより内部メモリ８１２に比べてかなり遅いＩ／Ｏ動作となる。また、オプションのディスク８１４で示す通り、ディスク８０８を実際に演算部８０６に含むことも、又は含まないこともできる。例えば、オプションのディスク８１４は、ネットワーク装置でもよい。
【００５１】
上記のコンセプト（例えば、プランニングに関する簡素な適用可能な状態設定の表示）実験的に評価した。続く議論及びデータ（例えば、表１及び２）は、限定された内容の特定な実施形態に対して提示されていることは明白である。一方、今説明しているコンセプトはその他の実施形態及び内容に適用可能と理解できる。したがって、この例では、国際プランニング競技（ＩＰＣ）のドメインの範囲内でのブラインド検索中に必要なピークメモリに焦点を当てる。この目的を達成するために、ＬＯＥＳとＢＯＤの比較評価に関して、幅優先検索の環境が実装された。ＬＯＥＳを最先端のプランナであるブラインド・ヒューリスティック・モードのファーストダウンワード（ＦＤ）とも比較し、ＦＤのリプロセッサにより生成されたＳＡＳ＋表示が入力として全てのテストで使用した。プランナのＢＯＤバージョンは、ＢｕＤＤｙパッケージ（二分決定グラフパッケージ）に基づき、ブラックボックスの設定表示として扱った。各層の後、変数記録はパッケージの推奨されたヒューリスティックを用いて行われた。層内の拡張の順序は一般に、ＢＯＤバージョンとＬＯＥＳバージョンの固有の反復順序により異なるため、今回のテストに関して開閉は、実現できない最後の層が拡張した後に調べられた。評価の間はＬＯＥＳのビット文字列に関して１２８バイトのメモリ容量が使われ、ＬＯＥＳに変換される前はピーク状態のために１メガバイトのバッファーが用いられた。使用されたテストマシンは、２台のインテル２．２６ＧＨｚＸｅｏｎプロセッサ（それぞれ４つのメモリを有する）及び８ＧＢのＲＡＭである。実験では、マルチスレッドを使用していない。
【００５２】
結果の概要を表１に示す。サイズの比較に関して、この表では明示状態の格納に関して参考として、（バティング又は関節費のない）まとまった状態（詰め込まれた）の理想的な連結を示す。最も小さなインスタンスを除いて、ＬＯＥＳの実際のピークメモリ要求は（理想的な）詰め込まれたものピークメモリ要求より十分に低い。全てのテストドメインの大きな場合に対して、設定要素は、平均で、理想的に詰め込んだ表示のメモリの６〜５８％のメモリしか必要しなかった。ＢＯＤが取り除く冗長性も、そのかなりの割合をＬＯＥＳも削除するため、その圧縮率は後者に近いが、分散はかなり小さい。具体的には、ＬＯＥＳは、ＢＯＤがドメイン内で晒されるフリーセル、ミクロバン、及びｎパズルのような引き伸ばしをさけて、全てのテストドメイン全般で安定性を示す。ＬＯＥＳは、また良好な圧縮に関して大きな設定に依存せず、検索空間の大部分を良好なヒューリスティック関数により取り除くことができればＢＯＤよりもより魅力的でさえある。ＢＯＤに対するもう一つの重要な優位性は、ＬＯＥＳではポインタを使わずに任意のデータを設定要素に関連付けることができることである。これにより大幅なシンボルのオーバーヘッド及び明示状態の検索の格納を表示することができる。
【００５３】
実行時間の比較ではＬＯＥＳは有利ではないことが表１から分かる。両方が解決できる大きなインスタンスに関して、ＦＤよりも１０及び２０倍長く時間を費やしている。あるオーバーヘッドはＬＯＥＳを用いていることから派生しているが、かなりの部分は現時点での実装によるもので、それは十分に改善できる。ノードを拡張するために、本実装では線形走査を接地演算子の設定全体に対して行って予備条件を満たすものを見出している。これに対しＦＤは決定木を用いて適用可能な演算子の設定を素早く決定する。同じ決定木を用いたならば、もちろん本プランナの速度を改善することができる。オーバーヘッドのもう１つの要因は、小さいバッファー用いて新しく生成される後続要素を収容し、このバッファーがいっぱいになったときはいつでも、次の層内の以前に生成された全ての状態を反復することも含み次の層のＬＯＥＳと組み合わせるために、現時点での実装がバルクインサートに関し特に最適化されていないことである。
【表６】
0006029867.tif 000009
【００５４】
表１には、多くのＩＰＣドメインに関する実験結果、即ち、詰め込まれた状態理想的に連結されたビット文字列、ＬＯＥＳ及びＢＤＤの間のピークメモリ要求の比較と、ファーストダウンフォワード（ＦＤ）及びＬＯＥＳの間の実行時間の比較との両方からの実験結果が示されている。Ｏ｜∪｜Ｃは状態の数を示し、層ｓｐｃｋ、ｓｌｏｅｓ及びｓｂｄｄは、詰め込めた、ＬＯＥＳ、及びＢＤＤ格納部品の各メモリ要求を（ＭＢで）示す。ｔｆｄ及びｔｌｏｅｓは、それぞれ実行時間を秒で示す（又は処理が時間切れ場合はＭＥＭ）。＊を表示されたインスタンスはまだ実行中であり、その場合、ＢＤＤ及びＬＯＥＳの両方が処理した最も大きな層から得た数字を含む。＊＊を表示されたインスタンスは解決していない。したがって、その数字は表示する到達可能な検索空間を示す。
【００５５】
もちろん、ＦＤは理想的に詰め込まれた表示で状態を格納しない、その代り設定の格納に関して時間効率が高いＣ＋＋ＳＴＬの構成要素を使用する。これによりかなりの空間オーバーヘッドがもたらされる。表２には、各ドメインの両方が解決できる最も大きなインスタンス上のＬＯＥＳ及びＦＤに関するピーク処理メモリの割り当ての比較が示されている。ポインタによる影響を示すため、ＦＤの３２ビット２進値に関する数値も含まれている。この表に示されるように、ＦＤはＬＯＥＳより、２桁まで大きな容量のＲＡＭを用いている。ＦＤが後続要素の生成においてより進んでいることを考えると、各ドメイン内のインスタンスのサイズで増えても、ＬＯＥＳは一定の倍数分だけしか遅くならないというのは少々驚きである。
【表７】
0006029867.tif 000010
【００５６】
ＬＯＥＳは、全てのサイズの明示状態の設定を表示する良好な空間効率を示している。それは、ｎパズル等の以前から堅固に組み合わされたドメイン内でさえも効率のよく空間の節約できる。具体的には、設定要素上の連続するアドレス空間を規定し、これによりオーバーヘッドに対処する必要なしに、空間効率よく補助データを設定要素に関連付けることができる。理論的には、その設定要素のテストの煩雑性は状態符号化のサイズのみに依存し、設定サイズには依存しないため、ＬＯＥＳは、特に大きな課題では、良好な時間効率も提供するはずである。ＬＯＥＳに関する特定な用途ではパターンデータベース（ＰＤＢ）を用いる。従来から、このクラスのヒューリスティックは、良好な検索性能を有する空間効率の良い表示に依存する。ＬＯＥＳの静的性質及びオーバーヘッドを作り出す可能性は、ＰＤＢに関してはほとんど心配ない。本出願のコンセプトを組み込んだＬＯＥＳ又は類似する表示は、ヒューリスティック検索に関する重複検出、及び一般の設定表示でも使用することができる。
【００５７】
詰め込まれた状態のソートされたリストをほとんどオーバーヘッドなしにＬＯＥＳに変換することができ、そのＬＯＥＳによりたとえ小さな設定にでも。良好な圧縮が行われることが分かる。整列併合された構造は、非常に不均等なＬＯＥＳ結合が、もう一方の存在が同じようなサイズになり償却された（ｌｏｇｎ）の構造を実現するのをサポートするまで遅れる。両方のケースでも、コンピュータシステム内の未使用のＲＡＭを用いて直接設定の構築のスピードをアップし、一方でメモリが乏しくなったときに、開示されたコンセプトによる最小ピークメモリを構築するアプローチが、フォールバックとして機能する。
【図１】
0006029867.tif 000011
【図２】
0006029867.tif 000012
【図３】
0006029867.tif 000013
【図４】
0006029867.tif 000014
【図５】
0006029867.tif 000015
【図６】
0006029867.tif 000016
【図７】
0006029867.tif 000017
【図８】
0006029867.tif 000018