(57)【要約】【課題】文字列探索にかかる処理時間の短縮化を図ること。【解決手段】文字列探索装置１０１は、探索文字列の先頭から１バイト分のビット列ｂ１を、対象文字列の先頭から８バイト分のビット列ｂ２とバイト単位で一括比較する第１比較命令を実行する。文字列探索装置１０１は、第１比較命令の比較結果に基づいて、探索文字列のビット列ｂ１の次の１バイト分のビット列ｂ６と、ビット列ｂ２のうちのビット列ｂ１と一致する箇所の次の１バイト分のビット列ｂ７とを比較する。文字列探索装置１０１は、ビット列ｂ６とビット列ｂ７とが一致する場合に、対象文字列のビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成するビット操作命令を実行する。文字列探索装置１０１は、生成したビット列ｂ８と、探索文字列の先頭から８バイト分のビット列ｂ４とをバイト単位で一括比較する第２比較命令を実行する。【選択図】図１
2014235454.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、
探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１比較と、
前記第１比較の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列との比較と、
前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列の生成と、
生成した前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第２比較と、
前記第２比較の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かの判断と、
を実行することを特徴とする文字列探索方法。
【請求項２】
前記コンピュータが、
前記探索文字列および前記対象文字列が特定の文字コードのときは、前記第３ビット列と前記第４ビット列とが一致する場合、前記探索文字ビット列のうち前記第３ビット列の次の前記第１ビット長のビット列と、前記対象文字ビット列のうち前記第４ビット列の次の前記第１ビット長のビット列との比較を実行し、
前記第３ビット列の次のビット列と前記第４ビット列の次のビット列とが一致する場合に、前記第５ビット列の生成を実行することを特徴とする請求項１に記載の文字列探索方法。
【請求項３】
前記第１ビット長は、１バイトであり、
前記第２ビット長は、ビット列同士をバイト単位で一括比較する比較命令の処理単位を表すビット長であることを特徴とする請求項１または２に記載の文字列探索方法。
【請求項４】
前記コンピュータが、
前記探索文字列および前記対象文字列がマルチバイト文字の場合、前記第１比較の比較結果に基づいて、前記第２ビット列のうち前記第１ビット列と一致する箇所がマルチバイト文字の先頭バイトか否かの判断を実行し、
前記第１ビット列と一致する箇所がマルチバイト文字の先頭バイトである場合に、前記第３ビット列と前記第４ビット列との比較を実行することを特徴とする請求項３に記載の文字列探索方法。
【請求項５】
前記コンピュータが、
前記第１ビット列を前記第２ビット長分第１レジスタに格納し、
前記第２ビット列を第２レジスタに格納する、処理を実行し、
前記第１レジスタに格納されたビット列と、前記第２レジスタに格納されたビット列とを前記第１ビット長単位で比較する第１比較を実行することを特徴とする請求項１〜４のいずれか一つに記載の文字列探索方法。
【請求項６】
前記コンピュータが、
前記対象文字ビット列のうち前記第２ビット列の次の前記第２ビット長のビット列を第３レジスタに格納する処理を実行し、
前記第１比較の比較結果に基づいて、前記第２レジスタに格納されたビット列を左シフトするとともにシフト元のビットをマスクし、前記第３レジスタに格納されたビット列を右シフトするとともにシフト元のビットをマスクし、前記第２レジスタに格納されたビット列と前記第３レジスタに格納されたビット列との論理和をとることにより、前記第５ビット列の生成を実行することを特徴とする請求項５に記載の文字列探索方法。
【請求項７】
探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１の比較部と、
前記第１の比較部の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列とを比較する第２の比較部と、
前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列を生成する生成部と、
前記生成部によって生成された前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第３の比較部と、
前記第３の比較部の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かを判断する判断部と、
を有することを特徴とする文字列探索装置。
【請求項８】
コンピュータに、
探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１比較と、
前記第１比較の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列との比較と、
前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列の生成と、
生成した前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第２比較と、
前記第２比較の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かの判断と、
を実行させることを特徴とする文字列探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文字列探索方法、文字列探索装置および文字列探索プログラムに関する。
【背景技術】
【０００２】
従来、文字列を検索する技術として、ターゲット文字列に対して、パターン文字列を１バイト単位で比較するものがある（以下、「従来技術１」と称する）。例えば、「Ｔｈｅ  ｑｕｉｃｋ  ｂｒｏｗｎ  ｆｏｘ」というターゲット文字列に対して、「ｑｕｅｅｎ」というパターン文字列を検索する場合、５バイト目の「ｑ」、６バイト目の「ｕ」を比較後、７バイト目の「ｉ」と「ｅ」との比較で検索結果が異なると判断することができる。
【０００３】
また、ターゲット文字列に対して、状態遷移図を用いて、パターン文字列の照合を行う技術がある（以下、「従来技術２」と称する）。状態遷移図は、状態が遷移していく様子を表現する図である。状態遷移図を用いて検索を行うことにより、例えば、上記の例では、７バイト目の「ｉ」と「ｅ」の比較が終わった後に、次の検索開始位置が８バイト目になるよう制御することができる。
【０００４】
また、複数のレジスタを用いて、文字列を検索する検索処理の一部をハードウェア処理により実行する技術がある。具体的には、従来装置は、第１レジスタに照合または被照合の文字列のデータのうち長いデータ長のデータを保持し、第２レジスタに短いデータをシフト自在に保持する。また、従来装置は、第２レジスタに保持した文字列の先頭の文字のデータを、第１レジスタに保持した文字列分第３レジスタに一旦保持し、第１レジスタ、第３レジスタに保持した文字列のデータの排他的論理和の演算結果を保持する。また、従来装置は、この演算結果により第２レジスタの文字列をシフトさせ、第１レジスタ、第２レジスタに保持したデータの排他的論理和の演算結果と第２レジスタの文字列のシフト位置により検索出力の可否またはさらなるシフトの可否を判定する（以下、「従来技術３」と称する）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−３１２３６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術によれば、ターゲット文字列やパターン文字列が長くなると、文字列探索にかかる処理時間が増大するという問題がある。例えば、従来技術１では、文字列の差異が見つかった場合、１バイト後方の文字列から再度検索処理を行うことになり、文字列探索にかかる処理時間の増大を招く。また、従来技術２では、検索を行うたびに状態遷移図を作成することになり、状態遷移図の作成にかかる処理負荷が増大する。また、従来技術３では、パターン文字列自体を加工する場合、同一文字列の再検索時には再度シフトを実施することになり、文字列探索にかかる処理時間の増大を招く。
【０００７】
一つの側面では、本発明は、文字列探索にかかる処理時間の短縮化を図る文字列探索方法、文字列探索装置および文字列探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一側面によれば、探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１比較と、前記第１比較の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列との比較と、前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列の生成と、生成した前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第２比較と、前記第２比較の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かの判断と、を実行する文字列探索方法、文字列探索装置および文字列探索プログラムが提案される。
【発明の効果】
【０００９】
本発明の一態様によれば、文字列探索にかかる処理時間の短縮化を図ることができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施の形態にかかる文字列探索方法の一実施例を示す説明図（その１）である。
【図２】図２は、実施の形態にかかる文字列探索方法の一実施例を示す説明図（その２）である。
【図３】図３は、システム３００のシステム構成例を示す説明図である。
【図４】図４は、データベースサーバ３０１のハードウェア構成例を示すブロック図である。
【図５】図５は、データベースサーバ３０１の機能的構成例を示すブロック図である。
【図６】図６は、文字コードがＳＪＩＳの場合の文字列探索処理例を示す説明図（その１）である。
【図７】図７は、文字コードがＳＪＩＳの場合の文字列探索処理例を示す説明図（その２）である。
【図８】図８は、文字コードがＳＪＩＳの場合の文字列探索処理例を示す説明図（その３）である。
【図９】図９は、データベースサーバ３０１の文字列探索処理手順の一例を示すフローチャート（その１）である。
【図１０】図１０は、データベースサーバ３０１の文字列探索処理手順の一例を示すフローチャート（その２）である。
【発明を実施するための形態】
【００１１】
以下に図面を参照して、本発明にかかる文字列探索方法、文字列探索装置および文字列探索プログラムの実施の形態を詳細に説明する。
【００１２】
（文字列探索方法の一実施例）
図１および図２は、実施の形態にかかる文字列探索方法の一実施例を示す説明図である。図１において、文字列探索装置１０１は、対象文字列から探索文字列を探索するコンピュータである。探索文字列は、探索する文字列である。対象文字列は、探索先の文字列である。
【００１３】
ここで、対象文字列から探索文字列を探索する技術として、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）により、探索文字列の先頭文字と対象文字列とを一括比較して、対象文字列から探索文字列の先頭文字を検出し、探索文字列との文字列マッチングを行うことが考えられる。すなわち、対象文字列から探索文字列の先頭文字と一致する箇所を検出するという一次スクリーニングを行った後に、より詳細な文字列探索を行うことが考えられる。
【００１４】
ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令とは、１命令で複数のデータを処理するものである。ただし、ＳＩＭＤ命令を用いる場合には、８バイトのバウンダリを守らなければならない。このため、探索文字列の先頭文字と対象文字列とを一括比較した比較結果に応じて、例えば、レジスタ内の対象文字列のデータを、Ｓｈｉｆｔ、Ｍａｓｋした上でＯｒをとり、ＳＩＭＤ命令にて探索文字列のデータと比較できる形に加工する必要がある。
【００１５】
この際、特定のビット操作命令（例えば、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒ）を用いて、レジスタ内の対象文字列のデータを加工することにより、Ｓｈｉｆｔ、Ｍａｓｋ、Ｏｒをそれぞれ独立した命令として実行する場合に比べて、データ加工にかかる処理時間を短縮することができる。
【００１６】
しかし、偶然先頭文字のみが一致したものについても、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行うことは、先頭文字が出現頻度の多い文字である場合、詳細探索を行って外れることによるペナルティが大きくなる。また、文字には、マルチバイト文字と呼ばれる１文字を複数バイトで表すものがある。
【００１７】
マルチバイト文字においては、文字が完全に一致しなくても、ビット列が一致する組み合わせが多数存在し、ＳＩＭＤ  Ｃｏｍｐａｒｅによるスクリーニングだけでは、先頭文字さえも一致しない余分な候補に対して、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行うことになる場合がある。
【００１８】
マルチバイト文字の文字コードとしては、例えば、ＳＪＩＳ（Ｓｈｉｆｔ＿ＪＩＳ）やＵＴＦ−８（Ｕｎｉｃｏｄｅ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｆｏｒｍａｔ−８）などがある。一方、１文字を１バイトで表すシングルバイト文字の文字コードとしては、例えば、ＡＳＣＩＩ（Ａｍｅｒｉｃａｎ  Ｓｔａｎｄａｒｄ  Ｃｏｄｅ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｉｎｔｅｒｃｈａｎｇｅ）がある。
【００１９】
ここで、ペナルティが大きくなる場合の具体例として、文字コードがＳＪＩＳの場合を例に挙げて説明する。ＳＪＩＳは、１文字を２バイトで表す文字コードである。また、対象文字列を「デジタル−テレビの普及」とし、探索文字列を「テレビ」とする。対象文字列「デジタル−テレビの普及」および探索文字列「テレビ」をＳＪＩＳで表すと以下のようになる。ただし、各文字の右側の括弧内の数字が各文字を表すデータ（０ｘ〜の〜の部分）である。
【００２０】
［対象文字列］デ（８３  ６６）ジ（８３  ５７）タ（８３  ５Ｅ）ル（８３  ８Ｂ）−（８１  ７Ｃ）テ（８３  ６５）レ（８３  ８Ｃ）ビ（８３  ７２）の（８２  ＣＣ）普（９５  ８１）及（８Ｂ  ７９）
【００２１】
［探索文字列］テ（８３  ６５）レ（８３  ８Ｃ）ビ（８３  ７２）
【００２２】
ＳＪＩＳではカタカナの先頭の１バイトは「８３」となるため、探索文字列の先頭１バイトだけの確認では、対象文字列に含まれるすべてのカタカナがヒットしてしまう。ヒットする度に、対象文字列を８バイトの文字列として加工し、ＳＩＭＤ命令により８バイトでの比較を実施すると、文字列探索にかかる処理時間の増大を招いてしまう。
【００２３】
そこで、本実施の形態では、文字列探索装置１０１は、例えば、ＳＩＭＤ命令を用いて探索文字列の先頭バイトと一致する箇所を対象文字列から検出し、その次のバイトも探索文字列と一致すれば、ＳＩＭＤ命令で比較可能にビット列を加工して詳細探索を行う。これにより、無駄な詳細探索を抑制して文字列探索にかかる処理時間の短縮化を図る。
【００２４】
以下、文字列探索装置１０１の文字列探索処理例について説明する。ここでは、文字コードを「ＡＳＣＩＩ」とし、探索文字列を「ｑｕｉｃｋ」とし、対象文字列を「Ｔｈｅ  ｑｕｉｃｋ  ｂｒｏｗｎ  ｆｏｘ  ｊｕｍｐｓ  ｏｖｅｒ  ｔｈｅ  ｌａｚｙ  ｄｏｇ」とする。
【００２５】
（１）文字列探索装置１０１は、探索文字列を表すビット列に含まれる第１ビット長ｌ１のビット列ｂ１を、レジスタＲ１に第２ビット長ｌ２分格納する。ここで、第１ビット長ｌ１は、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）の処理単位となるビット数である。第１ビット長ｌ１は、例えば、１バイト（８ビット）、２バイト、３バイトなどである。
【００２６】
また、第２ビット長ｌ２は、第１ビット長ｌ１のＸ倍のビット長であり（Ｘ：２以上の自然数）、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）において１回で処理されるデータのビット長である。第２ビット長ｌ２は、例えば、８バイト、１６バイト、３２バイトなどである。以下の説明では、第１ビット長ｌ１を「１バイト」とし、第２ビット長ｌ２を「８バイト」とする。
【００２７】
具体的には、例えば、文字列探索装置１０１は、探索文字列を表すビット列の先頭から１バイト分のビット列ｂ１をレジスタＲ１に８バイト分格納する。図１の例では、探索文字列の先頭文字「q」を表すビット列ｂ１「０１１１０００１」がレジスタＲ１に８個格納されている。
【００２８】
また、文字列探索装置１０１は、対象文字列を表すビット列の先頭から８バイト分のビット列ｂ２をレジスタＲ２に格納する。また、文字列探索装置１０１は、対象文字列を表すビット列のうちビット列ｂ２の次の８バイト分のビット列ｂ３をレジスタＲ３に格納する。
【００２９】
なお、対象文字列を表すビット列の先頭から８バイト分のビット列がない場合は、対象文字列を表すビット列の先頭から末尾までのビット列がレジスタＲ２に格納される。また、対象文字列を表すビット列のうちビット列ｂ２の次の８バイト分のビット列がない場合は、対象文字列を表すビット列のうちビット列ｂ２の次ビットから末尾までのビット列がレジスタＲ３に格納される。
【００３０】
図１の例では、対象文字列の先頭から８文字の文字列「The(br)quic」を表すビット列ｂ２がレジスタＲ２に格納されている。なお、（ｂｒ）は、ブランクを表す。また、対象文字列の９文字目から８文字の文字列「k(br)brown(br)」を表すビット列ｂ３がレジスタＲ３に格納されている。
【００３１】
また、文字列探索装置１０１は、探索文字列を表すビット列の先頭から８バイト分のビット列ｂ４をレジスタＲ４に格納する。なお、探索文字列を表すビット列の先頭から８バイト分のビット列がない場合は、探索文字列を表すビット列の先頭から末尾までのビット列ｂ４がレジスタＲ４に格納される。
【００３２】
図１の例では、探索文字列の先頭から５文字の文字列「quick」を表すビット列ｂ４がレジスタＲ４に格納されている。また、各レジスタＲに記憶される各ビットの初期値は「０」である。このため、レジスタＲ４の６バイト以降の各ビットの値は「０」となっている。
【００３３】
（２）文字列探索装置１０１は、探索文字列を表すビット列に含まれる１バイト分のビット列ｂ１を、対象文字列を表すビット列に含まれる８バイト分のビット列ｂ２とバイト単位で一括比較する第１比較命令を実行する。具体的には、例えば、文字列探索装置１０１は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ１に格納されたビット列とレジスタＲ２に格納されたビット列とをバイト単位で一括比較する。ＳＩＭＤ  Ｃｏｍｐａｒｅによれば、１回の命令で複数個のデータ同士（８ビットの符号なし整数）を一括比較することができる。
【００３４】
図２の例では、第１の比較命令の比較結果を表すビット列ｂ５がレジスタＲ５に格納されている。具体的には、ビット列ｂ５は、第１の比較命令のバイト単位の比較結果を表す。ここでは、「１」の場合、レジスタＲ１，Ｒ２のバイト単位のデータ同士が一致したことを示し、「０」の場合、レジスタＲ１，Ｒ２のバイト単位のデータ同士が不一致であることを示す。なお、レジスタＲ内の初期値の部分については、例えば、データ同士の比較が行われない、あるいは、比較結果が不一致となる。
【００３５】
ビット列ｂ５によれば、対象文字列を表すビット列における探索文字列の先頭文字を表すビット列ｂ１の出現位置を特定することができる。ここでは、対象文字列を表すビット列の５バイト目に、探索文字列の先頭文字「q」を表すビット列ｂ１があることがわかる。
【００３６】
（３）文字列探索装置１０１は、第１比較命令の比較結果に基づいて、探索文字列を表すビット列のうちビット列ｂ１の次の１バイト分のビット列ｂ６と、ビット列ｂ２のうちビット列ｂ１と一致する箇所の次の１バイト分のビット列ｂ７とを比較する。ここで、ビット列ｂ６は、探索文字列の２文字目の文字「u」を表すビット列である。また、ビット列ｂ７は、対象文字列のうち、探索文字列の先頭文字「q」と一致する５文字目の文字「q」の次の文字「u」を表すビット列である。
【００３７】
すなわち、文字列探索装置１０１は、探索文字列を表すビット列の先頭バイトの次のバイトも対象文字列を表すビット列にヒットしているか否かを確認する。図１の例では、ビット列ｂ６「０１１１０１０１」と、ビット列ｂ７「０１１１０１０１」とが一致する。これにより、探索文字列の先頭文字の次の文字も対象文字列にヒットしていることがわかる。
【００３８】
（４）文字列探索装置１０１は、ビット列ｂ６とビット列ｂ７とが一致する場合に、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成するビット操作命令を実行する。ここで、ビット操作命令とは、例えば、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒである。
【００３９】
Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒは、２つのレジスタに対して「Ｓｈｉｆｔ、Ｍａｓｋ、Ｏｒ」を１つの命令で実行するものである。Ｓｈｉｆｔは、ビット列を左または右にずらす（シフト）操作である。Ｍａｓｋは、あるビットをオン（１）にしたりオフ（０）にしたりする操作である。Ｏｒは、２つの同じ長さのビット列に対して、同じ位置のビットごとに論理和（Ｏｒ）をとって同じ長さのビット列を出力する操作である。
【００４０】
具体的には、例えば、まず、文字列探索装置１０１は、ビット列ｂ１と一致する箇所が先頭にくるようにレジスタＲ２を左シフトする。より具体的には、例えば、文字列探索装置１０１は、第１の比較命令の比較結果を表すビット列ｂ５の先頭から「１」が出現するまでに「０」が出現した数分、レジスタＲ２を左シフトする。図２の例では、レジスタＲ２が４バイト左シフトされている。そして、文字列探索装置１０１は、レジスタＲ２のシフト元のビット（空いたバイト）を「０」でマスクする。図２の例では、レジスタＲ２の右側４バイトのビット列が「０」でマスクされている。
【００４１】
また、文字列探索装置１０１は、レジスタサイズ（８バイト）から、ビット列ｂ５の先頭から「１」が出現するまでに「０」が出現した数分引いた値で、レジスタＲ３を右シフトする。図２の例では、レジスタＲ３が４バイト右シフトされている。そして、文字列探索装置１０１は、レジスタＲ３のシフト元のビット（空いたバイト）を「０」でマスクする。図２の例では、レジスタＲ３の左側４バイトのビット列が「０」でマスクされている。
【００４２】
そして、文字列探索装置１０１は、レジスタＲ２のビット列とレジスタＲ３のビット列とをＯｒ命令で結合したビット列ｂ８をレジスタＲ６に格納する。これにより、対象文字列を表すビット列のうち、探索文字列の先頭文字と一致する「q」から始まる８バイトのビット列ｂ８を生成することができる。
【００４３】
（５）文字列探索装置１０１は、生成したビット列ｂ８と、探索文字列を表すビット列のうち先頭から８バイト分のビット列ｂ４とをバイト単位で一括比較する第２比較命令を実行する。具体的には、例えば、文字列探索装置１０１は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ６に格納されたビット列ｂ８と、レジスタＲ４に格納されたビット列ｂ４とを１バイト単位で一括比較する。
【００４４】
図２の例では、第２の比較命令の比較結果を表すビット列ｂ９がレジスタＲ７に格納されている。具体的には、ビット列ｂ９は、第２の比較命令のバイト単位の比較結果を表す。ここでは、「１」の場合、レジスタＲ４，Ｒ６のバイト単位のデータ同士が一致したことを示し、「０」の場合、レジスタＲ４，Ｒ６のバイト単位のデータ同士が不一致であることを示す。
【００４５】
（６）文字列探索装置１０１は、第２比較命令の比較結果に基づいて、対象文字列に探索文字列が含まれるか否かを判断する。図２の例では、ビット列ｂ９の先頭から「１」が５個以上続いており、比較して一致した文字数が５文字以上連続していることを示している。また、探索文字列は５文字である。この場合、文字列探索装置１０１は、対象文字列に探索文字列が含まれると判断する。
【００４６】
このように、文字列探索装置１０１によれば、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）を用いて一次スクリーニングを高速に行って、特定のビット操作命令（例えば、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒ）および特定の比較命令を用いた文字列の詳細探索を効率的に行うことができる。
【００４７】
これにより、無駄な詳細探索を抑制して文字列探索にかかる処理時間の短縮化を図ることができる。具体的には、例えば、シングルバイト文字の場合は、偶然先頭文字のみが一致したものに対して、Ｓｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。また、例えば、マルチバイト文字の場合は、先頭文字さえも一致しない候補に対して、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。
【００４８】
（システム３００のシステム構成例）
次に、実施の形態にかかるシステム３００のシステム構成例について説明する。ここでは、図１に示した文字列探索装置１０１をシステム３００内のデータベースサーバ３０１に適用した場合を例に挙げて説明する。
【００４９】
図３は、システム３００のシステム構成例を示す説明図である。図３において、システム３００は、データベースサーバ３０１と、クライアント装置３０２と、を含む。システム３００において、データベースサーバ３０１およびクライアント装置３０２は、有線または無線のネットワーク３１０を介して接続される。ネットワーク３１０は、例えば、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、移動体通信網、インターネットなどである。
【００５０】
データベースサーバ３０１は、データベース３２０およびログＤＢ（データベース）３３０にアクセス可能なコンピュータである。データベース３２０は、複数のアプリケーションやユーザによって共有されるデータを記憶する。ログＤＢ３３０は、テンポラリログやアーカイブログを記録する。テンポラリログは、データベース３２０の更新履歴を示すログである。アーカイブログは、データベース３２０を復旧する際に使用されるログである。
【００５１】
データベースサーバ３０１は、クライアント装置３０２からデータの検索要求を受信すると、データベース３２０からデータをメモリ（例えば、後述の図４に示すメモリ４０２）に読み込む。そして、データベースサーバ３０１は、メモリに読み込まれたデータに対して検索を行い、その検索結果をクライアント装置３０２に送信する。
【００５２】
より具体的には、例えば、データベースサーバ３０１は、不図示の受付部、データ操作部、レコード操作部、バッファ管理部、トランザクション管理部、更新管理部、ログ管理部等を有する。受付部は、クライアント装置３０２からのデータの検索要求を受け付ける。データの検索要求は、例えば、データベース３２０に対するＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）操作である。
【００５３】
データ操作部は、アクセス手順を作成し、トランザクション管理部、レコード操作部にデータアクセスを依頼する。レコード操作部は、レコードと呼ばれるデータの集まりの検索・更新を行う。なお、レコード操作部は、例えば、後述の図５に示すデータベースサーバ３０１の機能部に相当する。
【００５４】
バッファ管理部は、データベースアクセスのメモリ上で管理するバッファアクセスを制御する。トランザクション管理部／更新管理部は、データベース３２０の変更の有効、無効の制御を行う。ログ管理部は、テンポラリログファイル、アーカイブログファイルのＩ／Ｏを管理する。
【００５５】
クライアント装置３０２は、システム３００のユーザが使用するコンピュータである。具体的には、例えば、クライアント装置３０２は、ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）、ノートＰＣ、スマートフォン、携帯電話機、タブレット型ＰＣなどである。
【００５６】
（データベースサーバ３０１のハードウェア構成例）
図４は、データベースサーバ３０１のハードウェア構成例を示すブロック図である。図４において、データベースサーバ３０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）４０１と、メモリ４０２と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）４０３と、磁気ディスクドライブ４０４と、磁気ディスク４０５と、を有する。また、各構成部は、バス４００によってそれぞれ接続される。
【００５７】
ここで、ＣＰＵ４０１は、データベースサーバ３０１の全体の制御を司る。メモリ４０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）およびフラッシュＲＯＭなどを有する。具体的には、例えば、フラッシュＲＯＭやＲＯＭが各種プログラムを記憶し、ＲＡＭがＣＰＵ４０１のワークエリアとして使用される。メモリ４０２に記憶されるプログラムは、ＣＰＵ４０１にロードされることで、コーディングされている処理をＣＰＵ４０１に実行させる。
【００５８】
Ｉ／Ｆ４０３は、通信回線を通じてネットワーク３１０に接続され、ネットワーク３１０を介して他のコンピュータ（例えば、図３に示したクライアント装置３０２）に接続される。そして、Ｉ／Ｆ４０３は、ネットワーク３１０と内部のインターフェースを司り、他のコンピュータからのデータの入出力を制御する。Ｉ／Ｆ４０３には、例えば、モデムやＬＡＮアダプタなどを採用することができる。
【００５９】
磁気ディスクドライブ４０４は、ＣＰＵ４０１の制御にしたがって磁気ディスク４０５に対するデータのリード／ライトを制御する。磁気ディスク４０５は、磁気ディスクドライブ４０４の制御で書き込まれたデータを記憶する。
【００６０】
なお、データベースサーバ３０１は、上述した構成部のほか、例えば、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、キーボード、マウス、ディスプレイなどを有することにしてもよい。また、図３に示したクライアント装置３０２についても、上述したデータベースサーバ３０１と同様のハードウェア構成例により実現することができる。
【００６１】
（データベースサーバ３０１の機能的構成例）
図５は、データベースサーバ３０１の機能的構成例を示すブロック図である。図５において、データベースサーバ３０１は、取得部５０１と、作成部５０２と、第１の比較部５０３と、第２の比較部５０４と、生成部５０５と、第３の比較部５０６と、判断部５０７と、出力部５０８と、を含む構成である。各機能部は、具体的には、例えば、図４に示したメモリ４０２、磁気ディスク４０５などの記憶装置に記憶されたプログラムをＣＰＵ４０１に実行させることにより、または、Ｉ／Ｆ４０３により、その機能を実現する。また、各機能部は、例えば、ハードウェアにより実現されてもよい。具体的には、例えば、各機能部は、論理積回路であるＡＮＤ、否定論理回路であるＩＮＶＥＲＴＥＲ、論理和回路であるＯＲ、論理和否定回路であるＮＯＲや、ラッチ回路であるＦＦ（Ｆｌｉｐ  Ｆｌｏｐ）などの素子によって形成されてもよい。各機能部の処理結果は、例えば、メモリ４０２、磁気ディスク４０５などの記憶装置に記憶される。
【００６２】
取得部５０１は、探索文字列を表すビット列を取得する機能を有する。具体的には、例えば、取得部５０１は、クライアント装置３０２からのデータの検索要求から、探索文字列を表すビット列を取得する。また、取得部５０１は、例えば、不図示のキーボードやマウスを用いたユーザの操作入力により、探索文字列を表すビット列を取得することにしてもよい。
【００６３】
また、取得部５０１は、対象文字列を表すビット列を取得する機能を有する。具体的には、例えば、取得部５０１は、データベース３２０から対象文字列を表すビット列を取得する。より具体的には、例えば、取得部５０１は、データベース３２０からメモリ４０２上のデータベースバッファ（不図示）に読み込まれたデータから、対象文字列を表すビット列を取得する。
【００６４】
作成部５０２は、探索文字列を表すビット列に含まれる１バイト分（第１ビット長ｌ１に相当）のビット列ｂ１をレジスタＲに８バイト分（第２ビット長ｌ２に相当）格納する機能を有する。具体的には、例えば、作成部５０２は、探索文字列を表すビット列の先頭（または、末尾）から１バイト分のビット列ｂ１をレジスタＲ１に８バイト分格納する。
【００６５】
また、作成部５０２は、対象文字列を表すビット列に含まれる８バイト分のビット列ｂ２，ｂ３をそれぞれ異なるレジスタＲに格納する機能を有する。ビット列ｂ２，ｂ３は、対象文字列を表すビット列に含まれる連続するビット列である。具体的には、例えば、作成部５０２は、対象文字列を表すビット列の先頭から８バイト分のビット列ｂ２をレジスタＲ２に格納する。また、作成部５０２は、例えば、対象文字列を表すビット列のうちビット列ｂ２の次の８バイト分のビット列ｂ３をレジスタＲ３に格納する。
【００６６】
また、作成部５０２は、探索文字列を表すビット列に含まれる８バイト分のビット列ｂ４をレジスタＲに格納する機能を有する。ビット列ｂ４の先頭１バイトは、ビット列ｂ１に対応する。具体的には、例えば、作成部５０２は、探索文字列を表すビット列の先頭から８バイト分のビット列ｂ４をレジスタＲ４に格納する。
【００６７】
第１の比較部５０３は、探索文字列を表すビット列に含まれる１バイト分のビット列ｂ１を、対象文字列を表すビット列に含まれる８バイト分のビット列ｂ２とバイト単位で一括比較する機能を有する。具体的には、例えば、第１の比較部５０３は、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）を実行することにより、レジスタＲ１のビット列（８バイト分のビット列ｂ１）とレジスタＲ２のビット列ｂ２とをバイト単位で一括比較する。
【００６８】
第１の比較部５０３の比較結果は、例えば、レジスタＲ５に記憶される。具体的には、例えば、第１の比較部５０３の比較結果は、レジスタＲ１，Ｒ２間のバイト単位の比較結果を表す１バイトのビット列ｂ５である。ここでは、バイト単位の比較結果が不一致だった場合は「０」が設定され、バイト単位の比較結果が一致の場合は「１」が設定される。
【００６９】
第２の比較部５０４は、探索文字列を表すビット列のうちビット列ｂ１の次の１バイト分のビット列ｂ６と、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所の次の１バイト分のビット列ｂ７とを比較する機能を有する。具体的には、例えば、第２の比較部５０４は、レジスタＲ４に格納されたビット列ｂ４のうちのビット列ｂ１の次の１バイト分のビット列ｂ６と、レジスタＲ２に格納されたビット列ｂ２のうちのビット列ｂ１と一致する箇所の次の１バイト分のビット列ｂ７とを比較する。これにより、ＳＪＩＳなどの１文字を２バイトで表すマルチバイト文字であっても、第２の比較部５０４の比較結果から、対象文字列に探索文字列の文字（例えば、先頭文字）と一致する文字があるか否かを判断することができる。
【００７０】
なお、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所は、例えば、第１の比較部５０３の比較結果を表すビット列ｂ５から特定することができる。例えば、ビット列ｂ５が「００００１０００」の場合、第２の比較部５０４は、対象文字列を表すビット列に含まれるビット列ｂ２の５バイト目にビット列ｂ１と一致する箇所があることを特定することができる。
【００７１】
また、対象文字列を表すビット列に含まれるビット列ｂ２のうちビット列ｂ１と一致する箇所がない場合がある。この場合、作成部５０２は、例えば、対象文字列を表すビット列のうちのビット列ｂ２の次の８バイト分のビット列を、新たなビット列ｂ２に設定してレジスタＲ２に格納する。また、作成部５０２は、対象文字列を表すビット列のうちの新たなビット列ｂ２の次の８バイト分のビット列を新たなビット列ｂ３に設定してレジスタＲ３に格納する。
【００７２】
なお、作成部５０２は、対象文字列を表すビット列のうちのビット列ｂ３の次の８バイト分のビット列をレジスタＲ２に格納することにしてもよい。この場合、ビット列ｂ１の比較対象は、レジスタＲ３のビット列となる。すなわち、ビット列ｂ１の比較対象を格納するレジスタＲを、レジスタＲ２，Ｒ３間で切り替えることにしてもよい。
【００７３】
生成部５０５は、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成するビット操作命令を実行する機能を有する。具体的には、例えば、生成部５０５は、ビット列ｂ６とビット列ｂ７とが一致する場合に、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒを実行することにより、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成する。
【００７４】
より詳細に説明すると、まず、生成部５０５は、第１の比較部５０３の比較結果に基づいて、レジスタＲ２に格納されたビット列ｂ２を左シフトする。具体的には、例えば、生成部５０５は、第１の比較命令の比較結果を表すビット列ｂ５の先頭から「１」が出現するまでに「０」が出現した数分、レジスタＲ２に格納されたビット列ｂ２を左シフトする。そして、生成部５０５は、レジスタＲ２のシフト元のビット（空いたバイト）を「０」でマスクする。
【００７５】
次に、生成部５０５は、第１の比較部５０３の比較結果に基づいて、レジスタＲ３に格納されたビット列ｂ３を右シフトする。具体的には、例えば、生成部５０５は、レジスタサイズ（８バイト）から、ビット列ｂ５の先頭から「１」が出現するまでに「０」が出現した数分引いた値で、レジスタＲ３に格納されたビット列ｂ３を右シフトする。そして、生成部５０５は、レジスタＲ３のシフト元のビット（空いたバイト）を「０」でマスクする。
【００７６】
次に、生成部５０５は、レジスタＲ２のビット列とレジスタＲ３のビット列とをＯｒ命令で結合したビット列ｂ８をレジスタＲ６に格納する。これにより、対象文字列を表すビット列のうち、ビット列ｂ１と一致する箇所から始まる８バイトのビット列ｂ８を生成することができる。
【００７７】
また、生成部５０５は、ビット列ｂ６とビット列ｂ７とが不一致の場合、ビット操作命令を実行しないことにしてもよい。これにより、例えば、シングルバイト文字においては、偶然先頭文字のみが一致したものに対して、Ｓｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。また、例えば、ＳＪＩＳなどのマルチバイト文字においては、先頭文字さえも一致しない候補に対して、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。
【００７８】
第３の比較部５０６は、生成部５０５によって生成されたビット列ｂ８と、探索文字列を表すビット列のうちビット列ｂ１から８バイト分のビット列ｂ４とをバイト単位で一括比較する機能を有する。具体的には、例えば、第３の比較部５０６は、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）を実行することにより、レジスタＲ６のビット列ｂ８とレジスタＲ４のビット列ｂ４とをバイト単位で一括比較する。
【００７９】
第３の比較部５０６の比較結果は、例えば、レジスタＲ７に記憶される。具体的には、例えば、第３の比較部５０６の比較結果は、レジスタＲ４，Ｒ６間のバイト単位の比較結果を表す１バイトのビット列ｂ９である。ここでは、バイト単位の比較結果が不一致だった場合は「０」が設定され、バイト単位の比較結果が一致の場合は「１」が設定される。
【００８０】
また、第２の比較部５０４は、探索文字列および対象文字列がマルチバイト文字の場合、対象文字列を表すビット列に含まれるビット列ｂ２のうちビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトか否かを判断することにしてもよい。具体的には、例えば、第２の比較部５０４は、ビット列ｂ１と一致する箇所が、対象文字列のある文字を表すビット列のうちの先頭１バイトのビット列か否かを判断する。
【００８１】
ビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトでない場合は、探索文字列の文字（例えば、先頭文字）と一致しているとはいえない。このため、第２の比較部５０４は、ビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトである場合に、ビット列ｂ６とビット列ｂ７とを比較することにしてもよい。
【００８２】
また、ビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトでない場合、作成部５０２は、例えば、対象文字列を表すビット列のうちのビット列ｂ２の次の８バイト分のビット列を、新たなビット列ｂ２に設定してレジスタＲ２に格納することにしてもよい。また、作成部５０２は、対象文字列を表すビット列のうちの新たなビット列ｂ２の次の８バイト分のビット列を新たなビット列ｂ３に設定してレジスタＲ３に格納することにしてもよい。なお、探索文字列および対象文字列がマルチバイト文字の場合のデータベースサーバ３０１の文字列探索処理例については、図６〜図８を用いて後述する。
【００８３】
また、第２の比較部５０４は、探索文字列を表すビット列のうちビット列ｂ６の次の１バイト分のビット列ｂ１０と、対象文字列を表すビット列のうちビット列ｂ７の次の１バイト分のビット列ｂ１１とを比較することにしてもよい。具体的には、例えば、第２の比較部５０４は、探索文字列および対象文字列が１文字を３バイトで表すマルチバイト文字のときに、ビット列ｂ６とビット列ｂ７とが一致する場合、ビット列ｂ１０とビット列ｂ１１とを比較することにしてもよい。
【００８４】
一例として、対象文字列「デジタルテレビの普及」および探索文字列「テレビ」を、１文字を３バイトで表すＵＴＦ−８で表すと以下のようになる。
【００８５】
［対象文字列］デ（Ｅ３  ８３  ８７）ジ（Ｅ３  ８２  Ｂ８）タ（Ｅ３  ８２  ＢＦ）ル（Ｅ３  ８３  ＡＢ）テ（Ｅ３  ８３  ８６）レ（Ｅ３  ８３  ＡＣ）ビ（Ｅ３  ８３  ９３）の（Ｅ３  ８１  ＡＥ）普（Ｅ６  ９９  ＡＥ）及（Ｅ５  ８Ｆ  ８Ａ）
【００８６】
［探索文字列］テ（Ｅ３  ８３  ８６）レ（Ｅ３  ８３  ＡＣ）ビ（Ｅ３  ８３  ９３）
【００８７】
この例では、対象文字列を表すビット列のうち、探索文字列の先頭文字「テ」の２バイト目まで一致する部分が多くなっている。このような場合に、対象文字列を８バイトの文字列として加工し、ＳＩＭＤ命令により８バイトでの比較を実施すると、文字列探索にかかる処理時間の増大を招く恐れがある。
【００８８】
このため、第２の比較部５０４は、文字コードがＵＴＦ−８などの場合、さらに、ビット列ｂ６の次の１バイト分のビット列ｂ１０と、ビット列ｂ７の次の１バイト分のビット列ｂ１１とを比較する。これにより、ＵＴＦ−８などの１文字を３バイトで表すマルチバイト文字であっても、対象文字列に探索文字列の文字（例えば、先頭文字）と一致する文字があるか否かを判断することができる。
【００８９】
また、生成部５０５は、ビット列ｂ１０とビット列ｂ１１とが一致する場合に、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成するビット操作命令を実行することにしてもよい。すなわち、生成部５０５は、文字コードがＵＴＦ−８などのときは、ビット列ｂ１０とビット列ｂ１１とが一致する場合にビット操作命令を実行することにしてもよい。
【００９０】
これにより、ＵＴＦ−８などのマルチバイト文字においては、先頭文字さえも一致しない候補に対して、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。また、例えば、シングルバイト文字においても、ビット列ｂ１０とビット列ｂ１１とが一致する場合にビット操作命令を実行することで、偶然先頭２文字のみが一致したものに対して、Ｓｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。
【００９１】
判断部５０７は、第３の比較部５０６の比較結果に基づいて、対象文字列に探索文字列が含まれるか否かを判断する機能を有する。具体的には、例えば、判断部５０７は、レジスタＲ７に格納されたビット列ｂ９のうち連続する１の数が探索文字列の長さＬ以上の場合に、対象文字列に探索文字列が含まれると判断する。
【００９２】
ここで、レジスタＲ７に格納されたビット列ｂ９のうち連続する１の数は、レジスタＲ６のビット列ｂ８とレジスタＲ４のビット列ｂ４とを比較して連続して一致した数（バイト数）である。以下の説明では、レジスタＲ７に格納されたビット列ｂ９のうち連続する１の数を「比較して一致した数ＣＮ」と表記する場合がある。
【００９３】
また、探索文字列の長さＬは、探索文字列の文字コードに応じて決まる。例えば、１文字を１バイトで表すシングルバイト文字の場合、探索文字列の文字数をｍ文字とすると、探索文字列の長さＬは、「Ｌ＝ｍ」となる。また、１文字を２バイトで表すマルチバイト文字の場合、探索文字列の文字数をｍ文字とすると、探索文字列の長さＬは、「Ｌ＝２ｍ」となる。また、１文字を３バイトで表すマルチバイト文字の場合、探索文字列の文字数をｍ文字とすると、探索文字列の長さＬは、「Ｌ＝３ｍ」となる。
【００９４】
また、判断部５０７は、比較して一致した数ＣＮが探索文字列の長さＬ未満の場合、探索文字列の長さＬが８ｎバイトより大きいか否かを判断することにしてもよい。なお、「８ｎ」の「８」は、ＣＰＵ４０１の処理単位である８バイト（第２ビット長ｌ２に相当）を表す。また、「８ｎ」の「ｎ」は、第３の比較部５０６の比較処理（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）を繰り返したループ数である（ｎ＝１，２，…）。
【００９５】
ここで、探索文字列の長さＬが８ｎバイト以下の場合、判断部５０７は、対象文字列を表すビット列のうち探索文字列を表すビット列と比較していない残余のビット列があるか否かを判断する。そして、探索文字列を表すビット列と比較していない残余のビット列がない場合、判断部５０７は、対象文字列に探索文字列が含まれないと判断する。
【００９６】
一方、探索文字列を表すビット列と比較していない残余のビット列がある場合、作成部５０２は、例えば、対象文字列を表すビット列のうちのビット列ｂ２の次の８バイト分のビット列を、新たなビット列ｂ２に設定してレジスタＲ２に格納する。また、作成部５０２は、例えば、対象文字列を表すビット列のうちの新たなビット列ｂ２の次の８バイト分のビット列を新たなビット列ｂ３に設定してレジスタＲ３に格納する。これにより、対象文字列を表すビット列のうち探索文字列を表すビット列と比較していない残余のビット列を、探索文字列を表すビット列と比較することができる。
【００９７】
また、探索文字列の長さＬが８ｎバイトより大きい場合、第３の比較部５０６は、対象文字列を表すビット列のうちビット列ｂ８の次の８バイト分のビット列と、探索文字列を表すビット列のうちビット列ｂ４の次の８バイト分のビット列とを比較する。すなわち、探索文字列の長さＬが８ｎバイトより大きい場合は、１回の比較処理により探索文字列のすべてを対象文字列と比較できない。このため、第３の比較部５０６は、探索文字列を表すビット列のうち対象文字列を表すビット列と比較していない残余のビット列を、対象文字列を表すビット列と比較する。
【００９８】
具体的には、例えば、第３の比較部５０６は、対象文字列を表すビット列のうちのビット列ｂ８の次の８バイト分のビット列を、新たなビット列ｂ８に設定してレジスタＲ６に格納する。また、第３の比較部５０６は、探索文字列を表すビット列のうちのビット列ｂ４の次の８バイト分のビット列を新たなビット列ｂ４に設定してレジスタＲ４に格納する。
【００９９】
そして、第３の比較部５０６は、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）を実行することにより、レジスタＲ６のビット列ｂ８とレジスタＲ４のビット列ｂ４とをバイト単位で一括比較する。これにより、探索文字列を表すビット列のうち対象文字列を表すビット列と比較していない残余のビット列を、対象文字列を表すビット列と比較することができる。
【０１００】
出力部５０８は、判断部５０７によって判断された判断結果を出力する機能を有する。ここで、判断結果は、対象文字列に探索文字列が含まれるか否かを示す情報である。例えば、対象文字列に探索文字列が含まれる場合、データベースサーバ３０１は、クライアント装置３０２からの検索要求に対する検索結果として、対象文字列を含むデータをクライアント装置３０２に送信する。また、対象文字列に探索文字列が含まれない場合は、例えば、データベースサーバ３０１は、検索要求に対するデータが検索されなかったことを示す検索結果をクライアント装置３０２に送信する。
【０１０１】
（マルチバイト文字の場合の文字列探索処理例）
次に、図６〜図８を用いて、探索文字列および対象文字列がマルチバイト文字の場合のデータベースサーバ３０１の文字列探索処理例について説明する。ここでは、マルチバイト文字の一例として、文字コードがＳＪＩＳの場合を例に挙げて説明する。
【０１０２】
図６〜図８は、文字コードがＳＪＩＳの場合の文字列探索処理例を示す説明図である。図６において、対象文字列は「デジタル−テレビの普及」であり、２２バイトのデータである。また、探索文字列は「テレビ」であり、６バイトのデータである。
【０１０３】
（１）作成部５０２は、探索文字列を表すビット列の先頭から１バイト分のビット列ｂ１をレジスタＲ１に８バイト分格納する。図６の例では、探索文字列の先頭文字「テ」を表す２バイトのビット列のうちの先頭バイトのビット列ｂ１「１０００００１１」がレジスタＲ１に８個格納されている。
【０１０４】
また、作成部５０２は、対象文字列を表すビット列のうち、先頭から８バイト分のビット列ｂ２をレジスタＲ２に格納するとともに、ビット列ｂ２の次の８バイト分のビット列ｂ３をレジスタＲ３に格納する。図６の例では、対象文字列のうち、先頭から４文字の文字列「デジタル」を表すビット列ｂ２がレジスタＲ２に格納され、５文字目から４文字の文字列「−テレビ」を表すビット列ｂ３がレジスタＲ３に格納されている。
【０１０５】
また、作成部５０２は、探索文字列を表すビット列の先頭から８バイト分のビット列ｂ４をレジスタＲ４に格納する。図６の例では、探索文字列の先頭から３文字の文字列「テレビ」を表すビット列ｂ４がレジスタＲ４に格納されている。
【０１０６】
（２）第１の比較部５０３は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ１のビット列（８バイト分のビット列ｂ１）とレジスタＲ２のビット列（ビット列ｂ２）とをバイト単位で一括比較して、比較結果をレジスタＲ５に格納する。図７の例では、第１の比較部５０３の比較結果を表すビット列ｂ５「１０１０１０１０」がレジスタＲ５に格納されている。このビット列ｂ５によれば、１，３，５，７バイト目に“８３（ビット列ｂ１）”があることを特定することができる。
【０１０７】
（３）第２の比較部５０４は、対象文字列を表すビット列に含まれるビット列ｂ２のうちビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトか否かを判断する。具体的には、例えば、第２の比較部５０４は、ビット列ｂ２のうちビット列ｂ１と一致する箇所（１，３，５，７バイト目）が奇数バイト目か否かを判断する。図７の例では、ビット列ｂ１と一致するすべての箇所が先頭バイトとなっている。
【０１０８】
次に、第２の比較部５０４は、探索文字列を表すビット列のうちビット列ｂ１の次の１バイト分のビット列ｂ６と、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所の次の１バイト分のビット列ｂ７とを比較する。図６の例では、ビット列ｂ６は「０１１００１０１」である。また、ビット列ｂ７は、ビット列ｂ２の２，４，６，８バイト目のいずれかのビット列であり、いずれのビット列もビット列ｂ６と一致しない。
【０１０９】
この場合、作成部５０２は、対象文字列を表すビット列のうちのビット列ｂ３の次の８バイト分のビット列（ここでは、「ビット列ｂ２’」と表記する）をレジスタＲ２に格納する。
【０１１０】
（４）第１の比較部５０３は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ１のビット列（８バイト分のビット列ｂ１）とレジスタＲ３のビット列ｂ３とをバイト単位で一括比較して、比較結果をレジスタＲ５に格納する。図７の例では、第１の比較部５０３の比較結果を表すビット列ｂ５「００１０１０１０」がレジスタＲ５に格納されている。このビット列ｂ５によれば、３，５，７バイト目に“８３（ビット列ｂ１）”があることを特定することができる。
【０１１１】
（５）第２の比較部５０４は、レジスタＲ３のビット列ｂ３のうちビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトか否かを判断する。図６の例では、レジスタＲ３のビット列ｂ３のうちビット列ｂ１と一致するすべての箇所が先頭バイトとなっている。
【０１１２】
次に、第２の比較部５０４は、探索文字列を表すビット列のうちビット列ｂ１の次の１バイト分のビット列ｂ６と、レジスタＲ３のビット列ｂ３のうちビット列ｂ１と一致する箇所の次の１バイト分のビット列ｂ７とを比較する。図６の例では、ビット列ｂ７は、レジスタＲ３のビット列ｂ３の４，６，８バイト目のいずれかのビット列であり、４バイト目のビット列がビット列ｂ６と一致する。
【０１１３】
（６）生成部５０５は、レジスタＲ２，Ｒ３に対して、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒを実行することにより、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成して、レジスタＲ６に格納する。図８の例では、対象文字列を表すビット列のうち、ビット列ｂ１と一致する箇所から始まる８バイトのビット列ｂ８が生成されている。
【０１１４】
（７）第３の比較部５０６は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ６のビット列（ビット列ｂ８）と、レジスタＲ４のビット列（ビット列ｂ４）とを１バイト単位で一括比較して、比較結果をレジスタＲ７に格納する。図８の例では、第３の比較部５０６の比較結果を表すビット列ｂ９「１１１１１１００」がレジスタＲ７に格納されている。
【０１１５】
（８）判断部５０７は、レジスタＲ７のビット列ｂ９のうち連続する１の数が探索文字列の長さＬ以上の場合に、対象文字列に探索文字列が含まれると判断する。ここでは、探索文字列の長さＬは、「６」である。また、ビット列ｂ９のうち連続する１の数は、「６」である。このため、判断部５０７は、対象文字列に探索文字列が含まれると判断する。
【０１１６】
このように、データベースサーバ３０１によれば、ＳＪＩＳなどのマルチバイト文字において、先頭文字が一致する候補に対して、Ｓｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行って、詳細探索を行うことができる。
【０１１７】
（データベースサーバ３０１の文字列探索処理手順）
次に、データベースサーバ３０１の文字列探索処理手順について説明する。ここでは、探索文字列および対象文字列がマルチバイト文字の場合を例に挙げて説明する。
【０１１８】
図９および図１０は、データベースサーバ３０１の文字列探索処理手順の一例を示すフローチャートである。図９のフローチャートにおいて、まず、データベースサーバ３０１は、探索文字列を表すビット列の先頭１バイトのビット列をレジスタＲ１に８バイト分格納する（ステップＳ９０１）。
【０１１９】
次に、データベースサーバ３０１は、対象文字列を表すビット列のうちの未処理のビット列の先頭から８バイト分のビット列をレジスタＲ２に格納する（ステップＳ９０２）。なお、未処理のビット列とは、対象文字列を表すビット列のうち、レジスタＲ１のビット列と比較していない残余のビット列である。
【０１２０】
次に、データベースサーバ３０１は、対象文字列を表すビット列のうちのレジスタＲ２のビット列の次の８バイト分のビット列をレジスタＲ３に格納する（ステップＳ９０３）。次に、データベースサーバ３０１は、探索文字列を表すビット列の先頭から８バイト分のビット列をレジスタＲ４に格納する（ステップＳ９０４）。
【０１２１】
そして、データベースサーバ３０１は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ１のビット列とレジスタＲ２のビット列とをバイト単位で一括比較して、比較結果をレジスタＲ５に格納する（ステップＳ９０５）。次に、データベースサーバ３０１は、比較結果に基づいて、レジスタＲ２のビット列のうち、探索文字列の先頭１バイトのビット列と一致する箇所があるか否かを判断する（ステップＳ９０６）。
【０１２２】
ここで、探索文字列の先頭１バイトのビット列と一致する箇所がある場合（ステップＳ９０６：Ｙｅｓ）、データベースサーバ３０１は、レジスタＲ２のビット列のうちの探索文字列の先頭１バイトのビット列と一致する箇所がマルチバイト文字の先頭バイトか否かを判断する（ステップＳ９０７）。
【０１２３】
ここで、マルチバイト文字の先頭バイトの場合（ステップＳ９０７：Ｙｅｓ）、データベースサーバ３０１は、探索文字列を表すビット列のうち先頭１バイトのビット列の次の１バイト分のビット列と、対象文字列を表すビット列のうちの探索文字列の先頭１バイトのビット列と一致する箇所の次の１バイト分のビット列とが一致するか否かを判断する（ステップＳ９０８）。
【０１２４】
ここで、ビット列が一致する場合（ステップＳ９０８：Ｙｅｓ）、データベースサーバ３０１は、レジスタＲ２，Ｒ３に対して、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒを実行することにより、対象文字列を表すビット列のうちの探索文字列の先頭１バイトのビット列と一致する箇所から８バイト分のビット列を生成して、レジスタＲ６に格納する（ステップＳ９０９）。
【０１２５】
そして、データベースサーバ３０１は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ６のビット列とレジスタＲ４のビット列とをバイト単位で一括比較して、比較結果をレジスタＲ７に格納し（ステップＳ９１０）、図１０に示すステップＳ１００１に移行する。
【０１２６】
また、ステップＳ９０７において、マルチバイト文字の先頭バイトではない場合（ステップＳ９０７：Ｎｏ）、データベースサーバ３０１は、レジスタＲ５に格納された比較結果を表すビット列のうちの最初の「１」を「０」にして（ステップＳ９１１）、ステップＳ９０６に戻る。また、ステップＳ９０８において、ビット列が不一致の場合（ステップＳ９０８：Ｎｏ）、データベースサーバ３０１は、ステップＳ９１１に移行する。
【０１２７】
また、ステップＳ９０６において、探索文字列の先頭１バイトのビット列と一致する箇所がない場合（ステップＳ９０６：Ｎｏ）、データベースサーバ３０１は、対象文字列を表すビット列のうち未処理のビット列があるか否かを判断する（ステップＳ９１２）。ここで、未処理のビット列がある場合（ステップＳ９１２：Ｙｅｓ）、データベースサーバ３０１は、ステップＳ９０２に戻る。
【０１２８】
一方、未処理のビット列がない場合（ステップＳ９１２：Ｎｏ）、データベースサーバ３０１は、対象文字列に探索文字列が含まれないと判断して（ステップＳ９１３）、本フローチャートによる一連の処理を終了する。
【０１２９】
図１０のフローチャートにおいて、まず、データベースサーバ３０１は、レジスタＲ７に格納された比較結果を表すビット列に基づいて、比較して一致した数ＣＮが探索文字列の長さＬ以上か否かを判断する（ステップＳ１００１）。ここで、比較して一致した数ＣＮが探索文字列の長さＬ以上の場合（ステップＳ１００１：Ｙｅｓ）、データベースサーバ３０１は、対象文字列に探索文字列が含まれると判断して（ステップＳ１００２）、本フローチャートによる一連の処理を終了する。
【０１３０】
一方、比較して一致した数ＣＮが探索文字列の長さＬ未満の場合（ステップＳ１００１：Ｎｏ）、データベースサーバ３０１は、探索文字列の長さＬが８ｎバイトより大きいか否かを判断する（ステップＳ１００３）。なお、「ｎ」の初期値は「ｎ＝１」である。
【０１３１】
ここで、探索文字列の長さＬが８ｎバイトより大きい場合（ステップＳ１００３：Ｙｅｓ）、データベースサーバ３０１は、対象文字列を表すビット列のうちのレジスタＲ６のビット列の次の８バイト分のビット列をレジスタＲ６に格納する（ステップＳ１００４）。次に、データベースサーバ３０１は、探索文字列を表すビット列のうちのレジスタＲ４のビット列の次の８バイト分のビット列をレジスタＲ４に格納する（ステップＳ１００５）。
【０１３２】
そして、データベースサーバ３０１は、ＳＩＭＤ  Ｃｏｍｐａｒｅを実行することにより、レジスタＲ６のビット列とレジスタＲ４のビット列とをバイト単位で一括比較して、比較結果をレジスタＲ７に格納する（ステップＳ１００６）。ただし、比較結果は、例えば、レジスタＲ７の未使用部分の先頭から順次格納される。
【０１３３】
次に、データベースサーバ３０１は、「ｎ」をインクリメントして（ステップＳ１００７）、ステップＳ１００１に戻る。また、ステップＳ１００３において、探索文字列の長さＬが８ｎバイト以下の場合（ステップＳ１００３：Ｎｏ）、データベースサーバ３０１は、「ｎ」を「ｎ＝１」で初期化する（ステップＳ１００８）。
【０１３４】
そして、データベースサーバ３０１は、レジスタＲ５に格納された比較結果を表すビット列のうちの最初の「１」を「０」にして（ステップＳ１００９）、図９に示したステップＳ９０６に戻る。
【０１３５】
これにより、ＳＩＭＤ  Ｃｏｍｐａｒｅを用いて一次スクリーニングを行った後で、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒを用いた詳細探索を行うことができ、対象文字列に探索文字列が含まれるか否かを効率的に判断することができる。なお、１文字を３バイトで表すマルチバイト文字の場合は、図９に示したステップＳ９０８において、さらに、次の１バイト分のビット列の一致判定を行うことにしてもよい。
【０１３６】
以上説明したように、実施の形態にかかるデータベースサーバ３０１によれば、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）により、探索文字列の先頭から１バイト分のビット列ｂ１を、対象文字列を表すビット列に含まれる８バイト分（例えば、先頭から８バイト分）のビット列ｂ２とバイト単位で一括比較することができる。これにより、ビット列同士を高速に比較して、対象文字列を表すビット列から探索文字列の先頭バイトの出現位置を検出することができる。例えば、ＡＳＣＩＩなどの１文字を１バイトで表すシングルバイト文字の場合、探索文字列の先頭文字が対象文字列にヒットしたか否かを判断することができる。
【０１３７】
また、データベースサーバ３０１によれば、探索文字列のビット列ｂ１の次の１バイト分のビット列ｂ６と、対象文字列のビット列ｂ１と一致する箇所の次の１バイト分のビット列ｂ７とを比較することができる。これにより、ＳＪＩＳなどの１文字を２バイトで表すマルチバイト文字であっても、探索文字列の先頭文字が対象文字列にヒットしたか否かを判断することができる。また、シングルバイト文字であれば、探索文字列の先頭文字の次の文字も対象文字列にヒットしているか否かを判断することができる。
【０１３８】
また、データベースサーバ３０１によれば、ビット列ｂ６とビット列ｂ７とが一致する場合に、特定のビット操作命令（例えば、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒ）により、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成することができる。また、データベースサーバ３０１によれば、特定の比較命令（例えば、ＳＩＭＤ  Ｃｏｍｐａｒｅ）により、生成したビット列ｂ８と、探索文字列の先頭から８バイト分のビット列ｂ４とをバイト単位で一括比較することができる。
【０１３９】
これにより、ビット列同士を高速に比較して、対象文字列を表すビット列から、探索文字列の先頭から８バイト分のビット列を検出することができる。また、ビット列ｂ６とビット列ｂ７とが不一致の場合は特定のビット操作命令が実行されないため、文字列探索にかかる処理時間の増大を抑制することができる。例えば、シングルバイト文字の場合は、偶然先頭文字のみが一致したものに対して、Ｓｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。また、例えば、マルチバイト文字の場合は、先頭文字さえも一致しない候補に対して、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。
【０１４０】
また、データベースサーバ３０１によれば、ビット列ｂ８とビット列ｂ４とをバイト単位で比較した比較結果に基づいて、対象文字列に探索文字列が含まれるか否かを判断することができる。例えば、データベースサーバ３０１は、ビット列ｂ８とビット列ｂ４とを比較した比較結果を表すビット列ｂ９のうち連続する１の数が探索文字列の長さＬ以上の場合に、対象文字列に探索文字列が含まれると判断することができる。
【０１４１】
これにより、探索文字列を含む対象文字列を検索することができる。この結果、例えば、データベースサーバ３０１は、クライアント装置３０２からのデータの検索要求に対する検索結果として、対象文字列を含むデータをクライアント装置３０２に送信することができる。
【０１４２】
また、データベースサーバ３０１によれば、マルチバイト文字の場合は、対象文字列を表すビット列に含まれるビット列ｂ２のうちのビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトか否かを判断することができる。そして、データベースサーバ３０１によれば、ビット列ｂ２のうちのビット列ｂ１と一致する箇所がマルチバイト文字の先頭バイトである場合に、ビット列ｂ６とビット列ｂ７とを比較することができる。これにより、マルチバイト文字においては、先頭バイトさえも一致しない候補に対して、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。
【０１４３】
また、データベースサーバ３０１によれば、１文字を３バイトで表すマルチバイト文字の場合は、探索文字列のビット列ｂ６の次の１バイト分のビット列ｂ１０と、対象文字列のビット列ｂ７の次の１バイト分のビット列ｂ１１とを比較することができる。これにより、ＵＴＦ−８などの１文字を３バイトで表すマルチバイト文字であっても、対象文字列に探索文字列の文字（例えば、先頭文字）と一致する文字があるか否かを判断することができる。
【０１４４】
また、データベースサーバ３０１によれば、ビット列ｂ１０とビット列ｂ１１とが一致する場合に、特定のビット操作命令により、対象文字列を表すビット列のうちビット列ｂ１と一致する箇所から８バイト分のビット列ｂ８を生成することができる。これにより、ＵＴＦ−８などのマルチバイト文字において、先頭文字さえも一致しない候補に対して、個別にＳｈｉｆｔ−Ｍａｓｋ−ＯｒとＳＩＭＤ  Ｃｏｍｐａｒｅを行う無駄な処理を削減することができる。
【０１４５】
これらのことから、データベースサーバ３０１によれば、ＳＩＭＤ  Ｃｏｍｐａｒｅ等の特定の比較命令を用いて一次スクリーニングを高速に行って、Ｓｈｉｆｔ−Ｍａｓｋ−Ｏｒ等の特定のビット操作命令を用いた詳細探索を効率的に行うことができる。これにより、文字列探索にかかる処理時間の短縮化を図ることができ、データ検索にかかる処理性能を向上させることができる。例えば、複数バイト単位Ｎ（例えば、８バイト）で文字列比較を行うことで、バイト単位で文字列比較を行う場合に比べて、検索コストを１／Ｎ程度に削減することができる。
【０１４６】
なお、本実施の形態で説明した文字列探索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本文字列探索プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また、本文字列探索プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１４７】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１４８】
（付記１）コンピュータが、
探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１比較と、
前記第１比較の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列との比較と、
前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列の生成と、
生成した前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第２比較と、
前記第２比較の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かの判断と、
を実行することを特徴とする文字列探索方法。
【０１４９】
（付記２）前記コンピュータが、
前記探索文字列および前記対象文字列が特定の文字コードのときは、前記第３ビット列と前記第４ビット列とが一致する場合、前記探索文字ビット列のうち前記第３ビット列の次の前記第１ビット長のビット列と、前記対象文字ビット列のうち前記第４ビット列の次の前記第１ビット長のビット列との比較を実行し、
前記第３ビット列の次のビット列と前記第４ビット列の次のビット列とが一致する場合に、前記第５ビット列の生成を実行することを特徴とする付記１に記載の文字列探索方法。
【０１５０】
（付記３）前記第１ビット長は、１バイトであり、
前記第２ビット長は、ビット列同士をバイト単位で一括比較する比較命令の処理単位を表すビット長であることを特徴とする付記１または２に記載の文字列探索方法。
【０１５１】
（付記４）前記コンピュータが、
前記探索文字列および前記対象文字列がマルチバイト文字の場合、前記第１比較の比較結果に基づいて、前記第２ビット列のうち前記第１ビット列と一致する箇所がマルチバイト文字の先頭バイトか否かの判断を実行し、
前記第１ビット列と一致する箇所がマルチバイト文字の先頭バイトである場合に、前記第３ビット列と前記第４ビット列との比較を実行することを特徴とする付記３に記載の文字列探索方法。
【０１５２】
（付記５）前記コンピュータが、
前記第１ビット列を前記第２ビット長分第１レジスタに格納し、
前記第２ビット列を第２レジスタに格納する、処理を実行し、
前記第１レジスタに格納されたビット列と、前記第２レジスタに格納されたビット列とを前記第１ビット長単位で比較する第１比較を実行することを特徴とする付記１〜４のいずれか一つに記載の文字列探索方法。
【０１５３】
（付記６）前記コンピュータが、
前記対象文字ビット列のうち前記第２ビット列の次の前記第２ビット長のビット列を第３レジスタに格納する処理を実行し、
前記第１比較の比較結果に基づいて、前記第２レジスタに格納されたビット列を左シフトするとともにシフト元のビットをマスクし、前記第３レジスタに格納されたビット列を右シフトするとともにシフト元のビットをマスクし、前記第２レジスタに格納されたビット列と前記第３レジスタに格納されたビット列との論理和をとることにより、前記第５ビット列の生成を実行することを特徴とする付記５に記載の文字列探索方法。
【０１５４】
（付記７）前記コンピュータが、
前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長のビット列を第４レジスタに格納し、
生成した前記第５ビット列を第５レジスタに格納する、処理を実行し、
前記第４レジスタに格納されたビット列と、前記第５レジスタに格納されたビット列とを前記第１ビット長単位で比較する第２比較を実行することを特徴とする付記６に記載の文字列探索方法。
【０１５５】
（付記８）前記コンピュータが、
前記第２ビット列のうち前記第１ビット列と一致する箇所がない場合、前記対象文字ビット列のうちの前記第２ビット列の次の前記第２ビット長のビット列を、前記第２ビット列として前記第２レジスタに格納する処理を実行することを特徴とする付記５〜７のいずれか一つに記載の文字列探索方法。
【０１５６】
（付記９）探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１の比較部と、
前記第１の比較部の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列とを比較する第２の比較部と、
前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列を生成する生成部と、
前記生成部によって生成された前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第３の比較部と、
前記第３の比較部の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かを判断する判断部と、
を有することを特徴とする文字列探索装置。
【０１５７】
（付記１０）コンピュータに、
探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１比較と、
前記第１比較の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列との比較と、
前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列の生成と、
生成した前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第２比較と、
前記第２比較の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かの判断と、
を実行させることを特徴とする文字列探索プログラム。
【０１５８】
（付記１１）コンピュータに、
探索文字列に対応する探索文字ビット列に含まれる第１ビット長の第１ビット列を、対象文字列に対応する対象文字ビット列に含まれる第２ビット長の第２ビット列と前記第１ビット長単位で比較する第１比較と、
前記第１比較の比較結果に基づいて、前記探索文字ビット列のうち前記第１ビット列の次の前記第１ビット長の第３ビット列と、前記第２ビット列のうち前記第１ビット列と一致する箇所の次の前記第１ビット長の第４ビット列との比較と、
前記第３ビット列と前記第４ビット列とが一致する場合に、前記対象文字ビット列のうち前記第１ビット列と一致する箇所から前記第２ビット長の第５ビット列の生成と、
生成した前記第５ビット列と、前記探索文字ビット列のうち前記第１ビット列から前記第２ビット長の第６ビット列とを前記第１ビット長単位で比較する第２比較と、
前記第２比較の比較結果に基づいて、前記対象文字列に前記探索文字列が含まれるか否かの判断と、
を実行させる文字列探索プログラムを記録したことを特徴とする前記コンピュータに読み取り可能な記録媒体。
【符号の説明】
【０１５９】
１０１  文字列探索装置
３００  システム
３０１  データベースサーバ
３０２  クライアント装置
５０１  取得部
５０２  作成部
５０３  第１の比較部
５０４  第２の比較部
５０５  生成部
５０６  第３の比較部
５０７  判断部
５０８  出力部
【図１】
2014235454.tif 000003
【図２】
2014235454.tif 000004
【図３】
2014235454.tif 000005
【図４】
2014235454.tif 000006
【図５】
2014235454.tif 000007
【図６】
2014235454.tif 000008
【図７】
2014235454.tif 000009
【図８】
2014235454.tif 000010
【図９】
2014235454.tif 000011
【図１０】
2014235454.tif 000012