(57)【要約】【課題】分割データ断片数を抑えながら、高い重複排除率を単純な仕組みで実現する。【解決手段】子チャンク決定部は、入力された任意のデータのうち、未だ第１のデータ断片として決定されていない残りのデータ部分から第２のデータ断片を順次決定する（ステップ４０３）。親チャンク決定部は、第１の条件を満たす状態に達するまでに決定された第２のデータ断片の組み合わせを１つの第３のデータ断片として決定する（ステップ４０７）。決定された第３のデータ断片の重複が検出されなかった場合（ステップ４０８）、制御部は、これらの処理の繰り返しを、第２の条件を満足する状態で重複が検出されるまで制御し、それでも重複が検出されなかった場合、親チャンク決定部は、その間に決定された第２のデータ断片のうちの第１の条件を満足する第２のデータ断片の組み合わせを、第１のデータ断片として決定する。【選択図】      図４
2011076421.tif 000002
【特許請求の範囲】
【請求項１】
入力手段、第１のデータ断片決定手段、第２のデータ断片決定手段、第３のデータ断片決定手段、重複検出手段及び制御手段を含む装置において、任意のデータを、重複検出を行いながら、複数の、任意の長さの第１のデータ断片に分割するためのデータ分割方法であって、
前記任意のデータを前記入力手段が入力する入力ステップと、
前記入力された任意のデータのうち、未だ前記第１のデータ断片として決定されていない残りのデータ部分から、前記第２のデータ断片決定手段が任意の長さまたは予め定められた長さの第２のデータ断片を順次決定する第１の決定ステップと、
予め定められた第１の条件を満足する状態に達するまでに、前記第１のステップにおいて決定された１つの第２のデータ断片それ自体または複数の第２のデータ断片の組み合わせを、前記第３の断片決定手段が１つの第３のデータ断片として決定する第２の決定ステップと、
前記決定された第３のデータ断片の重複の有無を、当該決定された第３のデータ断片に一致するビット列の第１のデータ断片が既に決定されているかによって、前記重複検出手段が検出する重複検出ステップと、
前記重複が検出された場合、前記決定された第３のデータ断片を前記第１のデータ断片決定手段が前記第１のデータ断片として決定する第３の決定ステップと、
前記重複が検出されなかった場合、前記第１及び第２の決定ステップを再実行させることにより、前記第１の条件を満足する状態に達するまでに新たな１つの第２のデータ断片または新たな複数の第２のデータ断片を決定させると共に、当該新たな１つの第２のデータ断片それ自体、当該新たな複数の第２のデータ断片の組み合わせ、前記重複が検出されなかった第３のデータ断片の一部と当該新たな１つの第２のデータ断片との組み合わせ、または前記重複が検出されなかった第３のデータ断片の一部と当該新たな複数の第２のデータ断片との組み合わせを、前記第３のデータ断片決定手段により１つの新たな第３のデータ断片として決定させるための制御を、予め定められた第２の条件を満足する状態で前記重複が検出されるまで前記制御手段が繰り返す第１の制御ステップと、
前記第２の条件を満足する状態で前記第１の制御ステップが繰り返されても前記重複が検出されなかった場合、その間に決定された前記第２のデータ断片のうちの、前記第１の条件を満足する、１つの第２のデータ断片それ自体、または複数の第２のデータ断片の組み合わせを、前記第１のデータ断片決定手段が新たな第１のデータ断片として決定する第４の決定ステップと、
前記入力された任意のデータが全て前記第１のデータ断片に分割されるまで、前記制御手段が前記第１の制御ステップを繰り返すための第２の制御ステップと
を具備することを特徴とするデータ分割方法。
【請求項２】
前記第２のデータ断片は、前記残りのデータ部分の第１の端部から当該残りのデータ部分の第２の端部の方に向かって順に決定され、
前記第１の条件は、前記第１のステップにおいて決定された前記１つの第２のデータ断片の長さ、または前記第１のステップにおいて順次決定された前記複数の第２のデータ断片を連結した場合の、その連結後の当該複数の第２のデータ断片の長さに関する条件であり、
前記第１の条件を満足する状態に達するまでに、前記第１のステップにおいて前記複数の第２のデータ断片が決定された場合、当該複数の第２のデータ断片をその決定順に連結することにより、当該複数の第２のデータ断片の組み合わせとしての前記第３のデータ断片が決定される
ことを特徴とする請求項１記載のデータ分割方法。
【請求項３】
前記第２の決定ステップは、
前記重複が検出されなかった第３のデータ断片に含まれる、前記残りのデータ部分の前記第１の端部に最も近い側の少なくとも１つの第２のデータ断片を、当該第３のデータ断片から取り外すステップと、
前記第１の条件を満足する状態に達するまでに前記第１の決定ステップで決定された前記新たな１つの第２のデータ断片または前記新たな複数の第２のデータ断片を、前記少なくとも１つの第２のデータ断片が取り外された前記第３のデータ断片に組み込むことにより、新たな第３のデータ断片を決定するステップとを含む
ことを特徴とする請求項２記載のデータ分割方法。
【請求項４】
前記第２の条件の範囲で前記第１の制御ステップが繰り返されても前記重複が検出されなかった場合に前記新たな第１のデータ断片として決定される、前記１つの第２のデータ断片それ自体、または前記複数の第２のデータ断片の組み合わせは、最も最近に第１のデータ断片が決定された後に最初に決定された第３の断片であり、
前記第３の決定ステップは、前記第２の条件の範囲で前記第１の制御ステップが繰り返されることによって前記重複が検出された結果、前記第１のデータ断片が決定された場合、前回決定された第１のデータ断片と今回決定された第１のデータ断片との間に挟まれている、未だ第１のデータ断片として決定されていないデータ断片を、前記第１のデータ断片決定手段が新たな第１のデータ断片として決定するステップを含む
ことを特徴とする請求項１乃至３のいずれか記載のデータ分割方法。
【請求項５】
前記第１の条件は、
前記第１のステップにおいて決定された前記１つの第２のデータ断片の長さ、または前記第１のステップにおいて順次決定された前記複数の第２のデータ断片を連結した場合の、その連結後の当該複数の第２のデータ断片の長さが、
予め定められた基準の長さを超えること、
予め定められた基準の長さに等しくなること、
予め定められた基準の長さに最も近くなること、
または予め定められた基準の長さを超えない最大値なること
のいずれか１つである
ことを特徴とする請求項４記載のデータ分割方法。
【請求項６】
前記第２の条件は、前記残りのデータ部分の前記第１の端部から、最も最近に重複が検出されなかった第３のデータ断片の当該第１の端部から遠い側の端部までの長さであるデータ断片長に関する条件であることを特徴とする請求項４記載のデータ分割方法。
【請求項７】
前記第２の条件は、前記データ断片長が、
予め定められた基準の長さを超えること、
予め定められた基準の長さに等しくなること、
予め定められた基準の長さに最も近くなること、
または予め定められた基準の長さを超えない最大値なること
のいずれか１つである
ことを特徴とする請求項６記載のデータ分割方法。
【請求項８】
任意のデータを、重複検出を行いながら、複数の、任意の長さの第１のデータ断片に分割するためのデータ分割装置において、
前記任意のデータを入力する入力手段と、
前記入力された任意のデータのうち、未だ前記第１のデータ断片として決定されていない残りのデータ部分から、任意の長さまたは予め定められた長さの第２のデータ断片を順次決定する第２のデータ断片決定手段と、
予め定められた第１の条件を満足する状態に達するまでに、前記第２のデータ断片決定手段によって決定された１つの第２のデータ断片それ自体または複数の第２のデータ断片の組み合わせを、１つの第３のデータ断片として決定する第３のデータ断片決定手段と、
前記決定された第３のデータ断片の重複の有無を、当該決定された第３のデータ断片に一致するビット列の第１のデータ断片が既に決定されているかによって検出する重複検出手段と、
前記重複が検出された場合、前記決定された第３のデータ断片を前記第１のデータ断片として決定する第１のデータ断片決定手段と、
前記重複が検出されなかった場合、前記第１の条件を満足する状態に達するまでに前記第２のデータ断片決定手段によって新たな１つの第２のデータ断片または新たな複数の第２のデータ断片を決定させると共に、前記新たな１つの第２のデータ断片それ自体、前記新たな複数の第２のデータ断片の組み合わせ、前記重複が検出されなかった第３のデータ断片の一部と当該新たな１つの第２のデータ断片との組み合わせ、または前記重複が検出されなかった第３のデータ断片の一部と当該新たな複数の第２のデータ断片との組み合わせを、前記第３のデータ断片決定手段によって１つの新たな第３のデータ断片として決定させるための制御を、予め定められた第２の条件を満足する状態で前記重複が検出されるまで繰り返し、この制御の繰り返しを、前記入力された任意のデータが全て前記第１のデータ断片に分割されるまで更に繰り返す制御手段とを具備し、
前記第１のデータ断片決定手段は、前記第２の条件を満足する状態で前記制御が繰り返されても前記重複が検出されなかった場合、その間に決定された前記第２のデータ断片のうちの、前記第１の条件を満足する、１つの第２のデータ断片それ自体、または複数の第２のデータ断片の組み合わせを、新たな第１のデータ断片として決定する
ことを特徴とするデータ分割装置。
【請求項９】
前記第２のデータ断片決定手段は、前記残りのデータ部分の第１の端部から当該残りのデータ部分の第２の端部の方に向かって前記第２のデータ断片を順に決定し、
前記第１の条件は、前記第２のデータ断片決定手段によって決定された前記１つの第２のデータ断片の長さ、または前記第２のデータ断片決定手段によって順次決定された前記複数の第２のデータ断片を連結した場合の、その連結後の当該複数の第２のデータ断片の長さに関する条件であり、
前記第３のデータ断片決定手段は、前記第１の条件を満足する状態に達するまでに、前記第２のデータ断片決定手段によって前記複数の第２のデータ断片が決定された場合、当該複数の第２のデータ断片をその決定順に連結することにより、当該複数の第２のデータ断片の組み合わせとしての前記第３のデータ断片を決定する
ことを特徴とする請求項８記載のデータ分割装置。
【請求項１０】
前記第３のデータ断片決定手段は、前記重複が検出されなかった第３のデータ断片に含まれる、前記残りのデータ部分の前記第１の端部に最も近い側の少なくとも１つの第２のデータ断片を、当該第３のデータ断片から取り外し、前記第１の条件を満足する状態に達するまでに前記第２のデータ断片決定手段によって決定された前記新たな１つの第２のデータ断片または前記新たな複数の第２のデータ断片を、前記少なくとも１つの第２のデータ断片が取り外された前記第３のデータ断片に組み込むことにより、新たな第３のデータ断片を決定することを特徴とする請求項９記載のデータ分割装置。
【請求項１１】
前記第２の条件の範囲で前記制御が繰り返されても前記重複が検出されなかった場合に、前記新たな第１のデータ断片として決定される、前記１つの第２のデータ断片それ自体、または前記複数の第２のデータ断片の組み合わせは、最も最近に第１のデータ断片が決定された後に最初に決定された第３の断片であり、
前記第１のデータ断片決定手段は、前記第２の条件の範囲で前記制御が繰り返されることによって前記重複が検出された結果、前記第１のデータ断片を決定した場合、前回決定した第１のデータ断片と今回した第１のデータ断片との間に挟まれている、未だ第１のデータ断片として決定されていないデータ断片を、新たな第１のデータ断片として決定する  ことを特徴とする請求項８乃至１０のいずれかに記載のデータ分割装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ間で重複するデータ断片を検出しながら、任意のデータを可変長のデータ断片に分割するのに好適な、データ分割方法及び装置に関する。
【背景技術】
【０００２】
昨今、官公庁・企業・個人のデータを管理する基盤は急速に肥大化・複雑化しており、その基盤の主要な構成要素である記憶装置に格納するデータも増大の一途をたどっている。このようなデータの保管・管理コストを削減するための１つの技術として、重複排除技術が注目されている。
【０００３】
重複排除技術とは、任意のデータ（以下、対象データと称する）を記憶装置に格納する際に、既に対象データと同じ内容のデータが当該記憶装置に格納されているかを検出、つまりデータの重複を検出し、既に格納されていれば当該対象データを例えばリンクで置き換えることにより重複データを１つにまとめる（排除する）技術をいう。この重複排除技術によれば、データの記憶に必要な記憶容量を少なくすることができる。
【０００４】
同じデータが記憶装置に格納されているか否かを高速に検出するためには、データの識別子を利用することが多い。即ち重複排除技術では一般に、データの重複を検出するのに、対象データ自身を既に記憶装置に格納されている全データと比較する手法ではなくて、対象データの識別子を求めてこれを既存の格納済みのデータの識別子の群と比較する手法が適用される。
【０００５】
データの重複は、予め定められた単位で検出される。この単位として、ファイルのようなデータ（コンテンツ）の一塊を用いることにより、データの重複を検出する第１の手法が古くから知られている。また最近では、上記の単位に、ファイルのようなデータを分割することによって得られるデータ断片（以下、チャンクと称する）を用いることにより、データの重複を検出する第２の手法が提案されている。第１の手法では、データの一部が異なるときにもデータ全体が異なるものであるとして処理される。これに対して第２の手法では、上記一部だけを処理すればよいという利点がある。
【０００６】
第２の手法を適用する重複排除技術では、一般に、以下のような手順を繰り返すことで重複排除が行われる。  
手順１）対象データからチャンクを切り出す。  
手順２）切り出されたチャンクの識別子を求める。  
手順３）切り出されたチャンクの識別子を既に記憶装置に格納済みのチャンクの群のそれぞれの識別子と比較する。もし、切り出されたチャンクと識別子が同一のチャンクがあれば、切り出されたチャンクと同一内容のチャンクであるとして、重複を排除する形式で、例えばリンクに置き換えることにより、切り出されたチャンクを記憶装置に格納する。
【０００７】
第２の手法を適用する重複排除技術では、手順１で実行されるチャンクの切り出しの方法、つまりどの長さでチャンクを切り出すかが重要である。第２の手法を適用する重複排除技術は、対象データからチャンクを切り出すときに当該チャンクの切り出し点を求める方法によって、大きく次の２種類に分類される。
【０００８】
Ａ）固定長重複排除方法
固定長重複排除方法とは、ある一定の長さでチャンクの切り出し点を定め、チャンク毎に重複検出・排除を行う方法である。  
Ｂ）可変長重複排除方法
可変長重複排除方法とは、対象データの内容に応じてデータ分割長を動的に調節して切り出し点を定め、チャンク毎に重複検出・排除を行う方法である。
【０００９】
以下、固定長重複排除方法及び可変長重複排除方法の違いについて、図２３を参照して説明する。  
図２３は、文書名が「文書＃１」の文書１１１及び文書名が「文書＃２」の文書１１２の２つの文書についてそれぞれ、チャンク切り出し点を固定長重複排除方法と可変長重複排除方法で求めた様子を示す。文書１１２は、文書１１１の一部を編集することによって、例えば文書１１１における文字列“name”及び“specified”の間に文字列“ABCD”を挿入することによって、生成された文書である。
【００１０】
固定長重複排除方法によれば、文書１１１及び文書１１２に対し、図２３において矢印１１３で示されるように、例えば１０文字の固定長を単位に、チャンクの切り出し点が定められる。一方、可変長重複排除方法によれば、文書１１１及び文書１１２に対し、図２３において矢印１１４で示されるように、データの中身に応じて、チャンクの切り出し点が定められる。この技術の詳細については後述する。
【００１１】
ここでは以下の点に注目されたい。  
固定長重複排除方法では、文書１１１と文書１１２との間で、文字列の挿入が発生した箇所から後ろ側、つまり文書の末尾側のチャンク全てが異なっている。  
これに対して可変長重複排除方法では、文書１１１と文書１１２との間で、文字列の挿入が発生した箇所周辺のチャンクが異なっているのみで、それより後ろ側のチャンクは全て一致している。
【００１２】
このように、固定長重複排除方法に比較して、可変長重複排除方法の方が、あるデータ間で、データの一部挿入／削除／変更が発生したときでも、その影響を極力抑えながら重複排除を実現できる。
【００１３】
上述のような可変長でのチャンク切り出し点の求め方と、それを利用した重複排除を行う方法は種々知られている。ここでは、特許文献１に記載されているような方法について、例を挙げて説明する。
【００１４】
特許文献１に記載の方法では、次の手順でチャンクの切り出し点が求められる。  
１）データ上のある連続する固定長の区間（以下、ウィンドウと称する）のデータ断片（バイト列）を取り出して、当該データ断片の識別子を求める。ここでは、ウィンドウの長さが２バイトであるとする。このデータ断片がチャンクとしてのデータ断片とは異なる点に注意すべきである。
【００１５】
２）求めた識別子の一部（例えば下位２ビット）が、予め定めた値（例えば０ｘ０１）と一致したときに、そこをチャンクの切り出し点とする。
【００１６】
図２４は、２バイト長のウィンドウＷ内の文字列（データ断片）の識別子を求めて、その識別子の下位２ビットが、予め定めた値０ｘ０１と一致するときにそこをチャンクの切り出し点として決定する場合の動作例を示す。図２４の例では、文書データ“The fil…”の先頭より２バイト（２文字）長の区間をウィンドウＷとして初期設定し、以後当該ウィンドウＷを１バイトずつシフトさせながら、当該ウィンドウＷ内の文字列の識別子を、例えば当該文字列のハッシュ値を計算することによって求めている。このハッシュ値の計算に用いられるハッシュ関数を、ｈα( )で表す。ウィンドウＷ内の文字列が“Th”であるものとすると、その識別子は、ｈα(“Th”)で表される。
【００１７】
ウィンドウＷ内の文字列“Th”の識別子ｈα(“Th”)が０ｘ１Ａであったとすると、当該識別子０ｘ１Ａの下位２ビットは０ｘ０２である。この識別子０ｘ１Ａの下位２ビットは、当該識別子０ｘ１Ａとマスクデータ０ｘ０３との論理積演算０ｘ１Ａ＆０ｘ０３によって求められる。識別子０ｘ１Ａの下位２ビット０ｘ０２は、予め定められた値０ｘ０１ではない。このため、このときのウィンドウＷの終端を、チャンクの切り出し点とはしない。
【００１８】
ウィンドウＷ内の文字列“ f”の識別子ｈα(“ f”)が０ｘ９９であったとすると、当該識別子０ｘ９９の下位２ビットは０ｘ０１である。これは予め定められた値０ｘ０１と同じなので、このときのウィンドウＷの終端をチャンクの切り出し点とする。これにより、文字列“The f”が切り出される。
【００１９】
この例では、チャンクの切り出し点を決定する条件とし、識別子の下位２ビットと予め定められた値との一致を用いているが、このビット数で、平均チャンクサイズが決定されることに注意されたい。例えば２ビットの場合、平均チャンクサイズは２2＝４バイトとなる。
【００２０】
以上のようにしてチャンクを切り出した上で、図２５に示すように、このチャンク自体の識別子を、例えば当該チャンクのハッシュ値を計算することによって求めている。切り出されたチャンクをＣAで表し、ハッシュ値の計算に用いられるハッシュ関数を、ｈβ( )で表す。チャンクＣAを構成する文字列が“The f”である図２５の例では、チャンクＣAの識別子は、ｈβ(“The f”)＝ｈβ(ＣA)で表される。以下の説明では、チャンクＣAの識別子をＨAで表す。
【００２１】
次に、前記手順３と同様に、求めたチャンクの識別子を、既に記憶装置に格納されているチャンクの群のそれぞれの識別子と比較する。もし、求めたチャンクと識別子が同一のチャンクがあれば、求めたチャンクと同一内容のチャンクが既に記憶装置に格納されているものとして処理する。これに対し、求めたチャンクと識別子が同一のチャンクがなければ、当該求めたチャンクを未だ記憶装置に格納されていない新しいチャンクとして処理する。  
上述の処理を、チャンクを求める毎に繰り返すことで、重複検出・排除を行う。
【００２２】
特許文献１に記載されたチャンクの切り出し方法によれば、例えば図２６に示す文書名が「文書＃１」の文書１１１（データ）は、識別子ＨxがＨA乃至ＨIの９つのチャンクを含むチャンクＣxの群に分割される。文書名が「文書＃１」の文書１１１から切り出されるチャンクＣxの群のそれぞれの識別子Ｈxは、図２６に示されるように、当該文書名「文書＃１」に対応付けて文書構成テーブル２５１に登録される。また、識別子ＨA乃至ＨIを含む識別子Ｈxの群のそれぞれと、その識別子Ｈxに対応するチャンクＣxとの一覧は、図２６に示されるようにチャンク一覧テーブル２５２に登録される。
【００２３】
一般的には、チャンク切り出しに当たり、チャンクの長さに最小長さ及び最大長さの制限を設けることが多い。このような場合、最大長さに達した位置を、強制的にチャンクの切り出し点と定める。
【００２４】
また、特許文献２には、チャンクの切り出し点を求めるためウィンドウをシフトしながら識別子を求める方法に関して、ＲｏｌｌｉｎｇＨａｓｈｉｎｇの手法を適用することが記載されている。
【００２５】
特許文献１，２に記載されているような可変長重複排除技術には、次のような２つの課題がある。  
＜第１の課題＞
重複排除率の向上のためには、チャンクの平均長を短くする必要がある。しかし、チャンクの平均長を短くすると、チャンクの個数が増える。このため、チャンク一覧テーブルに登録される識別子（より詳細には識別子とチャンクとの対）の数が増える。一般的にチャンク一覧テーブルはハッシュテーブルで実装されることが多いが、識別子の数が増えるとハッシュテーブルのサイズも大きくなってしまう。このため、チャンク一覧テーブルを、アクセス速度が高速なメモリ上に全て展開することが難しくなり、例えばメモリと比較して大容量だが低速なディスク装置上に展開せざるを得なくなる。このことは、性能を大幅に悪化させる要因となる。
【００２６】
＜第２の課題＞
逆に、チャンク一覧テーブルを全てメモリ上に展開するためには、当該メモリ上に展開可能なサイズにまでチャンク一覧テーブルを小さくする必要がある。そのためには、チャンク一覧テーブルに登録される識別子の数を少なく抑えなければならい。このことはつまり、チャンクの平均長を長くするということであり、重複排除率の低下を招くことになる。
【００２７】
以下に例を用いて説明する。図２７は上記第１の課題の例を、図２８は上記第２の課題の例を示している。図２７の例は、図２８と比較してチャンクの平均長を短くすることで、図２８と比較して、重複排除率の向上を実現している。チャンク一覧テーブル２５２に識別子に対応付けて登録されるチャンクの群のサイズを合計することで、重複排除率が高いことがわかる。しかし、図２８と比較して識別子数が多い。
【００２８】
このように、重複排除率とチャンクの個数（チャンクの平均長）はトレードオフの関係にあることがわかる。
【００２９】
最近、上述のような課題を解決するために、様々な手法が検討・採用されている。例えば特許文献３は、切り出されたチャンクを２つ以上連結し（ここでは便宜上、連結されたチャンク群を「連結チャンク」と称する）、少なくとも連結チャンクの単位で重複検出を行うことで、チャンクの個数を減らしつつ高い重複排除率を維持する手法を開示している。
【００３０】
特許文献３に開示されている手法の特徴は、チャンクの連結／非連結を動的に切り替えながら、連結チャンクと連結チャンクとの間に、非連結チャンクの群からなる「緩衝領域」を設ける点にある。この手法では、以下の第１及び第２の条件に基づいて、チャンクの連結／非連結が動的に切り替えられる。
【００３１】
第１の条件とは、「連結対象として仮に定められたチャンクの群が、既にシステム内に登録されている連結チャンクと重複するか否か」である。  
第２の条件とは、「連結対象として定められたチャンクの群の前後に連なるチャンクの群が、連結チャンクであるか否か」と、「上記連なるチャンクの群が、既にシステム内に登録されている連結チャンクと重複しているか否か」とである。
【先行技術文献】
【特許文献】
【００３２】
【特許文献１】米国特許第５，９９０，８１０号明細書
【特許文献２】米国特許第６，８１０，３９８号明細書
【特許文献３】米国特許出願公開第２００８／０１３３５６１号明細書
【発明の概要】
【発明が解決しようとする課題】
【００３３】
しかし、上記特許文献３に開示されているような手法では、連結／非連結を動的に切り替える条件が複雑である。条件が複雑であることは、実装上好ましくない。また、連結チャンクと連結チャンクの間に設けられる「緩衝領域」では細かなチャンクが多数生成される。このことは、文書構成テーブル及びチャンク一覧テーブルのエントリ数の増加を招き、結果的に性能劣化を引き起こす。
【００３４】
また、上記特許文献３に開示されているような手法では、常に複数個の非連結チャンクの群が連結されて、この連結の単位で重複検出・排除が行われる。このことは、可変長でのチャンク切り出しで切り出されたチャンクの長さが長いとき、更に大きな連結チャンクの単位で、重複検出・排除が行われることになって、重複排除率が低下する要因となることを意味する。
【００３５】
本発明は上記事情を考慮してなされたものでその目的は、分割されるデータ断片数を抑えながらも高い重複排除率を、単純な仕組みで実現できるデータ分割方法及び装置を提供することにある。
【課題を解決するための手段】
【００３６】
本発明の１つの観点によれば、入力手段、第１のデータ断片決定手段、第２のデータ断片決定手段、第３のデータ断片決定手段、重複検出手段及び制御手段を含む装置において、任意のデータを、重複検出を行いながら、複数の、任意の長さの第１のデータ断片に分割するためのデータ分割方法が提供される。このデータ分割方法は、前記任意のデータを前記入力手段が入力する入力ステップと、前記入力された任意のデータのうち、未だ前記第１のデータ断片として決定されていない残りのデータ部分から、前記第２のデータ断片決定手段が任意の長さまたは予め定められた長さの第２のデータ断片を順次決定する第１の決定ステップと、予め定められた第１の条件を満足する状態に達するまでに、前記第１のステップにおいて決定された１つの第２のデータ断片それ自体または複数の第２のデータ断片の組み合わせを、前記第３の断片決定手段が１つの第３のデータ断片として決定する第２の決定ステップと、前記決定された第３のデータ断片の重複の有無を、当該決定された第３のデータ断片に一致するビット列の第１のデータ断片が既に決定されているかによって、前記重複検出手段が検出する重複検出ステップと、前記重複が検出された場合、前記決定された第３のデータ断片を前記第１のデータ断片決定手段が前記第１のデータ断片として決定する第３の決定ステップと、前記重複が検出されなかった場合、前記第１及び第２の決定ステップを再実行させることにより、前記第１の条件を満足する状態に達するまでに新たな１つの第２のデータ断片または新たな複数の第２のデータ断片を決定させると共に、当該新たな１つの第２のデータ断片それ自体、当該新たな複数の第２のデータ断片の組み合わせ、前記重複が検出されなかった第３のデータ断片の一部と当該新たな１つの第２のデータ断片との組み合わせ、または前記重複が検出されなかった第３のデータ断片の一部と当該新たな複数の第２のデータ断片との組み合わせを、前記第３のデータ断片決定手段により１つの新たな第３のデータ断片として決定させるための制御を、予め定められた第２の条件を満足する状態で前記重複が検出されるまで前記制御手段が繰り返す第１の制御ステップと、前記第２の条件を満足する状態で前記第１の制御ステップが繰り返されても前記重複が検出されなかった場合、その間に決定された前記第２のデータ断片のうちの、前記第１の条件を満足する、１つの第２のデータ断片それ自体、または複数の第２のデータ断片の組み合わせを、前記第１のデータ断片決定手段が新たな第１のデータ断片として決定する第４の決定ステップと、前記入力された任意のデータが全て前記第１のデータ断片に分割されるまで、前記制御手段が前記第１の制御ステップを繰り返すための第２の制御ステップとを具備することを特徴とする。
【発明の効果】
【００３７】
本発明によれば、任意のデータを、重複検出を行いながら、複数の、任意の長さの第１のデータ断片に分割するためのデータ分割方法及び装置において、第２のデータ断片の長さを重複検出のオフセット間隔としながら、当該第２のデータ断片の長さよりも長くなる可能性が高く、且つ第１のデータ断片として用いられる可能性の高い第３のデータ断片の長さで重複検出を行う構成とすることにより、従来技術と比較してより単純・高速な手法で、第１のデータ断片の数（つまりチャンク数または分割数）を少なくしながらも重複排除率を高く維持した、重複検出を行うことができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の一実施形態に係るストレージシステムの構成を示すブロック図。
【図２】図１に示される文書格納装置のハードウェア構成を示すブロック図。
【図３】図１に示される文書格納装置の主として機能構成を示すブロック図。
【図４】同実施形態で適用される文書格納処理の手順を示すフローチャート。
【図５】同実施形態で適用される文書格納処理の手順を示すフローチャート。
【図６】同実施形態で適用される親チャンクと子チャンクの群との関係を説明するための図。
【図７】子チャンクの切り出し点を決定する手法を説明するための図。
【図８】第１及び第２の文書と、当該第１及び第２の文書の格納前における文書構成テーブル及びチャンク一覧テーブルの状態とを示す図。
【図９】第１の文書を格納するための格納動作（その１）を文書構成テーブルの状態と共に示す図。
【図１０】第１の文書を格納するための格納動作（その２）を文書構成テーブルの状態と共に示す図。
【図１１】第１の文書を格納するための格納動作（その３）を文書構成テーブルの状態と共に示す図。
【図１２】第１の文書を格納するための格納動作（その４）を文書構成テーブルの状態と共に示す図。
【図１３】第１の文書を格納するための格納動作（その５）を文書構成テーブルの状態と共に示す図。
【図１４】第１の文書の格納後における、文書構成テーブル及びチャンク一覧テーブルの状態を、当該第１の文書と当該第１の文書から切り出された親チャンクの列と共に示す図。
【図１５】第１の文書の格納後に行われる第２の文書を格納するための格納動作（その１）を文書構成テーブルの状態と共に示す図。
【図１６】第２の文書を格納するための格納動作（その２）を文書構成テーブルの状態と共に示す図。
【図１７】第２の文書を格納するための格納動作（その３）を文書構成テーブルの状態と共に示す図。
【図１８】第２の文書を格納するための格納動作（その４）を文書構成テーブルの状態と共に示す図。
【図１９】第２の文書を格納するための格納動作（その５）を文書構成テーブルの状態と共に示す図。
【図２０】第２の文書の格納後における、文書構成テーブル及びチャンク一覧テーブルの状態を、当該第２の文書と当該第２の文書から切り出された親チャンクの列と共に示す図。
【図２１】第１及び第２の文書の格納後における、文書構成テーブル及びチャンク一覧テーブルの状態を、当該第１及び第２の文書と当該第１及び第２の文書から切り出された親チャンクの列と共に示す図。
【図２２】同実施形態で適用される文書取得処理の手順を示すフローチャート。
【図２３】従来技術における固定長重複排除方法及び可変長重複排除方法の違いを説明するための図。
【図２４】従来技術における可変長重複排除方法で適用されるチャンク切り出し点を設定する動作の過程の一例を示す図。
【図２５】従来技術におけるチャンク切り出し方法を説明するための図。
【図２６】従来技術におけるチャンク切り出し方法によって文書を対象とするチャンク切り出しを行って、文書構成テーブル及びチャンク一覧テーブルを構成した例を示す図。
【図２７】従来技術における第１の課題の例を示す図。
【図２８】従来技術における第２の課題の例を示す図。
【発明を実施するための形態】
【００３９】
以下、本発明の実施の形態につき図面を参照して説明する。  
＜システム構成＞
図１は本発明の一実施形態に係るストレージシステムの構成を示すブロック図である。このストレージシステムは、文書格納装置１０と、クライアント装置２０とから構成される。文書格納装置１０とクライアント装置２０とは、例えばネットワーク３０によって接続されている。文書格納装置１０は文書をチャンクに分割して格納するためのデータ記憶装置である。クライアント装置２０は、文書格納装置１０を自身の記憶装置として利用する。つまりクライアント装置２０は、例えば当該クライアント装置２０上で動作するアプリケーションプログラムに従い、文書格納装置１０に対して文書格納を指示することにより当該文書格納装置１０に文書を格納させ、また文書格納装置１０に対して文書取得を指示することにより文書格納装置１０から文書を取得する。なお、文書格納装置１０とクライアント装置２０とが直接に接続されていても、クライアント装置２０としての機能が文書格納装置１０に内蔵されていても構わない。
【００４０】
文書格納装置１０は、クライアント装置２０から文書名で指定される文書の格納を指示するための文書格納指示が与えられると、後述する手続きに従って、当該文書名で指定される文書をチャンクに分割しながら重複検出・排除を行った上で、当該文書を後述する文書格納部３２（図３参照）に格納する。また文書格納装置１０は、クライアント装置２０から文書名で指定される文書の取得を指示するための文書取得指示が与えられると、当該文書名で指定される文書を文書格納部３２から取り出してクライアント装置２０に出力する。
【００４１】
ここでの文書とは例えばファイルまたは当該ファイル内のデータを指し、文書名とはファイル名を指す。なお、ファイルと当該ファイル内のデータとを区別するために、当該ファイル内のデータを文書のデータまたは文書データと称することもある。また、チャンクとは、データを断片化したもの（データ断片）を指す。また本実施形態では、データ断片として、「第１のデータ断片」、「第２のデータ断片」及び「第３のデータ断片」が定義される。以降の説明では、「第２のデータ断片」を「子チャンク」、「第３のデータ断片」を「親チャンク」と、それぞれ称する。また「第１のデータ断片」を、「登録済みのデータ断片」、「登録済みの親チャンク」または単に「親チャンク」と称する。
【００４２】
＜文書格納装置１０のハードウェア構成＞
本実施形態において、文書格納装置１０はコンピュータを用いて実現される。図２は、このような文書格納装置１０のハードウェア構成を示すブロック図である。図２に示されるように、文書格納装置１０、少なくとも１つの処理ユニット２１、主記憶装置２２、補助記憶装置２３、通信機構２４及び入出力装置２５の周知のハードウェア構成を有する。補助記憶装置２３は、例えばハードディスクドライブを用いて構成される。補助記憶装置２３は、処理ユニット２１によって実行されるプログラム２３０を格納した記憶媒体２３１を備えている。本実施形態において記憶媒体２３１はディスク媒体である。
【００４３】
＜文書格納装置１０の機能構成＞
図３は、文書格納装置１０の主として機能構成を示すブロック図である。文書格納装置１０は、文書格納部３１と、命令受け付けモジュール３２と、可変長重複排除モジュール３３と、作業用メモリ３４とを含む。本実施形態において、文書格納装置１０内の命令受け付けモジュール３２及び可変長重複排除モジュール３３は、当該文書格納装置１０が図２に示されるハードウェア構成のコンピュータから構成される場合に、当該コンピュータ内の処理ユニット２１が、補助記憶装置２３に格納されているプログラム２３０を主記憶装置２２に読み込んで実行することにより実現されるものとする。しかし、命令受け付けモジュール３２及び可変長重複排除モジュール３３の少なくとも１つがハードウェアとして実現されてもよい。
【００４４】
文書格納部３１は、文書構成テーブル３１１及びチャンク一覧テーブル３１２を用いて文書の群を格納する。文書格納部３１は、図２に示される補助記憶装置２３の記憶領域の一部を用いて実現される。文書構成テーブル３１１及びチャンク一覧テーブル３１２は、それぞれ、従来技術で適用されている文書構成テーブル２５１及びチャンク一覧テーブル２５２（図２６乃至図２８参照）に相当する。
【００４５】
文書構成テーブル３１１は、文書格納部３１に格納される文書の群のそれぞれについて、その文書の文書名と、その文書を構成するチャンクの群の識別子（ハッシュ値）の配列（つまりリスト）とを対応付けて保持する。チャンク一覧テーブル３１２は、文書格納部３１に格納される文書を構成するチャンクのそれぞれについて、そのチャンクのデータ断片と、そのチャンクの識別子（ハッシュ値）とを対応付けて保持する。つまり、文書格納部３１には、文書が、当該文書を構成するチャンクの群に分割して格納される。
【００４６】
本実施形態において、文書構成テーブル３１１及びチャンク一覧テーブル３１２は、文書格納装置１０の起動時（例えば文書格納装置１０の電源の投入時）に、アクセスの高速化のために、作業用メモリ３４にロードされて使用される。また、作業用メモリ３４にロードされている文書構成テーブル３１１及びチャンク一覧テーブル３１２は、例えば文書格納装置１０において処理を実行していない状態が一定時間続いた場合、或いは文書格納装置１０の動作停止時（例えば文書格納装置１０の電源の遮断時）に文書格納部３１に書き戻される。しかし、以降は便宜的に、文書格納装置１０の起動後においても文書格納部３１内の文書構成テーブル３１１及びチャンク一覧テーブル３１２が使用されるものとして説明する。
【００４７】
命令受け付けモジュール３２は、クライアント装置２０からの指示を受け付けて、当該指示の内容に従って動作する。命令受け付けモジュール３２は、クライアント装置２０からの指示が文書格納指示の場合、当該文書格納指示を可変長重複排除モジュール３３に渡すことにより、当該可変長重複排除モジュール３３による文書格納処理を行わせる。命令受け付けモジュール３２は、クライアント装置２０からの指示が文書取得指示の場合に動作する文書取得部３２０を含む。文書取得部３２０は、文書取得指示に従い、指定された文書名の文書のデータを文書格納部３１から取得するための文書取得処理を行う。文書取得部３２０によって取得された文書のデータは命令受け付けモジュール３２によってクライアント装置２０に出力される。
【００４８】
可変長重複排除モジュール３３は、命令受け付けモジュール３２から渡された文書格納指示に従い、指定された文書のデータから可変長でチャンクを切り出すためのチャンク切り出し処理と、切り出されたチャンク毎に重複を検出してそれを排除するための重複検出・排除処理とを行いながら、文書格納部３１に当該文書を格納する。可変長重複排除モジュール３３は、子チャンク決定部３３１と、親チャンク決定部３３２と、識別子生成部３３３と、重複検出部３３４と、親チャンク登録部３３５と、制御部３３６とを含む。
【００４９】
子チャンク決定部３３１は、可変長のチャンクを子チャンクとして決定する。親チャンク決定部３３２は、子チャンク決定部３３１によって決定された連続する子チャンクの列または単一の子チャンクを親チャンクとして決定する。
【００５０】
識別子生成部３３３は、チャンク（ここでは親チャンク）の切り出しと重複検出で利用される当該チャンクの識別子を生成する。本実施形態では、識別子としてチャンクのハッシュ値が用いられる。このハッシュ値には、例えばＳＨＡ１などのハッシュ関数を利用して生成された値が用いられる。
【００５１】
重複検出部３３４は、親チャンク決定部３３２によって決定された親チャンクの識別子に基づいて、当該識別子のデータ断片がチャンク一覧テーブル３１２に登録されている重複を検出する。
【００５２】
親チャンク登録部３３５は、重複検出部３３４の重複検出結果に基づいて、親チャンクを文書格納部３１内の文書構成テーブル３１１及びチャンク一覧テーブル３１２に登録するための親チャンク登録処理を行う。  
制御部３３６は、子チャンク決定部３３１、親チャンク決定部３３２、識別子生成部３３３及び重複検出部３３４の動作を制御する。
【００５３】
作業用メモリ３４は、可変長重複排除モジュール３３によるチャンク切り出し処理と重複検出・排除処理のための作業用の記憶領域を提供する。作業用メモリ３４は、図２に示される主記憶装置２２の記憶領域の一部を用いて実現される。作業用メモリ３４の記憶領域の一部は、処理の対象となる文書データを一時格納するための文書バッファ３４１として用いられる。作業用メモリ３４の記憶領域の他の一部は、処理に用いられる各種変数を一時格納するためのレジスタ部３４２として用いられる。レジスタ部３４２は、子チャンク番号ｉ，ｊ，ｋをそれぞれ保持するための、ｉレジスタ、ｊレジスタ、ｋレジスタと、子チャンク番号ｋの子チャンクの後述する開始オフセットｃk.offsetを保持するための子チャンク開始オフセットレジスタと、子チャンク番号ｋの子チャンクの長さ（子チャンク長）ｃk.lenを保持するための子チャンク長レジスタを含む。
【００５４】
＜文書格納処理＞
次に、文書格納装置１０における文書格納処理について、図４乃至図６を参照して説明する。なお、図４及び図５は、文書格納処理の手順を示すフローチャート、図６は文書格納装置１０に格納されるべき文書が図２３に示される文書１１１の場合における、親チャンクと子チャンクの群との関係を説明するため図である。
【００５５】
まず、クライアント装置２０から文書格納装置１０にネットワーク３０を介して文書格納指示が送られたものとする。この文書格納指示は、文書格納装置１０に格納されるべき文書を指定する文書名を含んでいる。
【００５６】
文書格納装置１０に送られたクライアント装置２０からの文書格納指示は、当該文書格納装置１０の命令受け付けモジュール３２で受け付けられる。命令受け付けモジュール３２は、この文書格納指示を受け付けると入力手段として機能して、当該文書格納指示で指定される文書名の文書のデータをクライアント装置２０から入力して作業用メモリ３４内の文書バッファ３４１に格納する。そして命令受け付けモジュール３２は、クライアント装置２０からの文書格納指示を、可変長重複排除モジュール３３に渡す。すると可変長重複排除モジュール３３は、図４及び図５のフローチャートに示す手順の文書格納処理を実行する。即ち可変長重複排除モジュール３３は、文書バッファ３４１に格納されている文書データの例えば先頭から末尾に至るまで、以下の処理を繰り返す。
【００５７】
まず可変長重複排除モジュール３３の制御部３３６は、子チャンク決定部３３１による子チャンクの切り出し（切り出し点の決定）のために、子チャンクｃkを指定するための子チャンク番号ｋを０に初期設定すると共に、当該子チャンクｃkのオフセット（開始オフセット）ｃk.offsetを文書データの先頭位置（ここでは先頭バイトの位置）を示す０に初期設定する（ステップ４０１）。つまり制御部３３６は、レジスタ部３４２内のｋレジスタに、子チャンク番号ｋとして０（ｋ＝０）を設定すると共に、レジスタ部３４２内の子チャンク開始オフセットレジスタに、子チャンクｃkの開始オフセットｃk.offsetとして０（ｃk.offset＝０）を設定する。子チャンクｃkの開始オフセットｃk.offsetは、当該子チャンクｃkの開始切り出し点を示すもので、当該開始切り出し点の文書データの先頭位置からのオフセット（相対位置）を示す。この時点では、子チャンクｃkの終了切り出し点を示す終了オフセットは決定されていないことに注意されたい。
【００５８】
次に制御部３３６は、子チャンクｃj，ｃiの子チャンク番号ｊ，ｉをいずれもｋに設定する（ステップ４０２）。つまり制御部３３６は、レジスタ部３４２内のｊレジスタ及びｉレジスタに、それぞれ子チャンク番号ｊ，ｉとしてｋ（ｋ＝０）を設定する。子チャンクｃiは、チャンク一覧テーブル３１２に登録すべき１つの親チャンクを決定するための一連の処理（登録親チャンク決定処理）の最初に求められる親チャンクにおける先頭の子チャンクを示す。子チャンクｃjは、登録親チャンク決定処理で求められる最新の親チャンクにおける先頭の子チャンクを示す。
【００５９】
すると、可変長重複排除モジュール３３内の子チャンク決定部３３１は、子チャンクｃkの終了切り出し点を示す終了オフセットを決定することにより、当該子チャンクｃkの長さを求め、その長さを、当該子チャンクｃkの長さを示す子チャンク長ｃk.lenとして、レジスタ部３４２内の子チャンク長レジスタに設定する（ステップ４０３）。子チャンクｃkの終了オフセットを決定する手法、つまり子チャンクｃk（可変長のチャンク）の切り出し点を定める手法には、前記特許文献１，２に記載されているような手法の他に、図７を参照して後述する手法を適用することが可能である。
【００６０】
次に可変長重複排除モジュール３３の制御部３３６は、子チャンクｃkの開始オフセットｃk.offsetに子チャンク長ｃk.lenを加算した値（ｃk.offset + ｃk.len）が、文書データのサイズ未満であるかを判定する（ステップ４０４）。この判定は、子チャンクｃkの終端が文書データの末尾（終了位置）に到達していないことを確認するために行われる。
【００６１】
もし、“ｃk.offset + ｃk.len”が文書データのサイズ未満であるならば（ステップ４０４のＮｏ）、制御部３３６は、“ｃk.offset + ｃk.len”から子チャンクｃjのオフセットｃj.offsetを減じた値（ｃk.offset + ｃk.len - ｃj.offset）が予め定められた連結ウィンドウサイズＷ以上であるかを判定する（ステップ４０５）。本実施形態では、連結ウィンドウサイズＷは１０バイト（Ｗ＝１０）であるものとする。
【００６２】
“ｃk.offset + ｃk.len - ｃj.offset”は、子チャンク番号がｊからｋまでの子チャンクｃj〜ｃkを連結した場合に、その連結された子チャンクの列の長さを表す。“ｃj.offset”、つまり連結された子チャンクの列の先頭の子チャンクｃjのオフセットは、当該連結された子チャンクの列の開始オフセットを示す。この連結された子チャンクの列の開始オフセットは、後述するように決定される親チャンクｐの開始オフセットとなる。そこで、この開始オフセットを、子チャンクの開始オフセットと区別するために、親チャンク開始オフセットと称する。
【００６３】
ステップ４０１，４０２が実行された後にステップ４０５が最初に実行される場合、子チャンクｃkは子チャンク番号ｋが０の先頭の子チャンクであり、図６の例ではデータ断片“The f”が先頭の子チャンクである。このとき子チャンクｃkは子チャンクｃjに一致するため、“ｃk.offset”は“ｃj.offset”に一致する。この場合、“ｃk.offset + ｃk.len - ｃj.offset”は子チャンクｃkの長さ“ｃk.len”に一致する。
【００６４】
もし、“ｃk.offset + ｃk.len - ｃj.offset”が、連結ウィンドウサイズＷ以上でないならば（ステップ４０５のＮｏ）、制御部３３６は、レジスタ部３４２内の子チャンク開始オフセットレジスタにより次の子チャンクｃk+1の開始オフセットｃk+1.offsetが示されるように、現在当該子チャンク開始オフセットレジスタに保持されている子チャンクｃkのオフセットｃk.offsetに現在子チャンク長レジスタに設定されている当該子チャンクｃkの長さを加算した値を、次の子チャンクｃk+1の開始オフセットｃk+1.offsetとして当該子チャンク開始オフセットレジスタに設定する（ステップ４０６）。このステップ４０６において制御部３３６は、ｋレジスタに保持されている子チャンク番号ｋを１インクリメントする。これにより、１インクリメント後の子チャンク番号ｋは、ステップ４０６が実行される前の子チャンクｃkに後続する子チャンクｃk+1を新たな子チャンクｃkとして指定することになる。このとき、子チャンク開始オフセットレジスタは、新たな子チャンクｃkの開始オフセットを示す。
【００６５】
制御部３３６によってステップ４０６が実行されると、子チャンク決定部３３１は再びステップ４０３を実行することにより新たな子チャンクｃkの長さを求めて、その長さを子チャンク長ｃk.lenとして設定する。図６の例において、ステップ４０６が実行される前の子チャンクｃkが先頭の子チャンク“The f”である場合、“The f”に後続するデータ断片“file”が新たな子チャンクｃkとして決定される。そして、この新たな子チャンクｃkの子チャンク長ｃk.lenに基づき、上述の処理が再び行われる。
【００６６】
すると、図６の例では、“file”に後続するデータ断片“ na”が更に新たな子チャンクｃkとして決定される。このとき“ｃk.offset + ｃk.len - ｃj.offset”、つまり子チャンク番号がｊからｋまでの子チャンクｃj（“The f”）〜ｃk（“ na”）を連結した場合に、その連結された子チャンクの列の長さをＬ１とする。この長さＬ１は、図６に示されるように連結ウィンドウサイズＷ以上となる。
【００６７】
このように、“ｃk.offset + ｃk.len - ｃj.offset”が連結ウィンドウサイズＷ以上となると（ステップ４０５のＹｅｓ）、親チャンク決定部３３２は、子チャンク番号がｊからｋまでの子チャンクｃj〜ｃkを１つに連結し、それを親チャンクｐとして定める（ステップ４０７）。図６の例では、文書１１１（文書名が「文書＃１」の文書）の先頭から３つの子チャンクが連結されて、親チャンクｐ１（ｐ＝ｐ１）として決定される。この親チャンクｐ１を、後述するように親チャンク開始オフセットが再設定されることによって定められる後続の親チャンクｐ２，ｐ３と区別するために、当初親チャンクと呼ぶこともある。なお、ステップ４０４の判定条件として、上述の条件の他に、（１）“ｃk.offset + ｃk.len - ｃj.offset”が連結ウィンドウサイズＷを超えること、（２）“ｃk.offset + ｃk.len - ｃj.offset”が連結ウィンドウサイズＷに一致すること、（３）“ｃk.offset + ｃk.len - ｃj.offset”が連結ウィンドウサイズＷに最も近くなること、（４）“ｃk.offset + ｃk.len - ｃj.offset”が連結ウィンドウサイズＷを超えない最大値となることのいずれかを適用しても構わない。
【００６８】
上記ステップ４０７において親チャンク決定部３３２は、子チャンクｃj〜ｃkを連結したデータｃj...k.dataを親チャンクｐのデータ（データ断片）ｐdataとして求める。また上記ステップ４０７において親チャンク決定部３３２は、当該親チャンクｐのデータｐdataの識別子として用いられる、当該親チャンクｐのデータｐdataのハッシュ値ｐhashを、識別子生成部３３３により生成させる。このハッシュ値を求めるのに用いられるハッシュ関数をhash( )のように表すものとすると、ハッシュ値ｐhashは、hash(ｐdata)の計算処理、つまりhash(ｃj...k.data)の計算処理により求められる。なお、子チャンク番号ｊがｋに一致するならば、つまり単一の子チャンクだけで連結ウィンドウサイズＷ以上となるならば、当該単一の子チャンク自体が親チャンクｐと決定される。
【００６９】
次に、可変長重複排除モジュール３３内の重複検出部３３４は、ステップ４０７で求められた親チャンクｐ（ｐ＝ｐ１）のデータ断片が既にチャンク一覧テーブル３１２に登録されているかを判定する（ステップ４０８）。このステップ４０８は、親チャンクｐと同一内容の親チャンクが、既に文書格納部３１に格納されている重複を検出するために実行される。ステップ４０８の判定は、親チャンクｐのデータｐdataの識別子（ハッシュ値）ｐhashに一致する識別子（ハッシュ値）が既にチャンク一覧テーブル３１２に登録されているかを調べることにより実現可能である。しかし、親チャンクｐのデータ（データ断片）ｐdataのビット列と、親チャンクｐのデータｐdataの識別子に一致する識別子と対をなしてチャンク一覧テーブル３１２に登録されているチャンクのデータのビット列とは、識別子（ハッシュ値）の計算に用いるハッシュ関数によっては、必ずしも一致するとは限らない。そこで、上記ステップ４０８において重複検出部３３４は、親チャンクｐのデータｐdataの識別子（ハッシュ値）ｐhashと当該データｐdataの対が、チャンク一覧テーブル３１２に登録されているかを判定する。更に詳細に述べるならば、重複検出部３３４は、親チャンクｐの識別子ｐhashに一致する識別子がチャンク一覧テーブル３１２に登録されているけでなく、当該親チャンクｐのデータｐdataのビット列に一致するチャンクのデータのビット列が、当該一致する識別子と対応付けてチャンク一覧テーブル３１２に登録されているかを判定する。このようにすると、より高精度の重複検出が行えて、いわゆるハッシュ衝突を防止することができる。
【００７０】
もし、ステップ４０７で求められた親チャンクｐのデータ（データ断片）ｐdataがチャンク一覧テーブル３１２に登録されていないならば（ステップ４０８のＮｏ）、制御部３３６は子チャンク番号ｊを１インクリメントする（ステップ４０９）。この１インクリメント後の子チャンク番号ｊは、ステップ４０７で求められた親チャンクｐを構成する子チャンクの列における先頭の子チャンクに後続する子チャンクであって、次に決定されるべき親チャンクｐの先頭の子チャンク（新たな子チャンク）ｃjを指す。
【００７１】
この新たな子チャンクｃjの開始オフセットｃj.offsetfは、ステップ４０７で求められた親チャンクｐを構成する子チャンクの列における先頭の子チャンクの長さだけ文書データの末尾側にずらされた、新たな親チャンク開始オフセットを示す。つまりステップ４０９により、親チャンク開始オフセットが再設定される。図６の例では、新たな（再設定された）親チャンク開始オフセットは、文書１１１の先頭から２番目の子チャンク（データ断片が“ile”の子チャンク）の開始オフセットに一致する。ステップ４０９は、後述するように、ステップ４０７で求められた親チャンクｐから、先頭の子チャンクののデータ断片を取り外すことと等価である。
【００７２】
次に制御部３３６は、“ｃj.offset + ｃj.len - ｃi.offset”が連結ウィンドウサイズＷ以上であるかを判定する（ステップ４１０）。このときｃj.offsetは、上述のように再設定された親チャンク開始オフセットを示す。一方、“ｃi.offset”は、当初親チャンクｐの開始オフセットを示す。したがって、“ｃj.offset + ｃj.len - ｃi.offset”は、子チャンク番号がｉからｊまでの子チャンクｃi〜ｃjを連結した場合に、その連結された子チャンクの列の長さを表す。つまり、“ｃj.offset + ｃj.len - ｃi.offset”は、ステップ４０９で再設定された親チャンク開始オフセットの当初親チャンクｐの開始オフセットからの「ずれ」を表す。
【００７３】
もし、“ｃj.offset + ｃj.len - ｃi.offset”が連結ウィンドウサイズＷ以上でないならば（ステップ４１０のＮｏ）、制御部３３６はステップ４０６に進み、レジスタ部３４２内の子チャンク開始オフセットレジスタが次の子チャンクｃk+1の開始オフセットｃk+1.offsetを示すように、当該レジスタの内容を“ｃk.offset + ｃk.len”に更新すると共に、子チャンク番号ｋを１インクリメントする。このインクリメントにより、次の子チャンクｃk+1が新たな子チャンクｃkとして扱われる。この例のように、ステップ４１０でＮｏが判定されたためにステップ４０６が実行された場合、新たな子チャンクｃkは、先に決定された親チャンクｐを構成するチャンクの列に後続する子チャンクである。図６の例では、“ na”に後続するデータ断片“me spe”が新たな子チャンクｃkのデータ断片して決定される。
【００７４】
制御部３３６によってステップ４０６が実行されると、子チャンク決定部３３１は再びステップ４０３を実行することにより新たな子チャンクｃkの長さを求めて、その長さを子チャンク長ｃk.lenとして設定する。このように本実施形態では、ステップ４０９で再設定された親チャンク開始オフセットから始まる子チャンクｃj〜ｃkの列の長さが連結ウィンドウサイズＷ以上となるところまで、子チャンクが定められる。ここでは、ステップ４０６の処理から明らかなように、再設定された親チャンク開始オフセット以降に出現する、以前の処理で既に定められた子チャンクｃj〜ｃk-1について再び定め直す必要はない。
【００７５】
図６の例では、このときの子チャンクｃj〜ｃkのデータ断片は“file”〜“me spe”である。子チャンクｃj（“file”）〜ｃk（“me spe”）を連結した場合に、その連結された子チャンクの列の長さ“ｃk.offset + ｃk.len - ｃj.offset”をＬ２とする。この長さＬ２は、図６に示されるように連結ウィンドウサイズＷ以上となる。
【００７６】
この例のように、“ｃk.offset + ｃk.len - ｃj.offset”が連結ウィンドウサイズＷ以上となったならば（ステップ４０５のＹｅｓ）、親チャンク決定部３３２は上述のように、子チャンク番号がｊからｋまでの子チャンクｃj〜ｃkを１つに連結し、それを親チャンクｐとして定める（ステップ４０７）。図６の例では、文書１１１の先頭から２番目乃至４番目の子チャンクが連結されて、親チャンクｐ２（ｐ＝ｐ２）として決定される。親チャンクｐ２は、先に決定された親チャンクｐ１から先頭の子チャンク（つまり文書１１１の先頭の子チャンク）を上記ステップ４０９によって取り外し、その先頭の子チャンクが取り外された親チャンクｐ１に、新たに文書１１１の先頭から４番目の子チャンクが上記ステップ４０６，４０３，４０７によって組み込まれることによって構成される新たな親チャンクと等価である。
【００７７】
次に重複検出部３３４は、ステップ４０７で求められた親チャンクｐ（ｐ＝ｐ２）のデータ（データ断片）ｐdataが既にチャンク一覧テーブル３１２に登録されているかを判定する（ステップ４０８）。もし、親チャンクｐのデータｐdataがチャンク一覧テーブル３１２に登録されていないならば（ステップ４０８のＮｏ）、制御部３３６は上述したようにステップ４０９に進み、子チャンク番号ｊを１インクリメントする。これにより、親チャンク開始オフセットが再設定される。図６の例では、再設定された親チャンク開始オフセットは、文書１１１の先頭から３番目の子チャンク（データ断片が“ na”の子チャンク）の開始オフセットに一致する。
【００７８】
図６の例では、このときの“ｃj.offset + ｃj.len - ｃi.offset”、つまり親チャンク開始オフセットの「ずれ」は、連結ウィンドウサイズＷ以上でない（ステップ４１０のＮｏ）。この場合、ステップ４０６及び４０３を含む処理が繰り返される。これにより図６の例では、文書１１１の先頭から３番目乃至５番目の子チャンクが連結されて、長さがＬ３（Ｌ３≧Ｗ）の親チャンクｐ３（ｐ＝ｐ３）として決定される（ステップ４０７）。
【００７９】
もし、決定された親チャンクｐ（ｐ＝ｐ３）のデータｐdataがチャンク一覧テーブル３１２に登録されていないならば（ステップ４０８のＮｏ）、制御部３３６は上述したようにステップ４０９に進み、子チャンク番号ｊを１インクリメントする。これにより、親チャンク開始オフセットが再設定される。図６の例では、再設定された親チャンク開始オフセットは、文書１１１の先頭から４番目の子チャンク（データ断片が“me spe”の子チャンク）の開始オフセットに一致する。
【００８０】
図６の例では、このときの“ｃj.offset + ｃj.len - ｃi.offset”、つまり親チャンク開始オフセットの「ずれ」は、連結ウィンドウサイズＷ以上である（ステップ４１０のＹｅｓ）。この場合、制御部３３６は、子チャンク番号ｋを子チャンク番号ｊから１を減じた値、つまりステップ４０９で１インクリメントされる前の子チャンク番号ｊに再設定する（ステップ４１１）。これにより、再設定された子チャンク番号ｋは、当初親チャンクにおける終端側の子チャンクｃkを示す。ステップ４１０が実行されると、ステップ５１０に進む。
【００８１】
一方、ステップ４０７で決定された親チャンクｐが既にチャンク一覧テーブル３１２に登録されている登録済み親チャンクであるならば（ステップ４０８のＹｅｓ）、親チャンク登録部３３５は文書構成テーブル３１１及びチャンク一覧テーブル３１２のうちの文書構成テーブル３１１のみに当該親チャンクｐを登録する（ステップ４１２）。更に詳細に述べるならば、親チャンク登録部３３５は、親チャンクｐを含む文書の文書名に対応付けて当該親チャンクｐの識別子（ハッシュ値）ｐhashを文書構成テーブル３１１に登録する。なお、文書構成テーブル３１１及びチャンク一覧テーブル３１２が空の状態にある場合、つまり未だ１つの親チャンクも文書構成テーブル３１１及びチャンク一覧テーブル３１２に登録されていない場合、最初にステップ４０７で決定された親チャンクｐを、文書構成テーブル３１１及びチャンク一覧テーブル３１２に登録しても構わない。
【００８２】
ここで、既に親チャンクｐを含む文書の文書名が文書構成テーブル３１１に登録されている場合、親チャンク登録部３３５は、当該文書名に対応付けて文書構成テーブル３１１に既に登録されている識別子の配列の末尾に当該親チャンクｐの識別子ｐhashを追加する。これにより、親チャンクｐを含む文書の文書名に対応付けて文書構成テーブル３１１に登録される識別子の並び順は、当該文書から対応する親チャンクが切り出される順番、つまり対応する親チャンクの当該文書における並び順に一致する。
【００８３】
可変長重複排除モジュール３３の制御部３３６は、文書構成テーブル３１１に親チャンクｐが登録されと（ステップ４１２）、子チャンク番号ｉと子チャンク番号ｊとが等しいかを判定する（ステップ４１３）。つまり制御部３３６は、文書構成テーブル３１１に登録された親チャンクｐが、親チャンク開始オフセットを再設定（ステップ４０９）することなく決定されたかを判定する。もし、子チャンク番号ｉと子チャンク番号ｊとが等しくないならば（ステップ４１３のＮｏ）、ステップ４１３からステップ５０１に進む。
【００８４】
このように、ステップ４０６，４０３を含む処理を繰り返した結果、親チャンクｐが決定されて（ステップ４０７）、当該決定された親チャンクｐのデータｐdataが既にチャンク一覧テーブル３１２に登録されていることが検出され（ステップ４０８のＹｅｓ）、且つｉ＝ｊでない場合（ステップ４１３のＮｏ）、ステップ５０１が実行される。また、親チャンク開始オフセットの「ずれ」が連結ウィンドウサイズＷ以上になったことが検出された場合には（ステップ４１０のＹｅｓ）、ステップ４１１を経てステップ５０１が実行される。
【００８５】
ステップ５０１において親チャンク決定部３３２は、子チャンク番号がｉからｊ−１までの子チャンクｃi〜ｃj-1を１つに連結し、それを親チャンクｐとして定める。またステップ５０１において、親チャンク決定部３３２は、子チャンクｃi〜ｃj-1を連結したデータｃi...j-1.dataを親チャンクｐのデータｐdataとして求めると共に、当該親チャンクｐのデータｐdataのハッシュ値（識別子）ｐhash（＝hash(ｃi...j-1.data)）を識別子生成部３３３により生成させる。
【００８６】
次に親チャンク登録部３３５は、チャンク一覧テーブル３１２に親チャンクｐを登録する（ステップ５０２）。更に詳細に述べるならば、親チャンク登録部３３５は、親チャンクｐの識別子（ハッシュ値）ｐhash及び当該親チャンクｐのデータ（データ断片）ｐdataをチャンク一覧テーブル３１２に登録する。また親チャンク登録部３３５は、文書構成テーブル３１１に親チャンクｐを登録する（ステップ５０３）。つまり親チャンク登録部３３５は、親チャンクｐを含む文書の文書名に対応付けて当該親チャンクｐの識別子ｐhashを文書構成テーブル３１１に登録する。
【００８７】
さて、ステップ４１０からステップ４１１を経てステップ５０１に進んだ場合、ステップ５０１で決定される親チャンクｐ、つまり子チャンクｃi〜ｃj-1の列から構成される親チャンクｐは、当初親チャンクｐ（図６の例では、親チャンクｐ１）に一致する。
【００８８】
一方、ステップ４１３からステップ５０１に進んだ場合、ステップ５０１で決定される親チャンクｐを構成する子チャンクｃi〜ｃj-1の列は、最も最近にチャンク一覧テーブル３１２に登録された親チャンクとステップ４０８での判定に用いられた親チャンクとの間に存在する子チャンクの列である。なお、ｉがｊ−１に等しい場合、子チャンクｃi〜ｃj-1は単一の子チャンクを意味する。
【００８９】
親チャンク登録部３３５によってステップ５０３が実行されると、１回の登録親チャンク決定処理が終了する。すると制御部３３６は先のステップ４０４と同様に、“ｃk.offset + ｃk.len”が文書データのサイズ未満であるかを判定する（ステップ５０４）。
【００９０】
もし、“ｃk.offset + ｃk.len”が文書データのサイズ未満であるならば（ステップ５０４のＹｅｓ）、制御部３３６は文書データの末尾まで処理をし終えていないと判断する。この場合、制御部３３６は、次の登録親チャンク決定処理のために、レジスタ部３４２内の子チャンク開始オフセットレジスタが次の子チャンクｃk+1の開始オフセットｃk+1.offsetを示すように、当該レジスタの内容を“ｃk.offset + ｃk.len”に更新すると共に、子チャンク番号ｋを１インクリメントする（ステップ５０５）。制御部３３６はステップ５０５を実行すると、ステップ４０２に戻り、子チャンク番号ｊ，ｉをいずれもｋに設定する。これにより、親チャンク開始オフセットが、先の登録親チャンク決定処理における当初親チャンクの終了オフセットの位置（つまり終端位置）に再設定される。以後、ステップ４０３を含む上述と同様の手順の登録親チャンク決定処理が文書データの末尾まで繰り返される。
【００９１】
そして文書データの末尾まで処理が行われた結果、“ｃk.offset + ｃk.len”が文書データのサイズ未満でなくなったものとする（ステップ４０４のＮｏ）。この場合、親チャンク決定部３３２は、ステップ４０７と同様に、子チャンク番号がｊからｋまでの子チャンクｃj〜ｃkを１つに連結し、それを親チャンクｐとして定める（ステップ４１４）。このステップ４１４において可変長重複排除モジュール３３は、子チャンクｃj〜ｃkを連結したデータｃj...k.dataを親チャンクｐのデータｐdataとして求めると共に、当該親チャンクｐのデータｐdataのハッシュ値（識別子）ｐhash（＝hash(ｃj...k.data)）を識別子生成部３３３により生成させる。
【００９２】
すると重複検出部３３４は、ステップ４１４で求められた親チャンクｐのデータ断片が既にチャンク一覧テーブル３１２に登録されているかを判定する（ステップ４１５）。  もし、ステップ４１４で求められた親チャンクｐのデータ断片がチャンク一覧テーブル３１２に登録されていないならば（ステップ４１５のＮｏ）、親チャンク登録部３３５は、チャンク一覧テーブル３１２に親チャンクｐの識別子（ハッシュ値）ｐhash及び当該親チャンクｐのデータ断片ｐdataを登録する（ステップ４１６）。次に親チャンク登録部３３５は上記ステップ４１２に進み、親チャンクｐを含む文書の文書名に対応付けて当該親チャンクｐの識別子ｐhashを文書構成テーブル３１１に登録する。これに対し、親チャンクｐのデータ断片がチャンク一覧テーブル３１２に既に登録されているならば（ステップ４１５のＹｅｓ）、親チャンク登録部３３５はステップ４１６をスキップして、ステップ４１２を実行する。
【００９３】
親チャンク登録部３３５によってステップ４１２が実行されると、制御部３３６は、子チャンク番号ｉと子チャンク番号ｊとが等しいかを判定する（ステップ４１３）。もし、子チャンク番号ｉと子チャンク番号ｊとが等しいならば（ステップ４１３のＹｅｓ）、制御部３３６上記ステップ５０４に進む。ステップ５０４において制御部３３６は、先のステップ４０４と同様に、“ｃk.offset + ｃk.len”が文書データのサイズ未満であるかを判定する。ステップ４０４の判定がＮｏであるこの例では、ステップ５０４の判定もＮｏとなる。この場合、可変長重複排除モジュール３３は文書データの末尾まで処理をし終えたとして、文書格納処理を終了する。
【００９４】
＜子チャンクの切り出し＞
次に、子チャンク（つまり可変長のデータ断片）の切り出し点を決定する手法について説明する。前述したように、この手法として、前記特許文献１，２に記載されているような手法を適用することが可能である。しかし、この特許文献１，２に記載の手法の他に、以下に述べるような新規の手法を適用することも可能である。この新規の手法の特徴は、あるデータ断片の識別子（ハッシュ値）の下位ｍビットが、予め定めた値Ａに一致したときに、当該データ断片の終端位置を子チャンクの切り出し点とすることにある。
【００９５】
以下、この新規の手法について、図７を参照して説明する。図７は、あるデータ断片の識別子（ハッシュ値）の下位２ビット（ｍ＝２）が、予め定めた値２（Ａ＝２）に一致したときに、、当該データ断片の終端位置を子チャンクの切り出し点とする例を示す。データ断片の識別子（ハッシュ値）の計算に用いられるハッシュ関数をｈβ( )のように表す。
【００９６】
図７の例では、文書データ“The fil…”におけるデータ断片“Th”の識別子ｈβ（“Th”）が０ｘ５Ａである。この識別子０ｘ５Ａの下位２ビットは０ｘ０２である。この識別子０ｘ５Ａの下位２ビットは、当該識別子０ｘ５Ａとマスクデータ０ｘ０３との論理積演算０ｘ５Ａ＆０ｘ０３によって求められる。識別子０ｘ５Ａの下位２ビット０ｘ０２は、規定値０ｘ０１に一致しない。このためデータ断片“Th”の終端位置は子チャンクの切り出し点ではない。
【００９７】
そこで子チャンク決定部３３１は、切り出し点決定に用いるデータ断片のサイズ（区間）を文書データの末尾側に１バイト拡張する。このサイズ拡張後のデータ断片“The”の識別子ｈβ(“The”)が０ｘＦ２であるものとする。この識別子０ｘＦ２の下位２ビットは０ｘ０２であり、規定値０ｘ０１に一致しない。そこで子チャンク決定部３３１は、データ断片のサイズを更に１バイト拡張する。
【００９８】
サイズ拡張後のデータ断片“The ”の識別子ｈβ(“The ”)が０ｘ７Ｃであるものとする。この識別子０ｘ７Ｃの下位２ビットは０ｘ００であり、規定値０ｘ０１に一致しない。そこで子チャンク決定部３３１は、データ断片のサイズを更に１バイト拡張する。
【００９９】
サイズ拡張後のデータ断片“The f”の識別子ｈβ(“The f”)が０ｘ９９であるものとする。この識別子０ｘ９９の下位２ビットは０ｘ０１であり、規定値０ｘ０１に一致する。そこで子チャンク決定部３３１は、このデータ断片“The f”の終端位置を切り出し点（終了オフセット）として決定し、当該データ断片“The f”を子チャンクとして切り出す。
【０１００】
上述の文書格納処理の主要な手順を以下に整理して示す。
【０１０１】
可変長重複排除モジュール３３は、文書データの先頭から末尾に至るまで、以下の処理を繰り返し行う。
【０１０２】
ａ）文書の先頭を親チャンク開始オフセットとして設定する（ステップ４０１，４０２）。
【０１０３】
ｂ）親チャンク開始オフセットから、連結後の長さが連結ウィンドウサイズＷ以上となるところまで、子チャンクの列（または単一の子チャンク）を定める（ステップ４０３〜４０６）。
【０１０４】
ｃ）処理ｂで子チャンクの列が定められたときには、これを１つに連結して、親チャンク（当初親チャンク）として定める（ステップ４０７）。処理ｂで単一の子チャンクが定められたときにも、これを親チャンク（当初親チャンク）として定める（ステップ４０７）。親チャンク（当初親チャンク）の長さは連結ウィンドウサイズＷ以上となる。
【０１０５】
ｄ）親チャンクの識別子（ハッシュ値）を求める（ステップ４０７）。
【０１０６】
ｅ）チャンク一覧テーブル３１２に既に親チャンクの識別子及びデータ断片が登録されているかを判定する（ステップ４０８）。
【０１０７】
ｅ．１）登録されていれば、親チャンクの識別子を文書名に対応付けて文書構成テーブル３１１に登録する（ステップ４１２）。
【０１０８】
ｅ．２）登録されていなければ、以下の処理を行う。
【０１０９】
ｅ．２-1）親チャンクを構成する子チャンクの列の先頭側の少なくとも１つの子チャンク、例えば先頭の子チャンク（つまり、親チャンク開始オフセット側に最も近い子チャンク）のサイズだけ後側にずらした位置を親チャンク開始オフセットとして再設定する（ステップ４０９）。
【０１１０】
ｅ．２-2）親チャンク開始オフセットから、連結後の長さが連結ウィンドウサイズＷ以上となるところまで、子チャンクの列（または単一の子チャンク）を定める（ステップ４０３〜４０６）。このとき、以前の処理で既に定めた子チャンクについて再び定め直す必要はない（ステップ４０６）。
【０１１１】
ｅ．２-3）処理ｅ．２-2で子チャンクの列が定められたときには、これを１つに連結して、親チャンクとして定める（ステップ４０７）。処理ｅ．２-2で単一の子チャンクが定められたときにも、これを親チャンクとして定める（ステップ４０７）。
【０１１２】
ｅ．２-4）親チャンクの識別子（ハッシュ値）を求める（ステップ４０７）。
【０１１３】
ｅ．２-5）チャンク一覧テーブル３１２に既に親チャンクの識別子及びデータ断片が登録されているかを判定する（ステップ４０８）。
【０１１４】
ｅ．２-６）以上の処理（ｅ．２-1〜ｅ．２-5）を、親チャンクの識別子及びデータ断片がチャンク一覧テーブル３１２に既に登録されているか（ステップ４０８のＹｅｓ）、親チャンク開始オフセットの「ずれ」が処理ｃで定めた当初親チャンクのサイズを超えるところまで（ステップ４１０のＹｅｓ）、繰り返す（図６の例では親チャンクｐ３まで）。
【０１１５】
ｅ．２-7）これでもなおデータ断片が登録されていないときには、処理ｃで定めた当初親チャンク（図６の例では親チャンクｐ１）の識別子及びデータ断片をチャンク一覧テーブル３１２に登録すると共に、当該識別子を文書名に対応付けて文書構成テーブル３１１に登録する（ステップ５０２，５０３）。そして、次の親チャンク開始オフセットとなる子チャンクの開始オフセットを、処理ｃで定めた当初親チャンクの終了オフセット（つまり当初親チャンクの終端側の子チャンクの終了オフセット）の位置に再設定して（ステップ４１１，５０５）、処理ｂに戻る。
【０１１６】
親チャンクの識別子及びデータ断片がチャンク一覧テーブル３１２に既に登録されているときには（ステップ４０８のＹｅｓ）、その親チャンクの識別子を文書名に対応付けて文書構成テーブル３１１に登録する（ステップ４１２）。また、文書構成テーブル３１１に登録された親チャンクと、前回チャンク一覧テーブル３１２に登録された親チャンクとの間に、チャンク一覧テーブル３１２に未登録のデータ断片が存在するときには（ステップ４１３のＮｏ）、当該データ断片を親チャンクとして、当該データ断片及び当該データ断片の識別子をチャンク一覧テーブル３１２に登録すると共に、当該データ断片の識別子を文書名に対応付けて文書構成テーブル３１１に登録する（ステップ５０１〜５０３）。このとき、文書を構成するチャンクの順序が正しくなるように、文書構成テーブル３１１におけるチャンク（データ断片）を書き換える必要がある。そして、次の親チャンク開始オフセットとなる子チャンクの開始オフセットを、今回登録された親チャンクの終了オフセット（つまり当初親チャンクの終端側の子チャンクの終了オフセット）の位置に再設定して（ステップ４１１，５０５）、処理ｂに戻る。なお、文書名に対応付けて親チャンクの識別子を文書構成テーブル３１１に登録する際に、当該親チャンクの対応する文書データ上での位置・長さを示す情報を当該親チャンクの識別子に付加するならば、上述のような書き換えは必ずしも必要ない。
【０１１７】
以上の処理を、データの末尾に至るまで繰り返すことで、可変長での重複排除を行いながら、データの格納を行うことができる。
【０１１８】
＜文書格納処理の具体例＞
次に、文書格納装置１０における文書格納処理の具体例について、図５及び図６のフローチャートに加えて、図８乃至図２１を参照して説明する。  
ここでは、文書名が「文書＃１」の文書１１１及び文書名が「文書＃２」の文書１１２の２つの文書を順次、重複を排除しながら文書格納部３１に格納する例について述べる。以下の説明では、文書１１１，１１２を格納するための格納処理をそれぞれ格納処理ＳＸ，ＳＹと呼ぶ。この例では、連結ウィンドウサイズＷが１０（１０バイト）に設定される。
【０１１９】
（１）格納処理ＳＸ，ＳＹの開始前
文書１１１，１１２が文書格納部３１に格納される前は、文書格納部３１内の文書構成テーブル３１１及びチャンク一覧テーブル３１２は空の状態になっている。図８は文書１１１，１１２（第１及び第２の文書）と、当該文書１１１，１１２の格納前における文書構成テーブル３１１及びチャンク一覧テーブル３１２の状態とを示す。
【０１２０】
（２）格納処理ＳＸ
文書１１１を格納するための格納処理（格納動作）ＳＸについて、図９乃至図１４を参照して説明する。図９乃至図１３は文書１１１の格納動作を文書構成テーブル３１１の状態と共に示し、図１４は文書１１１の格納後における、文書構成テーブル３１１及びチャンク一覧テーブル３１２の状態を、当該文書１１１と当該文書１１１から切り出された親チャンクの列と共に示す。
【０１２１】
Ａ）格納処理ＳＸその１
まず、文書１１１を格納するための格納処理ＳＸその１（以下、格納処理ＳＸ１と称する）について、図９を参照して説明する。なお、図９では、文書構成テーブル３１１は省略されている。
【０１２２】
Ａ１）
Ａ１-1）可変長重複排除モジュール３３は、文書１１１の先頭から、連結ウィンドウサイズＷ（この例ではＷ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。各子チャンクは、前述した可変長のチャンク切り出し手法により定められる。図９の例では、可変長重複排除モジュール３３は、文書１１１の先頭より５，８，１１文字目のところに切り出し点を定め、子チャンクｃ0（“The f”），ｃ1（“ile”），ｃ2（“ na”）を定めたものとする。
【０１２３】
Ａ１-2）可変長重複排除モジュール３３は、連結ウィンドウサイズＷ以上となるところまで子チャンクｃ0（“The f”），ｃ1（“ile”），ｃ2（“ na”）を順次定めたところで、それらの子チャンクを連結して親チャンク９０１を定め、当該親チャンク９０１の識別子（ハッシュ値）を生成する（ステップ４０７）。連結する子チャンクｃ0（“The f”），ｃ1（“ile”），ｃ2（“ na”）の識別子（ハッシュ値）を、ｃ0.hash＝ＨA，ｃ1.hash＝ＨB，ｃ2.hash＝ＨCとする。この例では、親チャンク９０１のデータのハッシュ値として、当該親チャンク９０１を構成する子チャンクｃ0，ｃ1，ｃ2の識別子（ハッシュ値）ＨA，ＨB，ＨCから生成されたハッシュ値ＨABCを用い、これを親チャンク９０１の識別子とする。
【０１２４】
Ａ１-3）可変長重複排除モジュール３３は、親チャンク９０１の識別子ＨABCに基づき、チャンク一覧テーブル３１２に当該識別子ＨABCに対応するデータ断片が登録されているかを判定する（ステップ４０８）。この例では、識別子ＨABCに対応するデータ断片は登録されていない。このため、親チャンク９０１に関するステップ４０８の判定結果は図９において矢印９１１で示されるよう未登録（Ｎｏ）となり、次の処理Ａ２に進む。
【０１２５】
Ａ２）
Ａ２-1）可変長重複排除モジュール３３は、上述の処理Ａ１で定めた親チャンク９０１を構成する子チャンクｃ0，ｃ1，ｃ2の列の先頭の子チャンクｃ0の長さだけ、文書１１１の末尾側にずらした位置（再設定された親チャンク開始位置）から（ステップ４０９）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、処理Ａ１で子チャンクｃ1，ｃ2を定めた部分についての再度の処理は必要ない。図９の例では、可変長重複排除モジュール３３は、文書１１１の先頭より１７文字目のところに切り出し点を定め、新たに子チャンクｃ3を定めたものとする。
【０１２６】
Ａ２-2）可変長重複排除モジュール３３は、連結ウィンドウサイズＷ以上となるところまで子チャンクｃ1，ｃ2，ｃ3を定めたところで、それらの子チャンクｃ1，ｃ2，ｃ3を連結して親チャンク９０２を定め、当該親チャンク９０２の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、連結する子チャンクｃ1（“ile”），ｃ2（“ na”），ｃ3（“me spe”）の識別子（ハッシュ値）ｃ1.hash＝ＨB，ｃ2.hash＝ＨC，ｃ3.hash＝ＨDから生成したハッシュ値ＨBCDを、親チャンク９０２の識別子（ハッシュ値）とする。
【０１２７】
Ａ２-3）可変長重複排除モジュール３３は、親チャンク９０２の識別子ＨBCDに基づき、チャンク一覧テーブル３１２に当該識別子ＨBCDに対応するデータ断片が登録されているかを判定する（ステップ４０８）。この例では、識別子ＨBCDに対応するデータ断片は登録されていない。このため、親チャンク９０２に関するステップ４０８の判定結果は図９において矢印９１２で示されるように未登録（Ｎｏ）となり、次の処理Ａ３に進む。
【０１２８】
Ａ３）
Ａ３-1）可変長重複排除モジュール３３は、上述の処理Ａ２で定めた親チャンク９０２を構成する子チャンクｃ1，ｃ2，ｃ3の列の先頭の子チャンクｃ1の長さだけ、文書１１１の末尾側にずらした位置から（ステップ４０９）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、処理Ａ２で子チャンクｃ2，ｃ3を定めた部分についての再度の処理は必要ない。図９の例では、可変長重複排除モジュール３３は、文書１１１の先頭より２０文字目のところに切り出し点を定め、新たに子チャンクｃ4を定めたものとする。
【０１２９】
Ａ３-2）可変長重複排除モジュール３３は、連結ウィンドウサイズＷ以上となるところまで子チャンクｃ2，ｃ3，ｃ4を定めたところで、それらの子チャンクｃ2，ｃ3，ｃ4を連結して親チャンク９０３を定め、当該親チャンク９０３の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、連結する子チャンクｃ2（“ na”），ｃ3（“me spe”）,ｃ4（“cif”）の識別子（ハッシュ値）ｃ2.hash＝ＨC，ｃ3.hash＝ＨD，ｃ4.hash＝ＨEから生成したハッシュ値ＨCDEを、親チャンク９０３の識別子（ハッシュ値）とする。
【０１３０】
Ａ３-3）可変長重複排除モジュール３３は、親チャンク９０３の識別子ＨCDEに基づき、チャンク一覧テーブル３１２に当該識別子ＨCDEに対応するデータ断片が登録されているかを判定する（ステップ４０８）。この例では、識別子ＨCDEに対応するデータ断片は登録されていない。このため、親チャンク９０３に関するステップ４０８の判定結果は図９において矢印９１３で示されるように未登録（Ｎｏ）となり、次の処理Ａ４に進む。
【０１３１】
Ａ４）
図９の例では、上述の処理Ａ３で定めた親チャンク９０３を構成する子チャンクｃ2，ｃ3，ｃ4の列の先頭の子チャンクｃ2の長さだけ、文書１１１の末尾側にずらした位置（つまり再設定された親チャンク開始位置）は、処理Ａ１で定められた親チャンク（つまり当初親チャンク）９０１の終端の位置を超えている。したがって、ステップ４０９で再設定された親チャンク開始オフセットの親チャンク９０１の開始オフセットからの「ずれ」は、連結ウィンドウサイズＷ以上となる（ステップ４１０のＹｅｓ）。この場合、可変長重複排除モジュール３３は、処理Ａ１で定められた親チャンク９０１の識別子ＨABC及びデータ（データ断片）“The file na”を、図９において矢印９０４で示すようにチャンク一覧テーブル３１２に登録する（ステップ５０２）。また図９では省略されているが、可変長重複排除モジュール３３は、文書１１１の文書名「文書＃１」及び親チャンク９０１の識別子ＨABCを文書構成テーブル３１１に登録する（ステップ５０３）。なお本実施形態では、ステップ５０２で登録される親チャンク９０１の識別子ＨABCは、ステップ５０１で改めて求められる。
【０１３２】
（Ｂ）格納処理ＳＸその２
上述の格納処理ＳＸ１に続いて実行される、文書１１１を格納するための格納処理ＳＸその２（以下、格納処理ＳＸ２と称する）について、図１０を参照して説明する。なお、図１０では、文書構成テーブル３１１は省略されている。
【０１３３】
Ｂ１）
Ｂ１-1）可変長重複排除モジュール３３は、格納処理ＳＸ１で定められた親チャンク９０１の終端の位置から（ステップ５０５）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、格納処理ＳＸ１で親チャンク９０１の終端の位置以降の子チャンクｃ3，ｃ4を定めた部分についての再度の処理は必要ない。図１０の例では、可変長重複排除モジュール３３は、文書１１１の先頭より２４文字目のところに切り出し点を定め、新たな子チャンクｃ5（“cif”）を定めたものとする。
【０１３４】
以降の処理は、格納処理ＳＸ１における、処理Ａ２-2〜Ａ２-3と同様であり、子チャンクｃ3，ｃ4，ｃ5を連結することにより親チャンク１００１が定められる。図１０の例では親チャンク１００１の識別子ＨDEFに対応するデータ断片は、チャンク一覧テーブル３１２に登録されていない。このため、親チャンク１００１に関するステップ４０８の判定結果は図１０において矢印１０１１で示されるように未登録（Ｎｏ）となり、次の処理Ｂ２に進む。
【０１３５】
Ｂ２）
処理Ｂ２は格納処理ＳＸ１における処理Ａ２と同様である。処理Ｂ２では、新たに子チャンクｃ6（“by path is ope”）が定められる。そして子チャンクｃ4，ｃ5，ｃ6を連結することにより親チャンク１００２が定められる。図１０の例では親チャンク１００２の識別子ＨEFGに対応するデータ断片は、チャンク一覧テーブル３１２に登録されていない。このため、親チャンク１００１に関するステップ４０８の判定結果は図１０において矢印１０１２で示されるように未登録（Ｎｏ）となり、次の処理Ｂ３に進む。
【０１３６】
Ｂ３）
処理Ｂ３は格納処理ＳＸ１における処理Ａ３と同様である。可変長重複排除モジュール３３は、上述の処理Ａ２で定めた親チャンク１００２を構成する子チャンクｃ4，ｃ5，ｃ6の列の先頭の子チャンクｃ4の長さだけ、文書１１１の末尾側にずらした位置から（ステップ４０９）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、処理Ｂ２で子チャンクｃ5，ｃ6を定めた部分についての再度の処理は必要ない。図１０の例では、子チャンクｃ4の長さだけずらした位置から連結ウィンドウサイズＷ以上となるところまでに、新たに定める子チャンクはない。そこで可変長重複排除モジュール３３は、処理Ａ２で定めた親チャンク１００２から先頭の子チャンクｃ4を除いた残りの子チャンクｃ5，ｃ6を連結して親チャンク１００３を定める。図１０の例では親チャンク１００３の識別子ＨFGに対応するデータ断片は、チャンク一覧テーブル３１２に登録されていない。このため、親チャンク１００３に関するステップ４０８の判定結果は図１０において矢印１０１３で示されるように未登録（Ｎｏ）となり、次の処理Ｂ４に進む。
【０１３７】
Ｂ４）
処理Ｂ４は格納処理ＳＸ１における処理Ａ４と同様である。つまり、図１０の例では、処理Ｂ３で定めた親チャンク１００３を構成する子チャンクｃ5，ｃ6の列の先頭の子チャンクｃ5の長さだけ、文書１１１の末尾側にずらした位置（つまり再設定された親チャンク開始位置）は、処理Ｂ１で定められた親チャンク（つまり当初親チャンク）１００１の終端の位置を超えている（ステップ４１０のＹｅｓ）。この場合、可変長重複排除モジュール３３は、処理Ｂ１で定められた親チャンク１００１の識別子ＨDEF及びデータ（データ断片）“me specified ”を、図１０において矢印１００４で示すようにチャンク一覧テーブル３１２に登録する（ステップ５０２）。また図９では省略されているが、可変長重複排除モジュール３３は、文書１１１の文書名「文書＃１」及び親チャンク１００１の識別子ＨDEFを文書構成テーブル３１１に登録する（ステップ５０３）。
【０１３８】
（Ｃ）格納処理ＳＸその３
上述の格納処理ＳＸ２に続いて実行される、文書１１１を格納するための格納処理その３（以下、格納処理ＳＸ３と称する）について、図１１を参照して説明する。なお、図１１では、文書構成テーブル３１１は省略されている。
【０１３９】
Ｃ１）
可変長重複排除モジュール３３は、格納処理ＳＸ２で定められた親チャンク１００１の終端の位置から（ステップ５０５）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。図１０の例では、可変長重複排除モジュール３３は、文書１１１の先頭より３８文字目のところに切り出し点を定め、子チャンクｃ6を定めたものとする。
【０１４０】
以降の処理は、格納処理ＳＸ１における、処理Ａ２-2〜Ａ２-3と同様である。但し、図１１の例では、子チャンクｃ6（“by path is ope”）のみで連結ウィンドウサイズＷ（Ｗ＝１０）以上となるため、当該子チャンクｃ6単体が親チャンク１１０１として定められる。可変長重複排除モジュール３３は、子チャンクｃ6（“by path is ope”）の識別子（ハッシュ値）ｃ6.hash＝ＨGより生成したハッシュ値ＨG’を親チャンク１１０１の識別子（ハッシュ値）とする。図１１の例では親チャンク１１０１の識別子ＨG’に対応するデータ断片は、チャンク一覧テーブル３１２に登録されていない。このため、親チャンク１１０１に関するステップ４０８の判定結果は図１１において矢印１１１１で示されるように未登録（Ｎｏ）となり、次の処理Ｃ２に進む。
【０１４１】
Ｃ２）
処理Ｃ２は、格納処理ＳＸ１における処理Ａ４と同様である。図１１の例では、上述の処理Ｃ１で定めた親チャンク１１０１の開始位置から当該親チャンク１１０１を構成する子チャンクｃ6の長さだけ、文書１１１の末尾側にずらした位置（つまり再設定された親チャンク開始位置）は、当該親チャンク（つまり当初親チャンク）１１０１の終端の位置を超えている（ステップ４１０のＹｅｓ）。この場合、可変長重複排除モジュール３３は、処理Ｃ１で定められた親チャンク１１０１の識別子ＨG’及びデータ（データ断片）“by path is ope”を、図１１において矢印１１０２で示すようにチャンク一覧テーブル３１２に登録する（ステップ５０２）。また図１１では省略されているが、可変長重複排除モジュール３３は、文書１１１の文書名「文書＃１」及び親チャンク１１０１の識別子ＨG’を文書構成テーブル３１１に登録する（ステップ５０３）。
【０１４２】
（Ｄ）格納処理ＳＸその４
上述の格納処理ＳＸ３に続いて実行される、文書１１１を格納するための格納処理ＳＸその４（以下、格納処理ＳＸ４と称する）について、図１２を参照して説明する。なお、図１２では、文書構成テーブル３１１は省略されている。
【０１４３】
Ｄ１）
Ｄ１-1）可変長重複排除モジュール３３は、格納処理ＳＸ３で定められた親チャンク１１０１の終端の位置から（ステップ５０５）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。図１２の例では、可変長重複排除モジュール３３は、文書１１１の先頭より４１，４７，５０文字目のところに切り出し点を定め、子チャンクｃ7，ｃ8，ｃ9を定めたものとする。
【０１４４】
以降の処理は、格納処理ＳＸ１における、処理Ａ２-2〜Ａ２-3と同様であり、子チャンクｃ7，ｃ8，ｃ9を連結することにより親チャンク１２０１が定められる。図１２の例では親チャンク１２０１の識別子ＨHIJに対応するデータ断片は、チャンク一覧テーブル３１２に登録されていない。このため、親チャンク１２０１に関するステップ４０８の判定結果は図１２において矢印１２１１で示されるように未登録（Ｎｏ）となり、次の処理Ｄ２に進む。
【０１４５】
Ｄ２）
処理Ｄ２は、格納処理ＳＸ１における処理Ａ２と同様であり、新たに子チャンクｃ10が定められる。そして子チャンクｃ8，ｃ9，ｃ10を連結することにより親チャンク１２０２が定められる。図１２の例では親チャンク１２０２の識別子ＨIJKに対応するデータ断片は、チャンク一覧テーブル３１２に登録されていない。このため、親チャンク１２０２に関するステップ４０８の判定結果は図１２において矢印１２１２で示されるように未登録（Ｎｏ）となり、次の処理Ｄ３に進む。
【０１４６】
Ｄ３）
処理Ｄ３は、格納処理ＳＸ１における処理Ａ３と同様である。可変長重複排除モジュール３３は、上述の処理Ｄ２で定めた親チャンク１２０２を構成する子チャンクｃ8，ｃ9，ｃ10の列の先頭の子チャンクｃ8の長さだけ、文書１１１の末尾側にずらした位置から（ステップ４０９）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、処理Ｄ２で子チャンクｃ9，ｃ10を定めた部分についての再度の処理は必要ない。図１２の例では、可変長重複排除モジュール３３は、文書１１１の先頭より５７文字目のところに切り出し点を定め、子チャンクｃ11を定めたものとする。可変長重複排除モジュール３３は、子チャンクｃ9，ｃ10，ｃ11を連結して親チャンク１２０３を定める。図１０の例では親チャンク１２０３の識別子ＨJKLに対応するデータ断片は、チャンク一覧テーブル３１２に登録されていない。このため、親チャンク１２０３に関するステップ４０８の判定結果は図１２において矢印１２１３で示されるように未登録（Ｎｏ）となり、次の処理Ｄ４に進む。
【０１４７】
Ｄ４）
処理Ｄ４は、格納処理ＳＸ１における処理Ａ４と同様である。つまり、図１２の例では、処理Ｄ３で定めた親チャンク１２０３を構成する子チャンクｃ9，ｃ10，ｃ11の列の先頭の子チャンクｃ9の長さだけ、文書１１１の末尾側にずらした位置は、処理Ｄ１で定められた親チャンク１２０１の終端の位置を超えている（ステップ４１０のＹｅｓ）。この場合、可変長重複排除モジュール３３は、処理Ｄ１で定められた親チャンク１２０１の識別子ＨHIJ及びデータ（データ断片）“ned for read”を、図１２において矢印１２０４で示すようにチャンク一覧テーブル３１２に登録する（ステップ５０２）。また図１２では省略されているが、可変長重複排除モジュール３３は、文書１１１の文書名「文書＃１」及び親チャンク１２０１の識別子ＨHIJを文書構成テーブル３１１に登録する（ステップ５０３）。
【０１４８】
（Ｅ）格納処理ＳＸその５
上述の格納処理ＳＸ４に続いて実行される、文書１１１を格納するための格納処理ＳＸその５（以下、格納処理ＳＸ５と称する）について、図１３を参照して説明する。この例では、説明の簡略化のために、便宜的に文字列“and”が文書１１１の末尾であるとしている。なお、図１３では、文書構成テーブル３１１は省略されている。
【０１４９】
Ｅ１）
可変長重複排除モジュール３３は、格納処理ＳＸ４で定められた親チャンク１２０１の終端の位置から（ステップ５０５）、子チャンクを順次定めていく（ステップ４０３〜４０６）。図１３の例では、子チャンクｃ10，ｃ11が定められ、その結果、切り出し点が文書１１１の末尾に達したものとする（ステップ４０４）。この場合、可変長重複排除モジュール３３は、切り出し点が、格納処理ＳＸ４で定められた親チャンク１２０１の終端の位置から連結ウィンドウサイズＷ（Ｗ＝１０）以上となるか否かに無関係に、子チャンクｃ10，ｃ11を連結することにより親チャンク１３０１を定める（ステップ４１４）。
【０１５０】
Ｅ２）
可変長重複排除モジュール３３は、処理Ｅ１で定められた親チャンク１３０１の識別子ＨKL及びデータ（データ断片）“ing and”を、図１３において矢印１３０２で示すようにチャンク一覧テーブル３１２に登録する（ステップ４１２）。また図１３では省略されているが、可変長重複排除モジュール３３は、文書１１１の文書名「文書＃１」及び親チャンク１３０１の識別子ＨKLを文書構成テーブル３１１に登録する（ステップ４１６）。これにより、文書１１１を格納するための格納処理ＳＸは完了する。
【０１５１】
上述の格納処理ＳＸ（つまり格納処理ＳＸ１乃至ＳＸ５）が完了した後における、文書構成テーブル３１１及びチャンク一覧テーブル３１２の状態（つまり文書１１１の登録状態）を、文書１１１及び当該文書１１１から切り出された親チャンクの列と共に図１４に示す。
【０１５２】
（３）格納処理ＳＹ
次に文書１１２を格納するための格納処理ＳＹについて、図１５乃至図２１を参照して説明する。図１５乃至図１９は文書１１１の格納後に行われる文書１１２の格納動作を文書構成テーブル３１１の状態と共に示す。図２０は文書１１２の格納後（つまり文書１１１，１１２の格納後）における、文書構成テーブル３１１及びチャンク一覧テーブル３１２の状態を、文書１１２及び当該文書１１２から切り出された親チャンクの列と共に示し、図２１は文書１１１，１１２の格納後における、文書構成テーブル３１１及びチャンク一覧テーブル３１２の状態を、当該文書１１１，１１２から切り出された親チャンクの列と共に示す。
【０１５３】
Ｆ）格納処理ＳＹその１
文書１１１を格納した後に、文書１１２を格納するための格納処理ＳＹその１（以下、格納処理ＳＹ１と称する）について、図１５を参照して説明する。なお、図１５では、文書構成テーブル３１１は省略されている。
【０１５４】
Ｆ-1）可変長重複排除モジュール３３は、文書１１２の先頭から、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。図１５の例では、可変長重複排除モジュール３３は、文書１１２の先頭より５，８，１１文字目のところに切り出し点を定め、子チャンクｃ0（“The f”），ｃ1（“ile”），ｃ2（“ na”）を定めたものとする。
【０１５５】
Ｆ-2）可変長重複排除モジュール３３は、連結ウィンドウサイズＷ以上となるところまで子チャンクｃ0（“The f”），ｃ1（“ile”），ｃ2（“ na”）を順次定めたところで、それらの子チャンクを連結して親チャンク１５０１を定め、当該親チャンク１５０１の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、連結する子チャンクｃ0（“The f”），ｃ1（“ile”），ｃ2（“ na”）の識別子（ハッシュ値）ｃ0.hash＝ＨA，ｃ1.hash＝ＨB，ｃ2.hash＝ＨCから生成したハッシュ値ＨABCを、親チャンク１５０１の識別子（ハッシュ値）とする。
【０１５６】
Ｆ-3）可変長重複排除モジュール３３は、親チャンク１５０１の識別子ＨABCに基づき、チャンク一覧テーブル３１２に当該識別子ＨABCに対応するデータ断片が登録されているかを判定する（ステップ４０８）。図１５に示すように、チャンク一覧テーブル３１２には、識別子ＨABCに対応するデータ断片が登録されている。このため、親チャンク１５０１に関するステップ４０８の判定結果は図１５において矢印１５１１で示されるようにＹｅｓ（登録済）となり、次の処理Ｇに進む。この場合、チャンク一覧テーブル３１２は図１５において矢印１５０２で示されるように、処理Ｆの前後で変わらない。なお、図１５では省略されているが、可変長重複排除モジュール３３は処理Ｇに進む前に、文書１１２の文書名「文書＃２」及び親チャンク１５０１の識別子ＨABCを文書構成テーブル３１１に登録する（ステップ５０３）。
【０１５７】
Ｇ）格納処理ＳＹその２
上述の格納処理ＳＹ１に続いて実行される、文書１１２を格納するための格納処理ＳＹその２（以下、格納処理ＳＹ２と称する）について、図１６を参照して説明する。なお、図１６では、文書構成テーブル３１１は省略されている。
【０１５８】
Ｇ１）
Ｇ１-1）可変長重複排除モジュール３３は、格納処理ＳＹ１で定められた親チャンク１５０１の終端の位置から（ステップ５０５）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。図１６の例では、可変長重複排除モジュール３３は、文書１１２の先頭より１３，２２文字目のところに切り出し点を定め、子チャンクｃ3，ｃ4を定めたものとする。
【０１５９】
Ｇ２-2）可変長重複排除モジュール３３は、連結ウィンドウサイズＷ以上となるところまで子チャンクｃ3，ｃ4を定めたところで、それらの子チャンクｃ3，ｃ4を連結して親チャンク１６０１を定め、当該親チャンク１６０１の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、連結する子チャンクｃ3（“me”），ｃ4（“ABCD spe”）の識別子（ハッシュ値）ｃ3.hash＝ＨX，ｃ4.hash＝ＨYから生成したハッシュ値ＨXYを、親チャンク１６０１の識別子（ハッシュ値）とする。
【０１６０】
Ｇ２-3）可変長重複排除モジュール３３は、親チャンク１６０１の識別子ＨXYに基づき、チャンク一覧テーブル３１２に当該識別子ＨXYに対応するデータ断片が登録されているかを判定する（ステップ４０８）。この例では、識別子ＨXYに対応するデータ断片は登録されていないため、次の処理Ｇ３に進む。
【０１６１】
Ｇ３）
Ｇ３-1）可変長重複排除モジュール３３は、上述の処理Ｇ２で定めた親チャンク１６０１を構成する子チャンクｃ3，ｃ4の列の先頭の子チャンクｃ3の長さだけ、文書１１２の末尾側にずらした位置から（ステップ４０９）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、処理Ｇ２で子チャンクｃ4を定めた部分についての再度の処理は必要ない。図１６の例では、可変長重複排除モジュール３３は、文書１１２の先頭より２５文字目のところに切り出し点を定め、新たに子チャンクｃ5を定めたものとする。
【０１６２】
Ｇ３-2）可変長重複排除モジュール３３は、連結ウィンドウサイズＷ以上となるところまで子チャンクｃ4，ｃ5を定めたところで、それらの子チャンクｃ4，ｃ5を連結して親チャンク１６０２を定め、当該親チャンク１６０２の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、連結する子チャンクｃ4（“ABCD spe”），ｃ5（“cif”）の識別子（ハッシュ値）ｃ4.hash＝ＨY，ｃ5.hash＝ＨEから生成したハッシュ値ＨYEを、親チャンク１６０２の識別子（ハッシュ値）とする。
【０１６３】
Ｇ３-3）可変長重複排除モジュール３３は、親チャンク１６０２の識別子ＨYEに基づき、チャンク一覧テーブル３１２に当該識別子ＨYEに対応するデータ断片が登録されているかを判定する（ステップ４０８）。この例では、識別子ＨYEに対応するデータ断片は登録されていないため、次の処理Ｇ４に進む。
【０１６４】
Ｇ４）
Ｇ４-1）図１６の例では、上述の処理Ｇ３で定めた親チャンク１６０２を構成する子チャンクｃ4，ｃ5の列の先頭の子チャンクｃ4の長さだけ、文書１１２の末尾側にずらした位置は、処理Ｇ１で定められた親チャンク（つまり当初親チャンク）１６０１の終端の位置を超えている。したがって、ステップ４０９で再設定された親チャンク開始オフセットの親チャンク１６０１の開始オフセットからの「ずれ」は、連結ウィンドウサイズＷ以上となる（ステップ４１０のＴｅｓ）。この場合、可変長重複排除モジュール３３は、処理Ｇ１で定められた親チャンク１６０１の識別子ＨXY及びデータ（データ断片）“me ABCD spe”を、図１６において矢印１６０３で示すようにチャンク一覧テーブル３１２に登録する（ステップ５０２）。また図１６では省略されているが、可変長重複排除モジュール３３は、文書１１２の文書名「文書＃２」及び親チャンク１６０１の識別子ＨXYを文書構成テーブル３１１に登録する（ステップ５０３）。
【０１６５】
Ｈ）格納処理ＳＹその３
上述の格納処理ＳＹ２に続いて実行される、文書１１２を格納するための格納処理ＳＹその３（以下、格納処理ＳＹ３と称する）について、図１７を参照して説明する。なお、図１７では、文書構成テーブル３１１は省略されている。
【０１６６】
Ｈ１）
Ｈ１-1）可変長重複排除モジュール３３は、格納処理ＳＹ２で定められた親チャンク１６０１の終端の位置から（ステップ５０５）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、格納処理ＳＹ２で親チャンク１６０１の終端の位置以降の子チャンクｃ5を定めた部分についての再度の処理は必要ない。図１６の例では、可変長重複排除モジュール３３は、文書１１２の先頭より２９，４３文字目のところに切り出し点を定め、新たな子チャンクｃ6（“ied”），ｃ7（“by path is ope”）を定めたものとする。
【０１６７】
Ｈ１-2）可変長重複排除モジュール３３は、連結ウィンドウサイズＷ以上となるところまで子チャンクｃ5，ｃ6，ｃ7を定めたところで、それらの子チャンクｃ5，ｃ6，ｃ7を連結して親チャンク１７０１を定め、当該親チャンク１７０１の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、連結する子チャンクｃ5（“cif”），ｃ6（“ied”）,ｃ7（“by path is ope”）の識別子（ハッシュ値）ｃ5.hash＝ＨE，ｃ6.hash＝ＨF，ｃ7.hash＝ＨGから生成したハッシュ値ＨEFGを、親チャンク１７０１の識別子（ハッシュ値）とする。
【０１６８】
Ｈ１-3）可変長重複排除モジュール３３は、親チャンク１７０１の識別子ＨEFGに基づき、チャンク一覧テーブル３１２に当該識別子ＨEFGに対応するデータ断片が登録されているかを判定する（ステップ４０８）。この例では、識別子ＨEFGに対応するデータ断片は登録されていない。このため、親チャンク１７０１に関するステップ４０８の判定結果は図１７において矢印１７１１で示されるように未登録（Ｎｏ）となり、次の処理Ｈ２に進む。
【０１６９】
Ｈ２）
Ｈ２-1）可変長重複排除モジュール３３は、上述の処理Ｈ１で定めた親チャンク１７０１０１を構成する子チャンクｃ5，ｃ6，ｃ7の列の先頭の子チャンクｃ5の長さだけ、文書１１２の末尾側にずらした位置から（ステップ４０９）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、処理Ｈ１で子チャンクｃ6，ｃ7を定めた部分についての再度の処理は必要ない。図１７の例では、子チャンクｃ5の長さだけずらした位置から連結ウィンドウサイズＷ以上となるところまでに、新たに定める子チャンクはない。
【０１７０】
Ｈ２-2）そこで可変長重複排除モジュール３３は、処理Ｈ１で定めた親チャンク１７０１から先頭の子チャンクｃ5を除いた残りの子チャンクｃ6，ｃ7を連結して親チャンク１７０２を定め、当該親チャンク１７０２の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、連結する子チャンクｃ6（“ied”）,ｃ7（“by path is ope”）の識別子（ハッシュ値）ｃ6.hash＝ＨF，ｃ7.hash＝ＨGから生成したハッシュ値ＨFGを、親チャンク１７０２の識別子（ハッシュ値）とする。
【０１７１】
Ｈ２-3）可変長重複排除モジュール３３は、親チャンク１７０２の識別子ＨFGに基づき、チャンク一覧テーブル３１２に当該識別子ＨFGに対応するデータ断片が登録されているかを判定する（ステップ４０８）。この例では、識別子ＨFGに対応するデータ断片は登録されていない。このため、親チャンク１７０２に関するステップ４０８の判定結果は図１７において矢印１７１２で示されるように未登録（Ｎｏ）となり、次の処理Ｈ３に進む。
【０１７２】
Ｈ３）
Ｈ３-1）可変長重複排除モジュール３３は、上述の処理Ｈ２で定めた親チャンク１７０１０２を構成する子チャンクｃ6，ｃ7の列の先頭の子チャンクｃ６の長さだけ、文書１１２の末尾側にずらした位置から（ステップ４０９）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。このとき、処理Ｈ２で子チャンクｃ7を定めた部分についての再度の処理は必要ない。図１７の例では、子チャンクｃ6の長さだけずらした位置から連結ウィンドウサイズＷ以上となるところまでに、新たに定める子チャンクはない。また子チャンクｃ7のみで、連結ウィンドウサイズＷ（Ｗ＝１０）以上となる。
【０１７３】
Ｈ３-2）そこで可変長重複排除モジュール３３は、処理Ｈ２で定めた親チャンク１７０２から先頭の子チャンクｃ6を除いた残りの子チャンクｃ7単体を親チャンク１７０３として定め、当該親チャンク１７０３の識別子（ハッシュ値）を生成する（ステップ４０７）。この例では可変長重複排除モジュール３３は、子チャンクｃ7（“by path is ope”）の識別子（ハッシュ値）ｃ7.hash＝ＨGから生成したハッシュ値ＨG’を、親チャンク１７０３の識別子（ハッシュ値）とする。
【０１７４】
Ｈ３-3）可変長重複排除モジュール３３は、親チャンク１７０３の識別子ＨG’に基づき、チャンク一覧テーブル３１２に当該識別子ＨG’に対応するデータ断片が登録されているかを判定する（ステップ４０８）。図１７に示すように、チャンク一覧テーブル３１２には、識別子ＨG’に対応するデータ断片が登録されている。このため、親チャンク１７０３に関するステップ４０８の判定結果は図１７において矢印１７１３で示されるようにＹｅｓ（登録済）となり、次の処理Ｈ４に進む。なお、図１７では省略されているが、可変長重複排除モジュール３３は処理Ｈ４に進む前に、文書１１２の文書名「文書＃２」及び親チャンク１５０１の識別子ＨG’を文書構成テーブル３１１に登録する（ステップ４１２）。
【０１７５】
Ｈ４）
Ｈ４-1）可変長重複排除モジュール３３は、前述の格納処理ＳＹ２で定めた親チャンク１６０１（つまり、識別子ＨXYにより識別されるデータ断片）と、上記処理Ｈ３で定めた親チャンク１７０３（つまり、識別子ＨG’により識別されるデータ断片）との間に子チャンクまたは子チャンクの列があるならば（ステップ４１３のＮｏ）、その子チャンクまたは子チャンクの列を親チャンクと定めて、当該親チャンクの識別子（ハッシュ値）を生成する（ステップ５０１）。図１７の例では、親チャンク１６０１と親チャンク１７０３との間に、子チャンクｃ5，ｃ6が存在する。そこで可変長重複排除モジュール３３は、子チャンクｃ5，ｃ6を連結して親チャンク１７０４を定め、当該親チャンク１７０４の識別子（ハッシュ値）を生成する（ステップ５０１）。即ち可変長重複排除モジュール３３は、連結する子チャンクｃ5（“cif”），ｃ6（“ied ”）の識別子（ハッシュ値）ｃ5.hash＝ＨE，ｃ6.hash＝ＨFから生成したハッシュ値ＨEFを、親チャンク１７０４の識別子（ハッシュ値）とする。
【０１７６】
Ｈ４-2）可変長重複排除モジュール３３は、親チャンク１７０４の識別子ＨEF及びデータ（データ断片）“cified ”を、図１７において矢印１７０５で示すようにチャンク一覧テーブル３１２に登録する（ステップ５０２）。また図１７では省略されているが、可変長重複排除モジュール３３は、文書１１２の文書名「文書＃２」及び親チャンク１７０４の識別子ＨEFを文書構成テーブル３１１に登録する（ステップ５０３）。
【０１７７】
Ｉ）格納処理ＳＹその４
上述の格納処理ＳＹ３に続いて実行される、文書１１２を格納するための格納処理ＳＹその４（以下、格納処理ＳＹ４と称する）について、図１８を参照して説明する。なお、図１８では、文書構成テーブル３１１は省略されている。
【０１７８】
Ｉ-1）可変長重複排除モジュール３３は、格納処理ＳＹ３で登録済みであると判定された親チャンク１７０３の終端の位置から（ステップ５０５）、連結ウィンドウサイズＷ（Ｗ＝１０）以上となるところまで、子チャンクを順次定めていく（ステップ４０３〜４０６）。図１８の例では、可変長重複排除モジュール３３は、文書１１２の先頭より４６，５２，５６文字目のところに切り出し点を定め、新たな子チャンクｃ8（“ned”），ｃ9（“ for r”），ｃ10（“ead”）を定めたものとする。
【０１７９】
以降の処理は格納処理ＳＹ１における、処理Ｆ-2〜Ｆ-3と同様であり、子チャンクｃ8，ｃ9，ｃ10を連結することにより親チャンク１８０１が定められる。図１８の例では親チャンク１８０１の識別子ＨHIJに対応するデータ断片は、チャンク一覧テーブル３１２に登録されている（ステップ４０８のＹｅｓ）。このため、親チャンク１８０１に関するステップ４０８の判定結果は図１８において矢印１８１１で示されるようにＹｅｓ（登録済）となり、次の処理Ｊに進む。この場合、チャンク一覧テーブル３１２は図１８において矢印１８０２で示されるように、処理Ｉの前後で変わらない。なお、図１８では省略されているが、可変長重複排除モジュール３３は処理Ｊに進む前に、文書１１２の文書名「文書＃２」及び親チャンク１８０１の識別子ＨHIJを文書構成テーブル３１１に登録する（ステップ５０３）。
【０１８０】
Ｊ）格納処理ＳＹその５
上述の格納処理ＳＹ４に続いて実行される、文書１１２を格納するための格納処理ＳＹその５（以下、格納処理ＳＹ５と称する）について、図１９を参照して説明する。なお、図１９では、文書構成テーブル３１１は省略されている。
【０１８１】
Ｊ１）
Ｊ１-1）可変長重複排除モジュール３３は、格納処理ＳＹ４で定められた親チャンク１８０１の終端の位置から（ステップ５０５）、子チャンクを順次定めていく（ステップ４０３〜４０６）。図１９の例では、子チャンクｃ11，ｃ12が定められ、その結果、切り出し点が文書１１１の末尾に達したものとする（ステップ４０４）。この場合、可変長重複排除モジュール３３は、切り出し点が、格納処理ＳＹ４で定められた親チャンク１８０１の終端の位置から連結ウィンドウサイズＷ（Ｗ＝１０）以上となるか否かに無関係に、子チャンクｃ11（“in”），ｃ12（“g and”）を連結することにより親チャンク１９０１を定める（ステップ４１４）。
【０１８２】
Ｊ１-2）親チャンク１９０１の識別子（ハッシュ値）ＨKLに対応するデータ断片はチャンク一覧テーブル３１２に登録されている（ステップ４１５のＹｅｓ）。このため、親チャンク１９０１に関するステップ４１５の判定結果は図１９において矢印１９１１で示されるようにＹｅｓ（登録済）となる。この場合、ステップ４１４で定められた親チャンク１９０１の識別子ＨKL及びデータ（データ断片）“ing and”をチャンク一覧テーブル３１２に登録する処理（ステップ４１６）は行われない。このためチャンク一覧テーブル３１２は図１９において矢印１９０２で示されるように、処理Ｊの前後で変わらない。なお、図１９では省略されているが、可変長重複排除モジュール３３は、文書１１２の文書名「文書＃２」及び親チャンク１５０１の識別子ＨKLを文書構成テーブル３１１に登録する（ステップ５０３）。これにより、文書１１２を格納するための格納処理ＳＹは完了する。
【０１８３】
格納処理ＳＸに続いて上述の格納処理ＳＹ（つまり格納処理ＳＹ１乃至ＳＹ５）が完了した後、つまり文書１１１，１１２の格納後における、文書構成テーブル３１１及びチャンク一覧テーブル３１２の状態を、文書１１２及び当該文書１１２から切り出された親チャンクの列と共に図２０に示す。
【０１８４】
同様に、文書１１１，１１２の格納後における、文書構成テーブル３１１及びチャンク一覧テーブル３１２の状態を、文書１１１，１１２から切り出された親チャンクの列と共に図２１に示す。文書１１１の格納後に文書１１２が格納される本実施形態では、当該文書１１２を格納するための格納処理ＸＹにより、重複データを排除しながら当該文書１１２を登録されることが、図２１からわかる。
【０１８５】
＜文書取得処理＞
次に、文書格納装置１０における文書取得処理について、図２２のフローチャートを参照して説明する。  
まず、クライアント装置２０から文書格納装置１０にネットワーク３０を介して文書取得指示が送られたものとする。この文書取得指示は、文書格納装置１０から取得されるべき文書を指定する文書名を含んでいる。
【０１８６】
文書格納装置１０に送られたクライアント装置２０からの文書取得指示は、当該文書格納装置１０の命令受け付けモジュール３２で受け付けられる。命令受け付けモジュール３２内の文書取得部３２０は、この文書取得指示が命令受け付けモジュール３２で受け付けられると、当該文書取得指示で指定される文書名と対応付けて文書構成テーブル３１１に登録されている全てのチャンク（親チャンク）群の識別子を取得する（ステップ２２０１）。取得されたチャンク群の識別子の並び順は、前述したように、対応する文書におけるチャンク群の並びに一致する。
【０１８７】
文書取得部３２０は、文書構成テーブル３１１から識別子の群を取得すると、当該識別子の群とそれぞれ対応付けてチャンク一覧テーブル３１２に登録されているチャンク（データ断片）の群を取得する（ステップ２２０２）。
【０１８８】
文書取得部３２０は、チャンク一覧テーブル３１２から取得したチャンクの群に基づき、当該チャンクの群の並び順が、先に取得した当該チャンクの群の識別子の並び順に一致するように、クライアント装置２０からの文書取得指示で指定された文書名の文書のデータを再構成する（ステップ２２０３）。
【０１８９】
命令受け付けモジュール３２は、文書取得部３２０によって再構成された文書データを、クライアント装置２０からの文書取得指示に対する応答として当該クライアント装置２０に返す（ステップ２２０４）。
【０１９０】
ところで、クライアント装置２０がユーザからの要求により、文書格納装置１０から文書（文書データ）上のデータ断片を取得したい場合がある。クライアント装置２０が文書格納装置１０から文書上のデータ断片を取得するための方法として、当該文書の文書名に加えて、当該データ断片の当該文書上の位置及び当該データ断片の長さを指定する方法が知られている。文書格納装置１０が、このような方法に適応するためには、クライアント装置２０によって指定された文書名の文書の文書データを上述のように再構成した上で、当該文書データからクライアント装置２０によって指定された位置・長さのデータ断片を取得する必要がある。
【０１９１】
そこで、例えば指定の文書名に対応付けてチャンク（親チャンク）の識別子を文書構成テーブル３１１に登録する際に、当該チャンクの対応する文書データ上での位置・長さを示す情報を当該チャンクの識別子に付加するとよい。このようにすると、この情報を参照して、この情報が付加されている識別子に対応付けてチャンク一覧テーブル３１２に保持されているチャンクを特定するだけで、指定の文書上の指定の位置・長さのデータ断片を取得することができる。
【０１９２】
＜本実施形態のまとめ＞
このように本実施形態では、文書格納装置１０が、任意の文書データを、重複検出を行いながら、可変長のチャンク（親チャンクもしくは登録済み親チャンク、または第１のデータ断片）に分割するデータ分割装置として機能する。
【０１９３】
本実施形態によれば、子チャンク（第２のデータ断片）の長さを重複検出のオフセット間隔としながら、当該子チャンクの長さよりも長くなる可能性が高く、且つ登録の対象として用いられる可能性の高い親チャンク（第３のデータ断片）の長さで重複検出を行う構成とすることにより、従来技術と比較してより単純・高速な手法で、登録済みとなる親チャンク（第１のデータ断片）の数（つまり分割数）を少なくしながらも重複排除率を高く維持した、重複検出を行うことができる。
【０１９４】
また本実施形態によれば、分割の対象となるデータの一端から順に、子チャンク（第２のデータ断片）を決定しながら、それがある条件を満たしたときに、決定されている複数の子チャンクを連結して（１つの子チャンクが決定されているときは連結しないで）親チャンク（第３のデータ断片）を決定し、当該決定した親チャンクの重複の有無を検出することにより、分割の対象となるデータがストリーム状態に入力されるときに、高速に重複検出を行うことができる。
【０１９５】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。例えば、上記実施形態では、文書データを、当該文書データの先頭から当該文書データの末尾の方向に分割している。しかし、文書データを、当該文書データの末尾から当該文書データの先頭の方向に分割しても構わない。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【符号の説明】
【０１９６】
１０…文書格納装置、２０…クライアント装置、３０…ネットワーク、３１…文書格納部、３２…命令受け付けモジュール（入力手段）、３３…可変長重複排除モジュール、３４…作業用メモリ、３１１…文書構成テーブル、３１２…チャンク一覧テーブル、３２０…文書取得部、３３１…子チャンク決定部（第２のデータ断片決定手段）、３３２…親チャンク決定部（第３のデータ断片決定手段）、３３３…識別子生成部、３３４…重複検出部、３３５…親チャンク登録部（第１のデータ断片決定手段）、３３６…制御部、３４１…文書バッファ、３４２…レジスタ部。
【図１】
2011076421.tif 000003
【図２】
2011076421.tif 000004
【図３】
2011076421.tif 000005
【図４】
2011076421.tif 000006
【図５】
2011076421.tif 000007
【図６】
2011076421.tif 000008
【図７】
2011076421.tif 000009
【図８】
2011076421.tif 000010
【図９】
2011076421.tif 000011
【図１０】
2011076421.tif 000012
【図１１】
2011076421.tif 000013
【図１２】
2011076421.tif 000014
【図１３】
2011076421.tif 000015
【図１４】
2011076421.tif 000016
【図１５】
2011076421.tif 000017
【図１６】
2011076421.tif 000018
【図１７】
2011076421.tif 000019
【図１８】
2011076421.tif 000020
【図１９】
2011076421.tif 000021
【図２０】
2011076421.tif 000022
【図２１】
2011076421.tif 000023
【図２２】
2011076421.tif 000024
【図２３】
2011076421.tif 000025
【図２４】
2011076421.tif 000026
【図２５】
2011076421.tif 000027
【図２６】
2011076421.tif 000028
【図２７】
2011076421.tif 000029
【図２８】
2011076421.tif 000030