文字クラスを利用した文字列検索

文字列検索ライブラリの「StringSearch」を利用すれば、Javaプログラムにおいてさまざまなアルゴリズムによる文字列検索を行うことができるようになる。前回ではこのライブラリの基本的な使い方と、ワイルドカードを利用した文字列検索のやり方を解説したので、今回はそれに引き続き、文字クラスを使った検索と、ミスマッチ文字を含んだ検索について紹介したい。

StringSearchでは、ShiftOrClassesクラスを使うことで、パターン文字列に文字クラスを利用して検索を行うことができる。具体的には、次のような記号を使うことでワイルドカードよりもさらに曖昧なパターン文字列を表現することができるようになっている。

  • ? - "任意の文字"を表す。いわゆるワイルドカード
  • [○△□] - "[]内の文字のいずれか"を表す
  • [○-△] - "○から△までの範囲の文字のいずれか"を表す
  • ^○ - "○以外の文字"を表す
  • \○ - エスケープ文字。○が文字クラスであったとしても通常の文字として扱う

たとえば"Java"または"java"の両方の文字を検索したいとする。この場合、パターン文字列を"[jJ]ava"としてShiftOrClassesクラスによる検索を実施すればよい。"[jJ]"は"jかJのいずれかの文字"を表す文字クラスなので、"Java"にも"java"にもマッチするからである。プログラムは次のようになる。

リスト1

public class ShiftOrSearchWithClasses {
    public static void main(String[] args) {
        String text = "Java, java, kava, Kava, sava, ^ava";
        String pattern = "[jJ]ava";

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

このプログラムは、"Java, java, kava, Kava, sava, ^ava"という文字列から、"Java"または"java"を探してその最初の文字の位置を表示するというものである。実行結果としては「1文字目」と「7文字目」が該当する文字として表示されるはずだ。

ではパターン文字列を"[A-Z]ava"とした場合にはどうなるだろうか。"[A-Z]"は"AからZの範囲の文字のいずれか"を表すので、"[A-Zava]は"大文字から始まりavaと続く文字列"を表すことになる。したがって"Java"と"Kava"がマッチするので、出力は「1文字目 13文字目」となる。

同様に、"^sava"とした場合には"s以外から始まる"ものが対象になるので、結果は「1文字目 7文字目 13文字目 19文字目 31文字目」となる。"^[kK]ava"のような使い方もできて、これは"^[kK]"が"[kK]以外の文字"、すなわち"kまたはK以外の文字"を表すので、結果は「1文字目 7文字目 25文字目 31文字目」となる。では"^ava"をマッチさせたい場合にはパターン文字列はどう記述したらいいだろうか。"^"が文字クラスなので、この場合はエスケープ文字を使って"\^ava"と書けばよいことになる。

このように、ShiftOrClassesクラスを利用すれば、正規表現ほどではないにしてもある程度柔軟なパターン文字列を表現することが可能となる。

ミスマッチ文字を含んだ文字列検索

ShiftOrMismatchesクラスは、ミスマッチ文字を含む検索をサポートしたクラスである。たとえばパターン文字列として"mismatch"を指定したとする。このとき、「1文字くらいは違う文字でもいい」というような条件を付け加えたいときはないだろうか。「mizmatch」や「mismotch」なども許容してしまいたい、という場合である。そのような曖昧さをサポートするのがShiftOrMismatchesクラスによる検索だ。

このクラスでは、指定された文字数までのミスマッチを許容した検索を行う。この文字数を「編集距離」と呼ぶ。編集距離は、processXXXX()メソッドの実行時と、searchXXXX()の実行時に、それぞれ最後の引数として指定する。編集距離を2文字としてsearchString()による検索を行うならば、次のような具合になる。

リスト2

ShiftOrMismatches search = new ShiftOrMismatches();
Object processed = search.processString(pattern, 2);
int[] x = search.searchString(text, pattern, processed, 2);

searchXXXX()メソッドはint型の配列を返すが、この第1要素にはマッチした先頭の文字の位置が、第2要素には何文字がミスマッチだったかが格納されている。実際のプログラムの例を以下に示す。

リスト3

public class ShiftOrSearchWithMismatch {
    public static void main(String[] args) {
        String pattern = "Java";
        String text = "Hello KaVa.";
        //String text = "Hello Java.";
        //String text = "Hello java.";
        //String text = "Hello JAVA.";

        // MismatchSearchオブジェクトの生成
        ShiftOrMismatches search = new ShiftOrMismatches();
        // 編集距離を指定した前処理の実行
        Object processed = search.processString(pattern, 2);
        // 検索の実行
        int[] x = search.searchString(text, pattern, processed, 2);
        System.out.println(x[0]+1 + "文字目");
        System.out.println("    " + x[1] + "文字のエラー");
    }
}

このプログラムの場合、パターン文字列は"Java"だが、2文字までのミスマッチを許容しているため、"KaVa"の文字列が検索にマッチする。検索対象のテキストをコメントアウトで示してある形に変えてそれぞれ実行してみると、"Java"や"java"はマッチするが、"JAVA"はマッチしないことを確認できる。"Java"と"JAVA"では編集距離が4文字であるため、条件に合っていないからである。

ShiftOrMismatchesクラスを使う際の注意点としては、パターン文字列の長さが「31/(log2(k+1))」文字まででなければならないという条件がある。kは編集距離であり、k=1の場合は15文字、k=2またはk=3の場合は10文字、k=4またはk=5の場合は7文字となる。あまりミスマッチが多い場合には実用的でないということだ。

JavaのコアAPIだけでも、java.lang.Stringや正規表現を利用して文字列検索を行うことが可能だが、StringSearchを使えばその選択の幅は大きく広がることになる。必要に応じて、使用を検討してみてはいかがだろうか。