(57)【特許請求の範囲】
【請求項１】
複数のデータを記憶するＳＬＣ型のフラッシュメモリである記憶部への第１のデータの書き込み要求を受け付け、
前記書き込み要求を受け付けた場合、前記複数のデータのうちのいずれかの第２のデータおよび前記第１のデータの排他的論理和を連長符号化に基づいて符号化した符号化データのサイズが、所定の閾値より小さいか否かを判定し、
前記符号化データのサイズが前記所定の閾値より小さいと判定した場合、前記第２のデータの位置を示す情報と、前記符号化データとを対応付けて前記記憶部に格納し、
前記複数のデータの各データおよび前記第１のデータの排他的論理和を連長符号化に基づいて符号化した各符号化データのサイズの全てが前記所定の閾値より大きいと判定した場合、前記第１のデータを２進数で表記した際の１の数が前記第１のデータのビット数の半分未満であれば、前記第１のデータをビット反転した反転データを前記記憶部に格納するとともに、前記反転データの位置を示す情報と、連長符号化により全てのビットが１であることを示す符号化データとを対応付けて前記記憶部に格納する、
制御部を有することを特徴とする情報記憶装置。
【請求項２】
前記書き込み要求は、前記第１のデータの書き込み先のアドレスと、前記第１のデータとを含み、
前記制御部は、
前記符号化データのサイズが前記所定の閾値より小さいと判定した場合、さらに、前記符号化データの位置を示す情報と、前記アドレスとを対応付けて前記記憶部に格納する、
ことを特徴とする請求項１に記載の情報記憶装置。
【請求項３】
前記記憶部は、
前記複数のデータと、前記複数のデータのいずれかのデータの位置を示す情報に対応付いた前記いずれかのデータおよび前記いずれかのデータに類似するデータの排他的論理和を連長符号化に基づいて符号化した符号化データと、アドレスに対応付いた前記複数のデータのいずれかのデータの位置を示す情報または前記符号化データの位置を示す情報と、を記憶し、
前記制御部は、
読み出し先のアドレスを含む読み出し要求を受け付け、
前記記憶部を参照して、前記読み出し先のアドレスに対応するデータが、前記複数のデータのいずれかのデータか符号化データかを判定し、
前記読み出し先のアドレスに対応するデータが符号化データであると判定した場合、前記読み出し先のアドレスに対応する符号化データの位置を示す情報により特定される読み出し先の符号化データを復号し、
前記読み出し先の符号化データを復号したデータと、前記読み出し先の符号化データに対応する前記複数のデータのいずれかのデータの位置を示す情報により特定される読み出し先のデータとの排他的論理和を算出する、
ことを特徴とする請求項１または２に記載の情報記憶装置。
【請求項４】
コンピュータが、
複数のデータを記憶するＳＬＣ型のフラッシュメモリである記憶部への第１のデータの書き込み要求を受け付け、
前記書き込み要求を受け付けた場合、前記複数のデータのうちのいずれかの第２のデータおよび前記第１のデータの排他的論理和を連長符号化に基づいて符号化した符号化データのサイズが、所定の閾値より小さいか否かを判定し、
前記符号化データのサイズが前記所定の閾値より小さいと判定した場合、前記第２のデータの位置を示す情報と、前記符号化データとを対応付けて前記記憶部に格納し、
前記複数のデータの各データおよび前記第１のデータの排他的論理和を連長符号化に基づいて符号化した各符号化データのサイズの全てが前記所定の閾値より大きいと判定した場合、前記第１のデータを２進数で表記した際の１の数が前記第１のデータのビット数の半分未満であれば、前記第１のデータをビット反転した反転データを前記記憶部に格納するとともに、前記反転データの位置を示す情報と、連長符号化により全てのビットが１であることを示す符号化データとを対応付けて前記記憶部に格納する、
処理を実行することを特徴とする重複除去方法。
【請求項５】
コンピュータに、
複数のデータを記憶するＳＬＣ型のフラッシュメモリである記憶部への第１のデータの書き込み要求を受け付け、
前記書き込み要求を受け付けた場合、前記複数のデータのうちのいずれかの第２のデータおよび前記第１のデータの排他的論理和を連長符号化に基づいて符号化した符号化データのサイズが、所定の閾値より小さいか否かを判定し、
前記符号化データのサイズが前記所定の閾値より小さいと判定した場合、前記第２のデータの位置を示す情報と、前記符号化データとを対応付けて前記記憶部に格納し、
前記複数のデータの各データおよび前記第１のデータの排他的論理和を連長符号化に基づいて符号化した各符号化データのサイズの全てが前記所定の閾値より大きいと判定した場合、前記第１のデータを２進数で表記した際の１の数が前記第１のデータのビット数の半分未満であれば、前記第１のデータをビット反転した反転データを前記記憶部に格納するとともに、前記反転データの位置を示す情報と、連長符号化により全てのビットが１であることを示す符号化データとを対応付けて前記記憶部に格納する、
処理を実行させることを特徴とする重複除去プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報記憶装置、重複除去方法、および重複除去プログラムに関する。
【背景技術】
【０００２】
従来、ストレージ内の複数のデータの中から同一のデータを検出し、複数の同一のデータのうち１つのマスターデータを残して他のデータを除去し、マスターデータへの参照と、マスターデータへの参照数で管理する重複除去技術がある。
【０００３】
関連する先行技術として、例えば、関連情報として提供し得る関連情報候補のうち、配信情報と重複した情報提供になるもの、または、配信情報と重複した情報提供になる可能性が高いものを除外して関連情報を決定するものがある。また、類似した基準事例に対して近傍事例探索が行われるように、基準事例をソートして探索の順番を決め、最初の基準事例に対する近傍事例探索時に基準事例周辺に存在していた探索事例をキャッシュとして記憶し、記憶した探索事例から探索する技術がある。また、参照点が入力された際、木構造インデックスのノードへのポインタとそのノードに対応する多次元ベクトル空間内の点と参照点との距離評価値の組を格納した管理情報を参照し木構造インデックスをルートノードから順に辿り、管理情報を更新する技術がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−３３１０１４号公報
【特許文献２】特開２００４−３２６６３６号公報
【特許文献３】特開平１０−３０１９３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術によれば、複数のデータの中から、類似のデータを重複するものとみなして除去する処理を、類似のデータの判定の精度を担保したまま、処理にかかる時間を短縮することは難しい。例えば、類似のデータであるか否かを高速に判定する方法として、複数のデータのうちのあるデータと、新たなデータとを数値とみなし、あるデータと新たなデータとの算術減算を実行して得られた値によって類似であるか否かを判定することが考えられる。しかしながら、この場合、ＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）側の少しのビットの差異が、算術減算の結果に大きく影響を与えてしまうため、類似のデータの判定の精度が劣化することになる。
【０００６】
１つの側面では、本発明は、類似のデータを除去する処理にかかる時間を短縮することができる情報記憶装置、重複除去方法、および重複除去プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一側面によれば、複数のデータを記憶する記憶部への第１のデータの書き込み要求を受け付け、書き込み要求を受け付けた場合、複数のデータのうちのいずれかの第２のデータおよび第１のデータの排他的論理和を連長符号化に基づいて符号化した符号化データのサイズが、所定の閾値より小さいか否かを判定し、符号化データのサイズが所定の閾値より小さいと判定した場合、第２のデータの位置を示す情報と、符号化データとを対応付けて記憶部に格納する情報記憶装置、重複除去方法、および重複除去プログラムが提案される。
【発明の効果】
【０００８】
本発明の一態様によれば、類似のデータを除去する処理にかかる時間を短縮することができるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】図１は、本実施の形態にかかる情報記憶装置１０１の動作例を示す説明図である。
【図２】図２は、ストレージシステム２００の構成例を示す説明図である。
【図３】図３は、情報記憶装置１０１のハードウェア構成例を示す説明図である。
【図４】図４は、情報記憶装置１０１の機能構成例を示す説明図である。
【図５】図５は、記憶部１０２の記憶内容の一例を示す説明図である。
【図６】図６は、実施例１におけるデータ読み出し処理手順の一例を示すフローチャートである。
【図７】図７は、実施例１におけるデータ書き込み処理手順の一例を示すフローチャートである。
【図８】図８は、ビット反転した際の類似度の説明図である。
【図９】図９は、実施例２におけるデータ書き込み処理手順の一例を示すフローチャート（その１）である。
【図１０】図１０は、実施例２におけるデータ書き込み処理手順の一例を示すフローチャート（その２）である。
【図１１】図１１は、実施例２におけるデータ書き込み処理手順の一例を示すフローチャート（その３）である。
【発明を実施するための形態】
【００１０】
以下に図面を参照して、開示の情報記憶装置、重複除去方法、および重複除去プログラムの実施の形態を詳細に説明する。
【００１１】
図１は、本実施の形態にかかる情報記憶装置１０１の動作例を示す説明図である。情報記憶装置１０１は、データを記憶するコンピュータである。近年のビックデータの増大は、ストレージの容量の増大速度を上回っており、データの重複除去技術と圧縮技術は、ストレージの利用効率を向上させる技術である。
【００１２】
重複除去技術とは、ストレージ内の複数のデータの中から同一のデータを検出し、複数の同一のデータのうち１つのマスターデータを残して他のデータを除去し、マスターデータへの参照と、マスターデータへの参照数で管理する技術である。
【００１３】
ここで、重複除去技術における「同一のデータ」を、「類似のデータ」に条件を緩和し、マスターデータへの参照と、マスターデータとの差分とを管理することができれば、条件を緩和した分、同一のデータを検出すること以上に重複箇所を検出することができる。そして、より多くの重複箇所を検出することにより、ストレージの利用効率をより向上させることができる。
【００１４】
また、ストレージ用途では、バックアップやスナップショットの作成において、データへの書き込みが発生するまでコピーを遅延するｃｏｐｙ−ｏｎ−ｗｒｉｔｅ処理が行われる。ｃｏｐｙ−ｏｎ−ｗｒｉｔｅ処理では、データ管理単位を大きくすると、元データｄと書き込みデータｄ’とで、連続した一部分だけ内容が異なるという現象が発生する。このように、ストレージ用途では、ビット単位で考慮した際に、ｄとｄ’との違いが局在化する場合があり、差分が小さく、差分とｄからｄ’を高速に復元でき、類似度も容易に算出できることが求められる。
【００１５】
具体的な数値として、ストレージの利用効率を向上させるためには、差分と書き込みデータのサイズ比をある程度大きくすることが求められる。例えば、データサイズを４［ＫｉＢ］とすると、ビット長は、３２Ｋとなる。また、ストレージの記憶容量が、１［ＴｉＢ］である場合、異なるデータは、１［ＴｉＢ］／４［ＫｉＢ］＝２＾２８個存在することになる。そして、例えば、データ１つあたり、自身を含め８個の類似データがあると仮定すると、全体で、２＾２５個、約３３００万のマスターデータが存在することになる。そして、新しいデータを追加する場合には、既存の約３３００万のマスターデータと、新たなデータとの３２Ｋのビットを比較し、類似度と差分計算を行うことになるため、類似度と差分計算とが、容易に算出できることが求められる。
【００１６】
しかしながら、類似のデータを重複するものとみなして除去する処理、類似のデータの判定の精度を維持したまま、処理にかかる時間を短縮することは難しい。例えば、類似のデータであるか否かを高速に判定する方法として、記憶済みの複数のデータのうちのあるデータｄと、新たなデータｄ’とを数値とみなし、データｄ、ｄ’の算術減算を実行して得られた値によって類似であるか否かを判定することが考えられる。しかしながら、この場合、差異がＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）側に集中すると類似と判定する一方で、ＭＳＢ側の少しのビットの差異は、算術減算の結果に大きく影響を与えて、類似していないと判定するため、類似のデータの判定の精度が劣化することになる。また、ストレージ用途、特に、ｃｏｐｙ−ｏｎ−ｗｒｉｔｅ処理において、ＬＳＢ側に差異が偏ることは期待できない。
【００１７】
また、類似のデータを検出した際に、差分を管理することになるが、差分のデータサイズがｄ’のデータサイズより小さくできることが求められる。もし、差分のデータサイズがｄ’のデータサイズより大きい場合、差分を取らずにｄ’をそのまま蓄積した方が有利であるためである。例えば、ｄとｄ’とをビット列として解釈し、類似度を、ｄとｄ’のハミング距離とし、ビット単位でｄとｄ’とを解釈した際の異なるビットの位置の集合とすることが考えられる。この場合、同一ハミング距離のデータは、同程度の類似であると判断することができるが、差分がｄ’のデータサイズより大きくなる場合がある。
【００１８】
そこで、本実施の形態では、ｄとｄ’の排他的論理和を連長符号化（ＲＬＥ：Ｒｕｎ  Ｌｅｎｇｔｈ  Ｅｎｃｏｄｉｎｇ）した符号化データのサイズが所定の閾値未満ならば、ｄの位置情報と符号化データとを対応付けて記憶する方法について説明する。具体的に、本実施の形態では、下記（１）式が満たされた場合、ｄとｄ’が類似するものとする。
【００１９】
ｓｉｚｅ（ＲＬＥ（ｘｏｒ（ｄ，ｄ’）））＜δ  …（１）
【００２０】
ここで、ｄとｄ’とは、固定長で同一サイズのバイナリデータである。また、ｘｏｒ（）は、ビットワイズの排他的論理和を行う操作である。ＲＬＥ（）は、連長符号化を行う操作である。ｓｉｚｅ（）は、ビット長を求める操作である。δは、類似を判定する所定の閾値であり、正の整数となる。δは、情報記憶装置１０１の管理者によって、ｄのサイズ等を考慮して予め設定される。
【００２１】
ここで、ｘｏｒ（）、ＲＬＥ（）、ｓｉｚｅ（）についてより詳細に説明する。ｘｏｒ（ｄ，ｄ’）は、ｄとｄ’との差分を求める操作となる。ｘｏｒ（ｄ，ｄ’）で得られる値は、ｄ、ｄ’と同一の固定長サイズである。ｄとｄ’とが同一内容である場合、ｘｏｒ（ｄ，ｄ’）は、００…０となる。ｘｏｒ（ｄ，ｄ’）で得られる値をビット単位で見た場合、同じビットは０となり、異なるビットは１となる。
【００２２】
ＲＬＥ（）は、連長符号化を行う操作である。出力結果には、０か１かを示すビットと、そのビットが何個続くかを示す数値との組が繰り返されたデータとして出力される。例えば、０がＮ回連続で並ぶデータが入力された場合、出力結果は、「０Ｎ」で表記され、１がＮ回連続で並ぶデータが入力された場合、出力結果は、「１Ｎ」で表記される。以下、０か１かを示すビットを、ビットが何個続くかを示す数値との区別をつけるため、０を示すビットを「ゼロ」と表記し、１を示すビットを「イチ」と表記する。
【００２３】
例えば、０がＮ回連続で並ぶデータが入力された場合、出力結果は、「ゼロＮ」で表記される。そして、この出力結果のデータ長は、（１＋ｌｏｇ（Ｎ））の小数以下を切り上げた数値分のビットである。ここで、ｌｏｇ（）は、底を２とした対数である。すなわち、「ゼロ」が１ビットで表現され、Ｎを２進数表記すると、ｌｏｇ（Ｎ）の小数以下を切り上げた数値分のビットで表現されるためである。例えば、Ｎ＝３では、「ゼロ３」のデータ長は、３となる。
【００２４】
ｓｉｚｅ（）は、符号長を求める操作である。例えば、ｓｉｚｅ（ゼロＮ）＝１＋ｌｏｇ（Ｎ）の小数以下を切り上げた数値となる。以上により、（１）式を文章にすると、「差分情報の情報量が、与えられた所定の閾値δより小さい」というものである。以下において、類似度の算出例を示す。また、以下の説明では、ｓｉｚｅ（）を、｜｜と表記する。
【００２５】
｜ＲＬＥ（ｘｏｒ（０００，１１１）｜＝｜ＲＬＥ（１１１）｜＝｜イチ３｜＝３
｜ＲＬＥ（ｘｏｒ（０００，０００）｜＝｜ＲＬＥ（０００）｜＝｜ゼロ３｜＝３
｜ＲＬＥ（ｘｏｒ（０１０，１０１）｜＝｜ＲＬＥ（１１１）｜＝｜イチ３｜＝３
｜ＲＬＥ（ｘｏｒ（００１，００１）｜＝｜ＲＬＥ（００１）｜＝｜ゼロ２イチ１｜＝５
【００２６】
このように、本実施の形態における類似度の特徴は、ビットワイズの違いが局所的に集中している場合、類似度が高いと判断される。また、ｄとｄ’との類似度が、ｄとｄ’をビット反転したデータとの類似度と同一であるという特徴もある。この特徴については、図８で詳細に説明する。
【００２７】
次に、本実施の形態における類似度を用いた情報記憶装置１０１の動作例について、図１を用いて説明する。まず、情報記憶装置１０１は、複数のデータを記憶する記憶部１０２を有する。より具体的には、記憶部１０２は、データ格納域テーブルｖｏｌを有し、複数のデータは、データ格納域テーブルｖｏｌに含まれる。データ格納域テーブルｖｏｌの記憶内容の一例は、図５で示す。
【００２８】
情報記憶装置１０１は、図１の（１）で示すように、記憶部１０２への第１のデータとして、データｄ１の書き込み要求を、情報記憶装置１０１を利用する装置から受け付ける。図１に示すデータｄ１は、「１１０１０００１０１１０」である。
【００２９】
次に、情報記憶装置１０１は、図１の（２）で示すように、データ格納域テーブルｖｏｌに含まれる複数のデータのうちのいずれかの第２のデータとして、データｄ２およびデータｄ１の排他的論理和を算出する。図１の例では、データｄ２は、「１１０１００１１１０００」である。従って、情報記憶装置１０１は、データｄ２およびデータｄ１の排他的論理和を算出し、データｄ＿ｘｏｒが得られる。データｄ＿ｘｏｒは、「００００００１０１１１０」となる。
【００３０】
そして、情報記憶装置１０１は、図１の（３）で示すように、データｄ＿ｘｏｒを連長符号化に基づいて符号化し、符号化データｄ＿ｒｌｅを得る。符号化データｄ＿ｒｌｅは、「ゼロ６イチ１ゼロ１イチ３ゼロ０」となる。
【００３１】
次に、情報記憶装置１０１は、図１の（４）で示すように、符号化データｄ＿ｒｌｅのサイズが、所定の閾値δより小さいか否かを判定する。図１で示すように、符号化データｄ＿ｒｌｅのサイズは、１３となり、情報記憶装置１０１は、１３が所定の閾値δより小さいか否かを判定する。
【００３２】
図１の例では、１３が所定の閾値δより小さいとする。この場合、情報記憶装置１０１は、図１の（５）で示すように、データｄ２の位置を示す情報ｐ＿ｄ２と、符号化データｄ＿ｒｌｅとを対応付けて記憶部１０２に格納する。より具体的には、情報記憶装置１０１は、データｄ２の位置を示す情報と、符号化データｄ＿ｒｌｅとを対応付けて、記憶部１０２に含まれる差分データ格納域テーブルｄｉｆｆに格納する。差分データ格納域テーブルｄｉｆｆの記憶内容の一例は、図５で示す。また、情報ｐ＿ｄ２は、例えば、データｄ２のデータ格納域テーブルｖｏｌのインデックス番号でもよいし、データｄ２が記憶されたＬＢＡ（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓｉｎｇ）の値でもよい。
【００３３】
また、１３が所定の閾値δ以上である場合、情報記憶装置１０１は、データ格納域テーブルｖｏｌに含まれる複数のデータのうちのいずれかの第２のデータとして、データｄ２とは異なるデータとデータｄ１とに対して、図１に示した（２）〜（４）を行う。
【００３４】
以上により、情報記憶装置１０１は、差分の大きさを示す符号化データのサイズが高速に得られるため、類似データを高速に重複除去することができる。また、類似度に、排他的論理和を利用しているため、０および１の論理が全く真逆に近いデータも類似度が高いと判定される。この結果、情報記憶装置１０１は、重複度を向上させることができる。次に、情報記憶装置１０１が含まれるシステムの構成例について、図２を用いて説明する。
【００３５】
図２は、ストレージシステム２００の構成例を示す説明図である。ストレージシステム２００は、情報記憶装置１０１と、サーバ２０１とを含む。情報記憶装置１０１と、サーバ２０１とは、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）等のネットワーク２０２により接続される。
【００３６】
サーバ２０１は、情報記憶装置１０１を利用するホストとなるコンピュータである。例えば、サーバ２０１は、例えば、Ｗｅｂサーバや、アプリケーションサーバである。次に、情報記憶装置１０１のハードウェア構成を、図３を用いて説明する。
【００３７】
図３は、情報記憶装置１０１のハードウェア構成例を示す説明図である。図３において、情報記憶装置１０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０１と、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０３と、を含む。また、情報記憶装置１０１は、ディスクドライブ３０４およびディスク３０５と、通信インターフェース３０６と、を含む。また、ＣＰＵ３０１〜ディスクドライブ３０４、通信インターフェース３０６はバス３０７によってそれぞれ接続される。
【００３８】
ＣＰＵ３０１は、情報記憶装置１０１の全体の制御を司る演算処理装置である。ＲＯＭ３０２は、ブートプログラムなどのプログラムを記憶する不揮発性メモリである。ＲＡＭ３０３は、ＣＰＵ３０１のワークエリアとして使用される揮発性メモリである。
【００３９】
ディスクドライブ３０４は、ＣＰＵ３０１の制御に従ってディスク３０５に対するデータのリードおよびライトを制御する制御装置である。ディスクドライブ３０４には、例えば、磁気ディスクドライブ、光ディスクドライブ、ソリッドステートドライブなどを採用することができる。ディスク３０５は、ディスクドライブ３０４の制御で書き込まれたデータを記憶する不揮発性メモリである。例えばディスクドライブ３０４が磁気ディスクドライブである場合、ディスク３０５には、磁気ディスクを採用することができる。また、ディスクドライブ３０４が光ディスクドライブである場合、ディスク３０５には、光ディスクを採用することができる。また、ディスクドライブ３０４がソリッドステートドライブである場合、ディスク３０５には、半導体素子によって形成された半導体メモリ、いわゆる半導体ディスクを採用することができる。
【００４０】
通信インターフェース３０６は、ネットワーク２０２と内部のインターフェースを司り、他の装置からのデータの入出力を制御する制御装置である。具体的に、通信インターフェース３０６は、通信回線を通じてネットワーク２０２を介して他の装置に接続される。通信インターフェース３０６には、例えば、モデムやＬＡＮアダプタなどを採用することができる。
【００４１】
また、情報記憶装置１０１の管理者が、情報記憶装置１０１を直接操作する場合、情報記憶装置１０１は、ディスプレイ、キーボード、マウスといったハードウェアを有してもよい。また、サーバ２０１も、情報記憶装置１０１と同様のハードウェアを有する。
【００４２】
（情報記憶装置１０１の機能構成例）
図４は、情報記憶装置１０１の機能構成例を示す説明図である。情報記憶装置１０１は、制御部４００を有する。制御部４００は、ユーザＩＯ（Ｉｎｐｕｔ  Ｏｕｔｐｕｔ）制御部４０１と、排他的論理和算出部４０２と、連長符号化部４０３と、類似判定部４０４と、格納部４０５と、格納先判定部４０６と、復号部４０７と、ＧＣ（Ｇａｒｂａｇｅ  Ｃｏｌｌｅｃｔｉｏｎ）制御部４０８とを含む。制御部４００は、記憶装置に記憶されたプログラムをＣＰＵ３０１が実行することにより、各部の機能を実現する。記憶装置とは、具体的には、例えば、図３に示したＲＯＭ３０２、ＲＡＭ３０３、ディスク３０５などである。また、各部の処理結果は、ＣＰＵ３０１のレジスタや、ＣＰＵ３０１のキャッシュメモリ、ＲＡＭ３０３等に格納される。
【００４３】
また、情報記憶装置１０１は、記憶部１０２にアクセス可能である。記憶部１０２は、ＲＡＭ３０３、ディスク３０５といった記憶装置に格納される。そして、記憶部１０２は、データ格納域テーブルｖｏｌと、差分データ格納域テーブルｄｉｆｆと、アドレス索引テーブルｔｍａｐとを有する。データ格納域テーブルｖｏｌは、複数のデータを記憶する。差分データ格納域テーブルｄｉｆｆは、データ格納域テーブルｖｏｌが記憶する複数のデータのいずれかのデータの位置を示す情報に対応付いた、前述のいずれかのデータおよび前述のいずれかのデータに類似するデータの排他的論理和の符号化データを記憶する。アドレス索引テーブルｔｍａｐは、サーバ２０１が認識するアドレスに対応付いた、データ格納域テーブルｖｏｌが記憶する複数のデータのいずれかのデータ、または、差分データ格納域テーブルｄｉｆｆが記憶する符号化データの位置を示す情報を記憶する。アドレス索引テーブルｔｍａｐと、データ格納域テーブルｖｏｌと、差分データ格納域テーブルｄｉｆｆの記憶内容の一例は、図５で示す。
【００４４】
ユーザＩＯ制御部４０１は、サーバ２０１から、読み出し、書き込み等のＩＯ要求を受け付ける。また、ＩＯ要求の完了後、ユーザＩＯ制御部４０１は、要求に対する応答をサーバ２０１に送信する。
【００４５】
サーバ２０１から書き込み要求を受け付けた際の処理について説明する。ユーザＩＯ制御部４０１は、記憶部１０２への第１のデータの書き込み要求を受け付ける。第１のデータの書き込み要求には、第１のデータの書き込み先のアドレスと、第１のデータとが含まれる。書き込み時の処理としては、本実施の形態では、実施例１の方法と、実施例２の方法とがある。まず、書き込み時の処理における実施例１の方法に関する各部の機能について説明する。
【００４６】
排他的論理和算出部４０２は、第１のデータの書き込み要求を受け付けた場合、複数のデータのうちのいずれかの第２のデータおよび第１のデータの排他的論理和を算出する。
【００４７】
連長符号化部４０３は、排他的論理和算出部４０２が算出した排他的論理和を、連長符号化に基づいて符号化する。
【００４８】
類似判定部４０４は、連長符号化部４０３が符号化した符号化データのサイズが、所定の閾値δより小さいか否かを判定する。
【００４９】
格納部４０５は、符号化データのサイズが所定の閾値δより小さいと類似判定部４０４が判定した場合、第２のデータの位置を示す情報と、符号化データとを対応付けて差分データ格納域テーブルｄｉｆｆに格納する。
【００５０】
また、格納部４０５は、符号化データのサイズが所定の閾値より小さいと類似判定部４０４が判定した場合、さらに、符号化データの位置を示す情報と、書き込み要求に含まれたアドレスとを対応付けてアドレス索引テーブルｔｍａｐに格納する。
【００５１】
また、排他的論理和算出部４０２〜類似判定部４０４は、データ格納域テーブルｖｏｌの複数のデータの各データについて、各データおよび第１のデータの排他的論理和の符号化を行って、符号化データのサイズが、所定の閾値δより小さいか否かを判定してもよい。そして、格納部４０５は、サイズが所定の閾値δより小さいと類似判定部４０４が判定した符号化データのうち、サイズが最小の符号化データを選択する。そして、格納部４０５は、選択した符号化データと、この符号化データに対応する第２のデータの位置を示す情報とを対応付けて、差分データ格納域テーブルｄｉｆｆに格納する。
【００５２】
また、排他的論理和算出部４０２〜類似判定部４０４は、所定の閾値δより小さい第２のデータが所定の個数見つかるまで、符号化データのサイズが、所定の閾値δより小さいか否かを判定してもよい。そして、格納部４０５は、サイズが所定の閾値δより小さいと類似判定部４０４が判定した所定の個数の符号化データのうち、サイズが最小の符号化データを選択する。そして、格納部４０５は、選択した符号化データと、この符号化データに対応する第２のデータの位置を示す情報とを対応付けて、差分データ格納域テーブルｄｉｆｆに格納する。
【００５３】
また、格納部４０５は、データ格納域テーブルｖｏｌの複数のデータの全てのデータについて、符号化データのサイズが、所定の閾値δ以上であると類似判定部４０４が判定した場合、第１のデータをデータ格納域テーブルｖｏｌに格納する。また、この場合、格納部４０５は、第１のデータの位置を示す情報と、書き込み要求に含まれたアドレスとを対応付けてアドレス索引テーブルｔｍａｐに格納する。
【００５４】
次に、書き込み時の処理における実施例２の方法に関する各部の機能について説明する。実施例２の方法は、図１で説明した、ｄとｄ’との類似度が、ｄとｄ’をビット反転したデータとの類似度と同一であるという特徴を利用する。具体的には、ディスク３０５がＳＬＣ（Ｓｉｎｇｌｅ  Ｌｅｖｅｌ  Ｃｅｌｌ）型フラッシュメモリである場合、ＳＬＣ型フラッシュメモリは、ビット１を表現する電圧レベルと、ビット０を表現する電圧レベルとが異なる。ここで、ＳＬＣ型フラッシュメモリとは、１つのセルの浮遊ゲートにある電子の蓄積量がＨｉかＬｏｗかで１ビットの情報を記録する方式のフラッシュメモリである。そして、ビット１は、ビット０に比べて、低消費電力、低エラー率でアクセスすることが可能である。実施例２の方法については、図８〜図１１でより詳細に説明する。
【００５５】
類似判定部４０４は、書き込み要求を受け付けた場合、複数のデータの各データおよび第１のデータの排他的論理和を連長符号化に基づいて符号化した各符号化データのサイズが、所定の閾値δより大きいか否かを判定する。
【００５６】
格納部４０５は、各符号化データのサイズの全てが所定の閾値より大きいと類似判定部４０４が判定した場合、第１のデータを２進数で表記した際の１の数が第１のデータのビット数の半分未満であるか否かを判定する。そして、１の数が第１のデータのビット数の半分未満であると判定した場合、格納部４０５は、第１のデータをビット反転した反転データをデータ格納域テーブルｖｏｌに格納する。さらに、格納部４０５は、反転データの位置を示す情報と、連長符号化により全てのビットが１であることを示す符号化データとを対応付けて差分データ格納域テーブルｄｉｆｆに格納する。
【００５７】
次に、サーバ２０１から読み出し要求を受け付けた際の処理について説明する。ユーザＩＯ制御部４０１は、読み出し先のアドレスを含む読み出し要求を受け付ける。
【００５８】
格納先判定部４０６は、アドレス索引テーブルｔｍａｐを参照して、読み出し先のアドレスに対応するデータが、データ格納域テーブルｖｏｌが記憶する複数のデータのいずれかのデータか、差分データ格納域テーブルｄｉｆｆが記憶する符号化データかを判定する。例えば、アドレス索引テーブルｔｍａｐは、さらに、アドレスに対応するデータが、データ格納域テーブルｖｏｌに記憶されているか、差分データ格納域テーブルｄｉｆｆに記憶されているかを示すフラグを記憶していてもよい。そして、格納先判定部４０６は、読み出し先のアドレスに対応するフラグを参照して判定する。
【００５９】
復号部４０７は、読み出し先のアドレスに対応するデータが符号化データであると格納先判定部４０６が判定した場合、読み出し先のアドレスに対応する符号化データの位置を示す情報により特定される読み出し先の符号化データを、連長符号化に基づいて復号する。
【００６０】
排他的論理和算出部４０２は、読み出し先の符号化データを復号したデータと、読み出し先の符号化データに対応する複数のデータのいずれかのデータの位置を示す情報により特定される読み出し先のデータとの排他的論理和を算出する。そして、ユーザＩＯ制御部４０１は、排他的論理和算出部４０２が算出した排他的論理和を、読み出し先のデータとして、サーバ２０１に送信する。
【００６１】
ＧＣ制御部４０８は、アドレス索引テーブルｔｍａｐから参照されていない差分データ格納域テーブルｄｉｆｆのエントリを記憶部１０２から削除する。同様に、ＧＣ制御部４０８は、アドレス索引テーブルｔｍａｐと差分データ格納域テーブルｄｉｆｆとから参照されていないデータ格納域テーブルｖｏｌのエントリを記憶部１０２から削除する。これにより、記憶部１０２のデータ域を再利用することができる。
【００６２】
図５は、記憶部１０２の記憶内容の一例を示す説明図である。記憶部１０２は、アドレス索引テーブルｔｍａｐと、データ格納域テーブルｖｏｌと、差分データ格納域テーブルｄｉｆｆとを有する。図５に示すアドレス索引テーブルｔｍａｐは、レコード５０１−１、２を有する。また、図５に示すデータ格納域テーブルｖｏｌは、レコード５０２−１、２を有する。また、図５に示す差分データ格納域テーブルｄｉｆｆは、レコード５０３−１を有する。
【００６３】
アドレス索引テーブルｔｍａｐは、アドレス、参照と、というフィールドを含む。アドレスフィールドには、サーバ２０１からのアドレスが格納される。参照フィールドには、サーバ２０１からのアドレスに対応するデータの格納位置を示すポインタが格納される。ポインタが示す領域は、図５で示すように、データ格納域テーブルｖｏｌ内の領域である場合と、差分データ格納域テーブルｄｉｆｆ内の領域である場合とがある。
【００６４】
データ格納域テーブルｖｏｌは、データというフィールドを有する。データフィールドには、情報記憶装置１０１が蓄積するデータが格納される。
【００６５】
差分データ格納域テーブルｄｉｆｆは、差分データと、参照というフィールドを含む。差分データフィールドには、参照フィールドにより示されるデータ格納域テーブルｖｏｌのデータとの差分である差分データが格納される。参照フィールドには、データ格納域テーブルｖｏｌのデータの格納位置を示すポインタが格納される。
【００６６】
例えば、レコード５０１−１は、サーバ２０１からのアドレス「００００」に関するレコードである。具体的には、レコード５０１−１は、アドレス「００００」のデータが、レコード５０１−１の参照フィールドに格納されたポインタが示すレコード５０２−１の「１１０１００１１１０００」であることを示す。
【００６７】
また、レコード５０１−２は、サーバ２０１からのアドレス「０００１」に関するレコードである。具体的には、レコード５０１−２は、アドレス「０００１」のデータが、レコード５０３−１の差分データを復号したデータと、レコード５０３−１の参照フィールドに格納されたポインタが示すレコード５０２−１のデータのＸＯＲで得られた値であることを示す。ここで、レコード５０３−１の差分データを復号したデータは、「００００００１０１１１０」となる。従って、アドレス「０００１」のデータは、「００００００１０１１１０」と「１１０１００１１１０００」とをＸＯＲした「１１０１０００１０１１０」となる。
【００６８】
また、図１で示した具体的な数値を当てはめると、データ格納域テーブルｖｏｌのデータのサイズが４［ＫｉＢ］であり、ビット長が３２Ｋとなる。そして、データ格納域テーブルｖｏｌのデータの合計が１［ＴｉＢ］であれば、データ格納域テーブルｖｏｌのエントリの数が、２＾２８個存在することになる。
【００６９】
（実施例１）
次に、実施例１におけるデータ読み出し処理とデータ書き込み処理について、図６、図７を用いて説明する。
【００７０】
図６は、実施例１におけるデータ読み出し処理手順の一例を示すフローチャートである。ここで、データ読み出し処理は、引数として、読み出し先のアドレスａｄｄｒを受け付ける。また、データ読み出し処理の戻り値の変数を、ｄａｔａとする。
【００７１】
情報記憶装置１０１は、アドレス索引テーブルｔｍａｐ［ａｄｄｒ］の値を変数ｐに代入する（ステップＳ６０１）。ここで、アドレス索引テーブルｔｍａｐ［ａｄｄｒ］は、アドレス索引テーブルｔｍａｐのアドレスフィールドに、ａｄｄｒの値が格納されたエントリを示す。ａｄｄｒの値が見つかれば、変数ｐには、該当のエントリの位置を示す値が格納され、ａｄｄｒの値が見つからなければ、変数ｐにはｎｕｌｌが格納される。
【００７２】
次に、情報記憶装置１０１は、変数ｐがｎｕｌｌか否かを判断する（ステップＳ６０２）。変数ｐがｎｕｌｌである場合（ステップＳ６０２：Ｙｅｓ）、情報記憶装置１０１は、０を変数ｄａｔａに代入する（ステップＳ６０３）。そして、情報記憶装置１０１は、データ読み出し処理を終了する。
【００７３】
一方、変数ｐがｎｕｌｌでない場合（ステップＳ６０２：Ｎｏ）、情報記憶装置１０１は、変数ｐが差分データ格納域ｄｉｆｆ内を示すか否かを判断する（ステップＳ６０４）。変数ｐがデータ格納域ｖｏｌ内を示す場合（ステップＳ６０４：Ｎｏ）、情報記憶装置１０１は、データ格納域テーブルｖｏｌ［ｐ］の値を変数ｄａｔａに代入する（ステップＳ６０５）。そして、情報記憶装置１０１は、データ読み出し処理を終了する。
【００７４】
一方、変数ｐが差分データ格納域ｄｉｆｆ内を示す場合（ステップＳ６０４：Ｙｅｓ）、情報記憶装置１０１は、差分格納域テーブルｄｉｆｆ［ｐ］．ｂｉｎの値を変数ｅｎに代入するとともに、差分格納域テーブルｄｉｆｆ［ｐ］．ｒｅｆの値を変数ｎｐに代入する（ステップＳ６０６）。ここで、差分格納域テーブルｄｉｆｆ［ｐ］．ｂｉｎは、差分格納域テーブルｄｉｆｆの変数ｐが示すエントリの差分データフィールドを示す。また、差分格納域テーブルｄｉｆｆ［ｐ］．ｒｅｆは、差分格納域テーブルｄｉｆｆの変数ｐが示すエントリの参照フィールドを示す。
【００７５】
次に、情報記憶装置１０１は、ｄｅｃｏｄｅ（ｅｎ）の戻り値を変数ｄｅｌｔａに代入する（ステップＳ６０７）。ここで、ｄｅｃｏｄｅ（）関数は、連長符号化されたデータを復号する関数である。そして、情報記憶装置１０１は、ｘｏｒ（データ格納域テーブルｖｏｌ［ｎｐ］，ｄｅｌｔａ）の戻り値を変数ｄａｔａに代入する（ステップＳ６０８）。そして、情報記憶装置１０１は、データ読み出し処理を終了する。
【００７６】
図７は、実施例１におけるデータ書き込み処理手順の一例を示すフローチャートである。ここで、データ書き込み処理は、引数として、書き込み先のアドレスａｄｄｒと、書き込みデータｄａｔａとを受け付ける。
【００７７】
情報記憶装置１０１は、変数ｉを０からＮ−１までを１刻みで、類似データ検索のループを行う（ステップＳ７０１〜Ｓ７０４）。ここで、ステップＳ７０１に記載した「ｉ＝０，Ｎ−１，１」は、「変数＝初期値、終了値、増分値」を意味する。また、類似データ検索のループは、データ格納域ｖｏｌの線形検索を行っているが、線形検索に限られない。類似データ検索のループの内部として、情報記憶装置１０１は、ｅｎｃｏｄｅ（ｘｏｒ（データ格納域テーブルｖｏｌ［ｉ］，ｄａｔａ））の戻り値を変数ｅｎに代入する（ステップＳ７０２）。ここで、ｅｎｃｏｄｅ（）関数は、データを連長符号化する関数である。
【００７８】
次に、情報記憶装置１０１は、類似データ検索のループの内部として、ｓｉｚｅ（ｅｎ）が閾値δより小さいか否かを判断する（ステップＳ７０３）。ｓｉｚｅ（ｅｎ）が閾値δより小さい場合（ステップＳ７０３：Ｙｅｓ）、すなわち、書き込みデータと類似するデータが見つかった場合には、情報記憶装置１０１は、類似データ検索のループを抜けて、引数ｄａｔａとデータ格納域テーブルｖｏｌ［ｉ］とが一致するか否かを判断する（ステップＳ７０５）。ステップＳ７０５の処理について、情報記憶装置１０１は、ビット単位で一致するか否かを判断してもよいし、変数ｅｎが「ゼロＬ」となるかを判断してもよい。ここで、Ｌは、ｖｏｌ［ｉ］や引数ｄａｔａのビット数である。
【００７９】
引数ｄａｔａとデータ格納域テーブルｖｏｌ［ｉ］とが一致する場合（ステップＳ７０５：Ｙｅｓ）、情報記憶装置１０１は、変数ｉの値を変数ｐに代入する（ステップＳ７０６）。
【００８０】
一方、引数ｄａｔａとデータ格納域テーブルｖｏｌ［ｉ］とが一致しない場合（ステップＳ７０５：Ｎｏ）、情報記憶装置１０１はｄｉｆｆ＿ａｌｌｏｃａｔｅ（）の戻り値を変数ｐに代入する（ステップＳ７０７）。ここで、ｄｉｆｆ＿ａｌｌｏｃａｔｅ（）は、差分データ格納域ｄｉｆｆの空きエントリのインデックスを返す関数である。
【００８１】
そして、情報記憶装置１０１は、変数ｅｎの値を差分格納域テーブルｄｉｆｆ［ｐ］．ｂｉｎに代入するとともに、変数ｉの値を差分格納域テーブルｄｉｆｆ［ｐ］．ｒｅｆに代入する（ステップＳ７０８）。
【００８２】
ｓｉｚｅ（ｅｎ）が閾値δ以上である場合（ステップＳ７０３：Ｎｏ）、情報記憶装置１０１は、類似データ検索のループの先頭に戻る（ステップＳ７０４）。そして、変数ｉがＮ−１の際にもｓｉｚｅ（ｅｎ）が閾値δ以上である、すなわち、書き込みデータと類似するデータが見つからなかった場合、情報記憶装置１０１は、類似データ検索のループを終了し、ｖｏｌ＿ａｌｌｏｃａｔｅ（）の戻り値を変数ｐに代入する（ステップＳ７０９）。次に、情報記憶装置１０１は、引数ｄａｔａの値をデータ格納域テーブルｖｏｌ［ｐ］に代入する（ステップＳ７１０）。
【００８３】
ステップＳ７０６、Ｓ７０８、Ｓ７１０のうちのいずれかの処理終了後、情報記憶装置１０１は、変数ｐの値をアドレス索引テーブルｔｍａｐ［ａｄｄｒ］に代入する（ステップＳ７１１）。そして、情報記憶装置１０１は、データ書き込み処理を終了する。
【００８４】
ここで、類似データ検索のループは、図７で示した形態に限られない。例えば、図７で示したフローチャートは、最初に見つかった類似データを選択する方法、いわゆるファーストフィット（ｆｉｒｓｔ−ｆｉｔ）方式である。そして、他の形態として、情報記憶装置１０１は、ｓｉｚｅ（ｅｎ）が閾値δより小さく、ｓｉｚｅ（ｅｎ）が最も小さい類似データを選択する方法、いわゆるベストフィット（ｂｅｓｔ−ｆｉｔ）方式を採用してもよい。ファーストフィット方式とベストフィット方式とを比較すると、ファーストフィット方式は、ベストフィット方式に比べてデータ書き込み処理を短時間で行うことができる。一方で、ベストフィット方式は、ファーストフィット方式に比べて記憶部１０２に記憶する容量を抑えることができるため、ストレージの利用効率を向上させることができる。
【００８５】
また、情報記憶装置１０１は、ｓｉｚｅ（ｅｎ）が閾値δより小さいデータの数が、予め決めておいた最大の選択候補データの数に達した場合、見つけたデータのうちｓｉｚｅ（ｅｎ）が小さいデータを、類似データとして選択する方法を採用してもよい。また、情報記憶装置１０１は、ループを開始する際にタイマを設定しておき、タイムアウトが通知されるまでに見つかったｓｉｚｅ（ｅｎ）が閾値δより小さいデータのうちｓｉｚｅ（ｅｎ）が小さいデータを、類似データとして選択する方法を採用してもよい。この２つの方法は、処理時間、記憶部１０２に記憶する容量との面で、ファーストフィット方式とベストフィット方式との中間程度の性能となる。
【００８６】
（実施例２）
次に、実施例２におけるデータ読み出し処理とデータ書き込み処理とについて、図８〜図１１を用いて説明する。まず、本実施の形態におけるｄとｄ’との類似度は、ｄとビット反転したｄ’との類似度と同一であるという性質がある。この性質については、図８で説明する。従って、ｄとｄ’との類似度を判断する代わりに、ｄとビット反転したｄ’との類似度が高いと判断することに有用性が高い状況がある。具体的には、ディスク３０５がＳＬＣ型フラッシュメモリである場合、ＳＬＣ型フラッシュメモリは、ビット１を表現する電圧レベルと、ビット０を表現する電圧レベルとが異なる。具体的には、ビット１は、ビット０に比べて、低消費電力、低エラー率でアクセスすることが可能である。
【００８７】
従って、実施例２では、ｄ’と、ビット反転したｄ’とのうち、より低コストなデータをデータ格納域テーブルｖｏｌに格納する方法を行う。具体的には、情報記憶装置１０１は、ｄ’と、ビット反転したｄ’とのうち、１のビットの多い方をデータ格納域テーブルｖｏｌに格納する。
【００８８】
図８は、ビット反転した際の類似度の説明図である。図８の例では、ｄとｄ’との類似度は、ｄとビット反転したｄ’との類似度と同一であるという性質を図示したものである。図８に示すｄは、「１１００１１１０００００」であるとする。また、図８において、ビット反転を「〜」で示す。また、ｄ’は、「１１００１１００１１１０」であるとする。従って、ビット反転した〜ｄ’は、「００１１００１１０００１」となる。次に、ｘｏｒ（ｄ，ｄ’）、ｘｏｒ（ｄ，〜ｄ’）、ＲＬＥ（ｘｏｒ（ｄ，ｄ’））、ＲＬＥ（ｘｏｒ（ｄ，〜ｄ’））、｜ＲＬＥ（ｘｏｒ（ｄ，ｄ’））｜、｜ＲＬＥ（ｘｏｒ（ｄ，〜ｄ’））｜について、下記に並べて示す。
【００８９】
ｘｏｒ（ｄ，ｄ’）＝００００００１０１１１０
ｘｏｒ（ｄ，〜ｄ’）＝１１１１１１０１０００１
ＲＬＥ（ｘｏｒ（ｄ，ｄ’））＝ゼロ６イチ１ゼロ１イチ３ゼロ１
ＲＬＥ（ｘｏｒ（ｄ，〜ｄ’））＝イチ６ゼロ１イチ１ゼロ３イチ１
｜ＲＬＥ（ｘｏｒ（ｄ，ｄ’））｜＝１３
｜ＲＬＥ（ｘｏｒ（ｄ，〜ｄ’））｜＝１３
【００９０】
このように、ｄとｄ’との類似度は、ｄと〜ｄ’との類似度と同一となることがわかる。次に、実施例２におけるデータ書き込み処理について、図９〜図１１を用いて説明する。なお、実施例２におけるデータ読み出し処理については、実施例１におけるデータ読み出し処理と同一であるため、説明を省略する。
【００９１】
図９は、実施例２におけるデータ書き込み処理手順の一例を示すフローチャート（その１）である。また、図１０は、実施例２におけるデータ書き込み処理手順の一例を示すフローチャート（その２）である。また、図１１は、実施例２におけるデータ書き込み処理手順の一例を示すフローチャート（その３）である。ここで、データ書き込み処理は、引数として、書き込み先のアドレスａｄｄｒと、書き込みデータｄａｔａとを受け付ける。
【００９２】
情報記憶装置１０１は、ｒａｎｋ（１，ｄａｔａ）がＬ／２より小さいか否かを判断する（ステップＳ９０１）。ここで、ｒａｎｋ（１，ｄａｔａ）は、ｄａｔａの２進数表現における１のビットの数を数える関数である。ビット長の中で１のビットの数を数える機能は、ｐｏｐｕｌａｔｉｏｎ  ｃｏｕｎｔとも呼ばれる。
【００９３】
ｒａｎｋ（１，ｄａｔａ）がＬ／２より小さい場合（ステップＳ９０１：Ｙｅｓ）、引数ｄａｔａには１より０のビットの方が多く含まれるため、情報記憶装置１０１は、ｘｏｒ（−１，ｄａｔａ）の戻り値を、ｄａｔａ２に代入する（ステップＳ９０２）。ここで、ｘｏｒ（−１，ｄａｔａ）は、変数ｄａｔａの全ビット判定操作となる。そして、情報記憶装置１０１は、ｔｒｕｅを変数ｉｎｖｅｒｔｅｄに代入する（ステップＳ９０３）。
【００９４】
一方、ｒａｎｋ（１，ｄａｔａ）がＬ／２以上である場合（ステップＳ９０１：Ｎｏ）、引数ｄａｔａには０と１のビットの数が同じ、または０より１のビットの方が多く含まれるため、情報記憶装置１０１は、引数ｄａｔａの値を、ｄａｔａ２に代入する（ステップＳ９０４）。そして、情報記憶装置１０１は、ｆａｌｓｅを変数ｉｎｖｅｒｔｅｄに代入する（ステップＳ９０５）。
【００９５】
ステップＳ９０３、またはＳ９０５の処理終了後、情報記憶装置１０１は、変数ｉを０からＮ−１までを１刻みで、類似データ検索のループを行う（ステップＳ１００１〜Ｓ１００４）。類似データ検索のループの内部として、情報記憶装置１０１は、ｅｎｃｏｄｅ（ｘｏｒ（データ格納域テーブルｖｏｌ［ｉ］，ｄａｔａ２））の戻り値を変数ｅｎに代入する（ステップＳ１００２）。
【００９６】
次に、情報記憶装置１０１は、類似データ検索のループの内部として、ｓｉｚｅ（ｅｎ）が閾値δより小さいか否かを判断する（ステップＳ１００３）。ｓｉｚｅ（ｅｎ）が閾値δより小さい場合（ステップＳ１００３：Ｙｅｓ）、すなわち、書き込みデータと類似するデータが見つかった場合には、情報記憶装置１０１は、類似データ検索のループを抜けて、引数ｄａｔａとデータ格納域テーブルｖｏｌ［ｉ］とが一致するか否かを判断する（ステップＳ１００５）。ここで、情報記憶装置１０１は、ステップＳ１００５の処理の代わりに（ｎｏｔ  ｉｎｖｅｒｔｅｄ  ＡＮＤ  ｅｎ＝＝ゼロＬ）の真偽値を求めてもよいし、（ｉｎｖｅｒｔｅｄ  ＡＮＤ  ｅｎ＝＝イチＬ）の真偽値を求めてもよい。
【００９７】
引数ｄａｔａとデータ格納域テーブルｖｏｌ［ｉ］とが一致する場合（ステップＳ１００５：Ｙｅｓ）、情報記憶装置１０１は、変数ｉの値を変数ｎｐに代入する（ステップＳ１００６）。
【００９８】
一方、引数ｄａｔａとデータ格納域テーブルｖｏｌ［ｉ］とが一致しない場合（ステップＳ１００５：Ｎｏ）、情報記憶装置１０１はｄｉｆｆ＿ａｌｌｏｃａｔｅ（）の戻り値を変数ｎｐに代入する（ステップＳ１００７）。そして、情報記憶装置１０１は、ｅｎｃｏｄｅ（ｘｏｒ（ｖｏｌ［ｉ］，ｄａｔａ））の戻り値を差分格納域テーブルｄｉｆｆ［ｎｐ］．ｂｉｎに代入するとともに、変数ｉの値を差分格納域テーブルｄｉｆｆ［ｎｐ］．ｒｅｆに代入する（ステップＳ１００８）。
【００９９】
そして、ステップＳ１００６、Ｓ１００８、また、図１１に示すステップＳ１１０４、Ｓ１１０６の処理終了後、情報記憶装置１０１は、変数ｎｐの値を、アドレス索引テーブルｔｍａｐ［ａｄｄｒ］に代入する（ステップＳ１００９）。
【０１００】
また、ｓｉｚｅ（ｅｎ）が閾値δ以上である場合（ステップＳ１００３：Ｎｏ）、情報記憶装置１０１は、類似データ検索のループの先頭に戻る（ステップＳ１００４）。そして、変数ｉがＮ−１の際にもｓｉｚｅ（ｅｎ）が閾値δ以上である場合、すなわち、書き込みデータと類似するデータが見つからなかった場合、情報記憶装置１０１は、類似データ検索のループを終了し、ｖｏｌ＿ａｌｌｏｃａｔｅ（）の戻り値を変数ｐに代入する（ステップＳ１１０１）。そして、情報記憶装置１０１は、ｄａｔａ２の値をデータ格納域テーブルｖｏｌ［ｐ］に格納する（ステップＳ１１０２）。
【０１０１】
次に、情報記憶装置１０１は、変数ｉｎｖｅｒｔｅｄの値がＴｒｕｅとＦａｌｓｅのいずれかを確認する（ステップＳ１１０３）。変数ｉｎｖｅｒｔｅｄの値がＦａｌｓｅである場合（ステップＳ１１０３：Ｆａｌｓｅ）、情報記憶装置１０１は、変数ｐの値を変数ｎｐに代入する（ステップＳ１１０４）。
【０１０２】
一方、変数ｉｎｖｅｒｔｅｄの値がＴｒｕｅである場合（ステップＳ１１０３：Ｔｒｕｅ）、情報記憶装置１０１は、ｄｉｆｆ＿ａｌｌｏｃａｔｅ（）の戻り値を、ｎｐに代入する（ステップＳ１１０５）。そして、情報記憶装置１０１は、イチＬを差分格納域テーブルｄｉｆｆ［ｎｐ］．ｂｉｎに格納するとともに、変数ｐを差分格納域テーブルｄｉｆｆ［ｎｐ］．ｒｅｆに格納する（ステップＳ１１０６）。ステップＳ１１０４、Ｓ１１０６のいずれかの処理終了後、情報記憶装置１０１は、ステップＳ１００９の処理を実行する。
【０１０３】
また、実施例２におけるデータ書き込み処理において、情報記憶装置１０１は、より低コストなデータをデータ格納域テーブルｖｏｌに格納する。従って、例えば、ディスク３０５が、複数存在しており、複数のディスク３０５のうちＳＬＣ型フラッシュメモリが含まれる、という形態にも実施例２を適用することができる。具体的には、複数のディスク３０５のうちのＳＬＣ型フラッシュメモリは、少なくとも、データ格納域テーブルｖｏｌを記憶すればよい。そして、複数のディスク３０５の残りとなる、磁気ディスク等が、アドレス索引テーブルｔｍａｐ、差分データ格納域テーブルｄｉｆｆを記憶すればよい。
【０１０４】
以上説明したように、情報記憶装置１０１は、蓄積済のデータｄと、サーバ２０１からの書き込み要求に含まれる新たなデータｄ’の排他的論理和を連長符号化した符号化データのサイズがδ未満ならば、ｄの位置情報と符号化データとを対応付けて記憶する。これにより、情報記憶装置１０１は、差分の大きさを示す符号化データのサイズが高速に得られるため、類似データを高速に重複除去することができる。
【０１０５】
また、情報記憶装置１０１は、符号化データのサイズがδ未満ならば、符号化データの位置を示す情報と、書き込み要求に含まれるアドレスとを対応付けてアドレス索引テーブルｔｍａｐに記憶する。これにより、情報記憶装置１０１は、書き込み要求があったアドレスに対して、サーバ２０１から読み出し要求が発生した際にも、アドレス索引テーブルｔｍａｐを参照して、書き込み要求に含まれていたデータを返却することができる。
【０１０６】
また、読み出し要求に含まれるアドレスに対応するデータが差分データ格納域テーブルｄｉｆｆに格納されているとする。この場合、情報記憶装置１０１は、差分データ格納域テーブルｄｉｆｆの差分データを復号したデータとデータ格納域テーブルｖｏｌのデータの排他的論理和により、アドレスに対応するデータを生成してもよい。このように、情報記憶装置１０１は、差分データ格納域テーブルｄｉｆｆに格納されているデータに対する読み出し要求にも対応することができる。
【０１０７】
また、ディスク３０５がＳＬＣ型フラッシュメモリであるとする。この場合、情報記憶装置１０１は、データ格納域テーブルｖｏｌにデータを格納する際に、格納するデータを２進数で表記した際の１の数がデータのビット数の半分未満であれば、反転したデータデータ格納域テーブルｖｏｌに書き込む。これにより、情報記憶装置１０１は、低消費電力、低エラー率でＳＬＣ型フラッシュメモリにアクセスすることができる。
【０１０８】
なお、本実施の形態で説明した重複除去方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本重複除去プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本重複除去プログラムは、インターネット等のネットワークを介して配布してもよい。
【符号の説明】
【０１０９】
ｄｉｆｆ  差分データ格納域テーブル
ｔｍａｐ  アドレス索引テーブル
ｖｏｌ  データ格納域テーブル
１０１  情報記憶装置
１０２  記憶部
４００  制御部
４０１  ユーザＩＯ制御部
４０２  排他的論理和算出部
４０３  連長符号化部
４０４  類似判定部
４０５  格納部
４０６  格納先判定部
４０７  復号部
４０８  ＧＣ制御部
【図１】
0006680057.tif 000002
【図２】
0006680057.tif 000003
【図３】
0006680057.tif 000004
【図４】
0006680057.tif 000005
【図５】
0006680057.tif 000006
【図６】
0006680057.tif 000007
【図７】
0006680057.tif 000008
【図８】
0006680057.tif 000009
【図９】
0006680057.tif 000010
【図１０】
0006680057.tif 000011
【図１１】
0006680057.tif 000012