説明

データ分割方法及び装置

【課題】分割データ断片数を抑えながら、高い重複排除率を単純な仕組みで実現する。
【解決手段】子チャンク決定部は、入力された任意のデータのうち、未だ第1のデータ断片として決定されていない残りのデータ部分から第2のデータ断片を順次決定する(ステップ403)。親チャンク決定部は、第1の条件を満たす状態に達するまでに決定された第2のデータ断片の組み合わせを1つの第3のデータ断片として決定する(ステップ407)。決定された第3のデータ断片の重複が検出されなかった場合(ステップ408)、制御部は、これらの処理の繰り返しを、第2の条件を満足する状態で重複が検出されるまで制御し、それでも重複が検出されなかった場合、親チャンク決定部は、その間に決定された第2のデータ断片のうちの第1の条件を満足する第2のデータ断片の組み合わせを、第1のデータ断片として決定する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、データ間で重複するデータ断片を検出しながら、任意のデータを可変長のデータ断片に分割するのに好適な、データ分割方法及び装置に関する。
【背景技術】
【0002】
昨今、官公庁・企業・個人のデータを管理する基盤は急速に肥大化・複雑化しており、その基盤の主要な構成要素である記憶装置に格納するデータも増大の一途をたどっている。このようなデータの保管・管理コストを削減するための1つの技術として、重複排除技術が注目されている。
【0003】
重複排除技術とは、任意のデータ(以下、対象データと称する)を記憶装置に格納する際に、既に対象データと同じ内容のデータが当該記憶装置に格納されているかを検出、つまりデータの重複を検出し、既に格納されていれば当該対象データを例えばリンクで置き換えることにより重複データを1つにまとめる(排除する)技術をいう。この重複排除技術によれば、データの記憶に必要な記憶容量を少なくすることができる。
【0004】
同じデータが記憶装置に格納されているか否かを高速に検出するためには、データの識別子を利用することが多い。即ち重複排除技術では一般に、データの重複を検出するのに、対象データ自身を既に記憶装置に格納されている全データと比較する手法ではなくて、対象データの識別子を求めてこれを既存の格納済みのデータの識別子の群と比較する手法が適用される。
【0005】
データの重複は、予め定められた単位で検出される。この単位として、ファイルのようなデータ(コンテンツ)の一塊を用いることにより、データの重複を検出する第1の手法が古くから知られている。また最近では、上記の単位に、ファイルのようなデータを分割することによって得られるデータ断片(以下、チャンクと称する)を用いることにより、データの重複を検出する第2の手法が提案されている。第1の手法では、データの一部が異なるときにもデータ全体が異なるものであるとして処理される。これに対して第2の手法では、上記一部だけを処理すればよいという利点がある。
【0006】
第2の手法を適用する重複排除技術では、一般に、以下のような手順を繰り返すことで重複排除が行われる。
手順1)対象データからチャンクを切り出す。
手順2)切り出されたチャンクの識別子を求める。
手順3)切り出されたチャンクの識別子を既に記憶装置に格納済みのチャンクの群のそれぞれの識別子と比較する。もし、切り出されたチャンクと識別子が同一のチャンクがあれば、切り出されたチャンクと同一内容のチャンクであるとして、重複を排除する形式で、例えばリンクに置き換えることにより、切り出されたチャンクを記憶装置に格納する。
【0007】
第2の手法を適用する重複排除技術では、手順1で実行されるチャンクの切り出しの方法、つまりどの長さでチャンクを切り出すかが重要である。第2の手法を適用する重複排除技術は、対象データからチャンクを切り出すときに当該チャンクの切り出し点を求める方法によって、大きく次の2種類に分類される。
【0008】
A)固定長重複排除方法
固定長重複排除方法とは、ある一定の長さでチャンクの切り出し点を定め、チャンク毎に重複検出・排除を行う方法である。
B)可変長重複排除方法
可変長重複排除方法とは、対象データの内容に応じてデータ分割長を動的に調節して切り出し点を定め、チャンク毎に重複検出・排除を行う方法である。
【0009】
以下、固定長重複排除方法及び可変長重複排除方法の違いについて、図23を参照して説明する。
図23は、文書名が「文書#1」の文書111及び文書名が「文書#2」の文書112の2つの文書についてそれぞれ、チャンク切り出し点を固定長重複排除方法と可変長重複排除方法で求めた様子を示す。文書112は、文書111の一部を編集することによって、例えば文書111における文字列“name”及び“specified”の間に文字列“ABCD”を挿入することによって、生成された文書である。
【0010】
固定長重複排除方法によれば、文書111及び文書112に対し、図23において矢印113で示されるように、例えば10文字の固定長を単位に、チャンクの切り出し点が定められる。一方、可変長重複排除方法によれば、文書111及び文書112に対し、図23において矢印114で示されるように、データの中身に応じて、チャンクの切り出し点が定められる。この技術の詳細については後述する。
【0011】
ここでは以下の点に注目されたい。
固定長重複排除方法では、文書111と文書112との間で、文字列の挿入が発生した箇所から後ろ側、つまり文書の末尾側のチャンク全てが異なっている。
これに対して可変長重複排除方法では、文書111と文書112との間で、文字列の挿入が発生した箇所周辺のチャンクが異なっているのみで、それより後ろ側のチャンクは全て一致している。
【0012】
このように、固定長重複排除方法に比較して、可変長重複排除方法の方が、あるデータ間で、データの一部挿入/削除/変更が発生したときでも、その影響を極力抑えながら重複排除を実現できる。
【0013】
上述のような可変長でのチャンク切り出し点の求め方と、それを利用した重複排除を行う方法は種々知られている。ここでは、特許文献1に記載されているような方法について、例を挙げて説明する。
【0014】
特許文献1に記載の方法では、次の手順でチャンクの切り出し点が求められる。
1)データ上のある連続する固定長の区間(以下、ウィンドウと称する)のデータ断片(バイト列)を取り出して、当該データ断片の識別子を求める。ここでは、ウィンドウの長さが2バイトであるとする。このデータ断片がチャンクとしてのデータ断片とは異なる点に注意すべきである。
【0015】
2)求めた識別子の一部(例えば下位2ビット)が、予め定めた値(例えば0x01)と一致したときに、そこをチャンクの切り出し点とする。
【0016】
図24は、2バイト長のウィンドウW内の文字列(データ断片)の識別子を求めて、その識別子の下位2ビットが、予め定めた値0x01と一致するときにそこをチャンクの切り出し点として決定する場合の動作例を示す。図24の例では、文書データ“The fil…”の先頭より2バイト(2文字)長の区間をウィンドウWとして初期設定し、以後当該ウィンドウWを1バイトずつシフトさせながら、当該ウィンドウW内の文字列の識別子を、例えば当該文字列のハッシュ値を計算することによって求めている。このハッシュ値の計算に用いられるハッシュ関数を、hα( )で表す。ウィンドウW内の文字列が“Th”であるものとすると、その識別子は、hα(“Th”)で表される。
【0017】
ウィンドウW内の文字列“Th”の識別子hα(“Th”)が0x1Aであったとすると、当該識別子0x1Aの下位2ビットは0x02である。この識別子0x1Aの下位2ビットは、当該識別子0x1Aとマスクデータ0x03との論理積演算0x1A&0x03によって求められる。識別子0x1Aの下位2ビット0x02は、予め定められた値0x01ではない。このため、このときのウィンドウWの終端を、チャンクの切り出し点とはしない。
【0018】
ウィンドウW内の文字列“ f”の識別子hα(“ f”)が0x99であったとすると、当該識別子0x99の下位2ビットは0x01である。これは予め定められた値0x01と同じなので、このときのウィンドウWの終端をチャンクの切り出し点とする。これにより、文字列“The f”が切り出される。
【0019】
この例では、チャンクの切り出し点を決定する条件とし、識別子の下位2ビットと予め定められた値との一致を用いているが、このビット数で、平均チャンクサイズが決定されることに注意されたい。例えば2ビットの場合、平均チャンクサイズは22=4バイトとなる。
【0020】
以上のようにしてチャンクを切り出した上で、図25に示すように、このチャンク自体の識別子を、例えば当該チャンクのハッシュ値を計算することによって求めている。切り出されたチャンクをCAで表し、ハッシュ値の計算に用いられるハッシュ関数を、hβ( )で表す。チャンクCAを構成する文字列が“The f”である図25の例では、チャンクCAの識別子は、hβ(“The f”)=hβ(CA)で表される。以下の説明では、チャンクCAの識別子をHAで表す。
【0021】
次に、前記手順3と同様に、求めたチャンクの識別子を、既に記憶装置に格納されているチャンクの群のそれぞれの識別子と比較する。もし、求めたチャンクと識別子が同一のチャンクがあれば、求めたチャンクと同一内容のチャンクが既に記憶装置に格納されているものとして処理する。これに対し、求めたチャンクと識別子が同一のチャンクがなければ、当該求めたチャンクを未だ記憶装置に格納されていない新しいチャンクとして処理する。
上述の処理を、チャンクを求める毎に繰り返すことで、重複検出・排除を行う。
【0022】
特許文献1に記載されたチャンクの切り出し方法によれば、例えば図26に示す文書名が「文書#1」の文書111(データ)は、識別子HxがHA乃至HIの9つのチャンクを含むチャンクCxの群に分割される。文書名が「文書#1」の文書111から切り出されるチャンクCxの群のそれぞれの識別子Hxは、図26に示されるように、当該文書名「文書#1」に対応付けて文書構成テーブル251に登録される。また、識別子HA乃至HIを含む識別子Hxの群のそれぞれと、その識別子Hxに対応するチャンクCxとの一覧は、図26に示されるようにチャンク一覧テーブル252に登録される。
【0023】
一般的には、チャンク切り出しに当たり、チャンクの長さに最小長さ及び最大長さの制限を設けることが多い。このような場合、最大長さに達した位置を、強制的にチャンクの切り出し点と定める。
【0024】
また、特許文献2には、チャンクの切り出し点を求めるためウィンドウをシフトしながら識別子を求める方法に関して、RollingHashingの手法を適用することが記載されている。
【0025】
特許文献1,2に記載されているような可変長重複排除技術には、次のような2つの課題がある。
<第1の課題>
重複排除率の向上のためには、チャンクの平均長を短くする必要がある。しかし、チャンクの平均長を短くすると、チャンクの個数が増える。このため、チャンク一覧テーブルに登録される識別子(より詳細には識別子とチャンクとの対)の数が増える。一般的にチャンク一覧テーブルはハッシュテーブルで実装されることが多いが、識別子の数が増えるとハッシュテーブルのサイズも大きくなってしまう。このため、チャンク一覧テーブルを、アクセス速度が高速なメモリ上に全て展開することが難しくなり、例えばメモリと比較して大容量だが低速なディスク装置上に展開せざるを得なくなる。このことは、性能を大幅に悪化させる要因となる。
【0026】
<第2の課題>
逆に、チャンク一覧テーブルを全てメモリ上に展開するためには、当該メモリ上に展開可能なサイズにまでチャンク一覧テーブルを小さくする必要がある。そのためには、チャンク一覧テーブルに登録される識別子の数を少なく抑えなければならい。このことはつまり、チャンクの平均長を長くするということであり、重複排除率の低下を招くことになる。
【0027】
以下に例を用いて説明する。図27は上記第1の課題の例を、図28は上記第2の課題の例を示している。図27の例は、図28と比較してチャンクの平均長を短くすることで、図28と比較して、重複排除率の向上を実現している。チャンク一覧テーブル252に識別子に対応付けて登録されるチャンクの群のサイズを合計することで、重複排除率が高いことがわかる。しかし、図28と比較して識別子数が多い。
【0028】
このように、重複排除率とチャンクの個数(チャンクの平均長)はトレードオフの関係にあることがわかる。
【0029】
最近、上述のような課題を解決するために、様々な手法が検討・採用されている。例えば特許文献3は、切り出されたチャンクを2つ以上連結し(ここでは便宜上、連結されたチャンク群を「連結チャンク」と称する)、少なくとも連結チャンクの単位で重複検出を行うことで、チャンクの個数を減らしつつ高い重複排除率を維持する手法を開示している。
【0030】
特許文献3に開示されている手法の特徴は、チャンクの連結/非連結を動的に切り替えながら、連結チャンクと連結チャンクとの間に、非連結チャンクの群からなる「緩衝領域」を設ける点にある。この手法では、以下の第1及び第2の条件に基づいて、チャンクの連結/非連結が動的に切り替えられる。
【0031】
第1の条件とは、「連結対象として仮に定められたチャンクの群が、既にシステム内に登録されている連結チャンクと重複するか否か」である。
第2の条件とは、「連結対象として定められたチャンクの群の前後に連なるチャンクの群が、連結チャンクであるか否か」と、「上記連なるチャンクの群が、既にシステム内に登録されている連結チャンクと重複しているか否か」とである。
【先行技術文献】
【特許文献】
【0032】
【特許文献1】米国特許第5,990,810号明細書
【特許文献2】米国特許第6,810,398号明細書
【特許文献3】米国特許出願公開第2008/0133561号明細書
【発明の概要】
【発明が解決しようとする課題】
【0033】
しかし、上記特許文献3に開示されているような手法では、連結/非連結を動的に切り替える条件が複雑である。条件が複雑であることは、実装上好ましくない。また、連結チャンクと連結チャンクの間に設けられる「緩衝領域」では細かなチャンクが多数生成される。このことは、文書構成テーブル及びチャンク一覧テーブルのエントリ数の増加を招き、結果的に性能劣化を引き起こす。
【0034】
また、上記特許文献3に開示されているような手法では、常に複数個の非連結チャンクの群が連結されて、この連結の単位で重複検出・排除が行われる。このことは、可変長でのチャンク切り出しで切り出されたチャンクの長さが長いとき、更に大きな連結チャンクの単位で、重複検出・排除が行われることになって、重複排除率が低下する要因となることを意味する。
【0035】
本発明は上記事情を考慮してなされたものでその目的は、分割されるデータ断片数を抑えながらも高い重複排除率を、単純な仕組みで実現できるデータ分割方法及び装置を提供することにある。
【課題を解決するための手段】
【0036】
本発明の1つの観点によれば、入力手段、第1のデータ断片決定手段、第2のデータ断片決定手段、第3のデータ断片決定手段、重複検出手段及び制御手段を含む装置において、任意のデータを、重複検出を行いながら、複数の、任意の長さの第1のデータ断片に分割するためのデータ分割方法が提供される。このデータ分割方法は、前記任意のデータを前記入力手段が入力する入力ステップと、前記入力された任意のデータのうち、未だ前記第1のデータ断片として決定されていない残りのデータ部分から、前記第2のデータ断片決定手段が任意の長さまたは予め定められた長さの第2のデータ断片を順次決定する第1の決定ステップと、予め定められた第1の条件を満足する状態に達するまでに、前記第1のステップにおいて決定された1つの第2のデータ断片それ自体または複数の第2のデータ断片の組み合わせを、前記第3の断片決定手段が1つの第3のデータ断片として決定する第2の決定ステップと、前記決定された第3のデータ断片の重複の有無を、当該決定された第3のデータ断片に一致するビット列の第1のデータ断片が既に決定されているかによって、前記重複検出手段が検出する重複検出ステップと、前記重複が検出された場合、前記決定された第3のデータ断片を前記第1のデータ断片決定手段が前記第1のデータ断片として決定する第3の決定ステップと、前記重複が検出されなかった場合、前記第1及び第2の決定ステップを再実行させることにより、前記第1の条件を満足する状態に達するまでに新たな1つの第2のデータ断片または新たな複数の第2のデータ断片を決定させると共に、当該新たな1つの第2のデータ断片それ自体、当該新たな複数の第2のデータ断片の組み合わせ、前記重複が検出されなかった第3のデータ断片の一部と当該新たな1つの第2のデータ断片との組み合わせ、または前記重複が検出されなかった第3のデータ断片の一部と当該新たな複数の第2のデータ断片との組み合わせを、前記第3のデータ断片決定手段により1つの新たな第3のデータ断片として決定させるための制御を、予め定められた第2の条件を満足する状態で前記重複が検出されるまで前記制御手段が繰り返す第1の制御ステップと、前記第2の条件を満足する状態で前記第1の制御ステップが繰り返されても前記重複が検出されなかった場合、その間に決定された前記第2のデータ断片のうちの、前記第1の条件を満足する、1つの第2のデータ断片それ自体、または複数の第2のデータ断片の組み合わせを、前記第1のデータ断片決定手段が新たな第1のデータ断片として決定する第4の決定ステップと、前記入力された任意のデータが全て前記第1のデータ断片に分割されるまで、前記制御手段が前記第1の制御ステップを繰り返すための第2の制御ステップとを具備することを特徴とする。
【発明の効果】
【0037】
本発明によれば、任意のデータを、重複検出を行いながら、複数の、任意の長さの第1のデータ断片に分割するためのデータ分割方法及び装置において、第2のデータ断片の長さを重複検出のオフセット間隔としながら、当該第2のデータ断片の長さよりも長くなる可能性が高く、且つ第1のデータ断片として用いられる可能性の高い第3のデータ断片の長さで重複検出を行う構成とすることにより、従来技術と比較してより単純・高速な手法で、第1のデータ断片の数(つまりチャンク数または分割数)を少なくしながらも重複排除率を高く維持した、重複検出を行うことができる。
【図面の簡単な説明】
【0038】
【図1】本発明の一実施形態に係るストレージシステムの構成を示すブロック図。
【図2】図1に示される文書格納装置のハードウェア構成を示すブロック図。
【図3】図1に示される文書格納装置の主として機能構成を示すブロック図。
【図4】同実施形態で適用される文書格納処理の手順を示すフローチャート。
【図5】同実施形態で適用される文書格納処理の手順を示すフローチャート。
【図6】同実施形態で適用される親チャンクと子チャンクの群との関係を説明するための図。
【図7】子チャンクの切り出し点を決定する手法を説明するための図。
【図8】第1及び第2の文書と、当該第1及び第2の文書の格納前における文書構成テーブル及びチャンク一覧テーブルの状態とを示す図。
【図9】第1の文書を格納するための格納動作(その1)を文書構成テーブルの状態と共に示す図。
【図10】第1の文書を格納するための格納動作(その2)を文書構成テーブルの状態と共に示す図。
【図11】第1の文書を格納するための格納動作(その3)を文書構成テーブルの状態と共に示す図。
【図12】第1の文書を格納するための格納動作(その4)を文書構成テーブルの状態と共に示す図。
【図13】第1の文書を格納するための格納動作(その5)を文書構成テーブルの状態と共に示す図。
【図14】第1の文書の格納後における、文書構成テーブル及びチャンク一覧テーブルの状態を、当該第1の文書と当該第1の文書から切り出された親チャンクの列と共に示す図。
【図15】第1の文書の格納後に行われる第2の文書を格納するための格納動作(その1)を文書構成テーブルの状態と共に示す図。
【図16】第2の文書を格納するための格納動作(その2)を文書構成テーブルの状態と共に示す図。
【図17】第2の文書を格納するための格納動作(その3)を文書構成テーブルの状態と共に示す図。
【図18】第2の文書を格納するための格納動作(その4)を文書構成テーブルの状態と共に示す図。
【図19】第2の文書を格納するための格納動作(その5)を文書構成テーブルの状態と共に示す図。
【図20】第2の文書の格納後における、文書構成テーブル及びチャンク一覧テーブルの状態を、当該第2の文書と当該第2の文書から切り出された親チャンクの列と共に示す図。
【図21】第1及び第2の文書の格納後における、文書構成テーブル及びチャンク一覧テーブルの状態を、当該第1及び第2の文書と当該第1及び第2の文書から切り出された親チャンクの列と共に示す図。
【図22】同実施形態で適用される文書取得処理の手順を示すフローチャート。
【図23】従来技術における固定長重複排除方法及び可変長重複排除方法の違いを説明するための図。
【図24】従来技術における可変長重複排除方法で適用されるチャンク切り出し点を設定する動作の過程の一例を示す図。
【図25】従来技術におけるチャンク切り出し方法を説明するための図。
【図26】従来技術におけるチャンク切り出し方法によって文書を対象とするチャンク切り出しを行って、文書構成テーブル及びチャンク一覧テーブルを構成した例を示す図。
【図27】従来技術における第1の課題の例を示す図。
【図28】従来技術における第2の課題の例を示す図。
【発明を実施するための形態】
【0039】
以下、本発明の実施の形態につき図面を参照して説明する。
<システム構成>
図1は本発明の一実施形態に係るストレージシステムの構成を示すブロック図である。このストレージシステムは、文書格納装置10と、クライアント装置20とから構成される。文書格納装置10とクライアント装置20とは、例えばネットワーク30によって接続されている。文書格納装置10は文書をチャンクに分割して格納するためのデータ記憶装置である。クライアント装置20は、文書格納装置10を自身の記憶装置として利用する。つまりクライアント装置20は、例えば当該クライアント装置20上で動作するアプリケーションプログラムに従い、文書格納装置10に対して文書格納を指示することにより当該文書格納装置10に文書を格納させ、また文書格納装置10に対して文書取得を指示することにより文書格納装置10から文書を取得する。なお、文書格納装置10とクライアント装置20とが直接に接続されていても、クライアント装置20としての機能が文書格納装置10に内蔵されていても構わない。
【0040】
文書格納装置10は、クライアント装置20から文書名で指定される文書の格納を指示するための文書格納指示が与えられると、後述する手続きに従って、当該文書名で指定される文書をチャンクに分割しながら重複検出・排除を行った上で、当該文書を後述する文書格納部32(図3参照)に格納する。また文書格納装置10は、クライアント装置20から文書名で指定される文書の取得を指示するための文書取得指示が与えられると、当該文書名で指定される文書を文書格納部32から取り出してクライアント装置20に出力する。
【0041】
ここでの文書とは例えばファイルまたは当該ファイル内のデータを指し、文書名とはファイル名を指す。なお、ファイルと当該ファイル内のデータとを区別するために、当該ファイル内のデータを文書のデータまたは文書データと称することもある。また、チャンクとは、データを断片化したもの(データ断片)を指す。また本実施形態では、データ断片として、「第1のデータ断片」、「第2のデータ断片」及び「第3のデータ断片」が定義される。以降の説明では、「第2のデータ断片」を「子チャンク」、「第3のデータ断片」を「親チャンク」と、それぞれ称する。また「第1のデータ断片」を、「登録済みのデータ断片」、「登録済みの親チャンク」または単に「親チャンク」と称する。
【0042】
<文書格納装置10のハードウェア構成>
本実施形態において、文書格納装置10はコンピュータを用いて実現される。図2は、このような文書格納装置10のハードウェア構成を示すブロック図である。図2に示されるように、文書格納装置10、少なくとも1つの処理ユニット21、主記憶装置22、補助記憶装置23、通信機構24及び入出力装置25の周知のハードウェア構成を有する。補助記憶装置23は、例えばハードディスクドライブを用いて構成される。補助記憶装置23は、処理ユニット21によって実行されるプログラム230を格納した記憶媒体231を備えている。本実施形態において記憶媒体231はディスク媒体である。
【0043】
<文書格納装置10の機能構成>
図3は、文書格納装置10の主として機能構成を示すブロック図である。文書格納装置10は、文書格納部31と、命令受け付けモジュール32と、可変長重複排除モジュール33と、作業用メモリ34とを含む。本実施形態において、文書格納装置10内の命令受け付けモジュール32及び可変長重複排除モジュール33は、当該文書格納装置10が図2に示されるハードウェア構成のコンピュータから構成される場合に、当該コンピュータ内の処理ユニット21が、補助記憶装置23に格納されているプログラム230を主記憶装置22に読み込んで実行することにより実現されるものとする。しかし、命令受け付けモジュール32及び可変長重複排除モジュール33の少なくとも1つがハードウェアとして実現されてもよい。
【0044】
文書格納部31は、文書構成テーブル311及びチャンク一覧テーブル312を用いて文書の群を格納する。文書格納部31は、図2に示される補助記憶装置23の記憶領域の一部を用いて実現される。文書構成テーブル311及びチャンク一覧テーブル312は、それぞれ、従来技術で適用されている文書構成テーブル251及びチャンク一覧テーブル252(図26乃至図28参照)に相当する。
【0045】
文書構成テーブル311は、文書格納部31に格納される文書の群のそれぞれについて、その文書の文書名と、その文書を構成するチャンクの群の識別子(ハッシュ値)の配列(つまりリスト)とを対応付けて保持する。チャンク一覧テーブル312は、文書格納部31に格納される文書を構成するチャンクのそれぞれについて、そのチャンクのデータ断片と、そのチャンクの識別子(ハッシュ値)とを対応付けて保持する。つまり、文書格納部31には、文書が、当該文書を構成するチャンクの群に分割して格納される。
【0046】
本実施形態において、文書構成テーブル311及びチャンク一覧テーブル312は、文書格納装置10の起動時(例えば文書格納装置10の電源の投入時)に、アクセスの高速化のために、作業用メモリ34にロードされて使用される。また、作業用メモリ34にロードされている文書構成テーブル311及びチャンク一覧テーブル312は、例えば文書格納装置10において処理を実行していない状態が一定時間続いた場合、或いは文書格納装置10の動作停止時(例えば文書格納装置10の電源の遮断時)に文書格納部31に書き戻される。しかし、以降は便宜的に、文書格納装置10の起動後においても文書格納部31内の文書構成テーブル311及びチャンク一覧テーブル312が使用されるものとして説明する。
【0047】
命令受け付けモジュール32は、クライアント装置20からの指示を受け付けて、当該指示の内容に従って動作する。命令受け付けモジュール32は、クライアント装置20からの指示が文書格納指示の場合、当該文書格納指示を可変長重複排除モジュール33に渡すことにより、当該可変長重複排除モジュール33による文書格納処理を行わせる。命令受け付けモジュール32は、クライアント装置20からの指示が文書取得指示の場合に動作する文書取得部320を含む。文書取得部320は、文書取得指示に従い、指定された文書名の文書のデータを文書格納部31から取得するための文書取得処理を行う。文書取得部320によって取得された文書のデータは命令受け付けモジュール32によってクライアント装置20に出力される。
【0048】
可変長重複排除モジュール33は、命令受け付けモジュール32から渡された文書格納指示に従い、指定された文書のデータから可変長でチャンクを切り出すためのチャンク切り出し処理と、切り出されたチャンク毎に重複を検出してそれを排除するための重複検出・排除処理とを行いながら、文書格納部31に当該文書を格納する。可変長重複排除モジュール33は、子チャンク決定部331と、親チャンク決定部332と、識別子生成部333と、重複検出部334と、親チャンク登録部335と、制御部336とを含む。
【0049】
子チャンク決定部331は、可変長のチャンクを子チャンクとして決定する。親チャンク決定部332は、子チャンク決定部331によって決定された連続する子チャンクの列または単一の子チャンクを親チャンクとして決定する。
【0050】
識別子生成部333は、チャンク(ここでは親チャンク)の切り出しと重複検出で利用される当該チャンクの識別子を生成する。本実施形態では、識別子としてチャンクのハッシュ値が用いられる。このハッシュ値には、例えばSHA1などのハッシュ関数を利用して生成された値が用いられる。
【0051】
重複検出部334は、親チャンク決定部332によって決定された親チャンクの識別子に基づいて、当該識別子のデータ断片がチャンク一覧テーブル312に登録されている重複を検出する。
【0052】
親チャンク登録部335は、重複検出部334の重複検出結果に基づいて、親チャンクを文書格納部31内の文書構成テーブル311及びチャンク一覧テーブル312に登録するための親チャンク登録処理を行う。
制御部336は、子チャンク決定部331、親チャンク決定部332、識別子生成部333及び重複検出部334の動作を制御する。
【0053】
作業用メモリ34は、可変長重複排除モジュール33によるチャンク切り出し処理と重複検出・排除処理のための作業用の記憶領域を提供する。作業用メモリ34は、図2に示される主記憶装置22の記憶領域の一部を用いて実現される。作業用メモリ34の記憶領域の一部は、処理の対象となる文書データを一時格納するための文書バッファ341として用いられる。作業用メモリ34の記憶領域の他の一部は、処理に用いられる各種変数を一時格納するためのレジスタ部342として用いられる。レジスタ部342は、子チャンク番号i,j,kをそれぞれ保持するための、iレジスタ、jレジスタ、kレジスタと、子チャンク番号kの子チャンクの後述する開始オフセットck.offsetを保持するための子チャンク開始オフセットレジスタと、子チャンク番号kの子チャンクの長さ(子チャンク長)ck.lenを保持するための子チャンク長レジスタを含む。
【0054】
<文書格納処理>
次に、文書格納装置10における文書格納処理について、図4乃至図6を参照して説明する。なお、図4及び図5は、文書格納処理の手順を示すフローチャート、図6は文書格納装置10に格納されるべき文書が図23に示される文書111の場合における、親チャンクと子チャンクの群との関係を説明するため図である。
【0055】
まず、クライアント装置20から文書格納装置10にネットワーク30を介して文書格納指示が送られたものとする。この文書格納指示は、文書格納装置10に格納されるべき文書を指定する文書名を含んでいる。
【0056】
文書格納装置10に送られたクライアント装置20からの文書格納指示は、当該文書格納装置10の命令受け付けモジュール32で受け付けられる。命令受け付けモジュール32は、この文書格納指示を受け付けると入力手段として機能して、当該文書格納指示で指定される文書名の文書のデータをクライアント装置20から入力して作業用メモリ34内の文書バッファ341に格納する。そして命令受け付けモジュール32は、クライアント装置20からの文書格納指示を、可変長重複排除モジュール33に渡す。すると可変長重複排除モジュール33は、図4及び図5のフローチャートに示す手順の文書格納処理を実行する。即ち可変長重複排除モジュール33は、文書バッファ341に格納されている文書データの例えば先頭から末尾に至るまで、以下の処理を繰り返す。
【0057】
まず可変長重複排除モジュール33の制御部336は、子チャンク決定部331による子チャンクの切り出し(切り出し点の決定)のために、子チャンクckを指定するための子チャンク番号kを0に初期設定すると共に、当該子チャンクckのオフセット(開始オフセット)ck.offsetを文書データの先頭位置(ここでは先頭バイトの位置)を示す0に初期設定する(ステップ401)。つまり制御部336は、レジスタ部342内のkレジスタに、子チャンク番号kとして0(k=0)を設定すると共に、レジスタ部342内の子チャンク開始オフセットレジスタに、子チャンクckの開始オフセットck.offsetとして0(ck.offset=0)を設定する。子チャンクckの開始オフセットck.offsetは、当該子チャンクckの開始切り出し点を示すもので、当該開始切り出し点の文書データの先頭位置からのオフセット(相対位置)を示す。この時点では、子チャンクckの終了切り出し点を示す終了オフセットは決定されていないことに注意されたい。
【0058】
次に制御部336は、子チャンクcj,ciの子チャンク番号j,iをいずれもkに設定する(ステップ402)。つまり制御部336は、レジスタ部342内のjレジスタ及びiレジスタに、それぞれ子チャンク番号j,iとしてk(k=0)を設定する。子チャンクciは、チャンク一覧テーブル312に登録すべき1つの親チャンクを決定するための一連の処理(登録親チャンク決定処理)の最初に求められる親チャンクにおける先頭の子チャンクを示す。子チャンクcjは、登録親チャンク決定処理で求められる最新の親チャンクにおける先頭の子チャンクを示す。
【0059】
すると、可変長重複排除モジュール33内の子チャンク決定部331は、子チャンクckの終了切り出し点を示す終了オフセットを決定することにより、当該子チャンクckの長さを求め、その長さを、当該子チャンクckの長さを示す子チャンク長ck.lenとして、レジスタ部342内の子チャンク長レジスタに設定する(ステップ403)。子チャンクckの終了オフセットを決定する手法、つまり子チャンクck(可変長のチャンク)の切り出し点を定める手法には、前記特許文献1,2に記載されているような手法の他に、図7を参照して後述する手法を適用することが可能である。
【0060】
次に可変長重複排除モジュール33の制御部336は、子チャンクckの開始オフセットck.offsetに子チャンク長ck.lenを加算した値(ck.offset + ck.len)が、文書データのサイズ未満であるかを判定する(ステップ404)。この判定は、子チャンクckの終端が文書データの末尾(終了位置)に到達していないことを確認するために行われる。
【0061】
もし、“ck.offset + ck.len”が文書データのサイズ未満であるならば(ステップ404のNo)、制御部336は、“ck.offset + ck.len”から子チャンクcjのオフセットcj.offsetを減じた値(ck.offset + ck.len - cj.offset)が予め定められた連結ウィンドウサイズW以上であるかを判定する(ステップ405)。本実施形態では、連結ウィンドウサイズWは10バイト(W=10)であるものとする。
【0062】
“ck.offset + ck.len - cj.offset”は、子チャンク番号がjからkまでの子チャンクcj〜ckを連結した場合に、その連結された子チャンクの列の長さを表す。“cj.offset”、つまり連結された子チャンクの列の先頭の子チャンクcjのオフセットは、当該連結された子チャンクの列の開始オフセットを示す。この連結された子チャンクの列の開始オフセットは、後述するように決定される親チャンクpの開始オフセットとなる。そこで、この開始オフセットを、子チャンクの開始オフセットと区別するために、親チャンク開始オフセットと称する。
【0063】
ステップ401,402が実行された後にステップ405が最初に実行される場合、子チャンクckは子チャンク番号kが0の先頭の子チャンクであり、図6の例ではデータ断片“The f”が先頭の子チャンクである。このとき子チャンクckは子チャンクcjに一致するため、“ck.offset”は“cj.offset”に一致する。この場合、“ck.offset + ck.len - cj.offset”は子チャンクckの長さ“ck.len”に一致する。
【0064】
もし、“ck.offset + ck.len - cj.offset”が、連結ウィンドウサイズW以上でないならば(ステップ405のNo)、制御部336は、レジスタ部342内の子チャンク開始オフセットレジスタにより次の子チャンクck+1の開始オフセットck+1.offsetが示されるように、現在当該子チャンク開始オフセットレジスタに保持されている子チャンクckのオフセットck.offsetに現在子チャンク長レジスタに設定されている当該子チャンクckの長さを加算した値を、次の子チャンクck+1の開始オフセットck+1.offsetとして当該子チャンク開始オフセットレジスタに設定する(ステップ406)。このステップ406において制御部336は、kレジスタに保持されている子チャンク番号kを1インクリメントする。これにより、1インクリメント後の子チャンク番号kは、ステップ406が実行される前の子チャンクckに後続する子チャンクck+1を新たな子チャンクckとして指定することになる。このとき、子チャンク開始オフセットレジスタは、新たな子チャンクckの開始オフセットを示す。
【0065】
制御部336によってステップ406が実行されると、子チャンク決定部331は再びステップ403を実行することにより新たな子チャンクckの長さを求めて、その長さを子チャンク長ck.lenとして設定する。図6の例において、ステップ406が実行される前の子チャンクckが先頭の子チャンク“The f”である場合、“The f”に後続するデータ断片“file”が新たな子チャンクckとして決定される。そして、この新たな子チャンクckの子チャンク長ck.lenに基づき、上述の処理が再び行われる。
【0066】
すると、図6の例では、“file”に後続するデータ断片“ na”が更に新たな子チャンクckとして決定される。このとき“ck.offset + ck.len - cj.offset”、つまり子チャンク番号がjからkまでの子チャンクcj(“The f”)〜ck(“ na”)を連結した場合に、その連結された子チャンクの列の長さをL1とする。この長さL1は、図6に示されるように連結ウィンドウサイズW以上となる。
【0067】
このように、“ck.offset + ck.len - cj.offset”が連結ウィンドウサイズW以上となると(ステップ405のYes)、親チャンク決定部332は、子チャンク番号がjからkまでの子チャンクcj〜ckを1つに連結し、それを親チャンクpとして定める(ステップ407)。図6の例では、文書111(文書名が「文書#1」の文書)の先頭から3つの子チャンクが連結されて、親チャンクp1(p=p1)として決定される。この親チャンクp1を、後述するように親チャンク開始オフセットが再設定されることによって定められる後続の親チャンクp2,p3と区別するために、当初親チャンクと呼ぶこともある。なお、ステップ404の判定条件として、上述の条件の他に、(1)“ck.offset + ck.len - cj.offset”が連結ウィンドウサイズWを超えること、(2)“ck.offset + ck.len - cj.offset”が連結ウィンドウサイズWに一致すること、(3)“ck.offset + ck.len - cj.offset”が連結ウィンドウサイズWに最も近くなること、(4)“ck.offset + ck.len - cj.offset”が連結ウィンドウサイズWを超えない最大値となることのいずれかを適用しても構わない。
【0068】
上記ステップ407において親チャンク決定部332は、子チャンクcj〜ckを連結したデータcj...k.dataを親チャンクpのデータ(データ断片)pdataとして求める。また上記ステップ407において親チャンク決定部332は、当該親チャンクpのデータpdataの識別子として用いられる、当該親チャンクpのデータpdataのハッシュ値phashを、識別子生成部333により生成させる。このハッシュ値を求めるのに用いられるハッシュ関数をhash( )のように表すものとすると、ハッシュ値phashは、hash(pdata)の計算処理、つまりhash(cj...k.data)の計算処理により求められる。なお、子チャンク番号jがkに一致するならば、つまり単一の子チャンクだけで連結ウィンドウサイズW以上となるならば、当該単一の子チャンク自体が親チャンクpと決定される。
【0069】
次に、可変長重複排除モジュール33内の重複検出部334は、ステップ407で求められた親チャンクp(p=p1)のデータ断片が既にチャンク一覧テーブル312に登録されているかを判定する(ステップ408)。このステップ408は、親チャンクpと同一内容の親チャンクが、既に文書格納部31に格納されている重複を検出するために実行される。ステップ408の判定は、親チャンクpのデータpdataの識別子(ハッシュ値)phashに一致する識別子(ハッシュ値)が既にチャンク一覧テーブル312に登録されているかを調べることにより実現可能である。しかし、親チャンクpのデータ(データ断片)pdataのビット列と、親チャンクpのデータpdataの識別子に一致する識別子と対をなしてチャンク一覧テーブル312に登録されているチャンクのデータのビット列とは、識別子(ハッシュ値)の計算に用いるハッシュ関数によっては、必ずしも一致するとは限らない。そこで、上記ステップ408において重複検出部334は、親チャンクpのデータpdataの識別子(ハッシュ値)phashと当該データpdataの対が、チャンク一覧テーブル312に登録されているかを判定する。更に詳細に述べるならば、重複検出部334は、親チャンクpの識別子phashに一致する識別子がチャンク一覧テーブル312に登録されているけでなく、当該親チャンクpのデータpdataのビット列に一致するチャンクのデータのビット列が、当該一致する識別子と対応付けてチャンク一覧テーブル312に登録されているかを判定する。このようにすると、より高精度の重複検出が行えて、いわゆるハッシュ衝突を防止することができる。
【0070】
もし、ステップ407で求められた親チャンクpのデータ(データ断片)pdataがチャンク一覧テーブル312に登録されていないならば(ステップ408のNo)、制御部336は子チャンク番号jを1インクリメントする(ステップ409)。この1インクリメント後の子チャンク番号jは、ステップ407で求められた親チャンクpを構成する子チャンクの列における先頭の子チャンクに後続する子チャンクであって、次に決定されるべき親チャンクpの先頭の子チャンク(新たな子チャンク)cjを指す。
【0071】
この新たな子チャンクcjの開始オフセットcj.offsetfは、ステップ407で求められた親チャンクpを構成する子チャンクの列における先頭の子チャンクの長さだけ文書データの末尾側にずらされた、新たな親チャンク開始オフセットを示す。つまりステップ409により、親チャンク開始オフセットが再設定される。図6の例では、新たな(再設定された)親チャンク開始オフセットは、文書111の先頭から2番目の子チャンク(データ断片が“ile”の子チャンク)の開始オフセットに一致する。ステップ409は、後述するように、ステップ407で求められた親チャンクpから、先頭の子チャンクののデータ断片を取り外すことと等価である。
【0072】
次に制御部336は、“cj.offset + cj.len - ci.offset”が連結ウィンドウサイズW以上であるかを判定する(ステップ410)。このときcj.offsetは、上述のように再設定された親チャンク開始オフセットを示す。一方、“ci.offset”は、当初親チャンクpの開始オフセットを示す。したがって、“cj.offset + cj.len - ci.offset”は、子チャンク番号がiからjまでの子チャンクci〜cjを連結した場合に、その連結された子チャンクの列の長さを表す。つまり、“cj.offset + cj.len - ci.offset”は、ステップ409で再設定された親チャンク開始オフセットの当初親チャンクpの開始オフセットからの「ずれ」を表す。
【0073】
もし、“cj.offset + cj.len - ci.offset”が連結ウィンドウサイズW以上でないならば(ステップ410のNo)、制御部336はステップ406に進み、レジスタ部342内の子チャンク開始オフセットレジスタが次の子チャンクck+1の開始オフセットck+1.offsetを示すように、当該レジスタの内容を“ck.offset + ck.len”に更新すると共に、子チャンク番号kを1インクリメントする。このインクリメントにより、次の子チャンクck+1が新たな子チャンクckとして扱われる。この例のように、ステップ410でNoが判定されたためにステップ406が実行された場合、新たな子チャンクckは、先に決定された親チャンクpを構成するチャンクの列に後続する子チャンクである。図6の例では、“ na”に後続するデータ断片“me spe”が新たな子チャンクckのデータ断片して決定される。
【0074】
制御部336によってステップ406が実行されると、子チャンク決定部331は再びステップ403を実行することにより新たな子チャンクckの長さを求めて、その長さを子チャンク長ck.lenとして設定する。このように本実施形態では、ステップ409で再設定された親チャンク開始オフセットから始まる子チャンクcj〜ckの列の長さが連結ウィンドウサイズW以上となるところまで、子チャンクが定められる。ここでは、ステップ406の処理から明らかなように、再設定された親チャンク開始オフセット以降に出現する、以前の処理で既に定められた子チャンクcj〜ck-1について再び定め直す必要はない。
【0075】
図6の例では、このときの子チャンクcj〜ckのデータ断片は“file”〜“me spe”である。子チャンクcj(“file”)〜ck(“me spe”)を連結した場合に、その連結された子チャンクの列の長さ“ck.offset + ck.len - cj.offset”をL2とする。この長さL2は、図6に示されるように連結ウィンドウサイズW以上となる。
【0076】
この例のように、“ck.offset + ck.len - cj.offset”が連結ウィンドウサイズW以上となったならば(ステップ405のYes)、親チャンク決定部332は上述のように、子チャンク番号がjからkまでの子チャンクcj〜ckを1つに連結し、それを親チャンクpとして定める(ステップ407)。図6の例では、文書111の先頭から2番目乃至4番目の子チャンクが連結されて、親チャンクp2(p=p2)として決定される。親チャンクp2は、先に決定された親チャンクp1から先頭の子チャンク(つまり文書111の先頭の子チャンク)を上記ステップ409によって取り外し、その先頭の子チャンクが取り外された親チャンクp1に、新たに文書111の先頭から4番目の子チャンクが上記ステップ406,403,407によって組み込まれることによって構成される新たな親チャンクと等価である。
【0077】
次に重複検出部334は、ステップ407で求められた親チャンクp(p=p2)のデータ(データ断片)pdataが既にチャンク一覧テーブル312に登録されているかを判定する(ステップ408)。もし、親チャンクpのデータpdataがチャンク一覧テーブル312に登録されていないならば(ステップ408のNo)、制御部336は上述したようにステップ409に進み、子チャンク番号jを1インクリメントする。これにより、親チャンク開始オフセットが再設定される。図6の例では、再設定された親チャンク開始オフセットは、文書111の先頭から3番目の子チャンク(データ断片が“ na”の子チャンク)の開始オフセットに一致する。
【0078】
図6の例では、このときの“cj.offset + cj.len - ci.offset”、つまり親チャンク開始オフセットの「ずれ」は、連結ウィンドウサイズW以上でない(ステップ410のNo)。この場合、ステップ406及び403を含む処理が繰り返される。これにより図6の例では、文書111の先頭から3番目乃至5番目の子チャンクが連結されて、長さがL3(L3≧W)の親チャンクp3(p=p3)として決定される(ステップ407)。
【0079】
もし、決定された親チャンクp(p=p3)のデータpdataがチャンク一覧テーブル312に登録されていないならば(ステップ408のNo)、制御部336は上述したようにステップ409に進み、子チャンク番号jを1インクリメントする。これにより、親チャンク開始オフセットが再設定される。図6の例では、再設定された親チャンク開始オフセットは、文書111の先頭から4番目の子チャンク(データ断片が“me spe”の子チャンク)の開始オフセットに一致する。
【0080】
図6の例では、このときの“cj.offset + cj.len - ci.offset”、つまり親チャンク開始オフセットの「ずれ」は、連結ウィンドウサイズW以上である(ステップ410のYes)。この場合、制御部336は、子チャンク番号kを子チャンク番号jから1を減じた値、つまりステップ409で1インクリメントされる前の子チャンク番号jに再設定する(ステップ411)。これにより、再設定された子チャンク番号kは、当初親チャンクにおける終端側の子チャンクckを示す。ステップ410が実行されると、ステップ510に進む。
【0081】
一方、ステップ407で決定された親チャンクpが既にチャンク一覧テーブル312に登録されている登録済み親チャンクであるならば(ステップ408のYes)、親チャンク登録部335は文書構成テーブル311及びチャンク一覧テーブル312のうちの文書構成テーブル311のみに当該親チャンクpを登録する(ステップ412)。更に詳細に述べるならば、親チャンク登録部335は、親チャンクpを含む文書の文書名に対応付けて当該親チャンクpの識別子(ハッシュ値)phashを文書構成テーブル311に登録する。なお、文書構成テーブル311及びチャンク一覧テーブル312が空の状態にある場合、つまり未だ1つの親チャンクも文書構成テーブル311及びチャンク一覧テーブル312に登録されていない場合、最初にステップ407で決定された親チャンクpを、文書構成テーブル311及びチャンク一覧テーブル312に登録しても構わない。
【0082】
ここで、既に親チャンクpを含む文書の文書名が文書構成テーブル311に登録されている場合、親チャンク登録部335は、当該文書名に対応付けて文書構成テーブル311に既に登録されている識別子の配列の末尾に当該親チャンクpの識別子phashを追加する。これにより、親チャンクpを含む文書の文書名に対応付けて文書構成テーブル311に登録される識別子の並び順は、当該文書から対応する親チャンクが切り出される順番、つまり対応する親チャンクの当該文書における並び順に一致する。
【0083】
可変長重複排除モジュール33の制御部336は、文書構成テーブル311に親チャンクpが登録されと(ステップ412)、子チャンク番号iと子チャンク番号jとが等しいかを判定する(ステップ413)。つまり制御部336は、文書構成テーブル311に登録された親チャンクpが、親チャンク開始オフセットを再設定(ステップ409)することなく決定されたかを判定する。もし、子チャンク番号iと子チャンク番号jとが等しくないならば(ステップ413のNo)、ステップ413からステップ501に進む。
【0084】
このように、ステップ406,403を含む処理を繰り返した結果、親チャンクpが決定されて(ステップ407)、当該決定された親チャンクpのデータpdataが既にチャンク一覧テーブル312に登録されていることが検出され(ステップ408のYes)、且つi=jでない場合(ステップ413のNo)、ステップ501が実行される。また、親チャンク開始オフセットの「ずれ」が連結ウィンドウサイズW以上になったことが検出された場合には(ステップ410のYes)、ステップ411を経てステップ501が実行される。
【0085】
ステップ501において親チャンク決定部332は、子チャンク番号がiからj−1までの子チャンクci〜cj-1を1つに連結し、それを親チャンクpとして定める。またステップ501において、親チャンク決定部332は、子チャンクci〜cj-1を連結したデータci...j-1.dataを親チャンクpのデータpdataとして求めると共に、当該親チャンクpのデータpdataのハッシュ値(識別子)phash(=hash(ci...j-1.data))を識別子生成部333により生成させる。
【0086】
次に親チャンク登録部335は、チャンク一覧テーブル312に親チャンクpを登録する(ステップ502)。更に詳細に述べるならば、親チャンク登録部335は、親チャンクpの識別子(ハッシュ値)phash及び当該親チャンクpのデータ(データ断片)pdataをチャンク一覧テーブル312に登録する。また親チャンク登録部335は、文書構成テーブル311に親チャンクpを登録する(ステップ503)。つまり親チャンク登録部335は、親チャンクpを含む文書の文書名に対応付けて当該親チャンクpの識別子phashを文書構成テーブル311に登録する。
【0087】
さて、ステップ410からステップ411を経てステップ501に進んだ場合、ステップ501で決定される親チャンクp、つまり子チャンクci〜cj-1の列から構成される親チャンクpは、当初親チャンクp(図6の例では、親チャンクp1)に一致する。
【0088】
一方、ステップ413からステップ501に進んだ場合、ステップ501で決定される親チャンクpを構成する子チャンクci〜cj-1の列は、最も最近にチャンク一覧テーブル312に登録された親チャンクとステップ408での判定に用いられた親チャンクとの間に存在する子チャンクの列である。なお、iがj−1に等しい場合、子チャンクci〜cj-1は単一の子チャンクを意味する。
【0089】
親チャンク登録部335によってステップ503が実行されると、1回の登録親チャンク決定処理が終了する。すると制御部336は先のステップ404と同様に、“ck.offset + ck.len”が文書データのサイズ未満であるかを判定する(ステップ504)。
【0090】
もし、“ck.offset + ck.len”が文書データのサイズ未満であるならば(ステップ504のYes)、制御部336は文書データの末尾まで処理をし終えていないと判断する。この場合、制御部336は、次の登録親チャンク決定処理のために、レジスタ部342内の子チャンク開始オフセットレジスタが次の子チャンクck+1の開始オフセットck+1.offsetを示すように、当該レジスタの内容を“ck.offset + ck.len”に更新すると共に、子チャンク番号kを1インクリメントする(ステップ505)。制御部336はステップ505を実行すると、ステップ402に戻り、子チャンク番号j,iをいずれもkに設定する。これにより、親チャンク開始オフセットが、先の登録親チャンク決定処理における当初親チャンクの終了オフセットの位置(つまり終端位置)に再設定される。以後、ステップ403を含む上述と同様の手順の登録親チャンク決定処理が文書データの末尾まで繰り返される。
【0091】
そして文書データの末尾まで処理が行われた結果、“ck.offset + ck.len”が文書データのサイズ未満でなくなったものとする(ステップ404のNo)。この場合、親チャンク決定部332は、ステップ407と同様に、子チャンク番号がjからkまでの子チャンクcj〜ckを1つに連結し、それを親チャンクpとして定める(ステップ414)。このステップ414において可変長重複排除モジュール33は、子チャンクcj〜ckを連結したデータcj...k.dataを親チャンクpのデータpdataとして求めると共に、当該親チャンクpのデータpdataのハッシュ値(識別子)phash(=hash(cj...k.data))を識別子生成部333により生成させる。
【0092】
すると重複検出部334は、ステップ414で求められた親チャンクpのデータ断片が既にチャンク一覧テーブル312に登録されているかを判定する(ステップ415)。 もし、ステップ414で求められた親チャンクpのデータ断片がチャンク一覧テーブル312に登録されていないならば(ステップ415のNo)、親チャンク登録部335は、チャンク一覧テーブル312に親チャンクpの識別子(ハッシュ値)phash及び当該親チャンクpのデータ断片pdataを登録する(ステップ416)。次に親チャンク登録部335は上記ステップ412に進み、親チャンクpを含む文書の文書名に対応付けて当該親チャンクpの識別子phashを文書構成テーブル311に登録する。これに対し、親チャンクpのデータ断片がチャンク一覧テーブル312に既に登録されているならば(ステップ415のYes)、親チャンク登録部335はステップ416をスキップして、ステップ412を実行する。
【0093】
親チャンク登録部335によってステップ412が実行されると、制御部336は、子チャンク番号iと子チャンク番号jとが等しいかを判定する(ステップ413)。もし、子チャンク番号iと子チャンク番号jとが等しいならば(ステップ413のYes)、制御部336上記ステップ504に進む。ステップ504において制御部336は、先のステップ404と同様に、“ck.offset + ck.len”が文書データのサイズ未満であるかを判定する。ステップ404の判定がNoであるこの例では、ステップ504の判定もNoとなる。この場合、可変長重複排除モジュール33は文書データの末尾まで処理をし終えたとして、文書格納処理を終了する。
【0094】
<子チャンクの切り出し>
次に、子チャンク(つまり可変長のデータ断片)の切り出し点を決定する手法について説明する。前述したように、この手法として、前記特許文献1,2に記載されているような手法を適用することが可能である。しかし、この特許文献1,2に記載の手法の他に、以下に述べるような新規の手法を適用することも可能である。この新規の手法の特徴は、あるデータ断片の識別子(ハッシュ値)の下位mビットが、予め定めた値Aに一致したときに、当該データ断片の終端位置を子チャンクの切り出し点とすることにある。
【0095】
以下、この新規の手法について、図7を参照して説明する。図7は、あるデータ断片の識別子(ハッシュ値)の下位2ビット(m=2)が、予め定めた値2(A=2)に一致したときに、、当該データ断片の終端位置を子チャンクの切り出し点とする例を示す。データ断片の識別子(ハッシュ値)の計算に用いられるハッシュ関数をhβ( )のように表す。
【0096】
図7の例では、文書データ“The fil…”におけるデータ断片“Th”の識別子hβ(“Th”)が0x5Aである。この識別子0x5Aの下位2ビットは0x02である。この識別子0x5Aの下位2ビットは、当該識別子0x5Aとマスクデータ0x03との論理積演算0x5A&0x03によって求められる。識別子0x5Aの下位2ビット0x02は、規定値0x01に一致しない。このためデータ断片“Th”の終端位置は子チャンクの切り出し点ではない。
【0097】
そこで子チャンク決定部331は、切り出し点決定に用いるデータ断片のサイズ(区間)を文書データの末尾側に1バイト拡張する。このサイズ拡張後のデータ断片“The”の識別子hβ(“The”)が0xF2であるものとする。この識別子0xF2の下位2ビットは0x02であり、規定値0x01に一致しない。そこで子チャンク決定部331は、データ断片のサイズを更に1バイト拡張する。
【0098】
サイズ拡張後のデータ断片“The ”の識別子hβ(“The ”)が0x7Cであるものとする。この識別子0x7Cの下位2ビットは0x00であり、規定値0x01に一致しない。そこで子チャンク決定部331は、データ断片のサイズを更に1バイト拡張する。
【0099】
サイズ拡張後のデータ断片“The f”の識別子hβ(“The f”)が0x99であるものとする。この識別子0x99の下位2ビットは0x01であり、規定値0x01に一致する。そこで子チャンク決定部331は、このデータ断片“The f”の終端位置を切り出し点(終了オフセット)として決定し、当該データ断片“The f”を子チャンクとして切り出す。
【0100】
上述の文書格納処理の主要な手順を以下に整理して示す。
【0101】
可変長重複排除モジュール33は、文書データの先頭から末尾に至るまで、以下の処理を繰り返し行う。
【0102】
a)文書の先頭を親チャンク開始オフセットとして設定する(ステップ401,402)。
【0103】
b)親チャンク開始オフセットから、連結後の長さが連結ウィンドウサイズW以上となるところまで、子チャンクの列(または単一の子チャンク)を定める(ステップ403〜406)。
【0104】
c)処理bで子チャンクの列が定められたときには、これを1つに連結して、親チャンク(当初親チャンク)として定める(ステップ407)。処理bで単一の子チャンクが定められたときにも、これを親チャンク(当初親チャンク)として定める(ステップ407)。親チャンク(当初親チャンク)の長さは連結ウィンドウサイズW以上となる。
【0105】
d)親チャンクの識別子(ハッシュ値)を求める(ステップ407)。
【0106】
e)チャンク一覧テーブル312に既に親チャンクの識別子及びデータ断片が登録されているかを判定する(ステップ408)。
【0107】
e.1)登録されていれば、親チャンクの識別子を文書名に対応付けて文書構成テーブル311に登録する(ステップ412)。
【0108】
e.2)登録されていなければ、以下の処理を行う。
【0109】
e.2-1)親チャンクを構成する子チャンクの列の先頭側の少なくとも1つの子チャンク、例えば先頭の子チャンク(つまり、親チャンク開始オフセット側に最も近い子チャンク)のサイズだけ後側にずらした位置を親チャンク開始オフセットとして再設定する(ステップ409)。
【0110】
e.2-2)親チャンク開始オフセットから、連結後の長さが連結ウィンドウサイズW以上となるところまで、子チャンクの列(または単一の子チャンク)を定める(ステップ403〜406)。このとき、以前の処理で既に定めた子チャンクについて再び定め直す必要はない(ステップ406)。
【0111】
e.2-3)処理e.2-2で子チャンクの列が定められたときには、これを1つに連結して、親チャンクとして定める(ステップ407)。処理e.2-2で単一の子チャンクが定められたときにも、これを親チャンクとして定める(ステップ407)。
【0112】
e.2-4)親チャンクの識別子(ハッシュ値)を求める(ステップ407)。
【0113】
e.2-5)チャンク一覧テーブル312に既に親チャンクの識別子及びデータ断片が登録されているかを判定する(ステップ408)。
【0114】
e.2-6)以上の処理(e.2-1〜e.2-5)を、親チャンクの識別子及びデータ断片がチャンク一覧テーブル312に既に登録されているか(ステップ408のYes)、親チャンク開始オフセットの「ずれ」が処理cで定めた当初親チャンクのサイズを超えるところまで(ステップ410のYes)、繰り返す(図6の例では親チャンクp3まで)。
【0115】
e.2-7)これでもなおデータ断片が登録されていないときには、処理cで定めた当初親チャンク(図6の例では親チャンクp1)の識別子及びデータ断片をチャンク一覧テーブル312に登録すると共に、当該識別子を文書名に対応付けて文書構成テーブル311に登録する(ステップ502,503)。そして、次の親チャンク開始オフセットとなる子チャンクの開始オフセットを、処理cで定めた当初親チャンクの終了オフセット(つまり当初親チャンクの終端側の子チャンクの終了オフセット)の位置に再設定して(ステップ411,505)、処理bに戻る。
【0116】
親チャンクの識別子及びデータ断片がチャンク一覧テーブル312に既に登録されているときには(ステップ408のYes)、その親チャンクの識別子を文書名に対応付けて文書構成テーブル311に登録する(ステップ412)。また、文書構成テーブル311に登録された親チャンクと、前回チャンク一覧テーブル312に登録された親チャンクとの間に、チャンク一覧テーブル312に未登録のデータ断片が存在するときには(ステップ413のNo)、当該データ断片を親チャンクとして、当該データ断片及び当該データ断片の識別子をチャンク一覧テーブル312に登録すると共に、当該データ断片の識別子を文書名に対応付けて文書構成テーブル311に登録する(ステップ501〜503)。このとき、文書を構成するチャンクの順序が正しくなるように、文書構成テーブル311におけるチャンク(データ断片)を書き換える必要がある。そして、次の親チャンク開始オフセットとなる子チャンクの開始オフセットを、今回登録された親チャンクの終了オフセット(つまり当初親チャンクの終端側の子チャンクの終了オフセット)の位置に再設定して(ステップ411,505)、処理bに戻る。なお、文書名に対応付けて親チャンクの識別子を文書構成テーブル311に登録する際に、当該親チャンクの対応する文書データ上での位置・長さを示す情報を当該親チャンクの識別子に付加するならば、上述のような書き換えは必ずしも必要ない。
【0117】
以上の処理を、データの末尾に至るまで繰り返すことで、可変長での重複排除を行いながら、データの格納を行うことができる。
【0118】
<文書格納処理の具体例>
次に、文書格納装置10における文書格納処理の具体例について、図5及び図6のフローチャートに加えて、図8乃至図21を参照して説明する。
ここでは、文書名が「文書#1」の文書111及び文書名が「文書#2」の文書112の2つの文書を順次、重複を排除しながら文書格納部31に格納する例について述べる。以下の説明では、文書111,112を格納するための格納処理をそれぞれ格納処理SX,SYと呼ぶ。この例では、連結ウィンドウサイズWが10(10バイト)に設定される。
【0119】
(1)格納処理SX,SYの開始前
文書111,112が文書格納部31に格納される前は、文書格納部31内の文書構成テーブル311及びチャンク一覧テーブル312は空の状態になっている。図8は文書111,112(第1及び第2の文書)と、当該文書111,112の格納前における文書構成テーブル311及びチャンク一覧テーブル312の状態とを示す。
【0120】
(2)格納処理SX
文書111を格納するための格納処理(格納動作)SXについて、図9乃至図14を参照して説明する。図9乃至図13は文書111の格納動作を文書構成テーブル311の状態と共に示し、図14は文書111の格納後における、文書構成テーブル311及びチャンク一覧テーブル312の状態を、当該文書111と当該文書111から切り出された親チャンクの列と共に示す。
【0121】
A)格納処理SXその1
まず、文書111を格納するための格納処理SXその1(以下、格納処理SX1と称する)について、図9を参照して説明する。なお、図9では、文書構成テーブル311は省略されている。
【0122】
A1)
A1-1)可変長重複排除モジュール33は、文書111の先頭から、連結ウィンドウサイズW(この例ではW=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。各子チャンクは、前述した可変長のチャンク切り出し手法により定められる。図9の例では、可変長重複排除モジュール33は、文書111の先頭より5,8,11文字目のところに切り出し点を定め、子チャンクc0(“The f”),c1(“ile”),c2(“ na”)を定めたものとする。
【0123】
A1-2)可変長重複排除モジュール33は、連結ウィンドウサイズW以上となるところまで子チャンクc0(“The f”),c1(“ile”),c2(“ na”)を順次定めたところで、それらの子チャンクを連結して親チャンク901を定め、当該親チャンク901の識別子(ハッシュ値)を生成する(ステップ407)。連結する子チャンクc0(“The f”),c1(“ile”),c2(“ na”)の識別子(ハッシュ値)を、c0.hash=HA,c1.hash=HB,c2.hash=HCとする。この例では、親チャンク901のデータのハッシュ値として、当該親チャンク901を構成する子チャンクc0,c1,c2の識別子(ハッシュ値)HA,HB,HCから生成されたハッシュ値HABCを用い、これを親チャンク901の識別子とする。
【0124】
A1-3)可変長重複排除モジュール33は、親チャンク901の識別子HABCに基づき、チャンク一覧テーブル312に当該識別子HABCに対応するデータ断片が登録されているかを判定する(ステップ408)。この例では、識別子HABCに対応するデータ断片は登録されていない。このため、親チャンク901に関するステップ408の判定結果は図9において矢印911で示されるよう未登録(No)となり、次の処理A2に進む。
【0125】
A2)
A2-1)可変長重複排除モジュール33は、上述の処理A1で定めた親チャンク901を構成する子チャンクc0,c1,c2の列の先頭の子チャンクc0の長さだけ、文書111の末尾側にずらした位置(再設定された親チャンク開始位置)から(ステップ409)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、処理A1で子チャンクc1,c2を定めた部分についての再度の処理は必要ない。図9の例では、可変長重複排除モジュール33は、文書111の先頭より17文字目のところに切り出し点を定め、新たに子チャンクc3を定めたものとする。
【0126】
A2-2)可変長重複排除モジュール33は、連結ウィンドウサイズW以上となるところまで子チャンクc1,c2,c3を定めたところで、それらの子チャンクc1,c2,c3を連結して親チャンク902を定め、当該親チャンク902の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、連結する子チャンクc1(“ile”),c2(“ na”),c3(“me spe”)の識別子(ハッシュ値)c1.hash=HB,c2.hash=HC,c3.hash=HDから生成したハッシュ値HBCDを、親チャンク902の識別子(ハッシュ値)とする。
【0127】
A2-3)可変長重複排除モジュール33は、親チャンク902の識別子HBCDに基づき、チャンク一覧テーブル312に当該識別子HBCDに対応するデータ断片が登録されているかを判定する(ステップ408)。この例では、識別子HBCDに対応するデータ断片は登録されていない。このため、親チャンク902に関するステップ408の判定結果は図9において矢印912で示されるように未登録(No)となり、次の処理A3に進む。
【0128】
A3)
A3-1)可変長重複排除モジュール33は、上述の処理A2で定めた親チャンク902を構成する子チャンクc1,c2,c3の列の先頭の子チャンクc1の長さだけ、文書111の末尾側にずらした位置から(ステップ409)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、処理A2で子チャンクc2,c3を定めた部分についての再度の処理は必要ない。図9の例では、可変長重複排除モジュール33は、文書111の先頭より20文字目のところに切り出し点を定め、新たに子チャンクc4を定めたものとする。
【0129】
A3-2)可変長重複排除モジュール33は、連結ウィンドウサイズW以上となるところまで子チャンクc2,c3,c4を定めたところで、それらの子チャンクc2,c3,c4を連結して親チャンク903を定め、当該親チャンク903の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、連結する子チャンクc2(“ na”),c3(“me spe”),c4(“cif”)の識別子(ハッシュ値)c2.hash=HC,c3.hash=HD,c4.hash=HEから生成したハッシュ値HCDEを、親チャンク903の識別子(ハッシュ値)とする。
【0130】
A3-3)可変長重複排除モジュール33は、親チャンク903の識別子HCDEに基づき、チャンク一覧テーブル312に当該識別子HCDEに対応するデータ断片が登録されているかを判定する(ステップ408)。この例では、識別子HCDEに対応するデータ断片は登録されていない。このため、親チャンク903に関するステップ408の判定結果は図9において矢印913で示されるように未登録(No)となり、次の処理A4に進む。
【0131】
A4)
図9の例では、上述の処理A3で定めた親チャンク903を構成する子チャンクc2,c3,c4の列の先頭の子チャンクc2の長さだけ、文書111の末尾側にずらした位置(つまり再設定された親チャンク開始位置)は、処理A1で定められた親チャンク(つまり当初親チャンク)901の終端の位置を超えている。したがって、ステップ409で再設定された親チャンク開始オフセットの親チャンク901の開始オフセットからの「ずれ」は、連結ウィンドウサイズW以上となる(ステップ410のYes)。この場合、可変長重複排除モジュール33は、処理A1で定められた親チャンク901の識別子HABC及びデータ(データ断片)“The file na”を、図9において矢印904で示すようにチャンク一覧テーブル312に登録する(ステップ502)。また図9では省略されているが、可変長重複排除モジュール33は、文書111の文書名「文書#1」及び親チャンク901の識別子HABCを文書構成テーブル311に登録する(ステップ503)。なお本実施形態では、ステップ502で登録される親チャンク901の識別子HABCは、ステップ501で改めて求められる。
【0132】
(B)格納処理SXその2
上述の格納処理SX1に続いて実行される、文書111を格納するための格納処理SXその2(以下、格納処理SX2と称する)について、図10を参照して説明する。なお、図10では、文書構成テーブル311は省略されている。
【0133】
B1)
B1-1)可変長重複排除モジュール33は、格納処理SX1で定められた親チャンク901の終端の位置から(ステップ505)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、格納処理SX1で親チャンク901の終端の位置以降の子チャンクc3,c4を定めた部分についての再度の処理は必要ない。図10の例では、可変長重複排除モジュール33は、文書111の先頭より24文字目のところに切り出し点を定め、新たな子チャンクc5(“cif”)を定めたものとする。
【0134】
以降の処理は、格納処理SX1における、処理A2-2〜A2-3と同様であり、子チャンクc3,c4,c5を連結することにより親チャンク1001が定められる。図10の例では親チャンク1001の識別子HDEFに対応するデータ断片は、チャンク一覧テーブル312に登録されていない。このため、親チャンク1001に関するステップ408の判定結果は図10において矢印1011で示されるように未登録(No)となり、次の処理B2に進む。
【0135】
B2)
処理B2は格納処理SX1における処理A2と同様である。処理B2では、新たに子チャンクc6(“by path is ope”)が定められる。そして子チャンクc4,c5,c6を連結することにより親チャンク1002が定められる。図10の例では親チャンク1002の識別子HEFGに対応するデータ断片は、チャンク一覧テーブル312に登録されていない。このため、親チャンク1001に関するステップ408の判定結果は図10において矢印1012で示されるように未登録(No)となり、次の処理B3に進む。
【0136】
B3)
処理B3は格納処理SX1における処理A3と同様である。可変長重複排除モジュール33は、上述の処理A2で定めた親チャンク1002を構成する子チャンクc4,c5,c6の列の先頭の子チャンクc4の長さだけ、文書111の末尾側にずらした位置から(ステップ409)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、処理B2で子チャンクc5,c6を定めた部分についての再度の処理は必要ない。図10の例では、子チャンクc4の長さだけずらした位置から連結ウィンドウサイズW以上となるところまでに、新たに定める子チャンクはない。そこで可変長重複排除モジュール33は、処理A2で定めた親チャンク1002から先頭の子チャンクc4を除いた残りの子チャンクc5,c6を連結して親チャンク1003を定める。図10の例では親チャンク1003の識別子HFGに対応するデータ断片は、チャンク一覧テーブル312に登録されていない。このため、親チャンク1003に関するステップ408の判定結果は図10において矢印1013で示されるように未登録(No)となり、次の処理B4に進む。
【0137】
B4)
処理B4は格納処理SX1における処理A4と同様である。つまり、図10の例では、処理B3で定めた親チャンク1003を構成する子チャンクc5,c6の列の先頭の子チャンクc5の長さだけ、文書111の末尾側にずらした位置(つまり再設定された親チャンク開始位置)は、処理B1で定められた親チャンク(つまり当初親チャンク)1001の終端の位置を超えている(ステップ410のYes)。この場合、可変長重複排除モジュール33は、処理B1で定められた親チャンク1001の識別子HDEF及びデータ(データ断片)“me specified ”を、図10において矢印1004で示すようにチャンク一覧テーブル312に登録する(ステップ502)。また図9では省略されているが、可変長重複排除モジュール33は、文書111の文書名「文書#1」及び親チャンク1001の識別子HDEFを文書構成テーブル311に登録する(ステップ503)。
【0138】
(C)格納処理SXその3
上述の格納処理SX2に続いて実行される、文書111を格納するための格納処理その3(以下、格納処理SX3と称する)について、図11を参照して説明する。なお、図11では、文書構成テーブル311は省略されている。
【0139】
C1)
可変長重複排除モジュール33は、格納処理SX2で定められた親チャンク1001の終端の位置から(ステップ505)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。図10の例では、可変長重複排除モジュール33は、文書111の先頭より38文字目のところに切り出し点を定め、子チャンクc6を定めたものとする。
【0140】
以降の処理は、格納処理SX1における、処理A2-2〜A2-3と同様である。但し、図11の例では、子チャンクc6(“by path is ope”)のみで連結ウィンドウサイズW(W=10)以上となるため、当該子チャンクc6単体が親チャンク1101として定められる。可変長重複排除モジュール33は、子チャンクc6(“by path is ope”)の識別子(ハッシュ値)c6.hash=HGより生成したハッシュ値HG’を親チャンク1101の識別子(ハッシュ値)とする。図11の例では親チャンク1101の識別子HG’に対応するデータ断片は、チャンク一覧テーブル312に登録されていない。このため、親チャンク1101に関するステップ408の判定結果は図11において矢印1111で示されるように未登録(No)となり、次の処理C2に進む。
【0141】
C2)
処理C2は、格納処理SX1における処理A4と同様である。図11の例では、上述の処理C1で定めた親チャンク1101の開始位置から当該親チャンク1101を構成する子チャンクc6の長さだけ、文書111の末尾側にずらした位置(つまり再設定された親チャンク開始位置)は、当該親チャンク(つまり当初親チャンク)1101の終端の位置を超えている(ステップ410のYes)。この場合、可変長重複排除モジュール33は、処理C1で定められた親チャンク1101の識別子HG’及びデータ(データ断片)“by path is ope”を、図11において矢印1102で示すようにチャンク一覧テーブル312に登録する(ステップ502)。また図11では省略されているが、可変長重複排除モジュール33は、文書111の文書名「文書#1」及び親チャンク1101の識別子HG’を文書構成テーブル311に登録する(ステップ503)。
【0142】
(D)格納処理SXその4
上述の格納処理SX3に続いて実行される、文書111を格納するための格納処理SXその4(以下、格納処理SX4と称する)について、図12を参照して説明する。なお、図12では、文書構成テーブル311は省略されている。
【0143】
D1)
D1-1)可変長重複排除モジュール33は、格納処理SX3で定められた親チャンク1101の終端の位置から(ステップ505)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。図12の例では、可変長重複排除モジュール33は、文書111の先頭より41,47,50文字目のところに切り出し点を定め、子チャンクc7,c8,c9を定めたものとする。
【0144】
以降の処理は、格納処理SX1における、処理A2-2〜A2-3と同様であり、子チャンクc7,c8,c9を連結することにより親チャンク1201が定められる。図12の例では親チャンク1201の識別子HHIJに対応するデータ断片は、チャンク一覧テーブル312に登録されていない。このため、親チャンク1201に関するステップ408の判定結果は図12において矢印1211で示されるように未登録(No)となり、次の処理D2に進む。
【0145】
D2)
処理D2は、格納処理SX1における処理A2と同様であり、新たに子チャンクc10が定められる。そして子チャンクc8,c9,c10を連結することにより親チャンク1202が定められる。図12の例では親チャンク1202の識別子HIJKに対応するデータ断片は、チャンク一覧テーブル312に登録されていない。このため、親チャンク1202に関するステップ408の判定結果は図12において矢印1212で示されるように未登録(No)となり、次の処理D3に進む。
【0146】
D3)
処理D3は、格納処理SX1における処理A3と同様である。可変長重複排除モジュール33は、上述の処理D2で定めた親チャンク1202を構成する子チャンクc8,c9,c10の列の先頭の子チャンクc8の長さだけ、文書111の末尾側にずらした位置から(ステップ409)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、処理D2で子チャンクc9,c10を定めた部分についての再度の処理は必要ない。図12の例では、可変長重複排除モジュール33は、文書111の先頭より57文字目のところに切り出し点を定め、子チャンクc11を定めたものとする。可変長重複排除モジュール33は、子チャンクc9,c10,c11を連結して親チャンク1203を定める。図10の例では親チャンク1203の識別子HJKLに対応するデータ断片は、チャンク一覧テーブル312に登録されていない。このため、親チャンク1203に関するステップ408の判定結果は図12において矢印1213で示されるように未登録(No)となり、次の処理D4に進む。
【0147】
D4)
処理D4は、格納処理SX1における処理A4と同様である。つまり、図12の例では、処理D3で定めた親チャンク1203を構成する子チャンクc9,c10,c11の列の先頭の子チャンクc9の長さだけ、文書111の末尾側にずらした位置は、処理D1で定められた親チャンク1201の終端の位置を超えている(ステップ410のYes)。この場合、可変長重複排除モジュール33は、処理D1で定められた親チャンク1201の識別子HHIJ及びデータ(データ断片)“ned for read”を、図12において矢印1204で示すようにチャンク一覧テーブル312に登録する(ステップ502)。また図12では省略されているが、可変長重複排除モジュール33は、文書111の文書名「文書#1」及び親チャンク1201の識別子HHIJを文書構成テーブル311に登録する(ステップ503)。
【0148】
(E)格納処理SXその5
上述の格納処理SX4に続いて実行される、文書111を格納するための格納処理SXその5(以下、格納処理SX5と称する)について、図13を参照して説明する。この例では、説明の簡略化のために、便宜的に文字列“and”が文書111の末尾であるとしている。なお、図13では、文書構成テーブル311は省略されている。
【0149】
E1)
可変長重複排除モジュール33は、格納処理SX4で定められた親チャンク1201の終端の位置から(ステップ505)、子チャンクを順次定めていく(ステップ403〜406)。図13の例では、子チャンクc10,c11が定められ、その結果、切り出し点が文書111の末尾に達したものとする(ステップ404)。この場合、可変長重複排除モジュール33は、切り出し点が、格納処理SX4で定められた親チャンク1201の終端の位置から連結ウィンドウサイズW(W=10)以上となるか否かに無関係に、子チャンクc10,c11を連結することにより親チャンク1301を定める(ステップ414)。
【0150】
E2)
可変長重複排除モジュール33は、処理E1で定められた親チャンク1301の識別子HKL及びデータ(データ断片)“ing and”を、図13において矢印1302で示すようにチャンク一覧テーブル312に登録する(ステップ412)。また図13では省略されているが、可変長重複排除モジュール33は、文書111の文書名「文書#1」及び親チャンク1301の識別子HKLを文書構成テーブル311に登録する(ステップ416)。これにより、文書111を格納するための格納処理SXは完了する。
【0151】
上述の格納処理SX(つまり格納処理SX1乃至SX5)が完了した後における、文書構成テーブル311及びチャンク一覧テーブル312の状態(つまり文書111の登録状態)を、文書111及び当該文書111から切り出された親チャンクの列と共に図14に示す。
【0152】
(3)格納処理SY
次に文書112を格納するための格納処理SYについて、図15乃至図21を参照して説明する。図15乃至図19は文書111の格納後に行われる文書112の格納動作を文書構成テーブル311の状態と共に示す。図20は文書112の格納後(つまり文書111,112の格納後)における、文書構成テーブル311及びチャンク一覧テーブル312の状態を、文書112及び当該文書112から切り出された親チャンクの列と共に示し、図21は文書111,112の格納後における、文書構成テーブル311及びチャンク一覧テーブル312の状態を、当該文書111,112から切り出された親チャンクの列と共に示す。
【0153】
F)格納処理SYその1
文書111を格納した後に、文書112を格納するための格納処理SYその1(以下、格納処理SY1と称する)について、図15を参照して説明する。なお、図15では、文書構成テーブル311は省略されている。
【0154】
F-1)可変長重複排除モジュール33は、文書112の先頭から、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。図15の例では、可変長重複排除モジュール33は、文書112の先頭より5,8,11文字目のところに切り出し点を定め、子チャンクc0(“The f”),c1(“ile”),c2(“ na”)を定めたものとする。
【0155】
F-2)可変長重複排除モジュール33は、連結ウィンドウサイズW以上となるところまで子チャンクc0(“The f”),c1(“ile”),c2(“ na”)を順次定めたところで、それらの子チャンクを連結して親チャンク1501を定め、当該親チャンク1501の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、連結する子チャンクc0(“The f”),c1(“ile”),c2(“ na”)の識別子(ハッシュ値)c0.hash=HA,c1.hash=HB,c2.hash=HCから生成したハッシュ値HABCを、親チャンク1501の識別子(ハッシュ値)とする。
【0156】
F-3)可変長重複排除モジュール33は、親チャンク1501の識別子HABCに基づき、チャンク一覧テーブル312に当該識別子HABCに対応するデータ断片が登録されているかを判定する(ステップ408)。図15に示すように、チャンク一覧テーブル312には、識別子HABCに対応するデータ断片が登録されている。このため、親チャンク1501に関するステップ408の判定結果は図15において矢印1511で示されるようにYes(登録済)となり、次の処理Gに進む。この場合、チャンク一覧テーブル312は図15において矢印1502で示されるように、処理Fの前後で変わらない。なお、図15では省略されているが、可変長重複排除モジュール33は処理Gに進む前に、文書112の文書名「文書#2」及び親チャンク1501の識別子HABCを文書構成テーブル311に登録する(ステップ503)。
【0157】
G)格納処理SYその2
上述の格納処理SY1に続いて実行される、文書112を格納するための格納処理SYその2(以下、格納処理SY2と称する)について、図16を参照して説明する。なお、図16では、文書構成テーブル311は省略されている。
【0158】
G1)
G1-1)可変長重複排除モジュール33は、格納処理SY1で定められた親チャンク1501の終端の位置から(ステップ505)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。図16の例では、可変長重複排除モジュール33は、文書112の先頭より13,22文字目のところに切り出し点を定め、子チャンクc3,c4を定めたものとする。
【0159】
G2-2)可変長重複排除モジュール33は、連結ウィンドウサイズW以上となるところまで子チャンクc3,c4を定めたところで、それらの子チャンクc3,c4を連結して親チャンク1601を定め、当該親チャンク1601の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、連結する子チャンクc3(“me”),c4(“ABCD spe”)の識別子(ハッシュ値)c3.hash=HX,c4.hash=HYから生成したハッシュ値HXYを、親チャンク1601の識別子(ハッシュ値)とする。
【0160】
G2-3)可変長重複排除モジュール33は、親チャンク1601の識別子HXYに基づき、チャンク一覧テーブル312に当該識別子HXYに対応するデータ断片が登録されているかを判定する(ステップ408)。この例では、識別子HXYに対応するデータ断片は登録されていないため、次の処理G3に進む。
【0161】
G3)
G3-1)可変長重複排除モジュール33は、上述の処理G2で定めた親チャンク1601を構成する子チャンクc3,c4の列の先頭の子チャンクc3の長さだけ、文書112の末尾側にずらした位置から(ステップ409)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、処理G2で子チャンクc4を定めた部分についての再度の処理は必要ない。図16の例では、可変長重複排除モジュール33は、文書112の先頭より25文字目のところに切り出し点を定め、新たに子チャンクc5を定めたものとする。
【0162】
G3-2)可変長重複排除モジュール33は、連結ウィンドウサイズW以上となるところまで子チャンクc4,c5を定めたところで、それらの子チャンクc4,c5を連結して親チャンク1602を定め、当該親チャンク1602の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、連結する子チャンクc4(“ABCD spe”),c5(“cif”)の識別子(ハッシュ値)c4.hash=HY,c5.hash=HEから生成したハッシュ値HYEを、親チャンク1602の識別子(ハッシュ値)とする。
【0163】
G3-3)可変長重複排除モジュール33は、親チャンク1602の識別子HYEに基づき、チャンク一覧テーブル312に当該識別子HYEに対応するデータ断片が登録されているかを判定する(ステップ408)。この例では、識別子HYEに対応するデータ断片は登録されていないため、次の処理G4に進む。
【0164】
G4)
G4-1)図16の例では、上述の処理G3で定めた親チャンク1602を構成する子チャンクc4,c5の列の先頭の子チャンクc4の長さだけ、文書112の末尾側にずらした位置は、処理G1で定められた親チャンク(つまり当初親チャンク)1601の終端の位置を超えている。したがって、ステップ409で再設定された親チャンク開始オフセットの親チャンク1601の開始オフセットからの「ずれ」は、連結ウィンドウサイズW以上となる(ステップ410のTes)。この場合、可変長重複排除モジュール33は、処理G1で定められた親チャンク1601の識別子HXY及びデータ(データ断片)“me ABCD spe”を、図16において矢印1603で示すようにチャンク一覧テーブル312に登録する(ステップ502)。また図16では省略されているが、可変長重複排除モジュール33は、文書112の文書名「文書#2」及び親チャンク1601の識別子HXYを文書構成テーブル311に登録する(ステップ503)。
【0165】
H)格納処理SYその3
上述の格納処理SY2に続いて実行される、文書112を格納するための格納処理SYその3(以下、格納処理SY3と称する)について、図17を参照して説明する。なお、図17では、文書構成テーブル311は省略されている。
【0166】
H1)
H1-1)可変長重複排除モジュール33は、格納処理SY2で定められた親チャンク1601の終端の位置から(ステップ505)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、格納処理SY2で親チャンク1601の終端の位置以降の子チャンクc5を定めた部分についての再度の処理は必要ない。図16の例では、可変長重複排除モジュール33は、文書112の先頭より29,43文字目のところに切り出し点を定め、新たな子チャンクc6(“ied”),c7(“by path is ope”)を定めたものとする。
【0167】
H1-2)可変長重複排除モジュール33は、連結ウィンドウサイズW以上となるところまで子チャンクc5,c6,c7を定めたところで、それらの子チャンクc5,c6,c7を連結して親チャンク1701を定め、当該親チャンク1701の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、連結する子チャンクc5(“cif”),c6(“ied”),c7(“by path is ope”)の識別子(ハッシュ値)c5.hash=HE,c6.hash=HF,c7.hash=HGから生成したハッシュ値HEFGを、親チャンク1701の識別子(ハッシュ値)とする。
【0168】
H1-3)可変長重複排除モジュール33は、親チャンク1701の識別子HEFGに基づき、チャンク一覧テーブル312に当該識別子HEFGに対応するデータ断片が登録されているかを判定する(ステップ408)。この例では、識別子HEFGに対応するデータ断片は登録されていない。このため、親チャンク1701に関するステップ408の判定結果は図17において矢印1711で示されるように未登録(No)となり、次の処理H2に進む。
【0169】
H2)
H2-1)可変長重複排除モジュール33は、上述の処理H1で定めた親チャンク170101を構成する子チャンクc5,c6,c7の列の先頭の子チャンクc5の長さだけ、文書112の末尾側にずらした位置から(ステップ409)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、処理H1で子チャンクc6,c7を定めた部分についての再度の処理は必要ない。図17の例では、子チャンクc5の長さだけずらした位置から連結ウィンドウサイズW以上となるところまでに、新たに定める子チャンクはない。
【0170】
H2-2)そこで可変長重複排除モジュール33は、処理H1で定めた親チャンク1701から先頭の子チャンクc5を除いた残りの子チャンクc6,c7を連結して親チャンク1702を定め、当該親チャンク1702の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、連結する子チャンクc6(“ied”),c7(“by path is ope”)の識別子(ハッシュ値)c6.hash=HF,c7.hash=HGから生成したハッシュ値HFGを、親チャンク1702の識別子(ハッシュ値)とする。
【0171】
H2-3)可変長重複排除モジュール33は、親チャンク1702の識別子HFGに基づき、チャンク一覧テーブル312に当該識別子HFGに対応するデータ断片が登録されているかを判定する(ステップ408)。この例では、識別子HFGに対応するデータ断片は登録されていない。このため、親チャンク1702に関するステップ408の判定結果は図17において矢印1712で示されるように未登録(No)となり、次の処理H3に進む。
【0172】
H3)
H3-1)可変長重複排除モジュール33は、上述の処理H2で定めた親チャンク170102を構成する子チャンクc6,c7の列の先頭の子チャンクcの長さだけ、文書112の末尾側にずらした位置から(ステップ409)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。このとき、処理H2で子チャンクc7を定めた部分についての再度の処理は必要ない。図17の例では、子チャンクc6の長さだけずらした位置から連結ウィンドウサイズW以上となるところまでに、新たに定める子チャンクはない。また子チャンクc7のみで、連結ウィンドウサイズW(W=10)以上となる。
【0173】
H3-2)そこで可変長重複排除モジュール33は、処理H2で定めた親チャンク1702から先頭の子チャンクc6を除いた残りの子チャンクc7単体を親チャンク1703として定め、当該親チャンク1703の識別子(ハッシュ値)を生成する(ステップ407)。この例では可変長重複排除モジュール33は、子チャンクc7(“by path is ope”)の識別子(ハッシュ値)c7.hash=HGから生成したハッシュ値HG’を、親チャンク1703の識別子(ハッシュ値)とする。
【0174】
H3-3)可変長重複排除モジュール33は、親チャンク1703の識別子HG’に基づき、チャンク一覧テーブル312に当該識別子HG’に対応するデータ断片が登録されているかを判定する(ステップ408)。図17に示すように、チャンク一覧テーブル312には、識別子HG’に対応するデータ断片が登録されている。このため、親チャンク1703に関するステップ408の判定結果は図17において矢印1713で示されるようにYes(登録済)となり、次の処理H4に進む。なお、図17では省略されているが、可変長重複排除モジュール33は処理H4に進む前に、文書112の文書名「文書#2」及び親チャンク1501の識別子HG’を文書構成テーブル311に登録する(ステップ412)。
【0175】
H4)
H4-1)可変長重複排除モジュール33は、前述の格納処理SY2で定めた親チャンク1601(つまり、識別子HXYにより識別されるデータ断片)と、上記処理H3で定めた親チャンク1703(つまり、識別子HG’により識別されるデータ断片)との間に子チャンクまたは子チャンクの列があるならば(ステップ413のNo)、その子チャンクまたは子チャンクの列を親チャンクと定めて、当該親チャンクの識別子(ハッシュ値)を生成する(ステップ501)。図17の例では、親チャンク1601と親チャンク1703との間に、子チャンクc5,c6が存在する。そこで可変長重複排除モジュール33は、子チャンクc5,c6を連結して親チャンク1704を定め、当該親チャンク1704の識別子(ハッシュ値)を生成する(ステップ501)。即ち可変長重複排除モジュール33は、連結する子チャンクc5(“cif”),c6(“ied ”)の識別子(ハッシュ値)c5.hash=HE,c6.hash=HFから生成したハッシュ値HEFを、親チャンク1704の識別子(ハッシュ値)とする。
【0176】
H4-2)可変長重複排除モジュール33は、親チャンク1704の識別子HEF及びデータ(データ断片)“cified ”を、図17において矢印1705で示すようにチャンク一覧テーブル312に登録する(ステップ502)。また図17では省略されているが、可変長重複排除モジュール33は、文書112の文書名「文書#2」及び親チャンク1704の識別子HEFを文書構成テーブル311に登録する(ステップ503)。
【0177】
I)格納処理SYその4
上述の格納処理SY3に続いて実行される、文書112を格納するための格納処理SYその4(以下、格納処理SY4と称する)について、図18を参照して説明する。なお、図18では、文書構成テーブル311は省略されている。
【0178】
I-1)可変長重複排除モジュール33は、格納処理SY3で登録済みであると判定された親チャンク1703の終端の位置から(ステップ505)、連結ウィンドウサイズW(W=10)以上となるところまで、子チャンクを順次定めていく(ステップ403〜406)。図18の例では、可変長重複排除モジュール33は、文書112の先頭より46,52,56文字目のところに切り出し点を定め、新たな子チャンクc8(“ned”),c9(“ for r”),c10(“ead”)を定めたものとする。
【0179】
以降の処理は格納処理SY1における、処理F-2〜F-3と同様であり、子チャンクc8,c9,c10を連結することにより親チャンク1801が定められる。図18の例では親チャンク1801の識別子HHIJに対応するデータ断片は、チャンク一覧テーブル312に登録されている(ステップ408のYes)。このため、親チャンク1801に関するステップ408の判定結果は図18において矢印1811で示されるようにYes(登録済)となり、次の処理Jに進む。この場合、チャンク一覧テーブル312は図18において矢印1802で示されるように、処理Iの前後で変わらない。なお、図18では省略されているが、可変長重複排除モジュール33は処理Jに進む前に、文書112の文書名「文書#2」及び親チャンク1801の識別子HHIJを文書構成テーブル311に登録する(ステップ503)。
【0180】
J)格納処理SYその5
上述の格納処理SY4に続いて実行される、文書112を格納するための格納処理SYその5(以下、格納処理SY5と称する)について、図19を参照して説明する。なお、図19では、文書構成テーブル311は省略されている。
【0181】
J1)
J1-1)可変長重複排除モジュール33は、格納処理SY4で定められた親チャンク1801の終端の位置から(ステップ505)、子チャンクを順次定めていく(ステップ403〜406)。図19の例では、子チャンクc11,c12が定められ、その結果、切り出し点が文書111の末尾に達したものとする(ステップ404)。この場合、可変長重複排除モジュール33は、切り出し点が、格納処理SY4で定められた親チャンク1801の終端の位置から連結ウィンドウサイズW(W=10)以上となるか否かに無関係に、子チャンクc11(“in”),c12(“g and”)を連結することにより親チャンク1901を定める(ステップ414)。
【0182】
J1-2)親チャンク1901の識別子(ハッシュ値)HKLに対応するデータ断片はチャンク一覧テーブル312に登録されている(ステップ415のYes)。このため、親チャンク1901に関するステップ415の判定結果は図19において矢印1911で示されるようにYes(登録済)となる。この場合、ステップ414で定められた親チャンク1901の識別子HKL及びデータ(データ断片)“ing and”をチャンク一覧テーブル312に登録する処理(ステップ416)は行われない。このためチャンク一覧テーブル312は図19において矢印1902で示されるように、処理Jの前後で変わらない。なお、図19では省略されているが、可変長重複排除モジュール33は、文書112の文書名「文書#2」及び親チャンク1501の識別子HKLを文書構成テーブル311に登録する(ステップ503)。これにより、文書112を格納するための格納処理SYは完了する。
【0183】
格納処理SXに続いて上述の格納処理SY(つまり格納処理SY1乃至SY5)が完了した後、つまり文書111,112の格納後における、文書構成テーブル311及びチャンク一覧テーブル312の状態を、文書112及び当該文書112から切り出された親チャンクの列と共に図20に示す。
【0184】
同様に、文書111,112の格納後における、文書構成テーブル311及びチャンク一覧テーブル312の状態を、文書111,112から切り出された親チャンクの列と共に図21に示す。文書111の格納後に文書112が格納される本実施形態では、当該文書112を格納するための格納処理XYにより、重複データを排除しながら当該文書112を登録されることが、図21からわかる。
【0185】
<文書取得処理>
次に、文書格納装置10における文書取得処理について、図22のフローチャートを参照して説明する。
まず、クライアント装置20から文書格納装置10にネットワーク30を介して文書取得指示が送られたものとする。この文書取得指示は、文書格納装置10から取得されるべき文書を指定する文書名を含んでいる。
【0186】
文書格納装置10に送られたクライアント装置20からの文書取得指示は、当該文書格納装置10の命令受け付けモジュール32で受け付けられる。命令受け付けモジュール32内の文書取得部320は、この文書取得指示が命令受け付けモジュール32で受け付けられると、当該文書取得指示で指定される文書名と対応付けて文書構成テーブル311に登録されている全てのチャンク(親チャンク)群の識別子を取得する(ステップ2201)。取得されたチャンク群の識別子の並び順は、前述したように、対応する文書におけるチャンク群の並びに一致する。
【0187】
文書取得部320は、文書構成テーブル311から識別子の群を取得すると、当該識別子の群とそれぞれ対応付けてチャンク一覧テーブル312に登録されているチャンク(データ断片)の群を取得する(ステップ2202)。
【0188】
文書取得部320は、チャンク一覧テーブル312から取得したチャンクの群に基づき、当該チャンクの群の並び順が、先に取得した当該チャンクの群の識別子の並び順に一致するように、クライアント装置20からの文書取得指示で指定された文書名の文書のデータを再構成する(ステップ2203)。
【0189】
命令受け付けモジュール32は、文書取得部320によって再構成された文書データを、クライアント装置20からの文書取得指示に対する応答として当該クライアント装置20に返す(ステップ2204)。
【0190】
ところで、クライアント装置20がユーザからの要求により、文書格納装置10から文書(文書データ)上のデータ断片を取得したい場合がある。クライアント装置20が文書格納装置10から文書上のデータ断片を取得するための方法として、当該文書の文書名に加えて、当該データ断片の当該文書上の位置及び当該データ断片の長さを指定する方法が知られている。文書格納装置10が、このような方法に適応するためには、クライアント装置20によって指定された文書名の文書の文書データを上述のように再構成した上で、当該文書データからクライアント装置20によって指定された位置・長さのデータ断片を取得する必要がある。
【0191】
そこで、例えば指定の文書名に対応付けてチャンク(親チャンク)の識別子を文書構成テーブル311に登録する際に、当該チャンクの対応する文書データ上での位置・長さを示す情報を当該チャンクの識別子に付加するとよい。このようにすると、この情報を参照して、この情報が付加されている識別子に対応付けてチャンク一覧テーブル312に保持されているチャンクを特定するだけで、指定の文書上の指定の位置・長さのデータ断片を取得することができる。
【0192】
<本実施形態のまとめ>
このように本実施形態では、文書格納装置10が、任意の文書データを、重複検出を行いながら、可変長のチャンク(親チャンクもしくは登録済み親チャンク、または第1のデータ断片)に分割するデータ分割装置として機能する。
【0193】
本実施形態によれば、子チャンク(第2のデータ断片)の長さを重複検出のオフセット間隔としながら、当該子チャンクの長さよりも長くなる可能性が高く、且つ登録の対象として用いられる可能性の高い親チャンク(第3のデータ断片)の長さで重複検出を行う構成とすることにより、従来技術と比較してより単純・高速な手法で、登録済みとなる親チャンク(第1のデータ断片)の数(つまり分割数)を少なくしながらも重複排除率を高く維持した、重複検出を行うことができる。
【0194】
また本実施形態によれば、分割の対象となるデータの一端から順に、子チャンク(第2のデータ断片)を決定しながら、それがある条件を満たしたときに、決定されている複数の子チャンクを連結して(1つの子チャンクが決定されているときは連結しないで)親チャンク(第3のデータ断片)を決定し、当該決定した親チャンクの重複の有無を検出することにより、分割の対象となるデータがストリーム状態に入力されるときに、高速に重複検出を行うことができる。
【0195】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。例えば、上記実施形態では、文書データを、当該文書データの先頭から当該文書データの末尾の方向に分割している。しかし、文書データを、当該文書データの末尾から当該文書データの先頭の方向に分割しても構わない。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【符号の説明】
【0196】
10…文書格納装置、20…クライアント装置、30…ネットワーク、31…文書格納部、32…命令受け付けモジュール(入力手段)、33…可変長重複排除モジュール、34…作業用メモリ、311…文書構成テーブル、312…チャンク一覧テーブル、320…文書取得部、331…子チャンク決定部(第2のデータ断片決定手段)、332…親チャンク決定部(第3のデータ断片決定手段)、333…識別子生成部、334…重複検出部、335…親チャンク登録部(第1のデータ断片決定手段)、336…制御部、341…文書バッファ、342…レジスタ部。

【特許請求の範囲】
【請求項1】
入力手段、第1のデータ断片決定手段、第2のデータ断片決定手段、第3のデータ断片決定手段、重複検出手段及び制御手段を含む装置において、任意のデータを、重複検出を行いながら、複数の、任意の長さの第1のデータ断片に分割するためのデータ分割方法であって、
前記任意のデータを前記入力手段が入力する入力ステップと、
前記入力された任意のデータのうち、未だ前記第1のデータ断片として決定されていない残りのデータ部分から、前記第2のデータ断片決定手段が任意の長さまたは予め定められた長さの第2のデータ断片を順次決定する第1の決定ステップと、
予め定められた第1の条件を満足する状態に達するまでに、前記第1のステップにおいて決定された1つの第2のデータ断片それ自体または複数の第2のデータ断片の組み合わせを、前記第3の断片決定手段が1つの第3のデータ断片として決定する第2の決定ステップと、
前記決定された第3のデータ断片の重複の有無を、当該決定された第3のデータ断片に一致するビット列の第1のデータ断片が既に決定されているかによって、前記重複検出手段が検出する重複検出ステップと、
前記重複が検出された場合、前記決定された第3のデータ断片を前記第1のデータ断片決定手段が前記第1のデータ断片として決定する第3の決定ステップと、
前記重複が検出されなかった場合、前記第1及び第2の決定ステップを再実行させることにより、前記第1の条件を満足する状態に達するまでに新たな1つの第2のデータ断片または新たな複数の第2のデータ断片を決定させると共に、当該新たな1つの第2のデータ断片それ自体、当該新たな複数の第2のデータ断片の組み合わせ、前記重複が検出されなかった第3のデータ断片の一部と当該新たな1つの第2のデータ断片との組み合わせ、または前記重複が検出されなかった第3のデータ断片の一部と当該新たな複数の第2のデータ断片との組み合わせを、前記第3のデータ断片決定手段により1つの新たな第3のデータ断片として決定させるための制御を、予め定められた第2の条件を満足する状態で前記重複が検出されるまで前記制御手段が繰り返す第1の制御ステップと、
前記第2の条件を満足する状態で前記第1の制御ステップが繰り返されても前記重複が検出されなかった場合、その間に決定された前記第2のデータ断片のうちの、前記第1の条件を満足する、1つの第2のデータ断片それ自体、または複数の第2のデータ断片の組み合わせを、前記第1のデータ断片決定手段が新たな第1のデータ断片として決定する第4の決定ステップと、
前記入力された任意のデータが全て前記第1のデータ断片に分割されるまで、前記制御手段が前記第1の制御ステップを繰り返すための第2の制御ステップと
を具備することを特徴とするデータ分割方法。
【請求項2】
前記第2のデータ断片は、前記残りのデータ部分の第1の端部から当該残りのデータ部分の第2の端部の方に向かって順に決定され、
前記第1の条件は、前記第1のステップにおいて決定された前記1つの第2のデータ断片の長さ、または前記第1のステップにおいて順次決定された前記複数の第2のデータ断片を連結した場合の、その連結後の当該複数の第2のデータ断片の長さに関する条件であり、
前記第1の条件を満足する状態に達するまでに、前記第1のステップにおいて前記複数の第2のデータ断片が決定された場合、当該複数の第2のデータ断片をその決定順に連結することにより、当該複数の第2のデータ断片の組み合わせとしての前記第3のデータ断片が決定される
ことを特徴とする請求項1記載のデータ分割方法。
【請求項3】
前記第2の決定ステップは、
前記重複が検出されなかった第3のデータ断片に含まれる、前記残りのデータ部分の前記第1の端部に最も近い側の少なくとも1つの第2のデータ断片を、当該第3のデータ断片から取り外すステップと、
前記第1の条件を満足する状態に達するまでに前記第1の決定ステップで決定された前記新たな1つの第2のデータ断片または前記新たな複数の第2のデータ断片を、前記少なくとも1つの第2のデータ断片が取り外された前記第3のデータ断片に組み込むことにより、新たな第3のデータ断片を決定するステップとを含む
ことを特徴とする請求項2記載のデータ分割方法。
【請求項4】
前記第2の条件の範囲で前記第1の制御ステップが繰り返されても前記重複が検出されなかった場合に前記新たな第1のデータ断片として決定される、前記1つの第2のデータ断片それ自体、または前記複数の第2のデータ断片の組み合わせは、最も最近に第1のデータ断片が決定された後に最初に決定された第3の断片であり、
前記第3の決定ステップは、前記第2の条件の範囲で前記第1の制御ステップが繰り返されることによって前記重複が検出された結果、前記第1のデータ断片が決定された場合、前回決定された第1のデータ断片と今回決定された第1のデータ断片との間に挟まれている、未だ第1のデータ断片として決定されていないデータ断片を、前記第1のデータ断片決定手段が新たな第1のデータ断片として決定するステップを含む
ことを特徴とする請求項1乃至3のいずれか記載のデータ分割方法。
【請求項5】
前記第1の条件は、
前記第1のステップにおいて決定された前記1つの第2のデータ断片の長さ、または前記第1のステップにおいて順次決定された前記複数の第2のデータ断片を連結した場合の、その連結後の当該複数の第2のデータ断片の長さが、
予め定められた基準の長さを超えること、
予め定められた基準の長さに等しくなること、
予め定められた基準の長さに最も近くなること、
または予め定められた基準の長さを超えない最大値なること
のいずれか1つである
ことを特徴とする請求項4記載のデータ分割方法。
【請求項6】
前記第2の条件は、前記残りのデータ部分の前記第1の端部から、最も最近に重複が検出されなかった第3のデータ断片の当該第1の端部から遠い側の端部までの長さであるデータ断片長に関する条件であることを特徴とする請求項4記載のデータ分割方法。
【請求項7】
前記第2の条件は、前記データ断片長が、
予め定められた基準の長さを超えること、
予め定められた基準の長さに等しくなること、
予め定められた基準の長さに最も近くなること、
または予め定められた基準の長さを超えない最大値なること
のいずれか1つである
ことを特徴とする請求項6記載のデータ分割方法。
【請求項8】
任意のデータを、重複検出を行いながら、複数の、任意の長さの第1のデータ断片に分割するためのデータ分割装置において、
前記任意のデータを入力する入力手段と、
前記入力された任意のデータのうち、未だ前記第1のデータ断片として決定されていない残りのデータ部分から、任意の長さまたは予め定められた長さの第2のデータ断片を順次決定する第2のデータ断片決定手段と、
予め定められた第1の条件を満足する状態に達するまでに、前記第2のデータ断片決定手段によって決定された1つの第2のデータ断片それ自体または複数の第2のデータ断片の組み合わせを、1つの第3のデータ断片として決定する第3のデータ断片決定手段と、
前記決定された第3のデータ断片の重複の有無を、当該決定された第3のデータ断片に一致するビット列の第1のデータ断片が既に決定されているかによって検出する重複検出手段と、
前記重複が検出された場合、前記決定された第3のデータ断片を前記第1のデータ断片として決定する第1のデータ断片決定手段と、
前記重複が検出されなかった場合、前記第1の条件を満足する状態に達するまでに前記第2のデータ断片決定手段によって新たな1つの第2のデータ断片または新たな複数の第2のデータ断片を決定させると共に、前記新たな1つの第2のデータ断片それ自体、前記新たな複数の第2のデータ断片の組み合わせ、前記重複が検出されなかった第3のデータ断片の一部と当該新たな1つの第2のデータ断片との組み合わせ、または前記重複が検出されなかった第3のデータ断片の一部と当該新たな複数の第2のデータ断片との組み合わせを、前記第3のデータ断片決定手段によって1つの新たな第3のデータ断片として決定させるための制御を、予め定められた第2の条件を満足する状態で前記重複が検出されるまで繰り返し、この制御の繰り返しを、前記入力された任意のデータが全て前記第1のデータ断片に分割されるまで更に繰り返す制御手段とを具備し、
前記第1のデータ断片決定手段は、前記第2の条件を満足する状態で前記制御が繰り返されても前記重複が検出されなかった場合、その間に決定された前記第2のデータ断片のうちの、前記第1の条件を満足する、1つの第2のデータ断片それ自体、または複数の第2のデータ断片の組み合わせを、新たな第1のデータ断片として決定する
ことを特徴とするデータ分割装置。
【請求項9】
前記第2のデータ断片決定手段は、前記残りのデータ部分の第1の端部から当該残りのデータ部分の第2の端部の方に向かって前記第2のデータ断片を順に決定し、
前記第1の条件は、前記第2のデータ断片決定手段によって決定された前記1つの第2のデータ断片の長さ、または前記第2のデータ断片決定手段によって順次決定された前記複数の第2のデータ断片を連結した場合の、その連結後の当該複数の第2のデータ断片の長さに関する条件であり、
前記第3のデータ断片決定手段は、前記第1の条件を満足する状態に達するまでに、前記第2のデータ断片決定手段によって前記複数の第2のデータ断片が決定された場合、当該複数の第2のデータ断片をその決定順に連結することにより、当該複数の第2のデータ断片の組み合わせとしての前記第3のデータ断片を決定する
ことを特徴とする請求項8記載のデータ分割装置。
【請求項10】
前記第3のデータ断片決定手段は、前記重複が検出されなかった第3のデータ断片に含まれる、前記残りのデータ部分の前記第1の端部に最も近い側の少なくとも1つの第2のデータ断片を、当該第3のデータ断片から取り外し、前記第1の条件を満足する状態に達するまでに前記第2のデータ断片決定手段によって決定された前記新たな1つの第2のデータ断片または前記新たな複数の第2のデータ断片を、前記少なくとも1つの第2のデータ断片が取り外された前記第3のデータ断片に組み込むことにより、新たな第3のデータ断片を決定することを特徴とする請求項9記載のデータ分割装置。
【請求項11】
前記第2の条件の範囲で前記制御が繰り返されても前記重複が検出されなかった場合に、前記新たな第1のデータ断片として決定される、前記1つの第2のデータ断片それ自体、または前記複数の第2のデータ断片の組み合わせは、最も最近に第1のデータ断片が決定された後に最初に決定された第3の断片であり、
前記第1のデータ断片決定手段は、前記第2の条件の範囲で前記制御が繰り返されることによって前記重複が検出された結果、前記第1のデータ断片を決定した場合、前回決定した第1のデータ断片と今回した第1のデータ断片との間に挟まれている、未だ第1のデータ断片として決定されていないデータ断片を、新たな第1のデータ断片として決定する ことを特徴とする請求項8乃至10のいずれかに記載のデータ分割装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate


【公開番号】特開2011−76421(P2011−76421A)
【公開日】平成23年4月14日(2011.4.14)
【国際特許分類】
【出願番号】特願2009−227887(P2009−227887)
【出願日】平成21年9月30日(2009.9.30)
【出願人】(000003078)株式会社東芝 (54,554)
【出願人】(301063496)東芝ソリューション株式会社 (1,478)
【Fターム(参考)】