(57)【要約】【課題】  分散的な情報処理を実現可能であり、しかもデータの同一性の検証を容易化することができる情報処理装置を提供する。【解決手段】  所定の記号の集合に属する記号の有限列である語を示す語データを取得する語入力部３０と、前記語が前記集合の所定の部分集合に属する記号の有限列であるか否かを判定する識別データ検査部３９と、前記語が前記部分集合に属する記号の有限列である場合に、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定するとともに、前記語が前記部分集合に属する記号の有限列でない場合に、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定する識別データ付与部４１と、を含むことを特徴とする。【選択図】        図７
2007058281.tif 000002
【特許請求の範囲】
【請求項１】
所定の記号の集合に属する記号の有限列である語を示す語データを取得する語データ取得手段と、
前記語データが示す前記語が前記集合の所定の部分集合に属する記号の有限列であるか否かを判定する語判定手段と、
前記語データが示す前記語が前記部分集合に属する記号の有限列である場合に、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する第１記号データ決定手段と、
前記語データが示す前記語が前記部分集合に属する記号の有限列でない場合に、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定する第２記号データ決定手段と、
を含むことを特徴とする情報処理装置。
【請求項２】
請求項１に記載の情報処理装置において、
前記第１記号データ決定手段は、前記語データにハッシュ関数を適用した結果に基づき、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する、
ことを特徴とする情報処理装置。
【請求項３】
請求項１又は２に記載の情報処理装置において、
前記第２記号データ決定手段は、
前記語データがミュータブルであるか否かを判断する手段と、
前記語データがミュータブルでない場合に、前記語データにハッシュ関数を適用した結果に基づき、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定するイミュータブルオブジェクト用記号データ決定手段と、
前記語データがミュータブルである場合に、乱数に基づき、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定するミュータブルオブジェクト用記号データ決定手段と、を含む、
ことを特徴とする画像情報処理装置。
【請求項４】
請求項３に記載の情報処理装置において、
前記語データのうち、前記第１記号データ決定手段又は前記イミュータブルオブジェクト用記号データ決定手段のいずれかにより、その対応する記号データが決定されるものを記憶するイミュータブル記憶手段と、
前記ミュータブルオブジェクト用記号データ決定手段により決定される記号データと、該記号データに対応する前記語データと、を対応づけて記憶するミュータブル記憶手段と、
をさらに含むことを特徴とする情報処理装置。
【請求項５】
請求項１乃至４のいずれかに記載の情報処理装置において、
第１の記号を示す第１記号データを取得する第１記号データ取得手段と、
第２の記号を示す第２記号データを取得する第２記号データ取得手段と、
前記第１記号データが示す前記第１の記号と前記第２記号データが示す前記第２の記号とが共に前記部分集合に属する記号を示す場合に、前記第１の記号と前記第２の記号とが等しいか否かに応じて、前記第１の記号と前記第２の記号との同値関係を判定する同値関係判定手段と、
をさらに含むことを特徴とする情報処理装置。
【請求項６】
請求項５に記載の情報処理装置において、
前記同値関係判定手段は、
前記第１記号データが示す前記第１の記号と前記第２記号データが示す前記第２の記号のうち、いずれか少なくとも一方が、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す場合に、前記第１の記号と前記第２の記号とが等しいか否か、又は前記第１の記号に対応する前記語データと前記第２の記号に対応する前記語データとが等しいか否かに応じて、前記第１の記号と前記第２の記号との同値関係を判定する、
ことを特徴とする情報処理装置。
【請求項７】
所定の記号の集合に属する記号の有限列である語を示す語データを取得する語データ取得ステップと、
前記語データが示す前記語が前記集合の所定の部分集合に属する記号の有限列であるか否かを判定する語判定ステップと、
前記語データが示す前記語が前記部分集合に属する記号の有限列である場合に、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する第１記号データ決定ステップと、
前記語データが示す前記語が前記部分集合に属する記号の有限列でない場合に、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定する第２記号データ決定ステップと、
を含むことを特徴とする情報処理方法。
【請求項８】
所定の記号の集合に属する記号の有限列である語を示す語データを取得する語データ取得手段、
前記語データが示す前記語が前記集合の所定の部分集合に属する記号の有限列であるか否かを判定する語判定手段、
前記語データが示す前記語が前記部分集合に属する記号の有限列である場合に、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する第１記号データ決定手段、及び
前記語データが示す前記語が前記部分集合に属する記号の有限列でない場合に、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定する第２記号データ決定手段
としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置、情報処理方法及びプログラムに関し、特に、分散的な情報処理に適した、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
情報オブジェクトの管理手法としてハッシュコンシング（hash consing）と呼ばれるものがある。まずハッシュコンシングの一般化について簡単に説明する。なお説明を簡単にするために、Ａをアルファベット（記号の集合）、Ａ*をＡ上の語（Ａ上の記号の有限列）の全体の集合、ＬをＡ上の有限言語（Ａ*の部分集合）、r:  Ａ*→Ａをランダム関数（実用的には耐衝突性を持った一方向性関数、つまり、暗号学的ハッシュ関数）、r(Ｌ)をrによるＬの像、ｒL:  Ｌ→r(Ｌ)  を、rをＬに制限した部分関数とする。これらをまとめて図示とすると次式（１）のようになる。
【０００３】
【数１】
2007058281.tif 000003
【０００４】
ここで、次式（２）が満足されるならばｒLは実質的に双射となる。ここで、｜Ｌ｜はＬに含まれる元の個数を示しており、πは円周率を示している。
【０００５】
【数２】
2007058281.tif 000004
【０００６】
正確に言うと、rがＬ上で単射ではなくなる。つまり、少なくとも１つの衝突対(x,y), x≠y, r(x)=r(y)が存在する確率が１/２を超えるのは、次式（３）が満足される場合である。
【０００７】
【数３】
2007058281.tif 000005
【０００８】
したがって、例えば、Ａとして１つのシンボルが５１２ビットの複雑度を持つアルファベットを選択し、rとして次式（４）よりも少ないオーダーのステップ数で衝突を生成するアルゴリズムが知られていない関数を選択することによって、現実的なＬの上で事実上ｒLは可逆な変換とみなせる。
【０００９】
【数４】
2007058281.tif 000006
【００１０】
ハッシュコンシングでは、このようなハッシュ関数の性質を利用して、任意の長さの語を単一の記号で表現するものである。かかるハッシュコンシングのメリットとしては、以下が挙げられる。
【００１１】
１．同一内容のデータ構造を１つしか保持しなくてすむためにデータ領域が節約できる。
【００１２】
２．データの同一性を検証するためにハッシュ値を比較するだけですみ、処理が高速化できる。
【００１３】
３.ハッシュ値はデータが偶然配置される場所によらないため、データ実体を用いずとも可搬性が保証できる（つまり分散した装置間で情報オブジェクトを共有するときにデータ実体のかわりにハッシュ値を用いることができる。）。
【００１４】
なお、このようなハッシュコンシングを用いたシステムの具体例が下記の非特許文献１に記載されている。ハッシュコンシングは、その名前からも分かるように、当初Lispにおいてイミュータブル（不変（書き換え不能）なconsセルの実装方式として提案された。従って、下記の非特許文献１では、car部とcdr部とからなる長さ２の語を記号に対応づけることが説明されている。
【非特許文献１】後藤英一著、“Monocopy and Associate Algorithms in an Extended Lisp”、Technical Report、東京大学、１９７４年５月、７４−０３
【発明の開示】
【発明が解決しようとする課題】
【００１５】
しかしながら、純粋なハッシュコンシングでは、循環参照に代表されるミュータブル（可変）なデータ構造を扱うことが不得手である。従来は、このようなデータ構造も扱えるようにするために、ハッシュコンシング形式のconsセル（hconsセル）とヒープおよびポインタを利用した通常のconsセルとを併用していた。この場合、通常のconsセルについては可搬性が保証できなくなり、分散的な情報処理が行えない。ポインタの有効性は単一のアドレス空間内に限られるからである。
【００１６】
そこで通常のヒープおよびポインタを利用したconsセルに代えて、ランダムに生成した記号（記号は通常のアドレス空間（例えば３２ビット）ではなくハッシュ値の空間（例えば５１２ビット）で選択される）をキーとし、語を値とするテーブルを生成することが考えられる。こうすれば、ランダムに生成したキーの有効性は単一のアドレス空間内に限られないことから、ハッシュコンシングを分散的な情報処理に用いることができるようになる。
【００１７】
しかしながら、この方法を採用した場合、オブジェクトを参照する記号は所与のアルファベットから無作為に抽出された記号と見えるので、二つの記号xとyから展開されるマークル（Merkle）グラフが同型であることを確認するためには、記号から完全なグラフを再度生成せざるを得ず、ハッシュコンシングのメリットのうち、上記２、すなわちデータの同一性の検証の容易化を損なうことは否めない。
【００１８】
ここで、マークルグラフとは、ａ及びｂ＿Ｉを記号として、ａ＝ｈ（ｂ＿１・・・ｂ＿ｎ）であるか上記テーブルにキーａに対してｂ＿1・・・ｂ＿ｎを値とするエントリがある場合に、項ａから項ｂ＿ｉに向き付けられたエッジを与えることによって生じるグラフのこととする。
【００１９】
本発明は上記課題を解決する為になされたもので、その目的の１つは、分散的な情報処理を実現可能であり、しかもデータの同一性の検証を容易化することができる情報処理装置、情報処理方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００２０】
上記課題を解決するために、本発明に係る情報処理装置は、所定の記号の集合に属する記号の有限列である語を示す語データを取得する語データ取得手段と、前記語データが示す前記語が前記集合の所定の部分集合に属する記号の有限列であるか否かを判定する語判定手段と、前記語データが示す前記語が前記部分集合に属する記号の有限列である場合に、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する第１記号データ決定手段と、前記語データが示す前記語が前記部分集合に属する記号の有限列でない場合に、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定する第２記号データ決定手段と、を含むことを特徴とする。
【００２１】
また、本発明に係る情報処理方法は、所定の記号の集合に属する記号の有限列である語を示す語データを取得する語データ取得ステップと、前記語データが示す前記語が前記集合の所定の部分集合に属する記号の有限列であるか否かを判定する語判定ステップと、前記語データが示す前記語が前記部分集合に属する記号の有限列である場合に、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する第１記号データ決定ステップと、前記語データが示す前記語が前記部分集合に属する記号の有限列でない場合に、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定する第２記号データ決定ステップと、を含むことを特徴とする。
【００２２】
さらに、本発明に係るプログラムは、所定の記号の集合に属する記号の有限列である語を示す語データを取得する語データ取得手段、前記語データが示す前記語が前記集合の所定の部分集合に属する記号の有限列であるか否かを判定する語判定手段、前記語データが示す前記語が前記部分集合に属する記号の有限列である場合に、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する第１記号データ決定手段、及び前記語データが示す前記語が前記部分集合に属する記号の有限列でない場合に、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定する第２記号データ決定手段としてコンピュータを機能させるためのプログラムである。
【００２３】
本発明によれば、語データに記号データが対応づけられる。このとき、語データは語を示すデータであり、語は、所定の記号の集合に属する記号の有限列である。そして、語データが示す語が、上記集合の部分集合に属する記号だけの有限列である場合には、その部分集合に属する記号を示す記号データを、該語データに対応づける。また、語データが示す語が、上記集合の部分集合に属する記号だけの有限列ではない場合には、その前記集合に属する記号であって、前記部分集合に属する記号ではないものを示す記号データを、該語データに対応づける。こうすれば、記号データが前記部分集合に属する記号を示すか否かによって、該記号データに対応する語データが示している語が、前記部分集合に属する記号以外の記号を含むか否かを直ちに判断できる。従って、部分集合に属する記号のみで閉じて表現される語については、記号の比較だけで直ちに同一性の判断が可能となる。
【００２４】
また、本発明の一態様では、前記第１記号データ決定手段は、前記語データにハッシュ関数を適用した結果に基づき、前記語データに対応する記号データとして、前記部分集合に属する記号を示す記号データを決定する。こうすれば、記号データにより語データの同一性の検証が可能となる。
【００２５】
また、本発明の一態様では、前記第２記号データ決定手段は、前記語データがミュータブル（可変）であるか否かを判断する手段と、前記語データがミュータブルでない場合（つまりイミュータブル（不変）である場合）に、前記語データにハッシュ関数を適用した結果に基づき、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定するイミュータブルオブジェクト用記号データ決定手段と、前記語データがミュータブルである場合に、乱数に基づき、前記語データに対応する記号データとして、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す記号データを決定するミュータブルオブジェクト用記号データ決定手段と、を含む。
【００２６】
この態様では、前記語データのうち、前記第１記号データ決定手段又は前記イミュータブルオブジェクト用記号データ決定手段のいずれかにより、その対応する記号データが決定されるものを記憶するイミュータブル記憶手段と、前記ミュータブルオブジェクト用記号データ決定手段により決定される記号データと、該記号データに対応する前記語データと、を対応づけて記憶するミュータブル記憶手段と、をさらに含むようにしてもよい。
【００２７】
また、本発明の一態様では、第１の記号を示す第１記号データを取得する第１記号データ取得手段と、第２の記号を示す第２記号データを取得する第２記号データ取得手段と、前記第１記号データが示す前記第１の記号と前記第２記号データが示す前記第２の記号とが共に前記部分集合に属する記号を示す場合に、前記第１の記号と前記第２の記号とが等しいか否かに応じて、前記第１の記号と前記第２の記号との同値関係を判定する同値関係判定手段と、をさらに含む。
【００２８】
この態様では、前記同値関係判定手段は、前記第１記号データが示す前記第１の記号と前記第２記号データが示す前記第２の記号のうち、いずれか少なくとも一方が、前記集合に属する記号のうち前記部分集合に属する記号以外の記号を示す場合に、前記第１の記号と前記第２の記号とが等しいか否か、又は前記第１の記号に対応する前記語データと前記第２の記号に対応する前記語データとが等しいか否かに応じて、前記第１の記号と前記第２の記号との同値関係を判定するようにしてもよい。
【発明を実施するための最良の形態】
【００２９】
本発明の実施形態について図面を参照しながら説明する。
【００３０】
以下において、アルファベットとは記号の有限集合のことである。アルファベットＡの元をＡ上の記号と呼ぶ。アルファベットＡ上の記号の有限列をＡ上の語と呼び、Ａ上の語の全体の集合をＡ*で表す。また、Ａ上の語の集合、つまりＡ*の部分集合をＡ上の言語と呼ぶ。写像r:  Ａ*→Ａを自己再帰的アルファベットと呼ぶ。自己再帰的アルファベットr:  Ａ*→Ａを(Ａ,r)、あるいはさらに簡単にＡと書くこともある。このとき写像rを自己再帰的アルファベットＡの簡約写像と呼ぶことにする。自己再帰的アルファベットＡ上の有限言語Ｌの上で簡約写像rが単射になるとき、Ｌは整であるという。
【００３１】
本実施形態では、記号の集合であるアルファベットＡ及びＡの部分アルファベットＡ０に対して、写像r:  Ａ*→Ａを評価する語の簡約手段を備える。語、すなわち記号の有限列が部分アルファベットＡ０上の語であるか否かを判定して、該語がＡ０上の語である場合には、写像Ａ０*→Ａ０によって、該語を評価する。すなわち、語がＡ０上の語である場合には、Ａ０上の記号を該語に対応づける。また、語がＡ０上の語でない場合には、写像Ａ*＼Ａ０*→Ａ＼Ａ０によって、該語を評価する。すなわち、語がＡ０上の語でない場合には、Ａに属する記号のうちＡ０に属する記号以外の記号を該語に対応づける。
【００３２】
ここでは、アルファベットＡを所定長のビット列の集合とし、部分アルファベットＡ０を、そのうち所定位置のビット（例えば先頭ビット）が０である同じ長さのビット列の集合とする。また、Ａ＼Ａ０を同じ位置のビットが１である同じ長さのビット列とする。つまり、アルファベットＡに属する記号は、その所定位置のビットが０であるか１であるかにより、部分アルファベットＡ０に属するか、Ａ＼Ａ０に属するかを直ちに判断することができるようにしている。
【００３３】
本実施形態では、アルファベットＡ上の有限言語Ｌを記憶する手段を含む。この際、特に各有限言語Ｌに関連づけて、該有限言語Ｌのハッシュ値に基づいて決定される、先頭ビットが０である所定長のビット列を記憶している。また、部分アルファベットＡ＼Ａ０から語の集合Ａ*への有限な関数関係Ｒを記憶する手段を含む。すなわち、部分アルファベットＡ＼Ａ０に属する記号と該記号に対応するアルファベットＡ上の語とを関連づけて記憶している。こうして、記号から、その記号に対応する語を取得できるようにしている。
【００３４】
また、本実施形態では、部分写像σ:  Ａ×Ｎ*×Ａ→Ａを評価する手段を備える。そして、記号xと位置(i0,…,in-1)と記号yの組(x,(i0,…,in-1),y)について、例えばハッシュ値を生成して、xをルートとするマークル（Merkle）木における位置(i0,…,in-1)の記号をｙに置換したマークル木のルートとなる記号xi,yを評価値としてもよい。
【００３５】
また、本実施形態では、記号の同値関係を判定する手段を含む。具体的には、Ａ）部分アルファベットＡ０上では、記号ｘと記号ｙとが等しい場合に両記号は同値である。また、部分アルファベットＡ０上の記号と部分アルファベットＡ＼Ａ０上の記号とは決して同値関係を満たさない。また、Ｂ）部分アルファベットＡ＼Ａ０上では、記号対(x,y)が同値になるのは、Ｂ１）記号xと記号yとが等しい場合、又はＢ２）記号xと記号yとが共に評価可能であり、記号xを評価した語（記号xに対応する語）の長さと、記号yを評価した語（記号yに対応する語）の長さとが等しく、それらをx0,…,xn-1、y0,…,yn-1としたとき、各ｉについて記号xiと記号yiとが同値である場合である。
【００３６】
以下、具体的な実装について説明する。本実施形態に係る分散型コンピューティングシステム１０は、図１に示すように、複数のコンピュータ１２と、ミュータブル記憶部２０と、イミュータブル記憶部２２と、を含んで構成され、さらにこれらが通信ネットワーク１４を介して相互に接続される情報処理システムである。
【００３７】
コンピュータ１２には、パーソナルコンピュータ、ワークステーション、携帯電話などの各種コンピュータを使用することができる。そして、各コンピュータ１２においては、処理の一単位であるプロセスが少なくとも１つ実行される。
【００３８】
ミュータブル記憶部２０は、例えば通信ネットワーク１４と接続されるサーバコンピュータに実装され、書き換え可能（ミュータブル）なデータオブジェクトを表現する語を記号と対応付けてなるテーブル（ミュータブルテーブル）を記憶する。ここで、記号とは、即値又は語を参照する識別子としてコンピュータ１２において処理されるデータであり、語とは、記号の有限列である。
【００３９】
ミュータブルテーブルの例を図２に示す。同図に示すように、ミュータブルテーブルでは、ランダムに生成された記号をキー（乱数を示すデータ）として、語を値として、対応関係が記憶される。このような表はいわゆるハッシュテーブル（連想配列）と呼ばれるデータ構造を用いて適切に実装できる。
【００４０】
イミュータブル記憶部２２も、例えば通信ネットワーク１４と接続されるサーバコンピュータに実装され、書き換え不可能（イミュータブル）なデータオブジェクトを表現する語を記号と対応付けて記憶するテーブル（イミュータブルテーブル）を記憶する。イミュータブルテーブルの例を図３に示す。同図に示すように、イミュータブルテーブルでは、語は語自身のハッシュ値に基づいて決定される値をキーとして記憶される。なお、ハッシュ関数とは、記号の有限列である語を記号に対応させる耐衝突性を持った所与の関数のことである。
【００４１】
本実施形態では、記号の集合であるアルファベットとして５１２ビットのビット列全体の集合を選択している。したがって、上記乱数（ランダム値）と、上記ハッシュ値に基づく値（例えば語のハッシュ値の先頭ビットを強制的に１又は０に変更した値）と、はともに５１２ビットの一様に分布する値とみなせる。このアルファベットのサイズはその時点の技術レベル（仮定できる計算資源の量）において耐衝突性の困難さを保証する要請から決定される。本実施例の執筆時点では耐衝突性を保証するためには少なくとも１６０ビット、さらに望ましくは２５６ビット以上が求められており（平成１５  年２  月２０  日発行の総務省・経済省による「電子政府推奨暗号リスト」の注釈を参照）、この閾値は、分散型コンピューティングシステムで取り扱われるデータオブジェクトの潜在的な総体を表現するのに十分である。
【００４２】
さらに、本実施形態では、上述のように、記号の集合（アルファベット）として５１２ビットのビット列全体を選択しており、ミュータブルテーブル（図２）に格納するキーとしては、いずれも、図４（ａ）に示すように、先頭ビットが０である５１２ビットのビット列を格納している。
【００４３】
一方、イミュータブルテーブル（図３）には、同図（ａ）に示される、先頭ビットが０である５１２ビットのビット列も、同図（ｂ）に示される、先頭ビットが１である５１２ビットのビット列も、キーとして格納されている。具体的には、図５（ａ）に示すように、先頭ビットが０である５１２ビットのビット列Ｐのみを含む語については、図４（ａ）に示される、先頭ビットが０である５１２ビットのビット列をキーとして関連づけて記憶している。また、図５（ｂ）に示すように、先頭ビットが１である５１２ビットのビット列Ｑを少なくとも一部に含む語については、図４（ｂ）に示される、先頭ビットが１である５１２ビットのビット列をキーとして関連づけて記憶している。
【００４４】
ミュータブルテーブル（図２）については、書き換えの可能性があり、該ミュータブルテーブルに格納された語を参照する記号を一部に含む語については、その語のキーのみからでは同値関係が判定できない。一方、イミュータブルテーブル（図３）に格納された語を参照する記号のみを含む語については、その語のキーのみから同値関係が判定できる。そこで、本実施形態では、以上のようにしてキーの値を決定することにより、２つのキーの先頭ビットが共に０であれば、キー値の比較のみで同キーに対応する語が同一か否かを判断するようにしている。
【００４５】
なお、従来はミュータブルテーブルの代わりに図６に示すヒープを使用していた。該ヒープでは、語はヒープの領域中に書き込まれ、ヒープ領域中に書き込まれた語を参照するために、語の配置されたオフセット（アドレス）をポインタとして利用していた。ここで、例えばLispのように取り扱う語の長さが固定長（Lispの場合はcar部とcdr部からなるので長さは２である）ではなく可変長の語まで扱うならば、オフセットに加えてさらに語長情報を保持したり、Ｃにおける文字列のヌル終端のような規則が必要となる。ポインタは該ヒープでしか有効でなかったが、本実施形態に係るイミュータブルテーブルでは、十分大きなアルファベットからランダムに選択した記号で語を参照するため、複数のミュータブルテーブル間において記号の衝突が極めて起こりにくい。
【００４６】
通信ネットワーク１４は、ＬＡＮなどの現実の通信ネットワークでもよいし、多数のプロセス間における仮想の通信ネットワークでもよい。また、上記での説明ではミュータブル記憶部２０とイミュータブル記憶部２２は通信ネットワーク１４に接続されたサーバコンピュータに実装されることとした（同図におけるミュータブル記憶部２０−０及びイミュータブル記憶部２２−０）が、もちろん、これらをコンピュータ毎に備えさせても構わない（同図におけるミュータブル記憶部２０−１乃至ｎ及びイミュータブル記憶部２２−１乃至ｎ）。このように記憶部が多数分散していたとしても、データオブジェクトを参照する記号を十分大きなアルファベット上でランダムに分布するように生成するので記号の衝突は実質的には起きないと仮定できる。
【００４７】
次に、ミュータブルテーブル及びイミュータブルテーブルに語を書き込み、或いは語を読み出す処理について説明する。図７は、分散型コンピューティングシステム１０の機能ブロック図である。同図に示すように、分散型コンピューティングシステム１０は機能的には、語入力部３０、判断部３２、ランダム値取得部３４、識別データ付与部３５、ミュータブル記憶書込部３６、ハッシュ値取得部３８、識別データ検査部３９、識別データ付与部４１、イミュータブル記憶書込部４０、記号入力部５０、ミュータブル記憶読出部５２、イミュータブル記憶読出部５４、検索部５６、記号対入力部６０，同値関係判定部６２、判定結果出力部６４、語変更部２３を含んで構成される。
【００４８】
語入力部３０は、ミュータブルテーブル又はイミュータブルテーブルに登録する語を入力するものであり、例えばキーボード入力、ファイル入力等により語を入力する。判断部３２は、語入力部３０により入力される語がミュータブルであるかイミュータブルであるかを判定する。例えば、語入力部３０により入力される語のデータ型により、ミュータブルであるかイミュータブルであるかを判定する。そして、ミュータブルであれば語をランダム値取得部３４に供給する。一方、イミュータブルであれば語をハッシュ値取得部３８に供給する。
【００４９】
ランダム値取得部３４では、供給された語のキー値の元となる値として５１２ビットの乱数を生成する。そして、識別データ付与部３５は、乱数の先頭ビット（識別データ）を１に書き換える。なお、５１１ビットの乱数をランダム値取得部３４にて生成し、その先頭に１の値のビットを付加して、先頭ビットが１である５１２ビットの乱数を得てもよい。そして、ミュータブル記憶書込部３６は、先頭ビットが１である５１２ビットの乱数をキーとし、それに対応する語（語データ）として判断部３２からランダム値取得部３４に供給された語を、互いに関連づけてミュータブル記憶部２０に格納する。こうして先頭ビットが１である５１２ビットの乱数をキーとしてミュータブル記憶部２０に格納される語は、語変更部２３により変更可能となっている（キーの値は変更されない）。
【００５０】
一方、ハッシュ値取得部３８では、判断部３２から供給された語のキー値の元となる値として、該語にハッシュ関数を適用して５１２ビットのハッシュ値を生成する。さらに、識別データ検査部３９では、判断部３２から供給された語に含まれる全ての記号の先頭ビットが０であるか否かを判断する。そして、識別データ付与部４１では、判断部３２から供給された語に含まれる全ての記号の先頭ビットが０であれば、ハッシュ値取得部３８で生成されたハッシュ値の先頭ビットを強制的に０（識別データ）にする。一方、判断部３２から供給された語に含まれる全ての記号の先頭ビットが０でなければ、すなわち１つでも先頭ビットが１である記号を含んでいれば、ハッシュ値取得部３８で生成されたハッシュ値の先頭ビットを強制的に１（識別データ）にする。なお、５１１ビットのハッシュ値をハッシュ値取得部３８にて生成し、その先頭に１の値のビットを付加して、先頭ビットが１である５１２ビットのキー値を得てもよい。そして、イミュータブル記憶書込部４０は、識別データ付与部４１で生成される先頭ビットが１又は０である５１２ビットのキーと、それに対応する語（語データ）として判断部３２からハッシュ値取得部３８に供給された語と、を互いに関連づけてイミュータブル記憶部２２に格納する。
【００５１】
記号入力部５０は、例えばユーザが任意に５１２ビットのビット列である記号を入力するものである。検索部５６は、ミュータブル記憶読出部５２又はイミュータブル記憶読出部５４を用いてミュータブル記憶部２０又はイミュータブル記憶部２２にアクセスし、記号入力部５０により入力される記号に対応する語を検索する。
【００５２】
また、記号対入力部６０は、例えばユーザが任意に５１２ビットのビット列である記号のペアを入力するものである。同値関係判定部６２は、それらの記号の値から、或いはミュータブル記憶読出部５２又はイミュータブル記憶読出部５４を用いてミュータブル記憶部２０又はイミュータブル記憶部２２にアクセスして得られる、それらの記号に対応する語から、同値関係を判定する。そして、判定結果出力部６４は、判定結果を例えばディスプレイ等に出力する。
【００５３】
以下、分散型コンピューティングシステム１０における各種処理について、処理のフロー図も参照しながら説明する。図８は、語及び記号をミュータブル記憶部２０又はイミュータブル記憶部２２のいずれかに書き込む際の書込処理のフローを示す図である。同図に示すように、まず語入力部３０に語が入力される（Ｓ１００）。そして判断部３２は、該語をイミュータブルなデータオブジェクトを表現するものか否かを判断する（Ｓ１０２）。イミュータブルであるか否かは、後にそのデータオブジェクトを更新する必要の有無で判断される。イミュータブルではない、つまり、ミュータブルなデータオブジェクトの典型例として循環参照がある。例えば、各語の属性として、ミュータブルであるかイミュータブルであるかを示す情報を付加しておいてもよい。このように、イミュータブルなデータオブジェクトを表現する場合とミュータブルなデータオブジェクトを表現する場合があるので、入力された語がイミュータブルなデータオブジェクトを表現する場合には、ハッシュ値取得部３８に該語を出力し、入力された語がミュータブルオブジェクトを表現する場合には、ランダム値取得部３４に該語を出力する。このデータ生成の二通りの使い分けは非特許文献１におけるhcons（イミュータブルなconsセルの生成）とcons（通常のミュータブルなconsセルの生成）に対応している。
【００５４】
ハッシュ値取得部３８では、語のハッシュ値を計算する（Ｓ１０４）。そして、識別データ検査部３９及び識別データ付与部４１により、語に含まれる全ての記号の先頭ビットが０であるか否かに応じて、ハッシュ値の先頭ビットを０又は１に強制的に変更する（Ｓ１０５）。そして、イミュータブル記憶書込部４０は、イミュータブル記憶部２２に、先頭ビットが強制的に変更されたハッシュ値である記号と関連付けて、入力された語を書き込む（Ｓ１０６）。
【００５５】
一方、ランダム値取得部３４では、乱数を生成してランダム値として取得する（Ｓ１０８）。そして、識別データ付与部３５は、その先頭ビットを１に強制的に変更する（Ｓ１０９）。その後、ミュータブル記憶書込部３６が、このように先頭ビットが強制的に１に変更されたランダム値と関連付けて、入力された語をミュータブル記憶部２０に書き込む（Ｓ１１０）。
【００５６】
次に、図９は、語をミュータブル記憶部２０又はイミュータブル記憶部２２のいずれかから読み出す際の読出処理のフローを示す図である。同図に示すように、まず記号入力部５０に記号が入力され（Ｓ２００）、該記号は検索部５６に入力される。そして、検索部５６は、ここではまずミュータブル記憶読出部５２においてミュータブル記憶部２０に記憶されている記号を検索し（Ｓ２０２）、入力された記号が記憶されているかを判断する（Ｓ２０４）。記憶されていれば、該記号に対応付けられて記憶される語を出力する。Ｓ２０４において、入力された記号が記憶されていないと判断された場合には、イミュータブル記憶読出部５４においてイミュータブル記憶部２２に記憶されている記号を検索し（Ｓ２０８）、入力された記号が記憶されているかを判断する（Ｓ２１０）。記憶されていれば、該記号に対応付けられて記憶される語を出力する。一方、該コンピュータで記号に対応する語が獲得できない場合には、他のコンピュータに入力された記号を送信する（Ｓ２１６）。そして他のコンピュータにおいて、本読出処理と同様の読出処理を行い（Ｓ２１８）、他のコンピュータから語を受信すれば、その語が検索部５６における検索結果となる。一方、他のコンピュータから語を受信しない場合には、タイムアウトする（Ｓ２２２）まで、他のコンピュータに記号を送信する処理を繰り返し（Ｓ２１４、Ｓ２２４）、タイムアウトすれば処理を終了する。この場合には、検索部５６は、入力された記号に対応する語はなかったということを示す検索結果を返す。このようにして得られた語は記号の列であり、その記号は即値であるか、他の語を参照する記号のいずれかである。即値であるとは該記号が値そのものの表現となっているということである。他の語を参照する記号の場合は上記の処理を必要なだけ繰り返すことによって、記号が語を参照している限り、対応する語を検索することができる。
【００５７】
以上のようにすることにより、分散型コンピューティングシステム１０において、複数のコンピュータやプロセス間でデータオブジェクトを表現する語を共有するために、記号のみを共有すればよいようにすることができる。そしてこのことにより、処理の高速化及び記憶領域の節約を実現することができる。
【００５８】
最後に、同値関係判定部６２による同値関係判定処理を説明する。図１０は、同値関係判定処理を示すフロー図である。同図に示すように、この処理では、まず記号対入力部６０により同値関係の判定対象である２つの記号ｘ及びｙを取得する（Ｓ３０１）。次に、ｘとｙとが等しいか否かを判断する（Ｓ３０２）。そして、等しければ、判定結果出力部６４は、両者が同値関係にある旨を出力する（Ｓ３０３）。一方、等しくなければ両記号ｘ及びｙの先頭ビットがいずれも０であるか否かを調べる（Ｓ３０４）。そして、いずれも先頭ビットが０であれば、判定結果出力部６４は、両者が同値関係にない旨を出力する（Ｓ３０５）。
【００５９】
一方、Ｓ３０４において、記号ｘ及びｙの先頭ビットのいずれかが１であると判断される場合、両記号ｘ及びｙに対応する語を取得する（Ｓ３０６）。この際、語に含まれる記号により他の語が参照されている場合には、その語も取得する。また、そうして取得される語に含まれる記号により他の語が参照されている場合には、その語も取得する。こうして、全ての両記号ｘ及びｙを、即値である記号の有限列に変換する。そして、それらの記号の有限列の長さが等しく、且つ各記号が同値であれば（Ｓ３０７）、判定結果出力部６４は、記号ｘ及びｙが同値関係にある旨を出力し（Ｓ３０３）、そうでなければ（Ｓ３０７）、判定結果出力部６４は、記号ｘ及びｙが同値関係にない旨を出力する（Ｓ３０５）。
【００６０】
以上のようにして、本実施形態によれば、アルファベットの部分集合、つまり先頭ビットが０である５１２ビットのビット列である記号を要素とする集合上の語であれば、その語のキーのみから同値関係を判定でき、極めて高速に同値関係を判定できる。
【００６１】
なお、本発明は上記実施の形態に限定されるものではない。例えば、上記読出処理ではミュータブル記憶部２０とイミュータブル記憶部２２とを順に検索したが、順番はいずれが先でもよい。
【図面の簡単な説明】
【００６２】
【図１】本発明の実施形態に係る分散型コンピューティングシステムの構成図である。
【図２】本発明の実施形態に係るミュータブルテーブルである。
【図３】本発明の実施形態に係るイミュータブルテーブルである。
【図４】本発明の実施形態において用いられる記号のパターンを示す図である。
【図５】本発明の実施形態において用いられる語のパターンを示す図である。
【図６】従来技術に係るヒープである。
【図７】本発明の実施形態に係る分散型コンピューティングシステムの機能ブロック図である。
【図８】本発明の実施形態に係る書込処理を示すフロー図である。
【図９】本発明の実施形態に係る読出処理を示すフロー図である。
【図１０】本発明の実施形態に係る同値関係判定処理を示すフロー図である。
【符号の説明】
【００６３】
１０  分散型コンピューティングシステム、１２  コンピュータ、１４  通信ネットワーク、２０  ミュータブル記憶部（ミュータブル記憶手段）、２２  イミュータブル記憶部（イミュータブル記憶手段）、２３  語変更部、３０  語入力部（語データ取得手段）、３２  判断部、３４  ランダム値取得部、３５  識別データ付与部（ミュータブルオブジェクト用記号データ決定手段）、３６  ミュータブル記憶書込部、３８  ハッシュ値取得部、３９  識別データ検査部（語判定手段）、４０  イミュータブル記憶書込部、４１  識別データ付与部（第１記号データ決定手段，イミュータブルオブジェクト用記号データ決定手段）、５０  記号入力部、５２  ミュータブル記憶読出部、５４  イミュータブル記憶読出部、５６  検索部、６０  記号対入力部（第１及び第２記号データ取得手段）、６２  同値関係判定部（同値関係判定手段）、６４  判定結果出力部。
【図１】
2007058281.tif 000007
【図２】
2007058281.tif 000008
【図３】
2007058281.tif 000009
【図４】
2007058281.tif 000010
【図５】
2007058281.tif 000011
【図６】
2007058281.tif 000012
【図７】
2007058281.tif 000013
【図８】
2007058281.tif 000014
【図９】
2007058281.tif 000015
【図１０】
2007058281.tif 000016