StringSearchを用いた文字列検索のキホン

このページに簡単な解説をまとめたので、本コラムと合わせて参考にしていただけたらと思う。今回は、StringSerachを使って実際に文字列検索を行う方法を解説する。

StringSearchでは、検索に用いる各クラスはすべてcom.eaio.stringsearch.StringSearch抽象クラスの実装であり、一部のメソッドを除いて共通の枠組みで利用できるようになっている。核となる文字列検索のためのメソッドはsearchBytes()、searchChars()、searchString()の3種類で、それぞれ対象文字列およびパターン文字列をbyte配列、char配列、Stringオブジェクトで指定して利用する。各メソッドとも引数の種類に応じて複数に呼び出し方が提供されている。たとえばsearchString()メソッドには以下の6種類がある。

  • searchString(String text, String pattern)
  • searchString(String text, int start, String pattern)
  • searchString(String text, int start, int end, String pattern)
  • searchString(String text, String pattern, Object processed)
  • searchString(String text, int start, String pattern, Object processed)
  • searchString(String text, int start, int end, String pattern, Object processed)

これらのメソッドは戻り値としてマッチした文字のインデックス(ただし、先頭も文字を0文字目とする)を返す。マッチする文字がなかった場合には-1を返す。引数のtextには検索を実施する対象の文字列を、patternにはパターン文字列を、startには検索を始める場所のインデックス、endには検索を終了するインデックスを指定する。processedについては後述する。例として、BoyerMooreHorspoolRaitaクラスを用いて検索を行うプログラムを以下に示す。

リスト1

public class BMHRSearchSample {
    public static void main(String[] args) {
        String text = "こんにちは世界。新世界へようこそ。";
        String pattern = "世界";

        // StringSearchオブジェクトの生成
        StringSearch search = new BoyerMooreHorspoolRaita();
        // 検索の実行
        int x = search.searchString(text, pattern);
        System.out.println(x+1 +  "文字目");
    }
}

このプログラムでは最初に現れる"世界"がマッチするため、「6文字目」というテキストが出力されるはずだ。

前処理を利用した文字列検索

前述の例で、文字列に含まれるすべての"世界"を検出したい場合には、検索開始位置を指定しながら繰り返し検索を実行すればいい。ただし、そのように同じパターン文字列を使って繰り返し検索を実施する場合には、前処理(pre-process)の結果を再利用することでより効率のよい検索を行うことができる。各検索アルゴリズムは、前処理→実際の検索という2段階の手続きで構成されている。前処理の結果はパターン文字列によって決定されるため、パターン文字列が同じであれば、その結果を別の検索にも再利用することができる。

StringSearchの場合、この前処理を行うためのメソッドとしてprocessBytes()、processChars()、processString()がある。これらのメソッドには引数としてパターン文字列を渡す。戻り値はObjectオブジェクトとして返される。通常のsearchXXXX()メソッド呼び出しでは、前処理->検索を一連の手順として実行するが、引数のprocessedの部分にprocessXXXX()メソッドの結果を渡すことで、前処理が省略されて検索のみが実行される。

次のプログラムは、BoyerMooreHorspoolRaitaクラスで前処理を利用して複数回の検索を実施する例を示している。マッチする文字列がなくなるまで(-1が返されるまで)、前回マッチした場所を開始点とした検索を実行する。

リスト2

public class BMHRSearchWithPreprocess {
    public static void main(String[] args) {
        String text = "こんにちは世界。新世界へようこそ。";
        String pattern = "世界";

        // StringSearchオブジェクトの生成
        StringSearch search = new BoyerMooreHorspoolRaita();
        // 前処理の実行
        Object processed = search.processString(pattern);
        // 検索の実行
        int x = -1;
        while ((x = search.searchString(text, x+1, pattern, processed)) != -1) {
            System.out.println(x+1 +  "文字目");
        }
    }
}

このプログラムでは2つある"世界"がそれぞれマッチするので、「6文字目」と「10文字目」というテキストが出力されるはずだ。

ワイルドカードを利用した文字列検索

BNDMWildcardsクラスとShiftOrWildcardsクラスでは、パターン文字列にワイルドカードを含めることができる。ワイルドカードは「何にでもマッチする文字」で、たとえばワイルドカードを表す文字が"?"で、パターン文字列が"H?llo"ならば、"Hello"でも"Hallo"でも"Hollo"でも、"?"の部分がどんな文字であってもマッチするような検索ということになる。

検索のやり方は通常のStringSearchの場合と同様である。次のプログラムは、BNDMWildcardsクラスを利用して検索を行う例を示している。デフォルトでは、ワイルドカードを表す文字は"?"になるので、パターン文字列を"世?"とした場合には"世◯"という文字列はすべてマッチすることになる。

リスト3

public class BNDMSearchWithWildcard {
    public static void main(String[] args) {
        String text = "こんにちは世界。新世紀へようこそ。";
        String pattern = "世?";

        // StringSearchオブジェクトの生成
        BNDMWildcards search = new BNDMWildcards();
        // 前処理の実行
        Object processed = search.processString(pattern);
        // 検索の実行
        int x = -1;
        while ((x = search.searchString(text, x+1, pattern, processed)) != -1) {
            System.out.println(x+1 +  "文字目");
        }
    }
}

この例では"世界"と"世紀"のそれぞれにマッチするため、「6文字目」と「10文字目」というテキストが出力される。

ワイルドカードとして"?"以外の文字を使うこともできる。その場合は、processXXXX()メソッドの第2引数としてワイルドカードとして使用したい文字をchar型で指定する。たとえば"*"を使う場合には次のようにすればよい。

リスト4

String pattern = "世*";
BNDMWildcards search = new BNDMWildcards();
Object processed = search.processString(pattern, '*');

ShiftOrWildcardsクラスも使い方は同様だが、BNDMWildcardsクラスの方が5倍程度高速とのことなので、特に理由が無ければBNDMWildcardsクラスの方を使えばよいだろう。