(57)【要約】      （修正有）【課題】パターンの検索を行う検索装置において、パターンの検索処理を高速に行う。【解決手段】検索効率計算部２１は、パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算する。検索処理部２２は、検索効率の値が大きい記号の順に、記号照合をして検索を行う。【選択図】図７
2008102926.tif 000002
【特許請求の範囲】
【請求項１】
パターンの検索を行う検索装置において、
パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、前記シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算する検索効率計算部と、
前記検索効率の値が大きい記号の順に、記号照合をして検索を行う検索処理部と、
を有することを特徴とする検索装置。
【請求項２】
前記検索効率計算部は、パターン中の連続する同一の記号からなる同一記号列の最後尾から検索を行うパターン検索方法、ＢＭ法、ＫＭＰ法の少なくとも１つに前記検索効率を導入することを特徴とする請求項１記載の検索装置。
【請求項３】
前記検索処理部は、前記パターン検索方法、前記ＢＭ法、前記ＫＭＰ法を任意に組み合わせて、前記検索効率の値が大きい記号の順にもとづいて検索を行うことを特徴とする請求項２記載の検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は検索装置に関し、特にパターンの検索を行う検索装置に関する。
【背景技術】
【０００２】
近年の情報化社会の発展に伴い、扱われる情報量は大規模化しており、マルチメディアサービスの高度化、広域化を実現するためには、記号列（文字列）検索処理の高速化が強く求められている。検索処理では、テキストと呼ばれる与えられた特定の記号列の中から、パターンと呼ばれる指定された記号列を検索する。
【０００３】
従来の最も単純な検索アルゴリズムでは、検索過程で不一致が検出されたら、パターンを１記号ずらして再び照合を繰り返すものであるが、より高速処理を可能とした代表的なアルゴリズムとして、Knuth、Morris、Prattによって提案されたＫＭＰ法や、BoyerとMorreによって提案されたＢＭ法がある。
【０００４】
ＫＭＰ法及びＢＭ法の基本検索操作としては、パターンの記号の照合時に（ＫＭＰ法はパターンの先頭から前→後の方向に、ＢＭ法ではパターンの最後尾から後→前の方向に照合していく）、不一致を検出したときには、ある条件にもとづき、パターンを大きく移動するものである。このような検索を行うことで、記号の不一致が生じたときに常にパターンを１記号ずらして照合を行う単純な方法と比べて、検索性能を向上させることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
情報通信の分野においては、連続する同一記号を含む構造を持つパターンの検索を行うことが多い。同一記号が連続するパターンとしては、例えば、ＨＤＬＣフラグやＭＰＥＧで圧縮されたストリーム中に存在するヘッダなどがある。
【０００６】
このような特定の構造を持つパターンに対して、上記のような従来のＫＭＰ法やＢＭ法で検索処理を行うと、無駄な記号照合が発生し、検索性能の向上を図れないといった問題があった。
【０００７】
高速検索アルゴリズムを代表するＫＭＰ法やＢＭ法であっても、あらゆる構造のパターンに対して有効とはいえず、同一記号列を持つパターンに対しての検索性能は必ずしも最良とはいえなかった。
【０００８】
本発明はこのような点に鑑みてなされたものであり、検索処理を高速に行う検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明では上記課題を解決するために、図７に示すような、パターンの検索を行う検索装置において、パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算する検索効率計算部２１と、検索効率の値が大きい記号の順に、記号照合をして検索を行う検索処理部２２と、を有することを特徴とする検索装置２０が提供される。
【００１０】
ここで、検索効率計算部２１は、パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算する。検索処理部２２は、検索効率の値が大きい記号の順に、記号照合をして検索を行う。
【発明の効果】
【００１１】
本発明の検索装置は、パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算し、検索効率の値が大きい記号の順に、記号照合をして検索を行う構成とした。これにより、無駄な記号照合を避けることができ、高速に検索を行うことが可能になる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施の形態を図面を参照して説明する。図１は検索装置の原理図である。検索装置１０は、テキスト（またはバイナリデータ）の中からパターンの検索を行う。
同一記号列認識部１１は、パターンの中の連続する同一の記号からなる同一記号列を認識する。検索処理部１２は、同一記号列の最後尾の記号から、パターンとテキストとの記号照合（または単に照合と呼ぶ）を開始する。そして、最後尾の記号の記号照合が失敗した場合には、同一記号の数だけパターンをシフトして再度記号照合をして検索を行う。
【００１３】
例えば、パターンを“000B”とすると、このパターンの同一記号列は“000”である。検索を行う際には、テキストとパターンの左端を合わせて出発して、“000”の最後尾の記号“0”からテキストとの記号照合を開始する。最後尾の記号“0”の記号照合が失敗した場合には（図のテキストは“C”であるから“0”と不一致である）、同一記号列の数（ここでは３記号分）だけシフトして、再び記号照合を行っていく。詳細な動作内容は図５で後述する。
【００１４】
次にＫＭＰ法とＢＭ法の概要について説明する。図２はＫＭＰ法を説明するための図である。テキストの中に、パターンの出現する位置を見つけるために、まず、テキストとパターンの左端を合わせて出発し、パターンの先頭（左端）から後方へテキストと１記号ずつ順に照合していく。
【００１５】
そして、記号の不一致が生じたとき（図の○と△）、パターンのその位置から左方にある部分列（図の太実線枠）と同じものがパターンの先頭部にもあれば、パターンを図の大きさだけ右にずらす。なお、部分列は最大長のものを選ぶ。
【００１６】
例えば、パターン“EFGHEF2”を図のテキストの中から見つける場合、“EFGHEF”まで照合が成功し、最後尾の“２”で不一致が生じた場合、“２”の左方にある部分列“EF”と同じものがパターンの先頭にもあるので、次のパターン位置は、位置Ｐ１までパターンの先頭をずらすことができる。
【００１７】
図３、図４はＢＭ法を説明するための図である。テキストの中にパターンの出現する位置を見つけるために、まず、テキストとパターンの左端を合わせて出発し、パターンの最後尾（右端）から前方へテキストと１記号ずつ順に照合していく。
【００１８】
また、ＢＭ法では、記号の不一致が生じたとき（図の○と△）、パターンを右へどれだけずらすかについて２つのアルゴリズムがある。図３に第１のアルゴリズム、図４に第２のアルゴリズムを示す。
【００１９】
図３に対し、第１のアルゴリズムはＫＭＰ法と似たもので、パターンの右端から不一致の前の位置にある部分列（図の太実線枠）と同じ部分列が左方にもあれば、その部分列がテキストの部分列と重なるようにパターンを右へずらす。
【００２０】
例えば、パターン“NEFGHEF2”を図のテキストの中から見つける場合、“EF2”まで照合が成功し、次の“H”で不一致が生じた場合、“H”の前の位置の部分列“EF”と同じ部分列がパターンの左方にもあるので、この部分列が重なる位置までずらすことができる（パターンの先頭は位置Ｐ２にくる）。
【００２１】
図４に対し、第２のアルゴリズムでは、不一致の際のテキストの記号を見て、パターンの左方に同じ記号があるとき、これとテキストのその記号とが重なるようにパターンをずらす。
【００２２】
例えば、パターン“NKFGHEF2”を図のテキストの中から見つける場合、“EF2”まで照合が成功し、次の“H”で不一致が生じた場合、不一致が生じたときのテキストの記号は“K”である。“K”はパターン左方にもあるので、パターンとテキストの“K”が重なる位置までずらすことができる（パターンの先頭は位置Ｐ３にくる）。
【００２３】
なお、一般的には、ＫＭＰ法よりもＢＭ法の検索速度の方が高速であることが知られている。また、ＢＭ法の中では、第１のアルゴリズムよりも第２のアルゴリズムの検索速度の方が高速であることが知られている。
【００２４】
次に検索装置１０の検索動作について従来のＢＭ法と比較しながら詳しく説明する。なお、以降では検索装置１０の検索動作をパターン検索方法とも呼ぶ。
図５は検索手順を示す図である。テキストを図に示す記号列とし、パターンを“000B”とする。まず、パターン中の連続する最長の同一記号列“000”に着目する。そして、テキストとパターンの左端を合わせて出発し、最初に、パターン“000B”の中の“000”の最後尾の記号“０”からテキストとの照合を行う。
【００２５】
もしも、照合した結果、記号の不一致が発見されたら、パターンの先頭方向には、記号の照合が失敗した文字“0”しか存在しないので、この場合に１文字及び２文字のシフトをして記号を照合しても、一致しないのは明白である。
【００２６】
そこで、パターンを３文字（同一記号列の数分）シフトして、再度同様な記号照合を繰り返していく。図では３回目のシフトのときに“000”の一番右の文字が一致している。したがって、次は“000”の２番目の文字とテキストを比較することになる。
【００２７】
ここで、もし、記号の不一致が発見されれば、１文字分シフトをして記号を照合しても、一致しないのは明白であるので、２文字シフトして記号の照合を再開する。なお、一般には、同一記号列の先頭から最後尾まで１〜ｎの番号を付けた際に、ｋ（２≦ｋ≦ｎ）番目の記号照合に失敗したときは、パターンをｋ個分シフトすることになる。
【００２８】
このような検索処理を行うことにより、シフト回数を大幅に削減することが可能になる。なお、図の例では、３回目のシフトで、テキスト中にパターン“000B”が検出されている（この３回目シフト位置における照合順番は、“000”の最後尾の“0”、中間の“0”、先頭の“0”の順に照合し、その次に“B”を照合して、パターンを検出している）。
【００２９】
図６は従来のＢＭ法の検索手順を示す図である。テキストとパターンの記号列は図５と同様である。図はＢＭ法の第２のアルゴリズムの場合を示している。ＢＭ法では、パターンの最後尾の文字から検索を開始する。
【００３０】
もしも、記号が不一致であれば、テキスト中の不一致であった記号を見て、パターンの左方に同じ記号があるとき、この記号を不一致が発見された位置にくるようにパターンをシフトする。ここでは、テキスト中の不一致であった記号は“0”であるので、この“0”と、“000B”の最後尾から２番目の“0”とが重なるようにパターンをシフトする。
【００３１】
このような処理は０回目シフトから２回目シフト、３回目シフトから６回目シフトにかけて行われている。また、２回目から３回目にシフトする際、テキスト中の“A”とパターン中の“B”は不一致であり、“A”はパターン左方に存在しないので、２回目シフトから３回目シフトへ行く際には、パターン４文字分のシフトが行われている。
【００３２】
図に示すように、ＢＭ法の場合では合計７回のシフト回数を要している。このように、同一記号列を含むパターンの場合では、検索装置１０による検索処理の方が高速であることがわかる。
【００３３】
次に検索効率を導入した場合の検索装置について説明する。図７は検索装置の構成を示す図である。検索装置２０は、検索効率計算部２１、検索処理部２２から構成される。なお、以降では検索装置２０の検索動作を単に検索方法とも呼ぶ。
【００３４】
検索効率計算部２１は、パターンの各記号に対する検索効率を計算する。検索効率とは、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、そのシフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数との比で表される。検索処理部２２は、検索効率の値が大きい記号の順に記号照合をして検索を行う。
【００３５】
次に検索効率及び検索装置２０の動作について詳しく説明する。検索速度を上げるためには、シフト量を大きくとって、無駄な記号照合をなくさなければならない。この場合に、パターン中のどこの記号から照合を行えば、照合が失敗したときに、シフト量を大きくとれるかといった指標が必要である。この指標を示すものが検索効率である。検索効率は、シフト量の期待値／記号照合回数である。
【００３６】
まず最初に、パターン検索方法に検索効率を導入した場合について説明する。具体例として、テキストがA、B、Cの３種類の記号からなり、パターンが“AAABCAB”の場合を考える。また、このパターン中の各記号に対して、パターン先頭から（１）、（２）、…、（７）の番号を付ける。
【００３７】
パターン検索方法では同一記号列に着目して検索を行うので、“AAA”に対する（３）、（２）、（１）のそれぞれの記号の検索効率を求めることになる。検索効率をＥ[（ｎ）]と表記すると（ｎはパターンに付けた番号である）、Ｅ[（３）]〜Ｅ[（１）]は以下の式で表される（Ｅ[（３）]とは、“AAA”の最後尾の“A”に関する検索効率、Ｅ[（２）]とは、“AAA”の中間の“A”に関する検索効率、Ｅ[（１）]とは、“AAA”の左端の“A”に関する検索効率のことである）。
Ｅ[（３）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×３＋Ｐ（Ｃ）×３）／１＝２      …（１ａ）
Ｅ[（２）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×２＋Ｐ（Ｃ）×２）／２＝４／６  …（１ｂ）
Ｅ[（１）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×１）／３＝２／９  …（１ｃ）
各式中のＰ（Ａ）は、テキスト中に記号“Ａ”が出現する確率、Ｐ（Ｂ）はテキスト中に記号“Ｂ”が出現する確率、Ｐ（Ｃ）はテキスト中に記号“Ｃ”が出現する確率である。ここでは、Ｐ（Ａ）＝Ｐ（Ｂ）＝Ｐ（Ｃ）＝１／３と仮定する。
【００３８】
一方、Ｅ[（ｎ）]の式の分子は、シフト量の期待値であり、確率変数であるシフト量の確率を重みとする加重平均で示されている。例えば、式（１ａ）のＰ（Ａ）×０に対し、“AAA”の最後尾の“A”をテキストと照合した際に、テキストの記号が“A”であったならば一致する。この場合、シフト操作はないので、シフト量は０である。すなわち、“AAA”の最後尾の“A”をテキストと照合した際に、シフト量が０となるためには、その位置のテキストに“A”が出現すればよく、その確率はＰ（Ａ）である。
【００３９】
また、式（１ａ）のＰ（Ｂ）×３及びＰ（Ｃ）×３に対し、“AAA”の最後尾の“A”をテキストと照合した際に、テキストの記号が“B”または“C”であったならば不一致である。この場合、シフト操作は図５で上述したように３記号分行うので、シフト量は３である。すなわち、“AAA”の最後尾の“A”をテキストと照合した際に、シフト量が３となるためには、その位置のテキストに“B”または“C”が出現すればよく、その確率はＰ（Ｂ）、Ｐ（Ｃ）である。
【００４０】
したがって、期待値とは、確率変数の値に、それぞれの値が実現する確率をかけたものの和であるから、式（１ａ）の分子（シフト量の期待値）は、Ｐ（Ａ）×０＋Ｐ（Ｂ）×３＋Ｐ（Ｃ）×３となる。式（１ｂ）、式（１ｃ）に対しても同様の考え方である。
【００４１】
一方、各式中の分母は、パターンとテキストとの記号照合回数を示している。“AAA”の最後尾の“A”の場合は、一番最初に記号照合されるので式（１ａ）では１となっている。
【００４２】
同様にして、“AAA”の中間の“A”の場合は、最後尾の“A”の照合が終わってその次に記号照合されるので、中間の“A”の照合を行うためにはパターンとテキストとの記号照合回数は２回要する。このため、式（１ｂ）では２となっている。さらに、“AAA”の左端の“A”の場合は、最後尾の“A”、中間の“A”の照合が終わってその次に記号照合されるので、左端の“A”の照合を行うためにはパターンとテキストとの記号照合回数は３回要する。このため、式（１ｃ）では３となっている。
【００４３】
このようにして計算した検索効率の値の大小を比べると、（１）＜（２）＜（３）である。したがって、検索効率が大きい値のものほど、照合が失敗したときに、シフト量を大きくとれることを示しているので、値の大きい（３）、（２）、（１）の順で（“AAA”の最後尾、中間、左端の順で）、記号照合を行えばよいことがわかる。
【００４４】
次にＢＭ法の第２のアルゴリズムに検索効率を導入した場合について説明する。例としては、上記と同様に、テキストはA、B、Cの３種類の記号からなり、パターンを“AAABCAB”とする。また、パターン先頭から（１）、（２）、…、（７）の番号を付ける。パターンの各記号に対してＢＭ法にもとづく検索効率Ｅ[（７）]〜Ｅ[（１）]は以下の式で表される。
Ｅ[（７）]＝（Ｐ（Ａ）×１＋Ｐ（Ｂ）×０＋Ｐ（Ｃ）×２）／１＝１      …（２ａ）
Ｅ[（６）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×２＋Ｐ（Ｃ）×１）／２＝１／２  …（２ｂ）
Ｅ[（５）]＝（Ｐ（Ａ）×２＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×０）／３＝１／３  …（２ｃ）
Ｅ[（４）]＝（Ｐ（Ａ）×１＋Ｐ（Ｂ）×０＋Ｐ（Ｃ）×４）／４＝５／１２
…（２ｄ）
Ｅ[（３）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×３＋Ｐ（Ｃ）×３）／５＝２／５  …（２ｅ）
Ｅ[（２）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×２＋Ｐ（Ｃ）×２）／６＝４／１８
…（２ｆ）
Ｅ[（１）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×１）／７＝２／２１
…（２ｇ）
ここで、例えば、式（２ｃ）について説明すると、Ｐ（Ｃ）×０に対し、“AAABCAB”の先頭から５番目の“C”をテキストと照合した際に、テキストの記号が“C”であったならば一致する。この場合、シフト操作はないので、シフト量は０である。すなわち、“AAABCAB”の先頭から５番目の“C”をテキストと照合した際に、シフト量が０となるためには、その位置のテキストに“C”が出現すればよく、その確率はＰ（Ｃ）である。
【００４５】
また、Ｐ（Ａ）×２に対し、“AAABCAB”の先頭から５番目の“C”をテキストと照合した際に、テキストの記号が“A”であったならば不一致である。この場合、シフト操作は図４で上述したように２記号分行うので（不一致であった位置に（３）の“A”を合わせることになるから）、シフト量は２である。すなわち、“AAABCAB”の先頭から５番目の“C”をテキストと照合した際に、シフト量が２となるためには、その位置のテキストに“A”が出現すればよく、その確率はＰ（Ａ）である。
【００４６】
さらに、Ｐ（Ｂ）×１に対し、“AAABCAB”の先頭から５番目の“C”をテキストと照合した際に、テキストの記号が“B”であったならば不一致である。この場合、シフト操作は図４で上述したように１記号分行うので（不一致であった位置に（４）の“B”を合わせることになるから）、シフト量は１である。すなわち、“AAABCAB”の先頭から５番目の“C”をテキストと照合した際に、シフト量が１となるためには、その位置のテキストに“B”が出現すればよく、その確率はＰ（Ｂ）である。
【００４７】
一方、式（２ｃ）の分母に対し、“AAABCAB”の先頭から５番目の“C”の場合は、パターン最後尾から３番目に照合されるので、パターンとテキストとの記号照合回数は３回要するために３となっている。なお、その他の式についても上記と同様な考え方である。
【００４８】
ここで、パターン検索方法に導入した場合の式（１ａ）〜（１ｃ）によるそれぞれの検索効率の値及びＢＭ法に導入した場合の式（２ａ）〜（２ｇ）によるそれぞれの検索効率の値の大小を比べると、式（１ａ）＝２が最も大きく、その次に式（２ａ）＝１が大きい。
【００４９】
したがって、パターン検索方法とＢＭ法を組み合わせる場合には、最初にパターン検索方法でパターン“AAABCAB”の（３）から照合し、その後にＢＭ法で（７）、（６）、（５）、（４）、（２）、（１）の順で、それぞれの記号の照合を行えば、検索性能を向上させることができる。
【００５０】
次にパターン検索方法及びＫＭＰ法を組み合わせ、これらに検索効率を導入した場合について説明する。例としては、テキストはA、B、Cの３種類の記号からなり、パターンを“ABCABAAA”とする。また、パターン先頭から（１）、（２）、…、（８）の番号を付ける。パターンの各記号に対して、パターン検索方法にもとづく検索効率Ｅ[（８）]〜Ｅ[（６）]は以下の式で表される。
Ｅ[（８）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×３＋Ｐ（Ｃ）×３）／１＝２      …（３ａ）
Ｅ[（７）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×２＋Ｐ（Ｃ）×２）／２＝４／６  …（３ｂ）
Ｅ[（６）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×１）／３＝２／９  …（３ｃ）
パターン検索方法における各式の考え方については上述したので説明は省略する。一方、ＫＭＰ法にもとづく検索効率Ｅ[（１）]〜Ｅ[（８）]は以下の式で表される。
Ｅ[（１）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×１）／１＝２／３  …（４ａ）
Ｅ[（２）]＝（Ｐ（Ａ）×１＋Ｐ（Ｂ）×０＋Ｐ（Ｃ）×１）／２＝２／６  …（４ｂ）
Ｅ[（３）]＝（Ｐ（Ａ）×１＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×０）／３＝２／９  …（４ｃ）
Ｅ[（４）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×１）／４＝２／１２
…（４ｄ）
Ｅ[（５）]＝（Ｐ（Ａ）×１＋Ｐ（Ｂ）×０＋Ｐ（Ｃ）×１）／５＝２／１５
…（４ｅ）
Ｅ[（６）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×３＋Ｐ（Ｃ）×３）／６＝２／６  …（４ｆ）
Ｅ[（７）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×１）／７＝２／２１
…（４ｇ）
Ｅ[（８）]＝（Ｐ（Ａ）×０＋Ｐ（Ｂ）×１＋Ｐ（Ｃ）×１）／８＝２／２４
…（４ｈ）
ここで、例えば、式（４ｆ）について説明すると、Ｐ（Ａ）×０に対し、“ABCABAAA”の先頭から６番目の“A”をテキストと照合した際に、テキストの記号が“A”であったならば一致する。この場合、シフト操作はないので、シフト量は０である。すなわち、“ABCABAAA”の先頭から６番目の“A”をテキストと照合した際に、シフト量が０となるためには、その位置のテキストに“A”が出現すればよく、その確率はＰ（Ａ）である。
【００５１】
また、式（４ｆ）のＰ（Ｂ）×３及びＰ（Ｃ）×３に対し、“ABCABAAA”の先頭から６番目の“A”をテキストと照合した際に、テキストの記号が“B”または“C”であったならば不一致である。この場合、シフト操作は図２で上述したように３記号分行うので（不一致となった位置から左方に部分列“AB”があり、この部分列はパターン先頭にもあるから、３記号分ずらすことになる）、シフト量は３である。すなわち、“ABCABAAA”の先頭から６番目の“A”をテキストと照合した際に、シフト量が３となるためには、その位置のテキストに“B”または“C”が出現すればよく、その確率はＰ（Ｂ）、Ｐ（Ｃ）である。
【００５２】
一方、式（４ｆ）の分母に対し、“ABCABAAA”の先頭から６番目の“A”の場合は、パターン先頭から６番目に照合されるので、パターンとテキストとの記号照合回数は６回要するため６となっている。なお、その他の式についても上記と同様な考え方である。
【００５３】
ここで、パターン検索方法に導入した場合の式（３ａ）〜（３ｃ）によるそれぞれの検索効率の値及びＫＭＰ法に導入した場合の式（４ａ）〜（４ｈ）によるそれぞれの検索効率の値の大小を比べると、式（３ａ）＝２が最も大きく、その次に式（３ｂ）＝式（４ａ）＝２／３が大きい。
【００５４】
したがって、最初にパターン検索方法でパターン“ABCABAAA”の（８）、（７）を照合し、その後にＫＭＰ法で、（１）、（２）、（３）、（４）、（５）、（６）の順で、それぞれの記号の照合を行えば、検索性能を向上させることができる。
【００５５】
次にパターン検索方法をソフトウェアで実施した場合について説明する。図８は同一記号列の最大長をカウントする際のプログラムを示す図である。プログラム２００は、同一記号列の最大長をカウントする。例えば、パターンが“AAAB”の場合は３、“AABBBBCC”の場合は４を返す。
【００５６】
図９はパターン検索方法の処理手順を示すフローチャートである。なお、Ｔｘｔはテキスト、Ｐａｔはパターンを示す。
〔Ｓ１〕記号照合開始順番をテーブルＴ[ｉ]に記憶する。例えば、パターンを“000B”として、パターン先頭から（０）〜（３）の番号を付ける。同一記号列の最後尾から検索を行うから、Ｔ[０]＝（２）、Ｔ[１]＝（１）、Ｔ[２]＝（０）、Ｔ[３]＝（３）となる。
〔Ｓ２〕記号照合失敗時のシフト量をテーブルＳ[Ｔ[ｉ]]に記憶する。例えば、パターン“000B”の場合、同一記号列の最後尾が不一致であったときには３記号分シフトするので、Ｓ[Ｔ[０]]＝３と表記される。
〔Ｓ３〕初期設定として、ｉ＝０、shift＝０とする。
〔Ｓ４〕ｉがパターンの記号数（パターンの長さ）になるまで、以下のステップＳ５〜Ｓ７のループ処理を行う。
〔Ｓ５〕シフト位置shift[Ｔ[ｉ]]のときのテキストＴｘｔ[shift[Ｔ[ｉ]]と、パターンＰａｔ[Ｔ[ｉ]]との記号を比較し、不一致ならばステップＳ６へ、一致ならばステップＳ７へ行く。
〔Ｓ６〕あらかじめ記憶してあるシフト量だけシフトする（ｉ＝０、shift＝shift＋Ｓ[Ｔ[ｉ]]）。
〔Ｓ７〕次に照合すべき記号へ移る（ｉ＋＋）。
【００５７】
次に検索方法についてフローチャートを用いて説明する。図１０は検索方法の処理手順を示すフローチャートである。
〔Ｓ１１〕パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、前記シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算する。
〔Ｓ１２〕検索効率の値が大きい記号の順に、記号照合をして検索を行う。
【００５８】
図１１はパターン検索方法及びＢＭ法を組み合わせて検索効率を導入したときの検索方法の処理手順を示すフローチャートである。
〔Ｓ２１〕パターンの中から同一記号列を特定する。
〔Ｓ２２〕同一記号列中の記号に対して検索効率を計算する。
〔Ｓ２３〕すべての記号に対してＢＭ法の検索効率を計算する。
〔Ｓ２４〕検索効率から記号照合順番を決定する。
〔Ｓ２５〕記号照合順番にもとづき検索を実行する。
【００５９】
図１２はパターン検索方法及びＫＭＰ法を組み合わせて検索効率を導入したときの検索方法の処理手順を示すフローチャートである。
〔Ｓ３１〕パターンの中から同一記号列の位置を特定する。
〔Ｓ３２〕同一記号列中の記号に対して検索効率を計算する。
〔Ｓ３３〕すべての記号に対してＫＭＰ法の検索効率を計算する。
〔Ｓ３４〕検索効率から記号照合順番を決定する。
〔Ｓ３５〕記号照合順番にもとづき検索を実行する。
【００６０】
図１３はパターン検索方法とＢＭ法とＫＭＰ法を組み合わせて検索効率を導入したときの検索方法の処理手順を示すフローチャートである。
〔Ｓ４１〕パターンの中から同一記号列の位置を特定する。
〔Ｓ４２〕同一記号列中の記号に対して検索効率を計算する。
〔Ｓ４３〕すべての記号に対してＢＭ法の検索効率を計算する。
〔Ｓ４４〕すべての記号に対してＫＭＰ法の検索効率を計算する。
〔Ｓ４５〕検索効率から記号照合順番を決定する。
〔Ｓ４６〕記号照合順番にもとづき検索を実行する。
【００６１】
以上説明したように、検索装置２０及び検索方法によれば、テキストやバイナリデータの検索時に、検索効率を用いて、記号照合手順を動的に変更し、無駄な記号照合を避けることとした。これにより、従来のＫＭＰ法またはＢＭ法だけで検索するよりも、高速にパターンを検索することが可能になる。
【００６２】
次に画像受信装置について説明する。図１４は画像通信システムの構成を示す図である。画像通信システム１００は、ネットワーク１０１で接続される、画像送信装置１２０と画像受信装置１１０とから構成される。
【００６３】
画像受信装置１１０に対し、ストリームデータ受信部１１１は、画像送信装置１２０から送信されたＭＰＥＧ４等のストリームデータを受信し格納する。ヘッダサーチ部１１２は、検索装置１０または検索装置２０の機能を有し、ストリームデータからヘッダ情報（同一記号列が含まれる）を検索し、ヘッダ位置情報を出力する。
【００６４】
情報分離部１１３は、ヘッダ位置情報にもとづき、ストリーム信号からヘッダ情報と画像情報を分離する。ヘッダ処理部１１４は、ヘッダ情報を処理し、デコーダ１１５は、画像情報をデコードして画面に表示する。
【００６５】
なお、上記の説明では、画像通信システムに適用したが、これ以外にもデータベースやファイルなどのサーチ、ＨＤＬＣ等の通信での同期フラグ検出など、様々な分野の検索システムや検索ソフトウェアに適用可能である。
【００６６】
（付記１）  パターンの検索を行う検索装置において、
パターン中の連続する同一の記号からなる同一記号列を認識する同一記号列認識部と、
前記同一記号列の最後尾の記号から、パターンとテキストとの記号照合を行い、前記最後尾の記号の記号照合が失敗した場合には、同一記号の数だけパターンをシフトして再度記号照合をして検索を行う検索処理部と、
を有することを特徴とする検索装置。
【００６７】
（付記２）  前記検索処理部は、前記同一記号列の先頭から最後尾まで１〜ｎの番号を付けて、前記同一記号列の最後尾の記号から先頭に向かって記号照合を行う際に、ｋ（２≦ｋ≦ｎ）番目の記号照合に失敗したときは、パターンをｋ個分シフトして再度記号照合を行うことを特徴とする付記１記載の検索装置。
【００６８】
（付記３）  パターンの検索を行う検索装置において、
パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、前記シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算する検索効率計算部と、
前記検索効率の値が大きい記号の順に、記号照合をして検索を行う検索処理部と、
を有することを特徴とする検索装置。
【００６９】
（付記４）  前記検索効率計算部は、パターン中の連続する同一の記号からなる同一記号列の最後尾から検索を行うパターン検索方法、ＢＭ法、ＫＭＰ法の少なくとも１つに前記検索効率を導入することを特徴とする付記３記載の検索装置。
【００７０】
（付記５）  前記検索処理部は、前記パターン検索方法、前記ＢＭ法、前記ＫＭＰ法を任意に組み合わせて、前記検索効率の値が大きい記号の順にもとづいて検索を行うことを特徴とする付記４記載の検索装置。
【００７１】
（付記６）  同一記号列を含むパターンの検索を行うパターン検索方法において、
パターン中の連続する同一の記号からなる同一記号列を認識し、
前記同一記号列の最後尾の記号から、パターンとテキストとの記号照合を行い、
前記最後尾の記号の記号照合が失敗した場合には、同一記号の数だけパターンをシフトして再度記号照合をして検索を行うことを特徴とするパターン検索方法。
【００７２】
（付記７）  前記同一記号列の先頭から最後尾まで１〜ｎの番号を付けて、前記同一記号列の最後尾の記号から先頭に向かって記号照合を行う際に、ｋ（２≦ｋ≦ｎ）番目の記号照合に失敗したときは、パターンをｋ個分シフトして再度記号照合を行うことを特徴とする付記６記載のパターン検索方法。
【００７３】
（付記８）  パターンの検索を行う検索方法において、
パターンとテキストの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、前記シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算し、
前記検索効率の値が大きい記号の順に、記号照合をして検索を行うことを特徴とする検索方法。
【００７４】
（付記９）  パターン中の連続する同一の記号からなる同一記号列の最後尾から検索を行うパターン検索方法、ＢＭ法、ＫＭＰ法の少なくとも１つに前記検索効率を導入することを特徴とする付記８記載の検索方法。
【００７５】
（付記１０）  前記パターン検索方法、前記ＢＭ法、前記ＫＭＰ法を任意に組み合わせて、前記検索効率の値が大きい記号の順にもとづいて検索を行うことを特徴とする付記９記載の検索方法。
【００７６】
（付記１１）  画像受信制御を行う画像受信装置において、
画像圧縮されたストリームデータを受信するストリームデータ受信部と、
パターン中の連続する同一の記号からなる同一記号列を認識する同一記号列認識部と、前記同一記号列の最後尾の記号から、パターンとストリームデータとの記号照合を行い、前記最後尾の記号の記号照合が失敗した場合には、同一記号の数だけパターンをシフトして再度記号照合をして、ヘッダの検索を行う検索処理部と、から構成されるヘッダサーチ部と、
を有することを特徴とする画像受信装置。
【００７７】
（付記１２）  前記検索処理部は、前記同一記号列の先頭から最後尾まで１〜ｎの番号を付けて、前記同一記号列の最後尾の記号から先頭に向かって記号照合を行う際に、ｋ（２≦ｋ≦ｎ）番目の記号照合に失敗したときは、パターンをｋ個分シフトして再度記号照合を行うことを特徴とする付記１１記載の画像受信装置。
【００７８】
（付記１３）  画像受信制御を行う画像受信装置において、
画像圧縮されたストリームデータを受信するストリームデータ受信部と、
パターンと前記ストリームデータの記号照合を行う際に、記号照合が失敗したときのシフト操作のとりうる値であるシフト量に、前記シフト量が生じるための確率をかけた総和であるシフト量の期待値と、記号照合回数と、の比である検索効率を計算する検索効率計算部と、前記検索効率の値が大きい記号の順に、記号照合をして、ヘッダの検索を行う検索処理部と、から構成されるヘッダサーチ部と、
を有することを特徴とする画像受信装置。
【００７９】
(付記１４)  前記検索効率計算部は、パターン中の連続する同一の記号からなる同一記号列の最後尾から検索を行うパターン検索方法、ＢＭ法、ＫＭＰ法の少なくとも１つに前記検索効率を導入することを特徴とする付記１３記載の画像受信装置。
【００８０】
（付記１５）  前記検索処理部は、前記パターン検索方法、前記ＢＭ法、前記ＫＭＰ法を任意に組み合わせて、前記検索効率の値が大きい記号の順にもとづいて検索を行うことを特徴とする付記１４記載の画像受信装置。
【図面の簡単な説明】
【００８１】
【図１】検索装置の原理図である。
【図２】ＫＭＰ法を説明するための図である。
【図３】ＢＭ法を説明するための図である。
【図４】ＢＭ法を説明するための図である。
【図５】検索手順を示す図である。
【図６】従来のＢＭ法の検索手順を示す図である。
【図７】検索装置の構成を示す図である。
【図８】同一記号列の最大長をカウントする際のプログラムを示す図である。
【図９】パターン検索方法の処理手順を示すフローチャートである。
【図１０】検索方法の処理手順を示すフローチャートである。
【図１１】パターン検索方法及びＢＭ法を組み合わせて検索効率を導入したときの検索方法の処理手順を示すフローチャートである。
【図１２】パターン検索方法及びＫＭＰ法を組み合わせて検索効率を導入したときの検索方法の処理手順を示すフローチャートである。
【図１３】パターン検索方法とＢＭ法とＫＭＰ法を組み合わせて検索効率を導入したときの検索方法の処理手順を示すフローチャートである。
【図１４】画像通信システムの構成を示す図である。
【符号の説明】
【００８２】
１０  検索装置
１１  同一記号列認識部
１２  検索処理部
【図１】
2008102926.tif 000003
【図２】
2008102926.tif 000004
【図３】
2008102926.tif 000005
【図４】
2008102926.tif 000006
【図５】
2008102926.tif 000007
【図６】
2008102926.tif 000008
【図７】
2008102926.tif 000009
【図８】
2008102926.tif 000010
【図９】
2008102926.tif 000011
【図１０】
2008102926.tif 000012
【図１１】
2008102926.tif 000013
【図１２】
2008102926.tif 000014
【図１３】
2008102926.tif 000015
【図１４】
2008102926.tif 000016