情報検索装置、情報検索方法
【課題】様々な時系列データに対して類似検索をすることができる情報検索装置を提供する。
【解決手段】擬似コード列生成部１６は複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、それらを構成要素とする擬似コード列を生成する。比較部３２は擬似コード列をパターンとして、擬似コード列であるテキストの先頭から順にパターンの構成要素の数と同数のテキストを部分テキストとしつつ、当該部分テキストとパターンとの比較をパターンの最後尾の擬似コードから先頭の擬似コードに向かって順に行う。スキップ関数生成部２２は比較途中で結果が不一致となった場合に、現在の部分テキストの先頭から次の部分テキストの先頭までずらす量を出力する関数をスキップ関数として生成する。スキップ関数生成部２２は、擬似コードとして取り得る値すべてについてずらす量を計算する。比較部３２はスキップ関数に基づいてずらす量を決定する。
【解決手段】擬似コード列生成部１６は複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、それらを構成要素とする擬似コード列を生成する。比較部３２は擬似コード列をパターンとして、擬似コード列であるテキストの先頭から順にパターンの構成要素の数と同数のテキストを部分テキストとしつつ、当該部分テキストとパターンとの比較をパターンの最後尾の擬似コードから先頭の擬似コードに向かって順に行う。スキップ関数生成部２２は比較途中で結果が不一致となった場合に、現在の部分テキストの先頭から次の部分テキストの先頭までずらす量を出力する関数をスキップ関数として生成する。スキップ関数生成部２２は、擬似コードとして取り得る値すべてについてずらす量を計算する。比較部３２はスキップ関数に基づいてずらす量を決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は情報検索装置および情報検索方法に関する。
【背景技術】
【０００２】
近年、ネットワーク上には大規模な情報が蓄積されており、その量は増加の一途をたどるばかりである。それに伴い、こうした情報の中から利用者が必要とする情報を効率よく取り出すための情報検索技術はますますその重要さを増している。テキストストリングに対する全文検索技術は、非常に高速なアルゴリズムとしてよく知られているＢｏｙｅｒ−Ｍｏｏｒｅ法［１］をはじめとして多くの研究が行われている（非特許文献参照）。
【先行技術文献】
【特許文献】
【０００３】
【非特許文献１】D. Gusfield, "Algorithms on Strings, Trees, and Sequence: Computer Science and Computational Biology," Cambridge University Press, 1997.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、Ｂｏｙｅｒ−Ｍｏｏｒｅ法はテキストストリングに対する全文検索技術であるため、一般の時系列データ、ベクトルデータに対しては適用することができない。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、様々な時系列データに対して類似検索をすることができる情報検索装置を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は情報検索装置に関する。この装置は、複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する擬似コード列生成部と、前記擬似コード列をパターンとして、擬似コード列であるテキストの先頭から順に前記パターンの構成要素の数と同数のテキストを部分テキストとしつつ、当該部分テキストと前記パターンとの比較を前記パターンの最後尾の擬似コードから先頭の擬似コードに向かって順に行う比較部と、比較途中で結果が不一致となった場合に、現在の部分テキストの先頭となっているテキストの位置から次の部分テキストの先頭となるテキストの位置までずらす量を、前記部分テキストの最後尾の擬似コードを入力として出力する関数をスキップ関数として生成するスキップ関数生成部とを含む。前記スキップ関数生成部は、擬似コードとして取り得る値すべてについて当該擬似コードが前記パターンの擬似コード列に含まれるか否かを特定し、含まれる場合には前記パターンの擬似コード列との位置関係から前記ずらす量を計算し、含まれない場合には前記パターンの擬似コード列の長さを前記ずらす量としてスキップ関数を生成する。前記比較部は、前記スキップ関数に基づいて現在の部分テキストの先頭から次の部分テキストの先頭までのずらす量を決定する。
【０００７】
本発明のさらに別の態様は情報検索方法に関する。この方法は、複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成するステップと、前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索するステップとをプロセッサに実行させる。
【０００８】
本発明のさらに別の態様は、情報を検索するためのプログラムに関する。このプログラムは、複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する機能と、前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索する機能とをコンピュータに実現させる。
【０００９】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１０】
本発明によれば、様々な時系列データに対して類似検索をすることができる情報検索装置を提供することができる。
【図面の簡単な説明】
【００１１】
【図１】ＬＳＰＣの例を示す図である。
【図２】２つのベクトル間の距離と二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされる確率との関係を示す図である。
【図３】ＢＭ法によるマッチングのプロセスを例示した図である。
【図４】図３の例におけるｓｋｉｐ関数である。
【図５】ＬＳＰＣにおけるｓｋｉｐ関数の一例を示す図である。
【図６】ＬＳＰＣにおけるｓｋｉｐ関数の別の一例を示す図である。
【図７】新聞画像の一部を例示した図である。
【図８】新聞画像から切出された文字を例示した図である。
【図９】検索対象とした文字列の画像を例示した図である。
【図１０】Ｒｅｃａｌｌ優先の設定の場合の実験結果を示す図である。
【図１１】Ｐｒｅｃｉｓｉｏｎ優先の設定の場合の実験結果を示す図である。
【図１２】実施の形態にかかる情報検索装置の全体構成を模式的に示した図である。
【図１３】実施の形態にかかる情報検索装置の処理の流れを説明するフローチャートである。
【図１４】テキストに含まれるパターンを検索する処理の流れを説明するフローチャートである。
【発明を実施するための形態】
【００１２】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１３】
［前提技術］
［１］ はじめに
本発明の実施の形態は、テキストストリングからキーワードを検索するアルゴリズムであるＢｏｙｅｒ−Ｍｏｏｒｅ法［１］（以下、「ＢＭ法」という。）の検索対象を、一般の実ベクトル系列に拡張したものである。実施の形態の基礎技術は、実ベクトルを擬似コード表現に変換し、その擬似コードの二項関係に基づいて探索ができるように、ＢＭ法を拡張したことである。
【００１４】
ネットワーク上には大規模な情報が蓄積されており、その量は増加の一途をたどるばかりである。それに伴い、こうした情報の中から利用者が必要とする情報を効率よく取り出すための情報検索技術はますますその重要さを増している。テキストストリングに対する全文検索技術はそのうちの最も基本的なものであると言え、古くから多くの研究が行われている。中でも、ＢＭ法は非常に高速なアルゴリズムとしてよく知られている。文字列照合に基づくアルゴリズムであるＢＭ法は、キーワードの末尾から照合を行うことで、テキストストリングのうちのいくつかの文字については１回もアクセスすることなく、すなわち、サブリニア時間で検索を行うことができる。
【００１５】
実施の形態は、このＢＭ法を拡張し、検索対象をテキストストリングから一般の実ベクトル系列に拡張する。これは、さまざまな時系列データ、あるいは擬似的に時系列と見なせるデータに対して高速な類似検索を提供するための基盤となりうる技術である。
【００１６】
この拡張における主な要素技術は次の２点である。１つは実ベクトルを擬似コードとして離散化表現する技術であるＬＳＰＣ［２］（後述する）である。この擬似コードＬＳＰＣは、通常のベクトル量子化に比べて、もとの実ベクトルの記述力を極力損なわないままベクトルを離散化することができる。ただしこの擬似コードにおいて中心的な役割を果たす二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔ（後述する）は同値関係ではなく、推移律を満たさないものであるため、既存の文字検索アルゴリズムがそのまま適用できるわけではない。そこで第２の要素技術として、実施の形態では、既存の文字列検索アルゴリズムのうち最も有力なものの１つであるＢＭ法について、これをＬＳＰＣに適用可能なようにアレンジする。これがＥｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法である。
【００１７】
アルゴリズムの詳述に先立ちあらかじめ本手法の限界点を述べると、ＬＳＰＣによる疑似コードの変換は確率的アルゴリズムであるため、それに基づく検索アルゴリズムでは結果が確実に正確であることは保証されない。試行回数やその他のパラメタの設定によって正確な出力が得られる確率を高めることはできるものの、それは計算量とトレードオフである。この点は他の確率的アルゴリズムと同様である。
【００１８】
［２］ 擬似コードＬＳＰＣ
［２．１］ ＬＳＰＣの概要
ＬＳＰＣ（Ｌｏｃａｌｉｔｙ−Ｓｅｎｓｉｔｉｖｅ Ｐｓｅｕｄｅ−Ｃｏｄｅ）は、Ｔｅｒａｓａｗａ ａｎｄ Ｔａｎａｋａ［２］により提唱された、実ベクトルを擬似コード表現に変換する技術である。通常のベクトル量子化とは異なり、１つのベクトルに対して複数の整数を割り当てることで、通常のベクトル量子化よりも豊かな記述力を残したままベクトルを離散化する。
【００１９】
図１はＬＳＰＣの例を図示したものである。図１中、黒丸がｄ次元の実空間（Ｒｄ空間）に分布しているベクトルを表し、黒丸に付けられた（８，１，４）などの数字の３つ組がそのベクトルを離散化した結果の擬似コードを表している。このように、１つのベクトルに複数の整数を割り当てることが擬似コードＬＳＰＣの特徴である。そして、ＬＳＰＣのもう１つの特徴が、そこに導入される二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔである。２つの擬似コードに割り当てられた複数の整数のうち、１つでも一致していればそれらのコード間で二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされると定義する。
【００２０】
以上をまとめると以下のようになる。
定義１（疑似コードＬＳＰＣの定義）：ｄ次元実ベクトルｐに対し、擬似コードＣ（ｐ）は、ｄ’個の整数の組として与えられる。すなわち、
ｐ∈Ｒｄ→Ｃ（ｐ）＝（ｃ１（ｐ） ｃ２（ｐ）・・・ｃｄ’（ｐ））Ｔ∈Ｎｄ。
定義２（二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔの定義）：擬似コードＬＳＰＣにおいてＣ（ｐ）＝｛ｃｉ（ｐ）｝とＣ（ｑ）＝｛ｃｉ（ｑ）｝とが二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たすとは、ｃｉ（ｐ）＝ｃｉ（ｑ）を満たすようなｉ∈｛１，・・・，ｄ’｝が存在することである。
【００２１】
ＬＳＰＣでは、通常のベクトル量子化よりも多様な表現が可能である。例えば、通常のベクトル量子化においては、境界面付近では似たベクトルに別な符号が割り当てられてしまうケースがどうしても発生する。一方ＬＳＰＣでは、図１に示すように、ある擬似コードとｓｅｍｉｅｑｕｉｖａｌｅｎｔな範囲と、別のあるコードとｓｅｍｉｅｑｕｉｖａｌｅｎｔな範囲とがオーバーラップすることが許されている。これにより、近いベクトル同士に割り当てられた擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔになる確率を極めて高くなるように擬似コードを割り振ることが可能となる。
【００２２】
二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされるか否かは、２つのベクトルの間の距離に依存している。図２は、２つのベクトル間の距離と二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされる確率との関係を図示したものである。この性質を用いて、２つのベクトル間の距離が一定の閾値以上であるか否かを、擬似コードの二項関係だけから推定することができる。例えば図２における実線が表す曲線の例であれば、２つのベクトル間の距離が０．９以上であればそれらのベクトルに対応する擬似コード同士がｓｅｍｉｅｑｕｉｖａｌｅｎｔである確率は極めて小さく、一方で２つのベクトル間の距離が０．４以下であればそれらのベクトルに対応する擬似コード同士がｓｅｍｉｅｑｕｉｖａｌｅｎｔである確率は極めて大きい。この性質を用いることで、２つの擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔであるかどうかを調べるだけで、元々のベクトル間の距離が大きいのか小さいのかをおおよそ推測することができる。
【００２３】
ここで重要な点は、擬似コードＣ（ｐ）、Ｃ（ｑ）が二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たすかどうかを照合するためのコストは、２つのベクトルｐ、ｑ間の距離を計算するコストよりも小さいということである。この差は特にもとのベクトル空間が高次元である場合に顕著である。パターン認識で用いられる特徴ベクトルの空間は非常に高い次元数を持つ場合がしばしばあるので、ＬＳＰＣを使用することによる計算コスト削減が大きな効果を持つことが期待できる。
【００２４】
［２．２］ ＬＳＰＣの構成法
前節では、擬似コードＬＳＰＣの持っている性質について述べた。この節では、そのような性質を持つ擬似コードをいかにして構成することができるかについて述べる。
【００２５】
擬似コードＬＳＰＣの各要素には、Ｌｏｃａｌｉｔｙ Ｓｅｎｓｉｔｉｖｅ Ｈａｓｈｉｎｇ（ＬＳＨ）［３］〜［５］のハッシュ関数のハッシュ値を利用する。ＬＳＨは、近似的最近傍探索問題の解法として非常に有力なものとして近年注目されているアルゴリズムである。以下、まずＬＳＨの概略を述べる。
【００２６】
ＬＳＨアルゴリズムにおいて中心的な役割を果たすのは、以下で定義されるＬＳＨ ｆａｍｉｌｙと呼ばれる関数族である。
定義３（ＬＳＨ ｆａｍｉｌｙ）：ベクトル空間Ｓから適当な離散空間Ｕへの関数族Ｈ＝｛ｈ：Ｓ→Ｕ｝は、以下を満たすとき（ｒ１，ｒ２，ｐ１，ｐ２）−ｓｅｎｓｉｔｉｖｅであると呼ばれる。
任意のｖ、ｑ∈Ｓについて、
ｄ（ｖ，ｑ）≦ｒ１のときＰｒＨ［ｈ（ｑ）＝ｈ（ｖ）］≧ｐ１。
ｄ（ｖ，ｑ）≧ｒ２のときＰｒＨ［ｈ（ｑ）＝ｈ（ｖ）］≦ｐ２。
ここでｄ（ｖ，ｑ）はベクトルｖ、ｑ間の距離を表し、ｐ１＞ｐ２、ｒ１＜ｒ２とする。
【００２７】
なお、このような関数族の存在はＬ１空間において［３］、ｓ∈（０，２］の任意のＬｓ空間において［４］、任意の次元の単位球上において［６］、それぞれ保証されている。
【００２８】
関数族Ｈに属する関数は、ベクトルｖ∈Ｒｄを整数ｈ（ｖ）∈Ｎに写像するという意味で、ハッシュ関数であると言える。近傍探索問題の解法としてのＬＳＨは、データ集合内の全ての点についてあらかじめハッシュ値を計算してハッシュ表を作成しておいて、クエリ点と同じハッシュ値を持つ点だけをハッシュ表から探し出して探索の対象にする。こうすることによって、クエリ点との距離を計算されるべき点の数を大きく削減する、というのがＬＳＨの基本アイデアである。
【００２９】
ＬＳＨにおける優れた工夫の一つは、ハッシュ関数を複数使うことによって、Ｆａｌｓｅ ｐｏｓｉｔｉｖｅを減らしつつ、Ｆａｌｓｅ ｎｅｇａｔｉｖｅを減らすようにできることである。例えば、あるＬＳＨ ｆａｍｉｌｙがあって、その中の関数は図２の点線で示されるような衝突確率を持っていたとする。ＬＳＨは、この関数ｋ個を組み合わせた関数をＬ個作ることで、その確率の差を増幅する。つまり、ｈｉｊをＬＳＨ ｆａｍｉｌｙ Ｈからランダムに選ばれたハッシュ関数として、
ｇｉ（ｐ）＝｛ｈｉ１（ｐ），ｈｉ２（ｐ），・・・ｈｉｋ（ｐ）｝ （１）
をｇ１（ｐ）からｇＬ（ｐ）までＬ個作成することによって、実効的な衝突確率を図２の実線のように変換するのである。
【００３０】
ＬＳＨの近傍探索問題の解き方は次のとおりである。まず、すべての点ｐに対するｇ１（ｐ），ｇ２（ｐ），・・・ｇＬ（ｐ）をあらかじめ計算し、ハッシュ表に格納しておく。クエリ点ｑが入力されたら、ｇ１（ｑ），ｇ２（ｑ），・・・ｇＬ（ｑ）を計算し、∃ｉ、ｇｉ（ｐ）＝ｇｉ（ｑ）となるような点ｐだけをハッシュ表から見つけてきて、探索の対象とする。これにより、クエリ点から遠い点との距離計算を減らしつつ、クエリ点に近い点の取りこぼしを減らすということを実現している。
【００３１】
擬似コードＬＳＰＣの基本アイデアは、このＬＳＨのハッシュ値は擬似コードとして使えるのではないかという着想である。ＬＳＨは近傍探索問題を解くためのハッシュ表を作成するための手段としてハッシュ関数を使っていたが、ＬＳＰＣではベクトル系列のマッチングのための擬似コード表現として同じハッシュ関数を用いるのである。すなわち、
定義４（疑似コードＬＳＰＣの構成法）：ｐ∈Ｒｄに対し、擬似コードＬＳＰＣ Ｃ（ｐ）を以下のように定義する。
Ｃ（ｐ）＝｛ｇ１（ｐ），ｇ２（ｐ），・・・ｇＬ（ｐ）｝ （２）
ｇｉ（ｐ）＝｛ｈｉ１（ｐ），ｈｉ２（ｐ），・・・ｈｉｋ（ｐ）｝ （３）
ここでｈｉｊはＬＳＨ ｆａｍｉｌｙ Ｈからランダムに選ばれた関数である。
【００３２】
上記の定義ではＣ（ｐ）はｋＬ個の整数から構成されるが、実用上これを次の方法でＬ個の整数として表すことにする。すなわち、ｈｉｊの値域は有限の整数であるので、この上限をＭとおく。このとき、ｇｉ（ｐ）＝ｈｉ１（ｐ）Ｍｋ−１＋ｈｉ２（ｐ）Ｍｋ−２＋・・・ｈｉｋ（ｐ）とすることで、ｇｉ（ｐ）は１つの整数で表すことができる。従って、Ｃ（ｐ）はＬ個の整数として表せる。
【００３３】
ＬＳＨにおける近傍探索は、クエリｑに対して、ハッシュ表から∃ｉ、ｇｉ（ｐ）＝ｇｉ（ｑ）となるような点ｐをすべて拾ってくるのであった。それに対応する、擬似コードＬＳＰＣにおける二項関係が次に述べるｓｅｍｉｅｑｕｉｖａｌｅｎｔである。
定義５（二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔの定義）：ＬＳＰＣ Ｃ（ｐ）＝｛ｇｉ（ｐ）｝とＣ（ｑ）＝｛ｇｉ（ｑ）｝とがｓｅｍｉｅｑｕｉｖａｌｅｎｔであるとは、ｇｉ（ｐ）＝ｇｉ（ｑ）となるようなｉが存在することである。
【００３４】
この二項関係が満たされているか否かは、前述の図２の実線に示すとおり、もとのベクトルｐ、ｑの間の距離に依存している。
【００３５】
ここで改めてパラメータｋとＬの意味を考えてみる。ｐ（ｃ）が単一のハッシュ関数で、間の距離がｃである２つの点が衝突する（同じハッシュ値を持つ）確率Ｐｓｅｍｉｅｑがそれらの点に対応する擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔである確率を表すとする。ＬＳＰＣでは、単一のハッシュ関数をｋ個組み合わせた物をＬ個作る、という操作で、Ｐｓｅｍｉｅｑを
Ｐｓｅｍｉｅｑ＝１−（１−ｐ（ｃ）ｋ）Ｌ （４）
のように増幅している。ｋとＬの値を設定することにより、図２における曲線の位置を変えることができる。ｋを増やせば曲線は左に移動し、Ｌを増やせば曲線は右に移動する。ｋとＬをともに増やせば、およその位置を変えずに曲線の勾配を増すことができる。
【００３６】
［３］ Ｂｏｙｅｒ−Ｍｏｏｒｅ法
この章では、Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法の前提となる、ＢＭ法について述べる。ＢＭ法は文字列検索アルゴリズムとしては古典的でかつきわめて有力な方法であり、多くの解説書が出版されている。以下の説明では、Ｂａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅの名は文献［７］に、ｓｋｉｐ関数の名は文献［８］によった。
【００３７】
なお、文献［７］で説明されているＢｏｙｅｒ−Ｍｏｏｒｅアルゴリズムは、Ｇｏｏｄ Ｓｕｆｆｉｘ ＲｕｌｅとＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅの２つの柱から構成されているが、このうちＬＳＰＣのような推移律を満たさないコードに適用可能なものは後者のみである。今日ＢＭ法と呼ばれるものには微妙なバリエーションがあるが、ちょうど文献［８］のＢＭ法の説明がＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅのみに焦点が置かれたものとなっており、Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法の前提とするのに都合がよいので、ここでは文献［８］に従い、Ｂｏｙｅｒ−ＭｏｏｒｅアルゴリズムのＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅについて、その概要を述べる。
【００３８】
まず、問題を正確に定式化する。Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題とは、次のような問題である。
定義６（Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題）：長さｎの文字列Ｐ（パターンあるいはキーワードと呼ぶ）と、長さｍ（≧ｎ）の文字列Ｔ（テキストと呼ぶ）とが与えられたとき、テキスト中のキーワードの出現開始位置、すなわちＰ（ξ）＝Ｔ（ｉ＋ξ−１）ｆｏｒ ａｌｌ ξ＝１，２，・・・，ｎとなるようなｉをすべて見つけること。
【００３９】
なお、文字列Ｐに対し、Ｐ（ξ）はＰのξ番目の文字を表す。たとえば、Ｔ＝ａｂｘａｂａｂａｂｘａｂａｂｘ、Ｐ＝ａｂａｂの時、Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題の解は｛４，６，１１｝である。また、以下では文字列Ｓのｉ番目からｊ番目の文字（ｊ≧ｉ）までで構成される部分文字列をＳ［ｉ：ｊ］と書くことにする。
【００４０】
Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題の素朴な解法（ｎａｉｖｅ ｍｅｔｈｏｄ）は、パターンＰに対し、まずＴの部分文字列Ｔ［１：ｎ］と照合を行い、次にＴ［２：ｎ＋１］、その次にＴ［３：ｎ＋２］・・・という具合に、Ｔの部分文字列の始点を１つずつずらしながらすべての部分文字列と照合を行う方法である。この方法の計算コスト（文字列照合回数）最小でｍであり、最大でＯ（ｍｎ）である。
【００４１】
ここからＢＭ法について述べる。素朴な解法がＴの部分文字列の始点を１つずつずらしながら文字列の照合を行っていくのに対し、ＢＭ法は始点を１つよりも大きくずらすことによって計算量を縮減する。
【００４２】
なお、文献［７］によればＢＭ法はＢａｄ Ｃｈａｒａｃｔｅｒ ＲｕｌｅとＧｏｏｄ Ｓｕｆｆｉｘ Ｒｕｌｅからなっており、この両方を用いることで計算量がＯ（ｍ）で抑えられることが保証される。一方で文献［８］では、上記２つのルールのうちＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅのみを使ったものをＢＭ法と呼んでおり、この場合はＯ（ｍ）の計算量が保証されない（最悪の場合Ｏ（ｍｎ）になってしまう）。しかし、極端な場合の入力（例えばＴ＝ａａａａａａａ、Ｐ＝ａａａ）を考えなければ、通常の場合はこれだけでも十分に高速である。
【００４３】
図３はＢＭ法によるマッチングのプロセスを例示したものである。ここでは、例としてＴ＝ａｂｃｂａｘａｂａｃａｂｂｃ、Ｐ＝ａｂａｃという場合を考える。ＢＭ法も素朴な解法と同様に、まずＰとＴ［１：４］とを照合する。ただしこの照合にあたって、ＢＭ法は文字の照合をＰとＴ［１：４］の末尾（すなわちこの場合は４文字目）から順に開始するというところに特徴がある。今の例の場合、Ｔ［１：４］の４文字目はｂ、Ｐの４文字目はｃであるから照合結果は「不一致」であり、Ｔの部分文字列の始点をずらして次の照合へ進む。
【００４４】
さてここでポイントは、Ｔの部分文字列の始点を何文字ずらすかである。いま、Ｔ［１：４］の４文字目はｂであることはすでに調べた。ということは、仮に１文字ずらした場合、次はＴ［２：５］の３文字目がｂであることはわかっているので、これがＰと一致しないことは調べるまでもなく明らかである。仮に２文字ずらすとすると、Ｔ［３：６］の２文字目であるｂは、Ｐの２文字目と一致する。よってこれは調べる価値がある。従ってＴ［１：４］を不一致と判断した次に調べるべきＴの文字列はＴ［３：６］であることがわかる。
【００４５】
では次に、Ｔ［３：６］とＰの照合を行う。Ｔ［３：６］の４文字目はｘ、Ｐの４文字目はｃであるから照合結果は不一致であり、Ｔの部分文字列の始点をずらして次の照合へ進む。さて今の場合、Ｔ［３：６］の４文字目であるｘはＰの中に一度も出てこない。ということは、Ｔ（６）＝ｘを含むようなＴの部分文字列とＰとは決して一致しないことはこの時点で明らかである。よって次に照合すべきＴの部分文字列は、一気に４つ飛んでＴ［７：１０］であるということになる。
【００４６】
続いて、ＰとＴ［７：１０］との照合を行う。ここも末尾から順に照合を行う。照合を４回行ったところで、ＰとＴ［７：１０］の全体が一致していることが判明するので、始点位置“７”が出力される。そして、末尾のｃに着目すると、Ｔ［７：１０］を１文字ずらした場合も２文字ずらした場合も３文字ずらした場合もＰとは一致しないことが明らかであるので、次に照合すべきＴの部分文字列は、４つ飛んでＴ［１１：１４］となる。最後にＴ［１１：１４］とＰの照合を行い、後ろから２番目の文字で不一致が判明して、アルゴリズムは終了する。図４は、図３の例におけるｓｋｉｐ関数である。
【００４７】
上記のＢＭ法のアルゴリズムでポイントとなるのは、Ｔ［ｉ：ｉ＋３］の４文字目が何であった場合に、次に照合するＴの始点を何文字ずらせばよいか、ということである。ここではこの「何文字ずらせばよいか」の値を「ｓｋｉｐ関数」で表すことにする。すなわち、ｓｋｉｐ（ｘ）は、Ｔ［ｉ：ｉ＋３］の末尾の文字（４文字目）がｘであった場合に照合の始点をずらすべき数として定義され、最小は１であり、最大はＰの長さ（この場合は４）である。
【００４８】
ｓｋｉｐ関数は次のように構成される。ｓｋｉｐ関数は、定義域として想定しているすべての文字（アルファベットΣと呼ぶ）、値域として１以上ｎ以下の自然数を持つ関数である。まず、すべての文字ｘ∈Σについて、ｓｋｉｐ（ｘ）をｎに初期化する。次に、Ｐの（ｎ−ｉ）文字目がｘであったら、ｓｋｉｐ（ｘ）をｉに更新する。この手続をｉ＝ｎ−１，ｎ−２，・・・，１の順に繰り返せば、所望のｓｋｉｐ関数が得られる。
【００４９】
ＢＭ法の特徴は、パターン文字列Ｐが長ければ長いほど、また、文字列中から適当に２つ選んだ文字が適合する確率が低いほど（すなわち文字種が多いほど）、効率が良くなるということである。
【００５０】
［４］ Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法
定義６で述べた問題をＬＳＰＣに拡張した問題を次のように定義する。
定義７（ＬＳＰＣに拡張されたＳｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題）：長さｎの擬似コード列Ｐと、長さｍ（≧ｎ）の擬似コード列Ｔとが与えられたとき、Ｐ（ξ）〜Ｔ（ｉ＋ξ−１）ｆｏｒ ａｌｌ ξ＝１，２，・・・，ｎとなるようなｉをすべて見つけること。
【００５１】
ここで、Ｓ（ｉ）〜Ｔ（ｊ）とは、Ｓ（ｉ）とＴ（ｊ）が二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たす関係にあることを意味する。
【００５２】
Ｅｘｔｅｎｄｅｄ ＢＭ法のアルゴリズムは、基本的にはＢＭ法と同じである。すなわち、
［Ｅｘｔｅｎｄｅｄ ＢＭ法のアルゴリズム］
まず、ｉ＝１として、ＰとＴ［ｉ：ｉ＋ｎ−１］が対応するか、すなわちＰ（ξ）〜Ｔ（ｉ＋ξ−１）ｆｏｒ ａｌｌ ξ＝１，２，・・・，ｎが成り立つかどうかを調べる。オリジナルのＢＭ法と同じく、この照合は右から左の順、すなわちξ＝ｎ，ｎ−１，ｎ−２，・・・の順に行う。照合が失敗したらそこで照合を打ち切り照合がξ＝１まで成功した場合は、キーワードを発見したとして出力する。次に、次のｉ位置に対して照合を行うため、ｉをｓｋｉｐ（Ｔ（ｉ＋ｎ−１））だけ動かす。ｉ＋ｎ−１＞ｍとなったら照合を終了する。
【００５３】
Ｅｘｔｅｎｄｅｄ ＢＭ法のＢＭ法との違いは、ｓｋｉｐ関数の構成法である。理論的には、ｓｋｉｐ関数は次の方法で構成される。すなわち、今回想定されるｓｋｉｐ関数の定義域は、擬似コードの取り得るあらゆる値（文字列の例にならい、アルファベットΣと呼ぶことにする）であり、値域として１以上ｎ以下の自然数を持つ関数である。まず、すべてのｘ∈Σにつて、ｓｋｉｐ（ｘ）をｎに初期化する。次に、擬似コードＰ（ｎ−ｉ）に対し、それとｓｅｍｉｅｑｕｉｖａｌｅｎｔになるようなすべての擬似コードｘ∈Σについて、ｓｋｉｐ（ｘ）をｉに更新する。この手続をｉ＝ｎ−１，ｎ−２，・・・，１の順に繰り返せば、所望のｓｋｉｐ関数が完成される。図５はＬＳＰＣにおけるｓｋｉｐ関数の一例を図示したものである。
【００５４】
理論上は上記で可能だが、現実的にはこのアルゴリズムは問題がある。この方法では、ｓｋｉｐ関数を格納するためにアルファベットΣのサイズに比例した配列サイズが必要だが、擬似コードＬＳＰＣはＬ個の整数を要素として持っている。各要素の値は１からＮまでであるとすると、この場合必要な配列のサイズはＮＬとなってしまい、実際にＬの値として２０程度から数百程度のものを用いようとすると、このサイズの配列を確保するのは現実的に不可能である。そこで次の定理が重要となる。
【００５５】
定理１：疑似コードＣ（ｐ）＝（ｃ１（ｐ） ｃ２（ｐ） ・・・ｃｄ’（ｐ））に対するｓｋｉｐ関数は、次の形で表現できる。
ｓｋｉｐ（Ｃ（ｐ））＝ｍｉｎ（ｓｋｉｐ１（ｃ１（ｐ）），ｓｋｉｐ２（ｃ２（ｐ）），・・・，ｓｋｉｐｄ’（ｃｄ’（ｐ）））
ここで、ｓｋｉｐｉ（ｃｉ（ｐ））は、通常のＢＭ法におけるのと同じ方法で構成されるｓｋｉｐ関数である。
【００５６】
（証明）ｓｋｉｐ（Ｃ（ｐ））とは、Ｐ（ｎ−ξ）とＣ（ｐ）がｓｅｍｉｅｑｕｉｖａｌｅｎｔになるような最小の整数ξ＞０である。λ＜ｍｉｎｉ＝１，・・・，ｄ’（ｓｋｉｐ１（ｃ１（ｐ）））のとき、Ｐ（ｎ−λ）とＣ（ｐ）はｓｅｍｉｅｑｕｉｖａｌｅｎｔにならない。なぜなら、Ｐ（ｎ−λ）〜Ｃ（ｐ）とすると、あるδ∈｛１，・・・，ｄ’｝についてＰ（ｎ−λ）の第δ要素Ｃ（ｐ）の第δ要素が一致するはずであるが、これはλ＜ｓｋｉｐδ（Ｃδ（ｐ））に反するからである。逆にλ＝ｍｉｎｉ＝１，・・・，ｄ’（ｓｋｉｐ１（ｃ１（ｐ）））のとき、あるδについてλ＝ｓｋｉｐδ（Ｃδ（ｐ））であり、これはＰ（ｎ−λ）の第δ要素とＣ（ｐ）の第δ要素が一致することに他ならないので、Ｐ（ｎ−λ）とＣ（ｐ）はｓｅｍｉｅｑｕｉｖａｌｅｎｔである。よって、ｓｋｉｐ（Ｃ（ｐ））＝ｍｉｎｉ＝１，・・・，ｄ’（ｓｋｉｐｉ（ｃｉ（ｐ）））である。（証明終）
【００５７】
この工夫により、記憶容量はＭＬからＭＬに削減され、実装が現実的に可能となる。図６はＬＳＰＣにおけるｓｋｉｐ関数の別の一例を図示したものである。
【００５８】
［５］ 新聞画像による実験
Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法の応用の一例として、ＯＣＲによるテキスト化が困難な古い新聞画像に対する全文探索実験を行い、従来法によるものと検索コストを比較する。
【００５９】
［５．１］ 実験の概要
明治期の「函館毎日新聞」を対象とする。新聞資料はマイクロフィルムによって保存されており、これをスキャナで取り込みデジタル化したデータを用いる。図７は、新聞画像の一部を例示したものである。解像度は１文字あたりおおむね７０×７０ピクセル程度である。
【００６０】
なお、このような古い新聞画像に対する全文探索というのは決して容易なタスクではない。ＯＣＲによるテキスト化ができれば話は簡単だが、ＯＣＲは言語や書体に依存した技術であるため、現在とはフォントも語法も異なる明治期の画像に対してＯＣＲをそのまま適用しても十分な精度は得られない。実際、新聞画像に対して、ＯＣＲによらず画像検索技術を用いて全文検索を行うための研究は他にも行われている［９］。
【００６１】
［５．２］ 文字切出し
文字切出しは、段落の縦方向射影ヒストグラムによる行切出しと、段落の横方向射影ヒストグラムによる文字切出しとを組み合わせるという方法で行った。図８は、新聞画像から切出された文字を例示したものである。このような方法が採用可能なのは、本実験では新聞画像を対象としたため、段落画像における文字の配置がほぼ格子状になっているためである。
【００６２】
ただし、単純な方法をそのまま適用しただけではさまざまな問題が発生する。１つは、段落の最後の行に２，３文字しかない場合に行切出しが失敗しやすいということと、もう１つは、振り仮名（ルビ）が漢字の右側に多く振られており、これは文字のマッチングには用いないため、除去する必要があるということである。
【００６３】
そこで、自己相関関数を用いて本文の幅と振り仮名の幅を特定できるような形で行幅を推定し、上記２点の問題に対処することとした。
【００６４】
［５．３］ 特徴量ベクトルおよび擬似コードの構成
特徴量は、勾配分布特徴量［１０］を用いた。文字切出しされた画像を４×４の小領域に分割し、あとはＳＩＦＴ［１１］と同じような方法で１２８次元の特徴量ベクトルを構成する。
【００６５】
次いで、この各特徴量ベクトルを擬似コードＬＳＰＣに変換する。使用する関数族（ＬＳＨ ｆａｍｉｌｙ）としては、今回使用する特徴量ベクトルはノルムが１に正規化されているものであるので、ＳＬＳＨ［６］のｏｒｔｈｏｐｌｅｘ法を用いた。今回使用する特徴量ベクトルはその要素がすべて非負であるという性質を持っているため、この場合１つのハッシュ関数の値域は１〜１２８となる。ＬＳＰＣ構成の際に設定するパラメタｋおよびＬ（前述の２．２節参照）については、Ｒｅｃａｌｌを優先する設置とＰｒｅｃｉｓｉｏｎを優先する設定ということで、（ｋ，Ｌ）＝（３，２６）と（ｋ，Ｌ）＝（３，２４）の２種類を試した。前者は特徴量ベクトルがやや離れていても擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔになりやすいかわりに拾い漏らしが少ない設定（すなわちＲｅｃａｌｌ優先の設定）であり、後者はその逆（すなわちＰｒｅｃｉｓｉｏｎ優先の設定）である。
【００６６】
以上のような方法で、文字切出しされた各文字画像が１２８次元ベクトルに変換され、次いで擬似コードに変換されることにより、新聞画像が擬似コードに変換されたこととなる。これに対してＥｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することで、新聞画像に対する全文探索を行うことができる。
【００６７】
［５．４］ 実験
今回実験で用いた新聞画像は、全７５５文字からなる。これに対し、手作業でテキスト化したデータを作成した後にｎ−ｇｒａｍ解析にかけ、３回以上登場する文字列のうち最長の長さであった「のみならず」を実験対象に用いた。図９は検索対象とした文字列の画像を例示したものである。３箇所の「のみならず」に対し、それぞれをクリエとして残りの２つを探すという実験を行い、素朴な解法（ｎａｉｖｅ ｍｅｔｈｏｄ）と、Ｅｘｔｅｎｄｅｄ ＢＭ法の２つで、それぞれ文字照合回数を数え上げた。なおここでは比較を明確にするため、素朴な解法においても文字照合はパターンの末尾の文字から順に行った。
【００６８】
［５．５］ 実験結果
図１０は、Ｒｅｃａｌｌ優先の設定の場合の実験結果を示す図である。また、図１１はＰｒｅｃｉｓｉｏｎ優先の設定の場合の実験結果を示す図である。図１０および図１１中、Ｎａｉｖｅは素朴な解法、Ｅｘｔｅｎｄｅｄ ＢＭ法（実施の形態）を表し、（＃ｃｏｍｐ）は文字照合回数、（＃ｓｋｉｐ）はＥｘｔｅｎｄｅｄ ＢＭ法におけるｓｋｉｐ関数の評価回数を表している。また、Ｒｅｃａｌｌは再現率、Ｐｒｅｃｉｓｉｏｎは適合率であり、それぞれ以下の式で定義される。
【数１】
【００６９】
なお、図１０および図１１に掲げた素朴な解法よりもさらに素朴な方法として、文字列の照合中に不一致が見つかっても照合を打ち切らないアルゴリズムというものが考えられる。この場合の計算コスト（文字照合回数）は、いずれをクエリに用いた場合においても７５１×５＝３７５５である。
【００７０】
図１０および図１１からわかるとおり、すべてのクエリに対してＥｘｔｅｎｄｅｄ ＢＭ法の文字列照合回数は、素朴な解法のものを下回っている。中でも、図１０における１つめのデータと、図１１におけるすべてのデータにおいては、文字列照合回数が全文字数（７５５文字）を下回っており、サブリニア時間での検索を達成している。
【００７１】
ただし、Ｅｘｔｅｎｄｅｄ ＢＭ法においては、素朴な解法に対する追加コストとしてｓｋｉｐ関数の評価回数を考えなければならない。文字パターン照合はＬ個の自然数の一致／不一致を判定する処理であり、ｓｋｉｐ関数評価はＬ個の自然数の最小値を取る処理であるため、これらの計算コストを完全に同一視することはできないが、仮に同じだとすると、Ｅｘｔｅｎｄｅｄ ＢＭ法のコストは（＃ｃｏｍｐ）に（＃ｓｋｉｐ）を加えたものとして評価できる。この場合も、表のすべての場合においてＥｘｔｅｎｄｅｄ ＢＭ法の計算コストは素朴な解法よりも削減できていることになる。
【００７２】
［６］ 参考文献
［１］R. S. Boyer and J. S. Moore, "A fast string searching alogorithm," Communications of the ACM, vol. 20, pp. 762-772, Oct. 1977.
［２］K. Terasawa and Y. Tanaka, "Locality Sensitive Pseudo-Code for Document Images," Proc. 9th Int. Conf. on Document Analysis and Recognition, ICDAR2007, vol. 1, pp. 73-77, 2007.
［３］A. Gionis, P. Indyk, R. Motwani, "Similarity Search in High Dimensions via Hashing," Proc. 25th Int. Conf. on Very Large Data Base, VLDB1999, pp. 518-529, 1999.
［４］M. Datar, P. Indyk, N. Immorlica, V. Mirrokni, "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions," Proc. 20th ACM Symposium on Computational Geometry, SoCG2004, pp. 253-262, 2004.
［５］A. Andoni, P. Indyk, "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions," Proc. Symposium on Foundations of Computer Science, FOCS'06, pp. 459-468, 2006.
［６］K. Terasawa and Y. Tanaka, "Sperical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere," Proc. 10th Workshop on Algorithms and Data Structures, WADS2007, LNCS4619, pp. 27-38, 2007.
［７］D. Gusfield, "Algorithms on Strings, Trees, and Sequence: Computer Science and Computational Biology," Cambridge University Press, 1997.
［８］北研二、津田和彦、獅々堀正幹、“情報検索アルゴリズム、”共立出版株式会社、東京、２００２年１月。
［９］Yue Lu and Chew Lim Tan, "Word spotting in Chinese Document images without layout analysis," Proc. 16th Int. Conf. on Pattern Recognition, ICPR2002, vol.3, pp.57-60, 2002.
［１０］寺沢憲吾、長崎健、川嶋稔夫、“勾配分布特徴量による高精度手書き文字検索、”画像の認識・理解シンポジウム（ＭＩＲＵ）２００６講演論文集、pp. 1325-1330, 2006.
［１１］D. G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110, 2004.
【００７３】
［具体例］
実施の形態
図１２は実施の形態にかかる情報検索装置１００の全体構成を模式的に示した図である。情報検索装置１００は、パターン画像取得部１０、画像変換部１２、テキスト画像取得部２６、パラメータ取得部１８、パターン生成部２０、および検索部２８を含む。画像変換部１２はさらに、特徴量計算部１４と擬似コード列生成部１６とを含む。
【００７４】
パターン画像取得部１０は、図示しないユーザインタフェースを介してユーザから検索により見つけ出したいパターン画像を取得する。以後、検索により見つけ出したい情報を「パターン」という。また、画像データとしてのパターンを「パターン画像」という。特徴量計算部１４は、パターン画像取得部１０からパターン画像を受け取り、パターン画像を実ベクトルである特徴量に変換する。これは前提技術[５．２]および前提技術[５．３]に記載のアルゴリズムに基づく。パラメータ取得部１８は、図示しないユーザインタフェースを介してユーザからパラメータを取得する。このパラメータは、前提技術［２．２］に記載したｋおよびＬである。
【００７５】
擬似コード列生成部１６は、特徴量計算部１４からパターンの実ベクトルを、パラメータ取得部１８からパラメータをそれぞれ受け取り、パターンの擬似コード列を生成する。ここで「擬似コード」とは、一文字のパターン画像の特徴量である実ベクトルから前提技術[２．２]の定義４の記載に基づいて生成されるＬ個の数字の組である。また「擬似コード列」とは、文字列のパターン画像それぞれについて擬似コードを生成して並べたものであり、文字列を構成する文字の数と同数の擬似コードを構成要素に持つデータである。
【００７６】
テキスト画像取得部２６は、図示しないユーザインタフェースを介してユーザからパターンの検索の対象となるテキスト画像を取得する。以後、パターンの検索対象となる情報を「テキスト」という。また、画像データとしてのテキストを「テキスト画像」という。特徴量計算部１４はテキスト画像取得部２６からテキスト画像を受け取り、パターン画像の場合と同様に前提技術[５．２]および前提技術[５．３]に記載のアルゴリズムに基づいて、テキスト画像を実ベクトルである特徴量に変換する。擬似コード列生成部１６は、特徴量計算部１４からテキストの実ベクトルを、パラメータ取得部１８からパラメータをそれぞれ受け取り、テキストの擬似コード列を生成する。
【００７７】
パターン生成部２０はさらに、スキップ関数生成部２２とパターン格納部２４とを含む。スキップ関数生成部２２は、擬似コード列生成部１６から擬似コード列を受け取ってスキップ関数を生成する。スキップ関数は前提技術［４］に記載のアルゴリズムに基づいて生成される。パターン格納部２４は、擬似コード列生成部１６が生成したパターンの擬似コードとスキップ関数生成部２２が生成したスキップ関数とを格納する。
【００７８】
検索部２８はさらに、テキスト格納部３０と比較部３２とを含む。テキスト格納部３０は、擬似コード列生成部１６が生成したテキストの擬似コード列を格納する。比較部３２は、テキスト格納部３０からテキストの擬似コード列を、パターン格納部２４からパターンの擬似コード列とスキップ関数とを取得し、テキストに含まれるパターンを検索し、結果を図示しないモニタ等の出力装置に出力する。
【００７９】
ここで比較部は、前提技術［３］および［４］に記載のアルゴリズムに基づいて、テキストに含まれるパターンを検索する。すなわち、テキストの擬似コード列の先頭から最後尾に向かってパターンの擬似コード列を順に重ね合わせ、パターンの擬似コードとテキストの擬似コードとをパターンの最後尾から先頭に向かって順番に比較する。比較の途中で不一致が見つかった場合には、テキストに重ね合わせるパターンの開始位置を所定量だけずらしつつ検索する。ここで所定量とは、不一致が見つかったときのテキストの擬似コードであって、パターンの擬似コード列の最後尾に対応する擬似コードに基づいて定まる量であり、具体的には前提技術［４］に記載のｓｋｉｐ関数により定まる。スキップ関数生成部２２が生成するスキップ関数とは、前提技術［４］に記載のｓｋｉｐ関数である。
【００８０】
情報検索装置１００の構成は、ハードウェア的には、任意のプロセッサ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００８１】
図１３は実施の形態にかかる情報検索装置１００の処理の流れを説明するフローチャートである。本フローチャートにおける処理は、例えばユーザが情報検索装置１００を起動したときに開始する。
【００８２】
パターン画像取得部１０はパターンである文字列の画像を取得する（Ｓ１０）。特徴量計算部１４は前提技術［５．３］の記載に基づいてパターン画像を実ベクトルに変換し、擬似コード列生成部１６は特徴量計算部１４が出力した実ベクトルとパラメータ取得部１８から取得したパラメータとに基づいてパターンの擬似コード列を生成する（Ｓ１２）。スキップ関数生成部２２は前提技術［４］の記載にしたがって擬似コード列生成部１６が生成したパターンの擬似コード列に基づいてスキップ関数を生成する（Ｓ１４）。パターン格納部２４は擬似コード列生成部１６が生成したパターンの擬似コード列とスキップ関数生成部２２が生成したスキップ関数とを格納する（Ｓ１６）。
【００８３】
テキスト画像取得部２６はテキストである文字列の画像を取得する（Ｓ１８）。特徴量計算部１４はテキスト画像を実ベクトルに変換し、擬似コード列生成部１６は特徴量計算部１４が出力した実ベクトルとパラメータ取得部１８から取得したパラメータとに基づいてテキストの擬似コード列を生成する（Ｓ２０）。テキスト格納部３０は擬似コード列生成部１６が生成したテキストの擬似コード列を格納する（Ｓ２２）。比較部３２はテキスト格納部３０からテキストの擬似コード列を、パターン格納部２４からパターンの擬似コード列とスキップ関数とを取得し、テキストに含まれるパターンを検索する（Ｓ２４）。比較部３２がパターンの検索を終了すると、本フローチャートにおける処理は終了する。
【００８４】
図１４は、テキストに含まれるパターンを検索する処理の流れを説明するフローチャートであり、図１３において比較部３２が行うステップＳ２４を詳細に説明するものである。本フローチャートにおける処理は、比較部３２がテキスト格納部３０からテキストの擬似コード列を、パターン格納部２４からパターンの擬似コード列とスキップ関数とを取得したときに開始する。
【００８５】
比較部３２は図示しない内部メモリにテキストの長さＴｌｅｎを設定する（Ｓ２６）。テキストの長さとは、テキストの擬似コード列を構成する擬似コードの数である。続いて、パターンの長さＰｌｅｎを設定する（Ｓ２８）。第１のループ変数ｉを１に初期化する（Ｓ３０）。第１のループ変数ｉは、テキストの擬似コード列の先頭から最後尾に向かってパターンの擬似コード列を順に重ね合わせるために用いられる変数である。
【００８６】
第１のループ変数ｉがＴｌｅｎ−Ｐｌｅｎ＋１以下である場合には（Ｓ３２Ｙ）、テキストＴ中の長さＰｌｅｎの部分文字列Ｔ［ｉ：ｉ＋Ｐｌｅｎ−１］をＴｅｘｔ［ｘ］として取り出す（Ｓ３４）。ここで部分文字列Ｔは、前提技術［３］に記載のものである。また、Ｔｅｘｔ［ｘ］＝Ｔ［ｉ：ｉ＋Ｐｌｅｎ−１］としたとき、Ｔｅｘｔ（ｊ）は部分文字列Ｔのｊ番目の擬似コードを表すものとする。さらに、Ｐ（ｘ）をパターンのｘ番目の擬似コードを表すものとする。
【００８７】
第２のループ変数ｊをＰｌｅｎで初期化する（Ｓ３６）。第２のループ変数ｊは、パターンと部分文字列Ｔとをパターの最後尾Ｐ（Ｐｌｅｎ）から先頭Ｐ（１）に向かって順番に比較するために用いられる変数である。Ｔｅｘｔ（ｊ）とＰ（ｊ）とが一致する場合には（Ｓ３８Ｙ）、ループ変数ｊをｊ−１で更新する（Ｓ４０）。これにより、パターンと部分文字列Ｔとはパターンの最後尾から先頭に向かって順番に比較される。ここで、Ｔｅｘｔ（ｊ）とＰ（ｊ）とが一致する場合とは、Ｔｅｘｔ（ｊ）とＰ（ｊ）とが前提技術［２］の定義２に記載の二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たす場合のことをいう。
【００８８】
ｊが０より大きい場合には（Ｓ４２Ｙ）、パターンと部分文字列Ｔとの比較が終了していないので、ステップＳ３８に戻って比較を継続する。ｊが０以下の場合には（Ｓ４２Ｎ）、パターンと部分文字列Ｔとが一致したことになるため、ｉを一致したものとして記録する（Ｓ４４）。その後スキップ関数を用いて第１のループ変数ｉを更新することにより部分文字列Ｔの開始点をずらす（Ｓ４６）。また、ｊが０より大きい間にＴｅｘｔ（ｊ）とＰ（ｊ）とが一致しないときは（Ｓ３８Ｎ）、パターンと部分文字列Ｔとが一致しないことになるため、スキップ関数を用いて第１のループ変数ｉを更新することにより部分文字列Ｔの開始点をずらす（Ｓ４６）。第１のループ変数ｉを更新した結果、ｉがＴｌｅｎ−Ｐｌｅｎ＋１よりも大きくなった場合には（Ｓ３２Ｎ）、テキストから部分文字列Ｔを取り出せないため、本フローチャートにおける処理を終了する。
【００８９】
以上のように、ＢＭ法における文字列の代わりに擬似コード列を採用し、あるふたつの擬似コードが前提技術［２］の定義２に記載の二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たす場合にそれらの擬似コードが一致するものとして、ＢＭ法を擬似コード列の比較に拡張したものがＥｘｔｅｎｄｅｄ ＢＭ法である。
【００９０】
以上の構成による動作は以下のとおりである。ユーザは、検索したいパターンの画像と、パターンの検索対象となる文字列の画像を用意する。これらの画像を実施の形態にかかる情報検索装置１００に入力すると、情報検索装置１００は図１３の手続を経てテキスト画像の中からパターン画像と一致する画像を出力する。
【００９１】
以上説明したように実施の形態によれば、文字列データではなく、文字列の画像データを対象として、高速な文字列検索を実行することができる。これにより、例えば古い時代の新聞画像のように、情報が文字列データではなくマイクロフィルム等の画像データとして保存されている場合でも、高速な文字列検索が可能となる。
【００９２】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００９３】
上記実施の形態では、擬似コード列生成部１６が擬似コード列に変換する実ベクトルは文字列画像から生成される場合につて説明したが、文字列画像から生成される場合に限られず、例えば音声データなど、任意の実ベクトルを入力とすることができる。
【００９４】
上記実施の形態では、検索の度にパターン画像を取得してパターンの擬似コード列およびスキップ関数を生成する場合について説明したが、パターン格納部２４に既に格納されているパターンの擬似コード列およびスキップ関数が流用できる場合には、パターン格納部２４から読み出してもよい。パターンの擬似コード列およびスキップ関数の生成を省略できるので計算コストの点で有利である。
【符号の説明】
【００９５】
１０ パターン画像取得部、 １２ 画像変換部、 １４ 特徴量計算部、 １６ 擬似コード列生成部、 １８ パラメータ取得部、 ２０ パターン生成部、 ２２ スキップ関数生成部、 ２４ パターン格納部、 ２６ テキスト画像取得部、 ２８ 検索部、 ３０ テキスト格納部、 ３２ 比較部、 １００ 情報検索装置。
【技術分野】
【０００１】
この発明は情報検索装置および情報検索方法に関する。
【背景技術】
【０００２】
近年、ネットワーク上には大規模な情報が蓄積されており、その量は増加の一途をたどるばかりである。それに伴い、こうした情報の中から利用者が必要とする情報を効率よく取り出すための情報検索技術はますますその重要さを増している。テキストストリングに対する全文検索技術は、非常に高速なアルゴリズムとしてよく知られているＢｏｙｅｒ−Ｍｏｏｒｅ法［１］をはじめとして多くの研究が行われている（非特許文献参照）。
【先行技術文献】
【特許文献】
【０００３】
【非特許文献１】D. Gusfield, "Algorithms on Strings, Trees, and Sequence: Computer Science and Computational Biology," Cambridge University Press, 1997.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、Ｂｏｙｅｒ−Ｍｏｏｒｅ法はテキストストリングに対する全文検索技術であるため、一般の時系列データ、ベクトルデータに対しては適用することができない。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、様々な時系列データに対して類似検索をすることができる情報検索装置を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は情報検索装置に関する。この装置は、複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する擬似コード列生成部と、前記擬似コード列をパターンとして、擬似コード列であるテキストの先頭から順に前記パターンの構成要素の数と同数のテキストを部分テキストとしつつ、当該部分テキストと前記パターンとの比較を前記パターンの最後尾の擬似コードから先頭の擬似コードに向かって順に行う比較部と、比較途中で結果が不一致となった場合に、現在の部分テキストの先頭となっているテキストの位置から次の部分テキストの先頭となるテキストの位置までずらす量を、前記部分テキストの最後尾の擬似コードを入力として出力する関数をスキップ関数として生成するスキップ関数生成部とを含む。前記スキップ関数生成部は、擬似コードとして取り得る値すべてについて当該擬似コードが前記パターンの擬似コード列に含まれるか否かを特定し、含まれる場合には前記パターンの擬似コード列との位置関係から前記ずらす量を計算し、含まれない場合には前記パターンの擬似コード列の長さを前記ずらす量としてスキップ関数を生成する。前記比較部は、前記スキップ関数に基づいて現在の部分テキストの先頭から次の部分テキストの先頭までのずらす量を決定する。
【０００７】
本発明のさらに別の態様は情報検索方法に関する。この方法は、複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成するステップと、前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索するステップとをプロセッサに実行させる。
【０００８】
本発明のさらに別の態様は、情報を検索するためのプログラムに関する。このプログラムは、複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する機能と、前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索する機能とをコンピュータに実現させる。
【０００９】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１０】
本発明によれば、様々な時系列データに対して類似検索をすることができる情報検索装置を提供することができる。
【図面の簡単な説明】
【００１１】
【図１】ＬＳＰＣの例を示す図である。
【図２】２つのベクトル間の距離と二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされる確率との関係を示す図である。
【図３】ＢＭ法によるマッチングのプロセスを例示した図である。
【図４】図３の例におけるｓｋｉｐ関数である。
【図５】ＬＳＰＣにおけるｓｋｉｐ関数の一例を示す図である。
【図６】ＬＳＰＣにおけるｓｋｉｐ関数の別の一例を示す図である。
【図７】新聞画像の一部を例示した図である。
【図８】新聞画像から切出された文字を例示した図である。
【図９】検索対象とした文字列の画像を例示した図である。
【図１０】Ｒｅｃａｌｌ優先の設定の場合の実験結果を示す図である。
【図１１】Ｐｒｅｃｉｓｉｏｎ優先の設定の場合の実験結果を示す図である。
【図１２】実施の形態にかかる情報検索装置の全体構成を模式的に示した図である。
【図１３】実施の形態にかかる情報検索装置の処理の流れを説明するフローチャートである。
【図１４】テキストに含まれるパターンを検索する処理の流れを説明するフローチャートである。
【発明を実施するための形態】
【００１２】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１３】
［前提技術］
［１］ はじめに
本発明の実施の形態は、テキストストリングからキーワードを検索するアルゴリズムであるＢｏｙｅｒ−Ｍｏｏｒｅ法［１］（以下、「ＢＭ法」という。）の検索対象を、一般の実ベクトル系列に拡張したものである。実施の形態の基礎技術は、実ベクトルを擬似コード表現に変換し、その擬似コードの二項関係に基づいて探索ができるように、ＢＭ法を拡張したことである。
【００１４】
ネットワーク上には大規模な情報が蓄積されており、その量は増加の一途をたどるばかりである。それに伴い、こうした情報の中から利用者が必要とする情報を効率よく取り出すための情報検索技術はますますその重要さを増している。テキストストリングに対する全文検索技術はそのうちの最も基本的なものであると言え、古くから多くの研究が行われている。中でも、ＢＭ法は非常に高速なアルゴリズムとしてよく知られている。文字列照合に基づくアルゴリズムであるＢＭ法は、キーワードの末尾から照合を行うことで、テキストストリングのうちのいくつかの文字については１回もアクセスすることなく、すなわち、サブリニア時間で検索を行うことができる。
【００１５】
実施の形態は、このＢＭ法を拡張し、検索対象をテキストストリングから一般の実ベクトル系列に拡張する。これは、さまざまな時系列データ、あるいは擬似的に時系列と見なせるデータに対して高速な類似検索を提供するための基盤となりうる技術である。
【００１６】
この拡張における主な要素技術は次の２点である。１つは実ベクトルを擬似コードとして離散化表現する技術であるＬＳＰＣ［２］（後述する）である。この擬似コードＬＳＰＣは、通常のベクトル量子化に比べて、もとの実ベクトルの記述力を極力損なわないままベクトルを離散化することができる。ただしこの擬似コードにおいて中心的な役割を果たす二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔ（後述する）は同値関係ではなく、推移律を満たさないものであるため、既存の文字検索アルゴリズムがそのまま適用できるわけではない。そこで第２の要素技術として、実施の形態では、既存の文字列検索アルゴリズムのうち最も有力なものの１つであるＢＭ法について、これをＬＳＰＣに適用可能なようにアレンジする。これがＥｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法である。
【００１７】
アルゴリズムの詳述に先立ちあらかじめ本手法の限界点を述べると、ＬＳＰＣによる疑似コードの変換は確率的アルゴリズムであるため、それに基づく検索アルゴリズムでは結果が確実に正確であることは保証されない。試行回数やその他のパラメタの設定によって正確な出力が得られる確率を高めることはできるものの、それは計算量とトレードオフである。この点は他の確率的アルゴリズムと同様である。
【００１８】
［２］ 擬似コードＬＳＰＣ
［２．１］ ＬＳＰＣの概要
ＬＳＰＣ（Ｌｏｃａｌｉｔｙ−Ｓｅｎｓｉｔｉｖｅ Ｐｓｅｕｄｅ−Ｃｏｄｅ）は、Ｔｅｒａｓａｗａ ａｎｄ Ｔａｎａｋａ［２］により提唱された、実ベクトルを擬似コード表現に変換する技術である。通常のベクトル量子化とは異なり、１つのベクトルに対して複数の整数を割り当てることで、通常のベクトル量子化よりも豊かな記述力を残したままベクトルを離散化する。
【００１９】
図１はＬＳＰＣの例を図示したものである。図１中、黒丸がｄ次元の実空間（Ｒｄ空間）に分布しているベクトルを表し、黒丸に付けられた（８，１，４）などの数字の３つ組がそのベクトルを離散化した結果の擬似コードを表している。このように、１つのベクトルに複数の整数を割り当てることが擬似コードＬＳＰＣの特徴である。そして、ＬＳＰＣのもう１つの特徴が、そこに導入される二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔである。２つの擬似コードに割り当てられた複数の整数のうち、１つでも一致していればそれらのコード間で二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされると定義する。
【００２０】
以上をまとめると以下のようになる。
定義１（疑似コードＬＳＰＣの定義）：ｄ次元実ベクトルｐに対し、擬似コードＣ（ｐ）は、ｄ’個の整数の組として与えられる。すなわち、
ｐ∈Ｒｄ→Ｃ（ｐ）＝（ｃ１（ｐ） ｃ２（ｐ）・・・ｃｄ’（ｐ））Ｔ∈Ｎｄ。
定義２（二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔの定義）：擬似コードＬＳＰＣにおいてＣ（ｐ）＝｛ｃｉ（ｐ）｝とＣ（ｑ）＝｛ｃｉ（ｑ）｝とが二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たすとは、ｃｉ（ｐ）＝ｃｉ（ｑ）を満たすようなｉ∈｛１，・・・，ｄ’｝が存在することである。
【００２１】
ＬＳＰＣでは、通常のベクトル量子化よりも多様な表現が可能である。例えば、通常のベクトル量子化においては、境界面付近では似たベクトルに別な符号が割り当てられてしまうケースがどうしても発生する。一方ＬＳＰＣでは、図１に示すように、ある擬似コードとｓｅｍｉｅｑｕｉｖａｌｅｎｔな範囲と、別のあるコードとｓｅｍｉｅｑｕｉｖａｌｅｎｔな範囲とがオーバーラップすることが許されている。これにより、近いベクトル同士に割り当てられた擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔになる確率を極めて高くなるように擬似コードを割り振ることが可能となる。
【００２２】
二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされるか否かは、２つのベクトルの間の距離に依存している。図２は、２つのベクトル間の距離と二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔが満たされる確率との関係を図示したものである。この性質を用いて、２つのベクトル間の距離が一定の閾値以上であるか否かを、擬似コードの二項関係だけから推定することができる。例えば図２における実線が表す曲線の例であれば、２つのベクトル間の距離が０．９以上であればそれらのベクトルに対応する擬似コード同士がｓｅｍｉｅｑｕｉｖａｌｅｎｔである確率は極めて小さく、一方で２つのベクトル間の距離が０．４以下であればそれらのベクトルに対応する擬似コード同士がｓｅｍｉｅｑｕｉｖａｌｅｎｔである確率は極めて大きい。この性質を用いることで、２つの擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔであるかどうかを調べるだけで、元々のベクトル間の距離が大きいのか小さいのかをおおよそ推測することができる。
【００２３】
ここで重要な点は、擬似コードＣ（ｐ）、Ｃ（ｑ）が二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たすかどうかを照合するためのコストは、２つのベクトルｐ、ｑ間の距離を計算するコストよりも小さいということである。この差は特にもとのベクトル空間が高次元である場合に顕著である。パターン認識で用いられる特徴ベクトルの空間は非常に高い次元数を持つ場合がしばしばあるので、ＬＳＰＣを使用することによる計算コスト削減が大きな効果を持つことが期待できる。
【００２４】
［２．２］ ＬＳＰＣの構成法
前節では、擬似コードＬＳＰＣの持っている性質について述べた。この節では、そのような性質を持つ擬似コードをいかにして構成することができるかについて述べる。
【００２５】
擬似コードＬＳＰＣの各要素には、Ｌｏｃａｌｉｔｙ Ｓｅｎｓｉｔｉｖｅ Ｈａｓｈｉｎｇ（ＬＳＨ）［３］〜［５］のハッシュ関数のハッシュ値を利用する。ＬＳＨは、近似的最近傍探索問題の解法として非常に有力なものとして近年注目されているアルゴリズムである。以下、まずＬＳＨの概略を述べる。
【００２６】
ＬＳＨアルゴリズムにおいて中心的な役割を果たすのは、以下で定義されるＬＳＨ ｆａｍｉｌｙと呼ばれる関数族である。
定義３（ＬＳＨ ｆａｍｉｌｙ）：ベクトル空間Ｓから適当な離散空間Ｕへの関数族Ｈ＝｛ｈ：Ｓ→Ｕ｝は、以下を満たすとき（ｒ１，ｒ２，ｐ１，ｐ２）−ｓｅｎｓｉｔｉｖｅであると呼ばれる。
任意のｖ、ｑ∈Ｓについて、
ｄ（ｖ，ｑ）≦ｒ１のときＰｒＨ［ｈ（ｑ）＝ｈ（ｖ）］≧ｐ１。
ｄ（ｖ，ｑ）≧ｒ２のときＰｒＨ［ｈ（ｑ）＝ｈ（ｖ）］≦ｐ２。
ここでｄ（ｖ，ｑ）はベクトルｖ、ｑ間の距離を表し、ｐ１＞ｐ２、ｒ１＜ｒ２とする。
【００２７】
なお、このような関数族の存在はＬ１空間において［３］、ｓ∈（０，２］の任意のＬｓ空間において［４］、任意の次元の単位球上において［６］、それぞれ保証されている。
【００２８】
関数族Ｈに属する関数は、ベクトルｖ∈Ｒｄを整数ｈ（ｖ）∈Ｎに写像するという意味で、ハッシュ関数であると言える。近傍探索問題の解法としてのＬＳＨは、データ集合内の全ての点についてあらかじめハッシュ値を計算してハッシュ表を作成しておいて、クエリ点と同じハッシュ値を持つ点だけをハッシュ表から探し出して探索の対象にする。こうすることによって、クエリ点との距離を計算されるべき点の数を大きく削減する、というのがＬＳＨの基本アイデアである。
【００２９】
ＬＳＨにおける優れた工夫の一つは、ハッシュ関数を複数使うことによって、Ｆａｌｓｅ ｐｏｓｉｔｉｖｅを減らしつつ、Ｆａｌｓｅ ｎｅｇａｔｉｖｅを減らすようにできることである。例えば、あるＬＳＨ ｆａｍｉｌｙがあって、その中の関数は図２の点線で示されるような衝突確率を持っていたとする。ＬＳＨは、この関数ｋ個を組み合わせた関数をＬ個作ることで、その確率の差を増幅する。つまり、ｈｉｊをＬＳＨ ｆａｍｉｌｙ Ｈからランダムに選ばれたハッシュ関数として、
ｇｉ（ｐ）＝｛ｈｉ１（ｐ），ｈｉ２（ｐ），・・・ｈｉｋ（ｐ）｝ （１）
をｇ１（ｐ）からｇＬ（ｐ）までＬ個作成することによって、実効的な衝突確率を図２の実線のように変換するのである。
【００３０】
ＬＳＨの近傍探索問題の解き方は次のとおりである。まず、すべての点ｐに対するｇ１（ｐ），ｇ２（ｐ），・・・ｇＬ（ｐ）をあらかじめ計算し、ハッシュ表に格納しておく。クエリ点ｑが入力されたら、ｇ１（ｑ），ｇ２（ｑ），・・・ｇＬ（ｑ）を計算し、∃ｉ、ｇｉ（ｐ）＝ｇｉ（ｑ）となるような点ｐだけをハッシュ表から見つけてきて、探索の対象とする。これにより、クエリ点から遠い点との距離計算を減らしつつ、クエリ点に近い点の取りこぼしを減らすということを実現している。
【００３１】
擬似コードＬＳＰＣの基本アイデアは、このＬＳＨのハッシュ値は擬似コードとして使えるのではないかという着想である。ＬＳＨは近傍探索問題を解くためのハッシュ表を作成するための手段としてハッシュ関数を使っていたが、ＬＳＰＣではベクトル系列のマッチングのための擬似コード表現として同じハッシュ関数を用いるのである。すなわち、
定義４（疑似コードＬＳＰＣの構成法）：ｐ∈Ｒｄに対し、擬似コードＬＳＰＣ Ｃ（ｐ）を以下のように定義する。
Ｃ（ｐ）＝｛ｇ１（ｐ），ｇ２（ｐ），・・・ｇＬ（ｐ）｝ （２）
ｇｉ（ｐ）＝｛ｈｉ１（ｐ），ｈｉ２（ｐ），・・・ｈｉｋ（ｐ）｝ （３）
ここでｈｉｊはＬＳＨ ｆａｍｉｌｙ Ｈからランダムに選ばれた関数である。
【００３２】
上記の定義ではＣ（ｐ）はｋＬ個の整数から構成されるが、実用上これを次の方法でＬ個の整数として表すことにする。すなわち、ｈｉｊの値域は有限の整数であるので、この上限をＭとおく。このとき、ｇｉ（ｐ）＝ｈｉ１（ｐ）Ｍｋ−１＋ｈｉ２（ｐ）Ｍｋ−２＋・・・ｈｉｋ（ｐ）とすることで、ｇｉ（ｐ）は１つの整数で表すことができる。従って、Ｃ（ｐ）はＬ個の整数として表せる。
【００３３】
ＬＳＨにおける近傍探索は、クエリｑに対して、ハッシュ表から∃ｉ、ｇｉ（ｐ）＝ｇｉ（ｑ）となるような点ｐをすべて拾ってくるのであった。それに対応する、擬似コードＬＳＰＣにおける二項関係が次に述べるｓｅｍｉｅｑｕｉｖａｌｅｎｔである。
定義５（二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔの定義）：ＬＳＰＣ Ｃ（ｐ）＝｛ｇｉ（ｐ）｝とＣ（ｑ）＝｛ｇｉ（ｑ）｝とがｓｅｍｉｅｑｕｉｖａｌｅｎｔであるとは、ｇｉ（ｐ）＝ｇｉ（ｑ）となるようなｉが存在することである。
【００３４】
この二項関係が満たされているか否かは、前述の図２の実線に示すとおり、もとのベクトルｐ、ｑの間の距離に依存している。
【００３５】
ここで改めてパラメータｋとＬの意味を考えてみる。ｐ（ｃ）が単一のハッシュ関数で、間の距離がｃである２つの点が衝突する（同じハッシュ値を持つ）確率Ｐｓｅｍｉｅｑがそれらの点に対応する擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔである確率を表すとする。ＬＳＰＣでは、単一のハッシュ関数をｋ個組み合わせた物をＬ個作る、という操作で、Ｐｓｅｍｉｅｑを
Ｐｓｅｍｉｅｑ＝１−（１−ｐ（ｃ）ｋ）Ｌ （４）
のように増幅している。ｋとＬの値を設定することにより、図２における曲線の位置を変えることができる。ｋを増やせば曲線は左に移動し、Ｌを増やせば曲線は右に移動する。ｋとＬをともに増やせば、およその位置を変えずに曲線の勾配を増すことができる。
【００３６】
［３］ Ｂｏｙｅｒ−Ｍｏｏｒｅ法
この章では、Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法の前提となる、ＢＭ法について述べる。ＢＭ法は文字列検索アルゴリズムとしては古典的でかつきわめて有力な方法であり、多くの解説書が出版されている。以下の説明では、Ｂａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅの名は文献［７］に、ｓｋｉｐ関数の名は文献［８］によった。
【００３７】
なお、文献［７］で説明されているＢｏｙｅｒ−Ｍｏｏｒｅアルゴリズムは、Ｇｏｏｄ Ｓｕｆｆｉｘ ＲｕｌｅとＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅの２つの柱から構成されているが、このうちＬＳＰＣのような推移律を満たさないコードに適用可能なものは後者のみである。今日ＢＭ法と呼ばれるものには微妙なバリエーションがあるが、ちょうど文献［８］のＢＭ法の説明がＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅのみに焦点が置かれたものとなっており、Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法の前提とするのに都合がよいので、ここでは文献［８］に従い、Ｂｏｙｅｒ−ＭｏｏｒｅアルゴリズムのＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅについて、その概要を述べる。
【００３８】
まず、問題を正確に定式化する。Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題とは、次のような問題である。
定義６（Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題）：長さｎの文字列Ｐ（パターンあるいはキーワードと呼ぶ）と、長さｍ（≧ｎ）の文字列Ｔ（テキストと呼ぶ）とが与えられたとき、テキスト中のキーワードの出現開始位置、すなわちＰ（ξ）＝Ｔ（ｉ＋ξ−１）ｆｏｒ ａｌｌ ξ＝１，２，・・・，ｎとなるようなｉをすべて見つけること。
【００３９】
なお、文字列Ｐに対し、Ｐ（ξ）はＰのξ番目の文字を表す。たとえば、Ｔ＝ａｂｘａｂａｂａｂｘａｂａｂｘ、Ｐ＝ａｂａｂの時、Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題の解は｛４，６，１１｝である。また、以下では文字列Ｓのｉ番目からｊ番目の文字（ｊ≧ｉ）までで構成される部分文字列をＳ［ｉ：ｊ］と書くことにする。
【００４０】
Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題の素朴な解法（ｎａｉｖｅ ｍｅｔｈｏｄ）は、パターンＰに対し、まずＴの部分文字列Ｔ［１：ｎ］と照合を行い、次にＴ［２：ｎ＋１］、その次にＴ［３：ｎ＋２］・・・という具合に、Ｔの部分文字列の始点を１つずつずらしながらすべての部分文字列と照合を行う方法である。この方法の計算コスト（文字列照合回数）最小でｍであり、最大でＯ（ｍｎ）である。
【００４１】
ここからＢＭ法について述べる。素朴な解法がＴの部分文字列の始点を１つずつずらしながら文字列の照合を行っていくのに対し、ＢＭ法は始点を１つよりも大きくずらすことによって計算量を縮減する。
【００４２】
なお、文献［７］によればＢＭ法はＢａｄ Ｃｈａｒａｃｔｅｒ ＲｕｌｅとＧｏｏｄ Ｓｕｆｆｉｘ Ｒｕｌｅからなっており、この両方を用いることで計算量がＯ（ｍ）で抑えられることが保証される。一方で文献［８］では、上記２つのルールのうちＢａｄ Ｃｈａｒａｃｔｅｒ Ｒｕｌｅのみを使ったものをＢＭ法と呼んでおり、この場合はＯ（ｍ）の計算量が保証されない（最悪の場合Ｏ（ｍｎ）になってしまう）。しかし、極端な場合の入力（例えばＴ＝ａａａａａａａ、Ｐ＝ａａａ）を考えなければ、通常の場合はこれだけでも十分に高速である。
【００４３】
図３はＢＭ法によるマッチングのプロセスを例示したものである。ここでは、例としてＴ＝ａｂｃｂａｘａｂａｃａｂｂｃ、Ｐ＝ａｂａｃという場合を考える。ＢＭ法も素朴な解法と同様に、まずＰとＴ［１：４］とを照合する。ただしこの照合にあたって、ＢＭ法は文字の照合をＰとＴ［１：４］の末尾（すなわちこの場合は４文字目）から順に開始するというところに特徴がある。今の例の場合、Ｔ［１：４］の４文字目はｂ、Ｐの４文字目はｃであるから照合結果は「不一致」であり、Ｔの部分文字列の始点をずらして次の照合へ進む。
【００４４】
さてここでポイントは、Ｔの部分文字列の始点を何文字ずらすかである。いま、Ｔ［１：４］の４文字目はｂであることはすでに調べた。ということは、仮に１文字ずらした場合、次はＴ［２：５］の３文字目がｂであることはわかっているので、これがＰと一致しないことは調べるまでもなく明らかである。仮に２文字ずらすとすると、Ｔ［３：６］の２文字目であるｂは、Ｐの２文字目と一致する。よってこれは調べる価値がある。従ってＴ［１：４］を不一致と判断した次に調べるべきＴの文字列はＴ［３：６］であることがわかる。
【００４５】
では次に、Ｔ［３：６］とＰの照合を行う。Ｔ［３：６］の４文字目はｘ、Ｐの４文字目はｃであるから照合結果は不一致であり、Ｔの部分文字列の始点をずらして次の照合へ進む。さて今の場合、Ｔ［３：６］の４文字目であるｘはＰの中に一度も出てこない。ということは、Ｔ（６）＝ｘを含むようなＴの部分文字列とＰとは決して一致しないことはこの時点で明らかである。よって次に照合すべきＴの部分文字列は、一気に４つ飛んでＴ［７：１０］であるということになる。
【００４６】
続いて、ＰとＴ［７：１０］との照合を行う。ここも末尾から順に照合を行う。照合を４回行ったところで、ＰとＴ［７：１０］の全体が一致していることが判明するので、始点位置“７”が出力される。そして、末尾のｃに着目すると、Ｔ［７：１０］を１文字ずらした場合も２文字ずらした場合も３文字ずらした場合もＰとは一致しないことが明らかであるので、次に照合すべきＴの部分文字列は、４つ飛んでＴ［１１：１４］となる。最後にＴ［１１：１４］とＰの照合を行い、後ろから２番目の文字で不一致が判明して、アルゴリズムは終了する。図４は、図３の例におけるｓｋｉｐ関数である。
【００４７】
上記のＢＭ法のアルゴリズムでポイントとなるのは、Ｔ［ｉ：ｉ＋３］の４文字目が何であった場合に、次に照合するＴの始点を何文字ずらせばよいか、ということである。ここではこの「何文字ずらせばよいか」の値を「ｓｋｉｐ関数」で表すことにする。すなわち、ｓｋｉｐ（ｘ）は、Ｔ［ｉ：ｉ＋３］の末尾の文字（４文字目）がｘであった場合に照合の始点をずらすべき数として定義され、最小は１であり、最大はＰの長さ（この場合は４）である。
【００４８】
ｓｋｉｐ関数は次のように構成される。ｓｋｉｐ関数は、定義域として想定しているすべての文字（アルファベットΣと呼ぶ）、値域として１以上ｎ以下の自然数を持つ関数である。まず、すべての文字ｘ∈Σについて、ｓｋｉｐ（ｘ）をｎに初期化する。次に、Ｐの（ｎ−ｉ）文字目がｘであったら、ｓｋｉｐ（ｘ）をｉに更新する。この手続をｉ＝ｎ−１，ｎ−２，・・・，１の順に繰り返せば、所望のｓｋｉｐ関数が得られる。
【００４９】
ＢＭ法の特徴は、パターン文字列Ｐが長ければ長いほど、また、文字列中から適当に２つ選んだ文字が適合する確率が低いほど（すなわち文字種が多いほど）、効率が良くなるということである。
【００５０】
［４］ Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法
定義６で述べた問題をＬＳＰＣに拡張した問題を次のように定義する。
定義７（ＬＳＰＣに拡張されたＳｔｒｉｎｇ Ｍａｔｃｈｉｎｇ問題）：長さｎの擬似コード列Ｐと、長さｍ（≧ｎ）の擬似コード列Ｔとが与えられたとき、Ｐ（ξ）〜Ｔ（ｉ＋ξ−１）ｆｏｒ ａｌｌ ξ＝１，２，・・・，ｎとなるようなｉをすべて見つけること。
【００５１】
ここで、Ｓ（ｉ）〜Ｔ（ｊ）とは、Ｓ（ｉ）とＴ（ｊ）が二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たす関係にあることを意味する。
【００５２】
Ｅｘｔｅｎｄｅｄ ＢＭ法のアルゴリズムは、基本的にはＢＭ法と同じである。すなわち、
［Ｅｘｔｅｎｄｅｄ ＢＭ法のアルゴリズム］
まず、ｉ＝１として、ＰとＴ［ｉ：ｉ＋ｎ−１］が対応するか、すなわちＰ（ξ）〜Ｔ（ｉ＋ξ−１）ｆｏｒ ａｌｌ ξ＝１，２，・・・，ｎが成り立つかどうかを調べる。オリジナルのＢＭ法と同じく、この照合は右から左の順、すなわちξ＝ｎ，ｎ−１，ｎ−２，・・・の順に行う。照合が失敗したらそこで照合を打ち切り照合がξ＝１まで成功した場合は、キーワードを発見したとして出力する。次に、次のｉ位置に対して照合を行うため、ｉをｓｋｉｐ（Ｔ（ｉ＋ｎ−１））だけ動かす。ｉ＋ｎ−１＞ｍとなったら照合を終了する。
【００５３】
Ｅｘｔｅｎｄｅｄ ＢＭ法のＢＭ法との違いは、ｓｋｉｐ関数の構成法である。理論的には、ｓｋｉｐ関数は次の方法で構成される。すなわち、今回想定されるｓｋｉｐ関数の定義域は、擬似コードの取り得るあらゆる値（文字列の例にならい、アルファベットΣと呼ぶことにする）であり、値域として１以上ｎ以下の自然数を持つ関数である。まず、すべてのｘ∈Σにつて、ｓｋｉｐ（ｘ）をｎに初期化する。次に、擬似コードＰ（ｎ−ｉ）に対し、それとｓｅｍｉｅｑｕｉｖａｌｅｎｔになるようなすべての擬似コードｘ∈Σについて、ｓｋｉｐ（ｘ）をｉに更新する。この手続をｉ＝ｎ−１，ｎ−２，・・・，１の順に繰り返せば、所望のｓｋｉｐ関数が完成される。図５はＬＳＰＣにおけるｓｋｉｐ関数の一例を図示したものである。
【００５４】
理論上は上記で可能だが、現実的にはこのアルゴリズムは問題がある。この方法では、ｓｋｉｐ関数を格納するためにアルファベットΣのサイズに比例した配列サイズが必要だが、擬似コードＬＳＰＣはＬ個の整数を要素として持っている。各要素の値は１からＮまでであるとすると、この場合必要な配列のサイズはＮＬとなってしまい、実際にＬの値として２０程度から数百程度のものを用いようとすると、このサイズの配列を確保するのは現実的に不可能である。そこで次の定理が重要となる。
【００５５】
定理１：疑似コードＣ（ｐ）＝（ｃ１（ｐ） ｃ２（ｐ） ・・・ｃｄ’（ｐ））に対するｓｋｉｐ関数は、次の形で表現できる。
ｓｋｉｐ（Ｃ（ｐ））＝ｍｉｎ（ｓｋｉｐ１（ｃ１（ｐ）），ｓｋｉｐ２（ｃ２（ｐ）），・・・，ｓｋｉｐｄ’（ｃｄ’（ｐ）））
ここで、ｓｋｉｐｉ（ｃｉ（ｐ））は、通常のＢＭ法におけるのと同じ方法で構成されるｓｋｉｐ関数である。
【００５６】
（証明）ｓｋｉｐ（Ｃ（ｐ））とは、Ｐ（ｎ−ξ）とＣ（ｐ）がｓｅｍｉｅｑｕｉｖａｌｅｎｔになるような最小の整数ξ＞０である。λ＜ｍｉｎｉ＝１，・・・，ｄ’（ｓｋｉｐ１（ｃ１（ｐ）））のとき、Ｐ（ｎ−λ）とＣ（ｐ）はｓｅｍｉｅｑｕｉｖａｌｅｎｔにならない。なぜなら、Ｐ（ｎ−λ）〜Ｃ（ｐ）とすると、あるδ∈｛１，・・・，ｄ’｝についてＰ（ｎ−λ）の第δ要素Ｃ（ｐ）の第δ要素が一致するはずであるが、これはλ＜ｓｋｉｐδ（Ｃδ（ｐ））に反するからである。逆にλ＝ｍｉｎｉ＝１，・・・，ｄ’（ｓｋｉｐ１（ｃ１（ｐ）））のとき、あるδについてλ＝ｓｋｉｐδ（Ｃδ（ｐ））であり、これはＰ（ｎ−λ）の第δ要素とＣ（ｐ）の第δ要素が一致することに他ならないので、Ｐ（ｎ−λ）とＣ（ｐ）はｓｅｍｉｅｑｕｉｖａｌｅｎｔである。よって、ｓｋｉｐ（Ｃ（ｐ））＝ｍｉｎｉ＝１，・・・，ｄ’（ｓｋｉｐｉ（ｃｉ（ｐ）））である。（証明終）
【００５７】
この工夫により、記憶容量はＭＬからＭＬに削減され、実装が現実的に可能となる。図６はＬＳＰＣにおけるｓｋｉｐ関数の別の一例を図示したものである。
【００５８】
［５］ 新聞画像による実験
Ｅｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法の応用の一例として、ＯＣＲによるテキスト化が困難な古い新聞画像に対する全文探索実験を行い、従来法によるものと検索コストを比較する。
【００５９】
［５．１］ 実験の概要
明治期の「函館毎日新聞」を対象とする。新聞資料はマイクロフィルムによって保存されており、これをスキャナで取り込みデジタル化したデータを用いる。図７は、新聞画像の一部を例示したものである。解像度は１文字あたりおおむね７０×７０ピクセル程度である。
【００６０】
なお、このような古い新聞画像に対する全文探索というのは決して容易なタスクではない。ＯＣＲによるテキスト化ができれば話は簡単だが、ＯＣＲは言語や書体に依存した技術であるため、現在とはフォントも語法も異なる明治期の画像に対してＯＣＲをそのまま適用しても十分な精度は得られない。実際、新聞画像に対して、ＯＣＲによらず画像検索技術を用いて全文検索を行うための研究は他にも行われている［９］。
【００６１】
［５．２］ 文字切出し
文字切出しは、段落の縦方向射影ヒストグラムによる行切出しと、段落の横方向射影ヒストグラムによる文字切出しとを組み合わせるという方法で行った。図８は、新聞画像から切出された文字を例示したものである。このような方法が採用可能なのは、本実験では新聞画像を対象としたため、段落画像における文字の配置がほぼ格子状になっているためである。
【００６２】
ただし、単純な方法をそのまま適用しただけではさまざまな問題が発生する。１つは、段落の最後の行に２，３文字しかない場合に行切出しが失敗しやすいということと、もう１つは、振り仮名（ルビ）が漢字の右側に多く振られており、これは文字のマッチングには用いないため、除去する必要があるということである。
【００６３】
そこで、自己相関関数を用いて本文の幅と振り仮名の幅を特定できるような形で行幅を推定し、上記２点の問題に対処することとした。
【００６４】
［５．３］ 特徴量ベクトルおよび擬似コードの構成
特徴量は、勾配分布特徴量［１０］を用いた。文字切出しされた画像を４×４の小領域に分割し、あとはＳＩＦＴ［１１］と同じような方法で１２８次元の特徴量ベクトルを構成する。
【００６５】
次いで、この各特徴量ベクトルを擬似コードＬＳＰＣに変換する。使用する関数族（ＬＳＨ ｆａｍｉｌｙ）としては、今回使用する特徴量ベクトルはノルムが１に正規化されているものであるので、ＳＬＳＨ［６］のｏｒｔｈｏｐｌｅｘ法を用いた。今回使用する特徴量ベクトルはその要素がすべて非負であるという性質を持っているため、この場合１つのハッシュ関数の値域は１〜１２８となる。ＬＳＰＣ構成の際に設定するパラメタｋおよびＬ（前述の２．２節参照）については、Ｒｅｃａｌｌを優先する設置とＰｒｅｃｉｓｉｏｎを優先する設定ということで、（ｋ，Ｌ）＝（３，２６）と（ｋ，Ｌ）＝（３，２４）の２種類を試した。前者は特徴量ベクトルがやや離れていても擬似コードがｓｅｍｉｅｑｕｉｖａｌｅｎｔになりやすいかわりに拾い漏らしが少ない設定（すなわちＲｅｃａｌｌ優先の設定）であり、後者はその逆（すなわちＰｒｅｃｉｓｉｏｎ優先の設定）である。
【００６６】
以上のような方法で、文字切出しされた各文字画像が１２８次元ベクトルに変換され、次いで擬似コードに変換されることにより、新聞画像が擬似コードに変換されたこととなる。これに対してＥｘｔｅｎｄｅｄ Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することで、新聞画像に対する全文探索を行うことができる。
【００６７】
［５．４］ 実験
今回実験で用いた新聞画像は、全７５５文字からなる。これに対し、手作業でテキスト化したデータを作成した後にｎ−ｇｒａｍ解析にかけ、３回以上登場する文字列のうち最長の長さであった「のみならず」を実験対象に用いた。図９は検索対象とした文字列の画像を例示したものである。３箇所の「のみならず」に対し、それぞれをクリエとして残りの２つを探すという実験を行い、素朴な解法（ｎａｉｖｅ ｍｅｔｈｏｄ）と、Ｅｘｔｅｎｄｅｄ ＢＭ法の２つで、それぞれ文字照合回数を数え上げた。なおここでは比較を明確にするため、素朴な解法においても文字照合はパターンの末尾の文字から順に行った。
【００６８】
［５．５］ 実験結果
図１０は、Ｒｅｃａｌｌ優先の設定の場合の実験結果を示す図である。また、図１１はＰｒｅｃｉｓｉｏｎ優先の設定の場合の実験結果を示す図である。図１０および図１１中、Ｎａｉｖｅは素朴な解法、Ｅｘｔｅｎｄｅｄ ＢＭ法（実施の形態）を表し、（＃ｃｏｍｐ）は文字照合回数、（＃ｓｋｉｐ）はＥｘｔｅｎｄｅｄ ＢＭ法におけるｓｋｉｐ関数の評価回数を表している。また、Ｒｅｃａｌｌは再現率、Ｐｒｅｃｉｓｉｏｎは適合率であり、それぞれ以下の式で定義される。
【数１】
【００６９】
なお、図１０および図１１に掲げた素朴な解法よりもさらに素朴な方法として、文字列の照合中に不一致が見つかっても照合を打ち切らないアルゴリズムというものが考えられる。この場合の計算コスト（文字照合回数）は、いずれをクエリに用いた場合においても７５１×５＝３７５５である。
【００７０】
図１０および図１１からわかるとおり、すべてのクエリに対してＥｘｔｅｎｄｅｄ ＢＭ法の文字列照合回数は、素朴な解法のものを下回っている。中でも、図１０における１つめのデータと、図１１におけるすべてのデータにおいては、文字列照合回数が全文字数（７５５文字）を下回っており、サブリニア時間での検索を達成している。
【００７１】
ただし、Ｅｘｔｅｎｄｅｄ ＢＭ法においては、素朴な解法に対する追加コストとしてｓｋｉｐ関数の評価回数を考えなければならない。文字パターン照合はＬ個の自然数の一致／不一致を判定する処理であり、ｓｋｉｐ関数評価はＬ個の自然数の最小値を取る処理であるため、これらの計算コストを完全に同一視することはできないが、仮に同じだとすると、Ｅｘｔｅｎｄｅｄ ＢＭ法のコストは（＃ｃｏｍｐ）に（＃ｓｋｉｐ）を加えたものとして評価できる。この場合も、表のすべての場合においてＥｘｔｅｎｄｅｄ ＢＭ法の計算コストは素朴な解法よりも削減できていることになる。
【００７２】
［６］ 参考文献
［１］R. S. Boyer and J. S. Moore, "A fast string searching alogorithm," Communications of the ACM, vol. 20, pp. 762-772, Oct. 1977.
［２］K. Terasawa and Y. Tanaka, "Locality Sensitive Pseudo-Code for Document Images," Proc. 9th Int. Conf. on Document Analysis and Recognition, ICDAR2007, vol. 1, pp. 73-77, 2007.
［３］A. Gionis, P. Indyk, R. Motwani, "Similarity Search in High Dimensions via Hashing," Proc. 25th Int. Conf. on Very Large Data Base, VLDB1999, pp. 518-529, 1999.
［４］M. Datar, P. Indyk, N. Immorlica, V. Mirrokni, "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions," Proc. 20th ACM Symposium on Computational Geometry, SoCG2004, pp. 253-262, 2004.
［５］A. Andoni, P. Indyk, "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions," Proc. Symposium on Foundations of Computer Science, FOCS'06, pp. 459-468, 2006.
［６］K. Terasawa and Y. Tanaka, "Sperical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere," Proc. 10th Workshop on Algorithms and Data Structures, WADS2007, LNCS4619, pp. 27-38, 2007.
［７］D. Gusfield, "Algorithms on Strings, Trees, and Sequence: Computer Science and Computational Biology," Cambridge University Press, 1997.
［８］北研二、津田和彦、獅々堀正幹、“情報検索アルゴリズム、”共立出版株式会社、東京、２００２年１月。
［９］Yue Lu and Chew Lim Tan, "Word spotting in Chinese Document images without layout analysis," Proc. 16th Int. Conf. on Pattern Recognition, ICPR2002, vol.3, pp.57-60, 2002.
［１０］寺沢憲吾、長崎健、川嶋稔夫、“勾配分布特徴量による高精度手書き文字検索、”画像の認識・理解シンポジウム（ＭＩＲＵ）２００６講演論文集、pp. 1325-1330, 2006.
［１１］D. G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110, 2004.
【００７３】
［具体例］
実施の形態
図１２は実施の形態にかかる情報検索装置１００の全体構成を模式的に示した図である。情報検索装置１００は、パターン画像取得部１０、画像変換部１２、テキスト画像取得部２６、パラメータ取得部１８、パターン生成部２０、および検索部２８を含む。画像変換部１２はさらに、特徴量計算部１４と擬似コード列生成部１６とを含む。
【００７４】
パターン画像取得部１０は、図示しないユーザインタフェースを介してユーザから検索により見つけ出したいパターン画像を取得する。以後、検索により見つけ出したい情報を「パターン」という。また、画像データとしてのパターンを「パターン画像」という。特徴量計算部１４は、パターン画像取得部１０からパターン画像を受け取り、パターン画像を実ベクトルである特徴量に変換する。これは前提技術[５．２]および前提技術[５．３]に記載のアルゴリズムに基づく。パラメータ取得部１８は、図示しないユーザインタフェースを介してユーザからパラメータを取得する。このパラメータは、前提技術［２．２］に記載したｋおよびＬである。
【００７５】
擬似コード列生成部１６は、特徴量計算部１４からパターンの実ベクトルを、パラメータ取得部１８からパラメータをそれぞれ受け取り、パターンの擬似コード列を生成する。ここで「擬似コード」とは、一文字のパターン画像の特徴量である実ベクトルから前提技術[２．２]の定義４の記載に基づいて生成されるＬ個の数字の組である。また「擬似コード列」とは、文字列のパターン画像それぞれについて擬似コードを生成して並べたものであり、文字列を構成する文字の数と同数の擬似コードを構成要素に持つデータである。
【００７６】
テキスト画像取得部２６は、図示しないユーザインタフェースを介してユーザからパターンの検索の対象となるテキスト画像を取得する。以後、パターンの検索対象となる情報を「テキスト」という。また、画像データとしてのテキストを「テキスト画像」という。特徴量計算部１４はテキスト画像取得部２６からテキスト画像を受け取り、パターン画像の場合と同様に前提技術[５．２]および前提技術[５．３]に記載のアルゴリズムに基づいて、テキスト画像を実ベクトルである特徴量に変換する。擬似コード列生成部１６は、特徴量計算部１４からテキストの実ベクトルを、パラメータ取得部１８からパラメータをそれぞれ受け取り、テキストの擬似コード列を生成する。
【００７７】
パターン生成部２０はさらに、スキップ関数生成部２２とパターン格納部２４とを含む。スキップ関数生成部２２は、擬似コード列生成部１６から擬似コード列を受け取ってスキップ関数を生成する。スキップ関数は前提技術［４］に記載のアルゴリズムに基づいて生成される。パターン格納部２４は、擬似コード列生成部１６が生成したパターンの擬似コードとスキップ関数生成部２２が生成したスキップ関数とを格納する。
【００７８】
検索部２８はさらに、テキスト格納部３０と比較部３２とを含む。テキスト格納部３０は、擬似コード列生成部１６が生成したテキストの擬似コード列を格納する。比較部３２は、テキスト格納部３０からテキストの擬似コード列を、パターン格納部２４からパターンの擬似コード列とスキップ関数とを取得し、テキストに含まれるパターンを検索し、結果を図示しないモニタ等の出力装置に出力する。
【００７９】
ここで比較部は、前提技術［３］および［４］に記載のアルゴリズムに基づいて、テキストに含まれるパターンを検索する。すなわち、テキストの擬似コード列の先頭から最後尾に向かってパターンの擬似コード列を順に重ね合わせ、パターンの擬似コードとテキストの擬似コードとをパターンの最後尾から先頭に向かって順番に比較する。比較の途中で不一致が見つかった場合には、テキストに重ね合わせるパターンの開始位置を所定量だけずらしつつ検索する。ここで所定量とは、不一致が見つかったときのテキストの擬似コードであって、パターンの擬似コード列の最後尾に対応する擬似コードに基づいて定まる量であり、具体的には前提技術［４］に記載のｓｋｉｐ関数により定まる。スキップ関数生成部２２が生成するスキップ関数とは、前提技術［４］に記載のｓｋｉｐ関数である。
【００８０】
情報検索装置１００の構成は、ハードウェア的には、任意のプロセッサ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００８１】
図１３は実施の形態にかかる情報検索装置１００の処理の流れを説明するフローチャートである。本フローチャートにおける処理は、例えばユーザが情報検索装置１００を起動したときに開始する。
【００８２】
パターン画像取得部１０はパターンである文字列の画像を取得する（Ｓ１０）。特徴量計算部１４は前提技術［５．３］の記載に基づいてパターン画像を実ベクトルに変換し、擬似コード列生成部１６は特徴量計算部１４が出力した実ベクトルとパラメータ取得部１８から取得したパラメータとに基づいてパターンの擬似コード列を生成する（Ｓ１２）。スキップ関数生成部２２は前提技術［４］の記載にしたがって擬似コード列生成部１６が生成したパターンの擬似コード列に基づいてスキップ関数を生成する（Ｓ１４）。パターン格納部２４は擬似コード列生成部１６が生成したパターンの擬似コード列とスキップ関数生成部２２が生成したスキップ関数とを格納する（Ｓ１６）。
【００８３】
テキスト画像取得部２６はテキストである文字列の画像を取得する（Ｓ１８）。特徴量計算部１４はテキスト画像を実ベクトルに変換し、擬似コード列生成部１６は特徴量計算部１４が出力した実ベクトルとパラメータ取得部１８から取得したパラメータとに基づいてテキストの擬似コード列を生成する（Ｓ２０）。テキスト格納部３０は擬似コード列生成部１６が生成したテキストの擬似コード列を格納する（Ｓ２２）。比較部３２はテキスト格納部３０からテキストの擬似コード列を、パターン格納部２４からパターンの擬似コード列とスキップ関数とを取得し、テキストに含まれるパターンを検索する（Ｓ２４）。比較部３２がパターンの検索を終了すると、本フローチャートにおける処理は終了する。
【００８４】
図１４は、テキストに含まれるパターンを検索する処理の流れを説明するフローチャートであり、図１３において比較部３２が行うステップＳ２４を詳細に説明するものである。本フローチャートにおける処理は、比較部３２がテキスト格納部３０からテキストの擬似コード列を、パターン格納部２４からパターンの擬似コード列とスキップ関数とを取得したときに開始する。
【００８５】
比較部３２は図示しない内部メモリにテキストの長さＴｌｅｎを設定する（Ｓ２６）。テキストの長さとは、テキストの擬似コード列を構成する擬似コードの数である。続いて、パターンの長さＰｌｅｎを設定する（Ｓ２８）。第１のループ変数ｉを１に初期化する（Ｓ３０）。第１のループ変数ｉは、テキストの擬似コード列の先頭から最後尾に向かってパターンの擬似コード列を順に重ね合わせるために用いられる変数である。
【００８６】
第１のループ変数ｉがＴｌｅｎ−Ｐｌｅｎ＋１以下である場合には（Ｓ３２Ｙ）、テキストＴ中の長さＰｌｅｎの部分文字列Ｔ［ｉ：ｉ＋Ｐｌｅｎ−１］をＴｅｘｔ［ｘ］として取り出す（Ｓ３４）。ここで部分文字列Ｔは、前提技術［３］に記載のものである。また、Ｔｅｘｔ［ｘ］＝Ｔ［ｉ：ｉ＋Ｐｌｅｎ−１］としたとき、Ｔｅｘｔ（ｊ）は部分文字列Ｔのｊ番目の擬似コードを表すものとする。さらに、Ｐ（ｘ）をパターンのｘ番目の擬似コードを表すものとする。
【００８７】
第２のループ変数ｊをＰｌｅｎで初期化する（Ｓ３６）。第２のループ変数ｊは、パターンと部分文字列Ｔとをパターの最後尾Ｐ（Ｐｌｅｎ）から先頭Ｐ（１）に向かって順番に比較するために用いられる変数である。Ｔｅｘｔ（ｊ）とＰ（ｊ）とが一致する場合には（Ｓ３８Ｙ）、ループ変数ｊをｊ−１で更新する（Ｓ４０）。これにより、パターンと部分文字列Ｔとはパターンの最後尾から先頭に向かって順番に比較される。ここで、Ｔｅｘｔ（ｊ）とＰ（ｊ）とが一致する場合とは、Ｔｅｘｔ（ｊ）とＰ（ｊ）とが前提技術［２］の定義２に記載の二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たす場合のことをいう。
【００８８】
ｊが０より大きい場合には（Ｓ４２Ｙ）、パターンと部分文字列Ｔとの比較が終了していないので、ステップＳ３８に戻って比較を継続する。ｊが０以下の場合には（Ｓ４２Ｎ）、パターンと部分文字列Ｔとが一致したことになるため、ｉを一致したものとして記録する（Ｓ４４）。その後スキップ関数を用いて第１のループ変数ｉを更新することにより部分文字列Ｔの開始点をずらす（Ｓ４６）。また、ｊが０より大きい間にＴｅｘｔ（ｊ）とＰ（ｊ）とが一致しないときは（Ｓ３８Ｎ）、パターンと部分文字列Ｔとが一致しないことになるため、スキップ関数を用いて第１のループ変数ｉを更新することにより部分文字列Ｔの開始点をずらす（Ｓ４６）。第１のループ変数ｉを更新した結果、ｉがＴｌｅｎ−Ｐｌｅｎ＋１よりも大きくなった場合には（Ｓ３２Ｎ）、テキストから部分文字列Ｔを取り出せないため、本フローチャートにおける処理を終了する。
【００８９】
以上のように、ＢＭ法における文字列の代わりに擬似コード列を採用し、あるふたつの擬似コードが前提技術［２］の定義２に記載の二項関係ｓｅｍｉｅｑｕｉｖａｌｅｎｔを満たす場合にそれらの擬似コードが一致するものとして、ＢＭ法を擬似コード列の比較に拡張したものがＥｘｔｅｎｄｅｄ ＢＭ法である。
【００９０】
以上の構成による動作は以下のとおりである。ユーザは、検索したいパターンの画像と、パターンの検索対象となる文字列の画像を用意する。これらの画像を実施の形態にかかる情報検索装置１００に入力すると、情報検索装置１００は図１３の手続を経てテキスト画像の中からパターン画像と一致する画像を出力する。
【００９１】
以上説明したように実施の形態によれば、文字列データではなく、文字列の画像データを対象として、高速な文字列検索を実行することができる。これにより、例えば古い時代の新聞画像のように、情報が文字列データではなくマイクロフィルム等の画像データとして保存されている場合でも、高速な文字列検索が可能となる。
【００９２】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００９３】
上記実施の形態では、擬似コード列生成部１６が擬似コード列に変換する実ベクトルは文字列画像から生成される場合につて説明したが、文字列画像から生成される場合に限られず、例えば音声データなど、任意の実ベクトルを入力とすることができる。
【００９４】
上記実施の形態では、検索の度にパターン画像を取得してパターンの擬似コード列およびスキップ関数を生成する場合について説明したが、パターン格納部２４に既に格納されているパターンの擬似コード列およびスキップ関数が流用できる場合には、パターン格納部２４から読み出してもよい。パターンの擬似コード列およびスキップ関数の生成を省略できるので計算コストの点で有利である。
【符号の説明】
【００９５】
１０ パターン画像取得部、 １２ 画像変換部、 １４ 特徴量計算部、 １６ 擬似コード列生成部、 １８ パラメータ取得部、 ２０ パターン生成部、 ２２ スキップ関数生成部、 ２４ パターン格納部、 ２６ テキスト画像取得部、 ２８ 検索部、 ３０ テキスト格納部、 ３２ 比較部、 １００ 情報検索装置。
【特許請求の範囲】
【請求項１】
複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する擬似コード列生成部と、
前記擬似コード列をパターンとして、擬似コード列であるテキストの先頭から順に前記パターンの構成要素の数と同数のテキストを部分テキストとしつつ、当該部分テキストと前記パターンとの比較を前記パターンの最後尾の擬似コードから先頭の擬似コードに向かって順に行う比較部と、
比較途中で結果が不一致となった場合に、現在の部分テキストの先頭となっているテキストの位置から次の部分テキストの先頭となるテキストの位置までずらす量を、前記部分テキストの最後尾の擬似コードを入力として出力する関数をスキップ関数として生成するスキップ関数生成部とを含み、
前記スキップ関数生成部は、擬似コードとして取り得る値すべてについて当該擬似コードが前記パターンの擬似コード列に含まれるか否かを特定し、含まれる場合には前記パターンの擬似コード列との位置関係から前記ずらす量を計算し、含まれない場合には前記パターンの擬似コード列の長さを前記ずらす量としてスキップ関数を生成し、
前記比較部は、前記スキップ関数に基づいて現在の部分テキストの先頭から次の部分テキストの先頭までのずらす量を決定することを特徴とする情報検索装置。
【請求項２】
前記比較部は、ふたつの擬似コードを比較するに際しては、それぞれの疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとすることを特徴とする請求項１に記載の情報検索装置。
【請求項３】
前記スキップ関数生成部は、疑似コードである数字の組の構成要素それぞれを入力とする、当該構成要素の数と同数の部分スキップ関数を生成し、疑似コードが入力されたときに当該擬似コードの構成要素それぞれを入力とした場合の対応する前記部分スキップ関数の出力値の最小値を出力値とする関数を前記スキップ関数として生成することを特徴とする請求項１または２に記載の情報検索装置。
【請求項４】
前記擬似コード列生成部は、任意のふたつの実ベクトル間の距離が近いほどそれらが同一の数字に変換される確率が高くなる複数の異なる関数を用いて実ベクトルを擬似コードに変換することを特徴とする請求項１から３のいずれかに記載の情報検索装置。
【請求項５】
複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成するステップと、
前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索するステップとをプロセッサに実行させることを特徴とする情報検索方法。
【請求項６】
複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する機能と、
前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索する機能とをコンピュータに実現させることを特徴とするプログラム。
【請求項１】
複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する擬似コード列生成部と、
前記擬似コード列をパターンとして、擬似コード列であるテキストの先頭から順に前記パターンの構成要素の数と同数のテキストを部分テキストとしつつ、当該部分テキストと前記パターンとの比較を前記パターンの最後尾の擬似コードから先頭の擬似コードに向かって順に行う比較部と、
比較途中で結果が不一致となった場合に、現在の部分テキストの先頭となっているテキストの位置から次の部分テキストの先頭となるテキストの位置までずらす量を、前記部分テキストの最後尾の擬似コードを入力として出力する関数をスキップ関数として生成するスキップ関数生成部とを含み、
前記スキップ関数生成部は、擬似コードとして取り得る値すべてについて当該擬似コードが前記パターンの擬似コード列に含まれるか否かを特定し、含まれる場合には前記パターンの擬似コード列との位置関係から前記ずらす量を計算し、含まれない場合には前記パターンの擬似コード列の長さを前記ずらす量としてスキップ関数を生成し、
前記比較部は、前記スキップ関数に基づいて現在の部分テキストの先頭から次の部分テキストの先頭までのずらす量を決定することを特徴とする情報検索装置。
【請求項２】
前記比較部は、ふたつの擬似コードを比較するに際しては、それぞれの疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとすることを特徴とする請求項１に記載の情報検索装置。
【請求項３】
前記スキップ関数生成部は、疑似コードである数字の組の構成要素それぞれを入力とする、当該構成要素の数と同数の部分スキップ関数を生成し、疑似コードが入力されたときに当該擬似コードの構成要素それぞれを入力とした場合の対応する前記部分スキップ関数の出力値の最小値を出力値とする関数を前記スキップ関数として生成することを特徴とする請求項１または２に記載の情報検索装置。
【請求項４】
前記擬似コード列生成部は、任意のふたつの実ベクトル間の距離が近いほどそれらが同一の数字に変換される確率が高くなる複数の異なる関数を用いて実ベクトルを擬似コードに変換することを特徴とする請求項１から３のいずれかに記載の情報検索装置。
【請求項５】
複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成するステップと、
前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索するステップとをプロセッサに実行させることを特徴とする情報検索方法。
【請求項６】
複数の実ベクトルそれぞれを複数の数字の組である擬似コードに変換し、当該複数の擬似コードを構成要素とする擬似コード列を生成する機能と、
前記擬似コード列をパターンとして、擬似コード列であるテキストから前記パターンを検索するに際し、ふたつの擬似コード列の比較は対応する擬似コード同士を比較することで行い、擬似コード同士の比較は疑似コードの構成要素である数字の組を順に比較していずれも不一致の場合のみ前記ふたつの擬似コードが不一致であるとして、Ｂｏｙｅｒ−Ｍｏｏｒｅ法を適用することにより検索する機能とをコンピュータに実現させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図７】
【図８】
【図９】
【公開番号】特開２０１１−１５０４０４（Ｐ２０１１−１５０４０４Ａ）
【公開日】平成２３年８月４日（２０１１．８．４）
【国際特許分類】
【出願番号】特願２０１０−９０６８（Ｐ２０１０−９０６８）
【出願日】平成２２年１月１９日（２０１０．１．１９）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ＭＩＲＵ２００９第１２回 画像の認識・理解シンポジウム論文集
【出願人】（５０８２３６２４０）公立大学法人公立はこだて未来大学 (16)
【Ｆターム（参考）】
【公開日】平成２３年８月４日（２０１１．８．４）
【国際特許分類】
【出願日】平成２２年１月１９日（２０１０．１．１９）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ＭＩＲＵ２００９第１２回 画像の認識・理解シンポジウム論文集
【出願人】（５０８２３６２４０）公立大学法人公立はこだて未来大学 (16)
【Ｆターム（参考）】
[ Back to top ]