(57)【特許請求の範囲】
【請求項１】
それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、
それぞれ、前記Ｌ個のハッシュ値の中の互いに異なる２つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域と、
データ集合に含まれるデータ毎に、前記データについてのｋ個のハッシュ値を前記Ｌ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、前記算出した各ハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶する情報設定部と、
前記ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、前記入力データが、前記データ集合に含まれていない新規データであると判定する判定部と
を備えることを特徴とするデータ有無判定装置。
【請求項２】
前記Ｌ個の第１記憶領域と前記Ｍ個の第２記憶領域とが、同一のメモリ上に、同一のハッシュ値に対応づけられている前記第１記憶領域に記憶されたカウント値と前記第２記憶領域に記憶された値とが１回のメモリアクセスで読み出せるように確保されている
ことを特徴とする請求項１に記載のデータ有無判定装置。
【請求項３】
前記第１記憶領域に記憶されるカウント値は１ビットである、
請求項１または２に記載のデータ有無判定装置。
【請求項４】
前記ｋ個のハッシュ関数を用いて、前記データ集合から削除される削除データのｋ個のハッシュ値を算出し、算出した前記削除データのｋ個のハッシュ値に含まれるあるハッシュ値に対応付けられている第２記憶領域上のカウント値が“０”である場合に、前記あるハッシュ値に対応付けられている第１記憶領域上のカウント値を“０”に変更する、
請求項１から３のいずれか一項に記載のデータ有無判定装置。
【請求項５】
メモリ上に確保された、それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、それぞれ、前記Ｌ個のハッシュ値の中の互いに異なる２つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域とを用いて、入力データが、既存のデータ集合に含まれていない新規データであるか否かを判定するデータ有無判定方法であって、
コンピュータが、
データ集合に含まれるデータ毎に、前記データについてのｋ個のハッシュ値を前記Ｌ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、前記算出した各ハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶し、
前記ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、前記入力データが、前記データ集合に含まれていない新規データであると判定する
ことを特徴とするデータ有無判定方法。
【請求項６】
コンピュータを、
それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、
それぞれ、前記Ｌ個のハッシュ値の中の互いに異なる２つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域と、
データ集合に含まれるデータ毎に、前記データについてのｋ個のハッシュ値を前記Ｌ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、前記算出した各ハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶する情報設定部と、
前記ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、前記入力データが、前記データ集合に含まれていない新規データであると判定する判定部と、
を備える装置として動作させることを特徴とするデータ有無判定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ有無判定装置、データ有無判定方法及びデータ有無判定プログラムに関する。
【背景技術】
【０００２】
データの有無のテストに使用できるデータ構造として、ブルームフィルタ(Bloom Filter)とカウンティングブルームフィルタ(Counting Bloom Filter)とが知られている。
【０００３】
まず、図１Ａ及び図１Ｂを用いて、ブルームフィルタについて説明する。
【０００４】
図１Ａに示したように、ブルームフィルタは、例えば、ｍ（図１Ａでは、ｍ＝１８）ビットのビット配列である。ブルームフィルタを用いる場合、ｋ個（図１Ａではｋ＝３）のハッシュ関数も用意（定義）される。また、各ハッシュ関数により得られる各ハッシュ値が、ブルームフィルタのいずれかのビットに対応付けられる。そして、各既存データについて、ｋ個のハッシュ関数を用いてその既存データについてのｋ個のハッシュ値を算出し、算出した各ハッシュ値に対応付けられているブルームフィルタのビット（初期値は“０”）に“１”を設定する処理が行われる。
【０００５】
或るデータ（以下、判定対象データと表記する）の有無のテスト時には、ｋ個のハッシュ関数を用いて、判定対象データについてのｋ個のハッシュ値が算出される。そして、算出したいずれかのハッシュ値に対応付けられているブルームフィルタのビット値が“０”であった場合に、判定対象データが、新規データであると判定される。また、そうでなかった場合には、判定対象データが、新規データ又は既存データであると判定される。
【０００６】
このように、ブルームフィルタを用いれば、判定対象データの有無（判定対象データが、新規データであるか新規データである可能性があるものであるかの別）を、高速且つ必要とされる記憶容量が少ない形で判定できる。ただし、ブルームフィルタは、登録した情報を削除できないものとなっている。
【０００７】
具体的には、図１Ａにおいて、データｘの存在を示しているブルームフィルタのビットは、左から２、６、１４番目のビットである。そのため、データ集合｛ｘ、ｙ、ｚ｝からデータｘを削除するために、ブルームフィルタの左から２、６、１４番目のビットの値を“０”に変えることが考えられる。しかしながら、そのようにブルームフィルタの内容を更新した場合、図１Ｂに示したように、データ集合に含まれるデータｚと同じデータｗが新規データであると判定されてしまうことになる。このような現象が生じてしまうと、偽陰性がないというブルームフィルタの特徴が失われてしまうので、ブルームフィルタから登録した情報を削除することができないのである。
【０００８】
次に、図２Ａ及び図２Ｂを用いて、カウンティングブルームフィルタについて説明する。
【０００９】
登録情報の削除が可能なように、ブルームフィルタを改良したものが、カウンティングブルームフィルタである。図２Ａに模式的に示してあるように、カウンティングブルームフィルタ（以下、ＣＢＦと表記する）は、ハッシュ値毎に、n （≧２）ビットの情報を記憶可能な構成を有している。
【００１０】
そして、ＣＢＦは、以下のような形でその内容が更新されるものとなっている。
既存データに関する情報の登録時：既存データから算出された各ハッシュ値に対応する記憶領域上の値に“１”を加算
集合データからのデータの削除時：削除データに関するｋ個のハッシュ値に対応する記憶領域上の値から“１”を減算
【００１１】
具体例を挙げれば、図２Ａにおいて、データｘの存在を示しているブルームフィルタのビットは、左から２、６、１４番目のビットである。従って、データ集合｛ｘ、ｙ、ｚ｝からデータｘを削除する場合、ＣＢＦの左から２、６、１４番目の各記憶領域の値が“１”デクリメントされる。そして、その結果として、ＣＢＦの状態は、図２Ｂに示した状態、つまり、データ集合｛ｙ、ｚ｝内の各データと一致するデータ（図２Ｂにおけるｗ等）を、新規データであると誤判定することがない状態、となる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２０１１−１７１９９５号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上記したように、ＣＢＦは、登録情報を削除することが出来るものとなっている。ただし、ＣＢＦは、その実現（実装）に、ブルームフィルタの実現に必要なメモリ量のｎ倍のメモリ量が必要とされるものとなっている。
【００１４】
１つの側面では、本発明は、入力データが或るデータ集合内に含まれていない新規データであるか否かの判定を、ＣＢＦを用いた場合よりも使用する記憶容量が少なく行え、及び／又は、データ集合からのデータの削除が可能な形で行える技術を提供することにある。
【課題を解決するための手段】
【００１５】
一態様のデータ有無判定装置は、
それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、
それぞれ、Ｌ個のハッシュ値の中の互いに異なる１つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域と、
或るデータ集合に含まれるデータ毎に、そのデータについてのｋ個のハッシュ値をＬ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶する情報設定部と、
ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、入力データが、データ集合に含まれていない新規データであると判定する判定部と、
を備える。
【００１６】
また、一態様のデータ有無判定方法は、
メモリ上に確保された、それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、それぞれ、Ｌ個のハッシュ値の中の互いに異なる１つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域とを用いて、入力データが、既存のデ
ータ集合に含まれていない新規データであるか否かを判定するデータ有無判定方法であって、
コンピュータが、
データ集合に含まれるデータ毎に、そのデータについてのｋ個のハッシュ値をＬ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶し、
ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、入力データが、データ集合に含まれていない新規データであると判定する。
【００１７】
また、一態様のデータ有無判定プログラムは、
コンピュータを、
それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、
それぞれ、Ｌ個のハッシュ値の中の互いに異なる１つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域と、
或るデータ集合に含まれるデータ毎に、そのデータについてのｋ個のハッシュ値をＬ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶する情報設定部と
ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、入力データが、データ集合に含まれていない新規データであると判定する判定部と、
を備える装置として動作させる。
【発明の効果】
【００１８】
入力データが或るデータ集合内に含まれていない新規データであるか否かの判定を、ＣＢＦを用いた場合よりも使用する記憶容量が少なく、及び／又は、データ集合からのデータの削除が可能な形で行える。
【図面の簡単な説明】
【００１９】
【図１Ａ】図１Ａは、ブルームフィルタの説明図である。
【図１Ｂ】図１Ｂは、ブルームフィルタから登録情報を削除できない理由の説明図である。
【図２Ａ】図２Ａは、カウンティングブルームフィルタの説明図である。
【図２Ｂ】図２Ｂは、データｘに関する情報を削除したカウンティングブルームフィルタの説明図である。
【図３】図３は、実施形態に係る重複除去ストレージ装置のハードウェア構成図である。
【図４】図４は、実施形態に係る重複除去ストレージ装置の機能ブロック図である。
【図５】図５は、実施形態に係る重複除去ストレージ装置の書込処理部が実行する書込処理の流れ図である。
【図６】図６は、実施形態に係る重複除去ストレージ装置が備える上位ビット共有カウンティングブルームフィルタの説明図である。
【図７】図７は、実施形態に係る重複除去ストレージ装置が備える上位ビット共有カウンティングブルームフィルタの説明図である。
【図８】図８は、図５の書込処理中で実行されるテスト処理の流れ図である。
【図９】図９は、図５の書込処理中で実行される追加処理の流れ図である。
【図１０】図１０は、図５の書込処理中で実行される削除処理の流れ図である。
【図１１Ａ】図１１Ａは、書込処理による上位ビット共有カウンティングブルームフィルタの更新内容の説明図（その１）である。
【図１１Ｂ】図１１Ｂは、書込処理による上位ビット共有カウンティングブルームフィルタの更新内容の説明図（その２）である。
【図１１Ｃ】図１１Ｃは、書込処理による上位ビット共有カウンティングブルームフィルタの更新内容の説明図（その３）である。
【図１１Ｄ】図１１Ｄは、書込処理による上位ビット共有カウンティングブルームフィルタの更新内容の説明図（その４）である。
【図１１Ｅ】図１１Ｅは、図１１Ｄに示した上位ビット共有カウンティングブルームフィルタの状態の意味を説明するための図である。
【図１２】図１２は、実施形態に係る重複除去ストレージ装置の読込処理部が実行する読込処理の流れ図である。
【図１３】図１３は、実施形態に係る重複除去ストレージ装置の書込処理部が実行する再構築処理の流れ図である。
【図１４】図１４は、再構築処理時に生成される上位ビット値フィルタの説明図である。
【図１５】図１５は、図１３の再構築処理の代わりに使用できる再構築処理の流れ図である。
【図１６Ａ】図１６Ａは、上位ビット共有カウンティングブルームフィルタの変形例の説明図である。
【図１６Ｂ】図１６Ｂは、上位ビット共有カウンティングブルームフィルタの変形例の説明図である。
【図１７】ｎビットのカウンタ値を記憶できる上位ビット共有カウンティングブルームフィルタを用いる場合に採用される追加処理の流れ図である。
【図１８】ｎビットのカウンタ値を記憶できる上位ビット共有カウンティングブルームフィルタを用いる場合に採用される削除処理の流れ図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施形態について、図面を参照して詳細に説明する。尚、以下で説明する実施形態は、本発明の一例に過ぎず、本発明は、実施形態とは具体的な構成／手順が異なる形でも実現することができるものである。
【００２１】
発明者が開発したデータ有無判定技術は、さまざまな装置／システムに利用できるものなのであるが、以下では、重複除去ストレージ装置に利用した場合を例に、発明者が開発したデータ有無判定技術の一実施形態を説明することにする。
【００２２】
図３に、実施形態に係るデータ有無判定技術を利用した重複除去ストレージ装置（以下、実施形態に係る重複除去ストレージ装置と表記する）１０のハードウェア構成を示す。また、図４に、実施形態に係る重複除去ストレージ装置１０の機能ブロック図を示す。
【００２３】
図３に示してあるように、本実施形態に係る重複除去ストレージ装置１０は、記憶装置３０及びホスト１００と接続されるコンピュータ５０のＨＤＤ（Hard Disk Drive）１３
に、ＯＳ(Operating System)、ストレージ制御プログラム２０等をインストールした装置である。
【００２４】
ストレージ制御プログラム２０は、コンピュータ５０を、図４に示したような各種ユニ
ット（機能ブロック）を備えた重複除去ストレージ装置１０として動作させるプログラムである。
【００２５】
すなわち、ＣＰＵ１１がストレージ制御プログラム２０を実行すると、コンピュータ５
０は、プロトコル処理部２１、読込処理部２２、ブロックマップ２３、書込処理部２４及びハッシュ値検索テーブル２５を備えた重複除去ストレージ装置１０として動作する。
【００２６】
プロトコル処理部２１は、ホスト１００からＩ／Ｏ要求を受信し、当該Ｉ／Ｏ要求を解
析することにより、Ｉ／Ｏ要求を読込要求、書込要求に分け、読込要求を読込処理部２２に供給し、書込要求を書込処理部２４に供給するユニット（機能ブロック）である。尚、このプロトコル処理部２１が受信するＩ／Ｏ要求は、アクセス先（リード／ライト先）をＬＢＡ（論理ブロックアドレス；logical Block Address）で指定する要求である。
【００２７】
ブロックマップ２３は、データが既に記憶されている各ＬＢＡについては、記憶されているデータの検証用ハッシュ値を記憶し、データが記憶されていない各ＬＢＡについて、その旨を示す空領域情報を記憶しているように、内容が更新される情報である。このブロックマップ２３に記憶される検証用ハッシュ値の詳細については後述するが、ブロックマップ２３は、メモリ１２上に用意される情報（テーブル）であると共に、随時、記憶装置３０にバックアップされる情報となっている。
【００２８】
ハッシュ値検索テーブル２５は、ブロックマップ２３に記憶されている各検証用ハッシュ値について、その検証用ハッシュ値に対応付けられているデータの記憶装置内３０でのデータ位置（物理アドレス）を記憶しておくためのテーブルである。より具体的には、このハッシュ値検索テーブル２５は、検証用ハッシュ値とデータ位置とが設定されたレコードを複数個記憶可能なテーブルとなっている。
【００２９】
書込処理部２４は、プロトコル処理部２１から書込要求が供給されると、図５に示した手順の書込処理を行うユニット（機能ブロック）である。この書込処理の内容を説明する前に、書込処理時に参照・更新される上位ビット共有カウンティングブルームフィルタ２８（以下、フィルタ２８又は上位ビット共有ＣＢＦ２８とも表記する）の構成を説明する。
【００３０】
図６に模式的に示してあるように、フィルタ２８は、３Ｍ個の下位ビットと、３個の下位ビット毎に設けられた上位ビットとを含む。図６においては、第１記憶領域の個数Ｌは１８個、第２記憶領域の個数Ｍは６個、カウント値ｎは１ビットの例を示している。尚、図６には、１８個の下位ビットしか示していないが、通常、フィルタ２８としては、より多くの下位ビットを含むものが使用される。また、フィルタ２８が図６に示したような状態（値が“１”のビットがある状態）を取るのは、幾つかのデータの記憶装置３０への書込が完了している場合である。換言すれば、フィルタ２８は、データが初めて記憶装置３０へ書き込まれるまでは、各ビットの値が全て“０”となっているものである。
【００３１】
また、重複除去ストレージ装置１０は、メモリ１２（図３）上の一記憶領域が、このフィルタ２８として機能する装置として構成（プログラミング）されている。さらに、重複除去ストレージ装置１０は、フィルタ２８の各ビットを、図７に示したように、Ａ〜Ｈと表記すると、メモリ１２上の１バイトのデータを読み出せば、ＡＢＣＤＥＦＧＨの順に各ビット値が並んだデータが読み出せるように、フィルタ２８の各ビット値のメモリ１２上での位置を定めた装置となっている。
【００３２】
図５に戻って、書込処理の内容を説明する。尚、以下の説明において、処理対象ＬＢＡ
とは、プロトコル処理部２１から供給された書込要求中のＬＢＡのことであり、書込データとは、書込要求で書込が要求されているデータのことである。また、新規／既存データとは、新規データである可能性があるデータのことである。
【００３３】
図５に示してあるように、この書込処理を開始した書込処理部２４は、まず、処理対象ＬＢＡに対応付けられている情報（ハッシュ値群、又は、空領域情報）をブロックマップ２３から読み込む（ステップＳ２１）。
【００３４】
ブロックマップ２３から読み込んだ情報が空領域情報であった場合、すなわち、今回の書込要求が上書き要求ではなかった場合（ステップＳ２２；ＮＯ）、書込処理部２４は、テスト処理（ステップＳ２４）を行う。
【００３５】
ステップＳ２４で行われるテスト処理は、図８に示した手順の処理である。すなわち、このテスト処理を開始した書込処理部２４は、まず、書込データの検証用ハッシュ値を算出し、予め用意されているｋ個のハッシュ関数を用いて検証用ハッシュ値についてのｋ個のハッシュ値を算出する（ステップＳ１０１）。尚、ｋ個のハッシュ関数により得られる各ハッシュ値は、上記したフィルタ２８のいずれかの下位ビットに対応づけられている。また、フィルタ２８の各上位ビットは、配下の各下位ビットに対応付けられている各ハッシュ値に対応づけられている。
【００３６】
ステップＳ１０１の処理を終えた書込処理部２４は、全ハッシュ値に対する、ステップＳ１０３及びＳ１０４の処理が完了したか否かを判断する（ステップＳ１０２）。
【００３７】
全ハッシュ値に対する処理が完了していなかった場合（ステップＳ１０２；ＮＯ）、書込処理部２４は、算出済みのｋ個のハッシュ値の中の最初（又は次）のハッシュ値に対応づけられている下位ビットの値をフィルタ２８から読み出す（ステップＳ１０３）。
【００３８】
そして、書込処理部２４は、読み出した下位ビット値が“０”であった場合（ステップＳ１０４；ＹＥＳ）には、書込対象データが新規データであると判定（ステップＳ１０５）してから、このテスト処理を終了する。
【００３９】
一方、読み出した下位ビット値が“０”でなかった場合（ステップＳ１０４；ＹＥＳ）、書込処理部２４は、ステップＳ１０２以降の処理を再び実行する。
【００４０】
書込処理部２４は、或るハッシュ値に関する下位ビット値として“０”が読み出されるか、全ハッシュ値に対する処理が完了するまで、上記した処理を繰り返す。そして、書込処理部２４は、２〜ｋ番目のいずれかのハッシュ値に関する下位ビット値として“０”が読み出された場合には、書込データが新規データであると判定して（ステップＳ１０５）、このテスト処理を終了する。一方、いずれのハッシュ値に関する下位ビット値としても“０”が読み出されることなく、全てのハッシュ値に対する処理が完了した場合（ステップＳ１０２；ＹＥＳ）、書込処理部２４は、書込データが新規／既存データであると判定して（ステップＳ１０６）、このテスト処理を終了する。
【００４１】
テスト処理（図６；ステップＳ２４）を終えた書込処理部２４は、テスト処理により書込データが新規データであると判定した場合（ステップＳ２５；ＹＥＳ）には、記憶装置３０内の空きブロックに書込データを書き込む（ステップＳ２８）。
【００４２】
続くステップＳ２９にて、書込処理部２４は、図９に示した手順の追加処理を行う。
【００４３】
すなわち、この追加処理を開始した書込処理部２４は、まず、ステップＳ１０１（図８
）の処理で算出したｋ個のハッシュ値に対するステップＳ２０３〜Ｓ２０５の処理が完了しているか否かを判断する（ステップＳ２０２）。
【００４４】
全ハッシュ値に対する処理が完了していなかった場合（ステップＳ２０２；ＮＯ）、書込処理部２４は、ｋ個のハッシュ値の中の最初（又は次）のハッシュ値（以下、処理対象ハッシュ値と表記する）に対応づけられている下位ビット値をフィルタ２８から読み出す（ステップＳ２０３）。
【００４５】
そして、書込処理部２４は、処理対象ハッシュ値に対応付けられている下位ビット値が“０”であった場合（ステップＳ２０４；ＹＥＳ）には、当該下位ビット値を“１”に変更（ステップＳ２０６）してから、ステップＳ２０２以降の処理を再び開始する。
【００４６】
一方、処理対象ハッシュ値に対応付けられている下位ビット値が“１”であった場合（ステップＳ２０４；ＮＯ）、書込処理部２４は、処理対象ハッシュ値に対応付けられているフィルタ２８の上位ビットに“１”を設定する（ステップＳ２０５）。尚、この処理は、上位ビットの値が変わらない場合がある処理である。
【００４７】
その後、書込処理部２４は、ステップＳ２０２以降の処理を再び開始し、全ハッシュ値に対する処理が完了したとき（ステップＳ２０２；ＹＥＳ）に、この追加処理を終了する。
【００４８】
追加処理（図６；ステップ２９）を終えた書込処理部２４は、続くステップＳ３０にて、まず、予め定められているハッシュ関数を用いて、書込データについての検証用ハッシュ値を算出する。ここで、検証用ハッシュ値とは、既存データの検証用ハッシュ値と書込データの検証用ハッシュ値とが一致していれば、既存データと書込データとが一致していると見なせるハッシュ値のことである。
【００４９】
次いで、書込処理部２４は、算出した検証用ハッシュ値とステップＳ２８の処理時に書込データを書き込んだデータ位置とを設定したレコードをハッシュ値検索テーブル２５に追加する。そして、書込処理部２４は、ステップＳ３０の処理を終了する。
【００５０】
その後、書込処理部２４は、ブロックマップ２３上の、処理対象ＬＢＡに関する情報を更新する（ステップＳ３１）。具体的には、このステップＳ３１にて、書込処理部２４は、処理対象ＬＢＡに対応づけられているブロックマップ２３上の情報を、書込データの検証用ハッシュ値に書き換える処理を行う。
【００５１】
また、書込処理部２４は、書込データが新規／既存データであると判定した場合（ステップＳ２５；ＮＯ）には、書込データの検証用ハッシュ値を算出し、算出した検証用ハッシュ値でハッシュ値検索テーブル２５を検索する（ステップＳ２６）。
【００５２】
算出した検証用ハッシュ値を含むレコードがハッシュ値検索テーブル２５内に存在していなかった場合には、書込データが新規データであることになる（ステップＳ２７；ＹＥＳ）。そのため、書込処理部２４は、ステップＳ２８以降の処理を開始する。尚、この場合に実行されるステップＳ３０では、検証用ハッシュ値を算出することなく、ステップＳ２６の処理で算出した検証用ハッシュ値を用いてハッシュ値検索テーブル２５へレコードが追加される。
【００５３】
一方、算出した検証用ハッシュ値を含むレコードがハッシュ値検索テーブル２５から検索できた場合には、書込データと同じデータが既に存在している（ステップＳ２７；ＮＯ）ことになる。そのため、書込処理部２４は、処理対象ＬＢＡに対応づけられているブロ
ックマップ２３上の情報を、書込データの検証用ハッシュ値及びステップ２４で算出したｋ個のハッシュ値に変更する（ステップＳ３１）。そして、書込処理部２４は、この書込処理を終了する。
【００５４】
また、ブロックマップ２３から読み出された情報が空領域情報でなかった場合、すなわち、今回の書込要求が上書き要求であった場合（ステップＳ２２；ＹＥＳ）、書込処理部２４は、削除処理（ステップＳ２３）を行う。
【００５５】
この削除処理は、図１０に示した手順の処理である。すなわち、削除処理を開始した書込処理部２４は、まず、ブロックマップ２３から読み出した検証用ハッシュ値についてのｋ個のハッシュ値を算出し、それぞれのハッシュ値に対する処理が完了したか否かを判断する（ステップＳ３０２）。
【００５６】
全ハッシュ値に対する処理が完了していなかった場合（ステップＳ３０２；ＮＯ）、書込処理部２４は、ｋ個のハッシュ値の中の最初（又は次）のハッシュ値（処理対象ハッシュ値と表記する）に対応づけられている上位ビットの値をフィルタ２８から読み出す（ステップＳ３０３）。
【００５７】
そして、書込処理部２４は、処理対象ハッシュ値に対応付けられている上位ビットの値が“０”であった場合（ステップＳ３０５；ＹＥＳ）には、処理対象ハッシュ値に対応付けられているフィルタ２８の下位ビットの値を“０”に変更する（ステップＳ３０５）。そして、書込処理部２４は、ステップＳ３０２以降の処理を再び開始する。
【００５８】
一方、処理対象ハッシュ値に対応付けられている上位ビットの値が“１”であった場合（ステップＳ３０４；ＮＯ）、書込処理部２４は、フィルタ２８内のいずれのビット値も変更することなく、ステップＳ３０２以降の処理を開始する。
【００５９】
そして、書込処理部２４は、全ハッシュ値に対する処理が完了したときに（ステップＳ３０２；ＹＥＳ）に、この削除処理を終了して、図６のステップＳ２４以降の処理を開始する。
【００６０】
ここで、ここまで説明した重複除去ストレージ装置１０の動作内容を、図１１Ａ〜図１１Ｅを用いて、さらに具体的に説明しておくことにする。尚、以下の説明では、ｋ（ハッシュ関数の数）は、“３”であるとする。また、図１１Ａ等に示したフィルタ２８の左側からｉ番目の下位ビットのことを下位ビットｉと表記し、下位ビットｉに対応づけられているハッシュ値をＨｉと表記する。さらに、Ｈ３ｊ＋１〜Ｈ３ｊ＋３（下位ビット３ｊ＋１〜下位ビット３ｊ＋３）に対応づけられている上位ビットのことを、上位ビット〔３ｊ＋１〜３ｊ＋３〕（上位ビット〔１〜３〕等）と表記する。
【００６１】
フィルタ２８の全ビットが“０”となっている状況下、３個のハッシュ関数により算出される３個のハッシュ値（以下、単に、３個のハッシュ値と表記する）が、Ｈ２、Ｈ６、Ｈ１４となるデータｘの書込要求がホスト１００から送信されてきた場合を考える。
【００６２】
この場合、書込処理（図５）のステップＳ２２で“ＮＯ”側への分岐が行われる。従って、削除処理が行われることなく、テスト処理（図８）が行われる。そして、最初のハッシュ値（Ｈ２であるとする）に対応づけられている下位ビット２の値が“０”である（図８、ステップＳ１０４；ＹＥＳ）ため、テスト処理によりデータｘが新規データであると判断される。
【００６３】
従って、ステップＳ２５（図５）では、“ＹＥＳ”側への分岐が行われ、記憶装置３０
に書込データが書き込まれてから、追加処理（図９）が行われる。
【００６４】
そして、この時点における下位ビット２の値、下位ビット６の値、下位ビット１４の値は、いずれも“０”である（ステップＳ２０４；ＹＥＳ）。そのため、データｘに関する追加処理時には、下位ビット２の値、下位ビット６の値、下位ビット１４の値が“１”に変更（ステップＳ２０６）され、フィルタ２８が図１１Ａに示した状態となる。
【００６５】
フィルタ２８が図１１Ａに示した状態になった後に、３個のハッシュ値が、Ｈ５、Ｈ１２、Ｈ１７となるデータｙの書込要求がホスト１００から送信されてきた場合にも、テスト処理と追加処理とが行われる。そして、その結果として、フィルタ２８は、図１１Ｂに示した状態となる。
【００６６】
フィルタ２８が図１１Ｂに示した状態にある状況下、３個のハッシュ値が、Ｈ４、Ｈ６、Ｈ１２となるデータｚの書込要求がホスト１００から送信されてきた場合にも、テスト処理と追加処理とが行われる。ただし、この場合、下位ビット４の値は“０”であるが、下位ビット６、下位ビット１２の値が、“１”となっている。そのため、Ｈ４についてのステップＳ２０４（図９）では、“ＹＥＳ”側への分岐が行われ、Ｈ６、Ｈ１２についてのステップＳ２０４では、“ＮＯ”側への分岐が行われる。そして、その結果として、フィルタ２８は、図１１Ｃに示した状態となる。
【００６７】
次に、フィルタ２８が図１１Ｃに示した状態にある状況下、データｘの書換要求（データｘと同じＬＢＡへのデータｘ′の書込要求）がホスト１００から送信されてきた場合を考える。この場合、ステップＳ２１にて、データｘの３個のハッシュ値Ｈ２、Ｈ６、Ｈ１４がブロックマップ２３から読み出される。そして、ステップＳ２２で“ＹＥＳ”側への分岐が行われて、削除処理（図１０）が開始される。
【００６８】
この時点における上位ビット〔１〜３〕の値は、“０”である（ステップＳ３０４；ＹＥＳ）ため、Ｈ２については、下位ビット２の値が“０”に変更される（ステップＳ３０５）。また、Ｈ１４についても、上位ビット〔１３〜１５〕の値が、“０”である（ステップＳ３０４；ＹＥＳ）ため、下位ビット１４の値が“０”に変更される（ステップＳ３０５）。ただし、上位ビット〔４〜６〕の値が“１”である（ステップＳ３０４；ＮＯ）ため、下位ビット６の値は変更されない。
【００６９】
従って、削除処理が完了すると、フィルタ２８の状態は図１１Ｄに示したものとなる。この状態は、図１１Ｅに示した状態、すなわち、フィルタ２８の全ビットが“０”となっている状況下、データｙの書込要求とデータｚの書込要求がホスト１００から送信されてきた場合の状態と同じ状態である。
【００７０】
そして、流れ図（図９）から明らかなように、追加処理にてフィルタ２８の下位ビットに対して行われている処理は、通常のブルームフィルタ（図１Ａ、図１Ｂ参照）に対して行われているものと同じ処理である。
【００７１】
従って、フィルタ２８は、下位ビットの値を用いれば、通常のブルームフィルタと同様の判定を行えるもの（図８参照）であることになる。また、フィルタ２８は、ＣＢＦと同様に登録情報の削除が可能なもの（図１１Ｃ〜図１１Ｅ参照）であるにも拘わらず、上位ビットを共通化している分、ＣＢＦよりもメモリの消費量が少ないものともなっていることになる。
【００７２】
図４に戻って、読込処理部２２の機能を説明する。
【００７３】
読込処理部２２は、ホスト１００からの読込要求を処理するユニット（機能ブロック）である。この読込処理部２２は、プロトコル処理部２１から読込要求が供給されると、図１２に示した手順の読込処理を開始し、まず、ブロックマップ２３から処理対象ＬＢＡ（読込要求中のＬＢＡ）に対応付けられている検証用ハッシュ値（図１２では、“ハッシュ値”）を読み込む（ステップＳ１１）。
【００７４】
次いで、読込処理部２２は、読み込んだハッシュ値に対応づけられているデータ位置をハッシュ値検索テーブル２５から読み込む（ステップＳ１２）。そして、読込処理部２２は、読み込んだデータ位置のデータを記憶装置３０から読み込んで、ホスト１００に返送（ステップＳ１３）してから、この読込処理を終了する。
【００７５】
また、上記した書込処理部２４は、値が“１”となっている上位ビットの数が所定数を超えた場合等に再構築処理を実行する機能も有している。
【００７６】
書込処理部２４が実行可能な再構築処理は、図１３に示した手順の処理である。
【００７７】
すなわち、この再構築処理を開始した書込処理部２４は、まず、フィルタ２８の上位ビット値を並べた上位ビット値フィルタをメモリ１２上に生成する（ステップＳ４０１）。より具体的には、書込処理部２４は、図１４に模式的に示したように、フィルタ２８の各上位ビット値を、対応している下位ビットの数と同数ずつ並べた上位ビット値フィルタを生成する。
【００７８】
次いで、書込処理部２４は。フィルタ２８の上位ビットが“１”である場所を“０”クリアする（ステップＳ４０２）。ここで、フィルタ２８の上位ビットが“１”である場所とは、“１”である上位ビット、及び、その上位ビットに対応している３個の下位ビットのことである。
【００７９】
その後、書込処理部２４は。記憶装置３０内の全データについての、ステップＳ４０４以降の処理が完了しているか否かを判断する（ステップＳ４０３）。そして、書込処理部２４は。全データについての処理が完了していなかった場合（ステップＳ４０３；ＮＯ）には、まず、記憶装置３０内の最初／次のデータについてのｋ個のハッシュ値を算出する（ステップＳ４０４）。
【００８０】
次いで、書込処理部２４は、算出した各ハッシュ値について（ステップＳ４０５；ＮＯ）、ステップＳ４０６以降の処理を行う。
【００８１】
或るハッシュ値（以下、処理対象ハッシュ値と表記する）についてのステップＳ４０６以降の処理を開始した書込処理部２４は、まず、処理対象ハッシュ値に対応づけられているビット値を、上位ビット値フィルタから読み出す（ステップＳ４０６）。
【００８２】
そして、書込処理部２４は、読み出したビット値が“０”であった場合（ステップＳ４０７；ＹＥＳ）には、特に処理を行うことなく、ステップＳ４０５に戻って、次のハッシュ値に対する処理を開始する。
【００８３】
一方、読み出したビット値が“１”であった場合（ステップＳ４０７；ＮＯ）、書込処理部２４は、処理対象ハッシュ値に対応付けられている下位ビットの値をフィルタ２８から読み出す（ステップＳ４０８）。そして、書込処理部２４は、読み出した値が“０”であった場合（ステップＳ４０９；ＹＥＳ）には、処理対象ハッシュ値に対応付けられている下位ビットの値を“１”に変更（ステップＳ４１１）してから、ステップＳ４０５に戻って、次のハッシュ値に対する処理を開始する。
【００８４】
また、書込処理部２４は、読み出した値が“１”であった場合（ステップＳ４０９；ＮＯ）には、処理対象ハッシュ値に対応付けられている上位ビットに“１”を設定する（ステップＳ４１０）。その後、書込処理部２４は、ステップＳ４０５に戻って、次のハッシュ値に対する処理を開始する。
【００８５】
書込処理部２４は、このような処理を、算出した各ハッシュ値について行ってから（ステップＳ４０５；ＹＥＳ）、残りの各データについても同様の処理を行う。そして、書込処理部２４は、全データに対する処理が完了したときに（ステップＳ４０３；ＹＥＳ）、この再構築処理を終了する。
【００８６】
要するに、本実施形態に係るフィルタ２８は、上記更新手順から明らかなように、上位ビットの値が“０”となっている下位ビットの値（“０”又は“１”）は、常に正確なものとなっている。そのため、再構築処理を、上位ビットの値が“０”となっている下位ビットの値（“０”又は“１”）の再構築を省略する処理としてあるのである。
【００８７】
《変形形態》
上記した重複除去ストレージ装置１０については、各種の変形を行うことが出来る。例えば、重複除去ストレージ装置１０を、上記した再構築処理（図１３）の代わりに、図１５に示した手順の再構築処理を実行する装置に変形することが出来る。すなわち、重複除去ストレージ装置１０を、フィルタ２８がクリアされてから、記憶装置３０内の各データについて追加処理（図９）が行われる再構築処理（ステップＳ５０１〜５０３）を実行する装置に変形することが出来る。
【００８８】
また、上位ビット共有ＣＢＦ２８として、図１６Ａに示したように、２個の下位ビット毎に１個の上位ビットを備えたものや、図１６Ｂに示したように、各上位ビット配下の下位ビット数が異なるものを用いることも出来る。
【００８９】
さらに、上位ビット共有ＣＢＦ２８として、“下位ビット”に相当する部分にｎビットの情報（以下、カウンタ値と表記する）が記憶できるものを採用することも出来る。尚、そのような上位ビット共有ＣＢＦ２８を用いる場合、図１７に示した手順の追加処理、図１８に示した手順の削除処理が行われるようにしておけば良い。
【００９０】
すなわち、ｎビットのカウンタ値を記憶できる上位ビット共有ＣＢＦ２８を用いる場合、以下の点が、上記したものとは異なる追加処理が行われるようにしておけば良い。
ステップＳ２０３に相当するステップＳ２０３′にて、最初／次のハッシュ値に対応づけられているカウンタ値（以下、対応カウント値と表記する）がフィルタ２８から読み出される。
ステップＳ２０４に相当するステップＳ２０４′にて、『対応カウンタ値＜２ｎ−１』が成立するか否かが判断される。
ステップＳ２０６に相当するステップＳ２０６′にて、フィルタ２８の対応カウンタ値に“１”が加算される。
【００９１】
また、ｎビットのカウンタ値を記憶できる上位ビット共有ＣＢＦ２８を用いる場合、以下の点が、上記したものとは異なる削除処理が行われるようにしておけば良い。
ステップＳ３０５に相当するステップＳ３０５′にて、フィルタ２８の対応カウンタ値が“１”デクリメントされる。
【００９２】
重複除去ストレージ装置１０を、上記したものとは異なる構成のブロックマップ２３やハッシュ値検索テーブル２５を備えた装置に変形することも出来る。さらに、ストレージ
制御プログラム２０から、上位ビット共有ＣＢＦ２８の参照／更新によるデータの有無判定に関する部分のみを取り出したプログラムを作成しても良いことや、上記内容のデータの有無判定を、重複除去ストレージ装置１０以外の装置に適用しても良いことなどは、当然のことである。
【００９３】
以上開示した技術に関し、更に以下の付記を開示する。
【００９４】
（付記１）  それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、
それぞれ、前記Ｌ個のハッシュ値の中の互いに異なる１つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域と、
或るデータ集合に含まれるデータ毎に、そのデータについてのｋ個のハッシュ値を前記Ｌ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶する情報設定部と、
前記ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、入力データが、前記データ集合に含まれていない新規データであると判定する判定部と、
を備えることを特徴とするデータ有無判定装置。
【００９５】
（付記２）  前記Ｌ個の第１記憶領域と前記Ｍ個の第２記憶領域とが、同一のメモリ上に、同一のハッシュ値に対応づけられている前記第１記憶領域に記憶されたカウント値と前記第２記憶領域に記憶された値とが１回のメモリアクセスで読み出せるように確保されている
ことを特徴とする付記１に記載のデータ有無判定装置。
【００９６】
（付記３）  前記データ集合から取り除くデータについてのｋ個のハッシュ値を前記ｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応付けられている第２記憶領域上の値が“０”であった場合に限り、そのハッシュ値に対応付けられている第１記憶領域上のカウンタ値を“１”デクリメントする登録情報削除部を、さらに備える
ことを特徴とする付記１又は２のいずれか一項に記載のデータ有無判定装置。
【００９７】
（付記４）  ｎ＝１である
ことを特徴とする付記１乃至３のいずれか一項に記載のデータ有無判定装置。
【００９８】
（付記５）  各第２記憶領域が同数のハッシュ値に対応付けられている
ことを特徴とする付記１乃至３のいずれか一項に記載のデータ有無判定装置。
【００９９】
（付記６）  メモリ上に確保された、それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、それぞれ、前記Ｌ個のハッシュ値の中の互いに異なる１つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域とを用いて、入力データが、既存のデータ集合に含まれていない新規データであるか否かを判定するデータ有無判定方法であって、
コンピュータが、
前記データ集合に含まれるデータ毎に、そのデータについてのｋ個のハッシュ値を前記
Ｌ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶し、
前記ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、入力データが、前記データ集合に含まれていない新規データであると判定する
ことを特徴とするデータ有無判定方法。
【０１００】
（付記７）  コンピュータを、
それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、
それぞれ、前記Ｌ個のハッシュ値の中の互いに異なる１つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域と、
或るデータ集合に含まれるデータ毎に、そのデータについてのｋ個のハッシュ値を前記Ｌ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶する情報設定部と
前記ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、入力データが、前記データ集合に含まれていない新規データであると判定する判定部と、
を備える装置として動作させることを特徴とするデータ有無判定プログラム。
【０１０１】
（付記８）  コンピュータを、
それぞれ、Ｌ個のハッシュ値の中の互いに異なるハッシュ値に対応づけられた、ｎ（≧１）ビットのカウント値を記憶するＬ個の第１記憶領域と、
それぞれ、前記Ｌ個のハッシュ値の中の互いに異なる１つ以上のハッシュ値に対応付けられた、１ビットの値を記憶するＭ（＜Ｌ）個の第２記憶領域と、
或るデータ集合に含まれるデータ毎に、そのデータについてのｋ個のハッシュ値を前記Ｌ個のハッシュ値のいずれかが算出されるｋ個のハッシュ関数を用いて算出し、算出した各ハッシュ値について、そのハッシュ値に対応づけられている第１記憶領域上のカウント値が、２ｎ−１よりも少ない場合には、当該カウント値をカウントアップし、当該カウント値が、２ｎ−１であった場合には、そのハッシュ値に対応づけられている第２記憶領域に“１”を記憶する情報設定部と
前記ｋ個のハッシュ関数を用いて、入力データのｋ個のハッシュ値を算出し、算出したいずれかのハッシュ値に対応付けられている第１記憶領域上のカウント値が“０”であった場合に、入力データが、前記データ集合に含まれていない新規データであると判定する判定部と、
を備える装置として動作させるデータ有無判定プログラムを記録したコンピュータ可読媒体。
【符号の説明】
【０１０２】
１０    重複除去ストレージ装置
１１    ＣＰＵ
１２    メモリ
１３    ＨＤＤ
２０    ストレージ制御プログラム
２１    プロトコル処理部
２２    読込処理部
２３    ブロックマップ
２４    書込処理部
２５    ハッシュ値検索テーブル
２８    上位ビット共有カウンティングブルームフィルタ
３０    記憶装置
５０    コンピュータ
１００    ホスト
【図１Ａ】
0005821744.tif 000002
【図１Ｂ】
0005821744.tif 000003
【図２Ａ】
0005821744.tif 000004
【図２Ｂ】
0005821744.tif 000005
【図３】
0005821744.tif 000006
【図４】
0005821744.tif 000007
【図５】
0005821744.tif 000008
【図６】
0005821744.tif 000009
【図７】
0005821744.tif 000010
【図８】
0005821744.tif 000011
【図９】
0005821744.tif 000012
【図１０】
0005821744.tif 000013
【図１１Ａ】
0005821744.tif 000014
【図１１Ｂ】
0005821744.tif 000015
【図１１Ｃ】
0005821744.tif 000016
【図１１Ｄ】
0005821744.tif 000017
【図１１Ｅ】
0005821744.tif 000018
【図１２】
0005821744.tif 000019
【図１３】
0005821744.tif 000020
【図１４】
0005821744.tif 000021
【図１５】
0005821744.tif 000022
【図１６Ａ】
0005821744.tif 000023
【図１６Ｂ】
0005821744.tif 000024
【図１７】
0005821744.tif 000025
【図１８】
0005821744.tif 000026