読者です 読者をやめる 読者になる 読者になる

感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

文字列探索の「力まかせ法」について、まとめる。

<スポンサーリンク>

文字列検索では、探しだす文字列を「パターン」と呼び、探索される側の文字列を「テキスト」と呼ぶ。
今回見ていく「力任せ法」というのは、方法論というよりは単なる力技だ。

単純法とも呼ばれるこの方法では、たとえば「ABCDEFG」という文字列(テキスト)の中に、「CDE」という文字列(パターン)があるかを検索する場合、
前から順番にテキストの「A」とパターンの「C」が一致するか?
一致しないから次、
テキストの「B」とパターンの「C」が一致するか?
一致しないから次、テキストの「C」とパターンの「C」が一致するか?
一致するから次のパターン側の2文字目「D」と、テキストの「C」の次の文字が一致するか?・・・

というように、前から順番に力任せで何度も繰り返しテキストの前方に戻りながら(=後退しながら)検索していく。
力任せ法は効率が悪い検索方法と言える。

サンプル

実際にサンプルで見てみよう。

以下が力まかせ検索のロジックを組んだクラスだ。

package sample.search;

public class BfMatcher {
    public int bfMatch(String text, String pattern) {
        int textCursor = 0;
        int patternCursor = 0;

        //textの末尾に達してない&&パターンの末尾に達してない = textの末尾に達するか、patternの末尾に達すると終わり
        while (textCursor != text.length() && patternCursor != pattern.length()) {
            System.out.println("-----------------");
            String match = "+";
            String indexMark = "|";
            String blank = " ";
            String insertBlank = getStringOfIndexLength(textCursor, blank);

            //X番目の文字が一致したら次の文字が一致するか調べる
            System.out.println("patternの文字は:" + pattern.charAt(patternCursor));
            System.out.println("textの文字は:" + text.charAt(textCursor));
            System.out.println("検索対象の文字列の位置は・・・");
            System.out.println(text);
            System.out.print(insertBlank);
            if (text.charAt(textCursor) == pattern.charAt(patternCursor)) {
                System.out.print(match);
                System.out.println(" MATCH!");
                textCursor++;
                patternCursor++;
            } else {
                //textが持ってるカーソルを前に調べた文字の次の文字から検索する
                textCursor = textCursor - patternCursor + 1;
                patternCursor = 0;
                System.out.println(indexMark);
            }
        }
        
        if (patternCursor == pattern.length()) {
            return textCursor - patternCursor;
        }
        
        return -1;
    }
    
    private String getStringOfIndexLength(int index, String str) {
        StringBuffer strBuf = new StringBuffer();
        for(int i=0; i < index; i++) {
            strBuf.append(str);
        }
        
        return strBuf.toString();
    }
}

こちらを使うMainクラスがこちら。

package sample.search;

public class Main {
    public static void main(String[] args) {
        String text = "new members coupon"; //手元に落ちてたカードにあった文字列
        String pattern = "upo"; //この文字列を検索する
        BfMatcher matcher = new BfMatcher();
        int index = matcher.bfMatch(text, pattern);
        
        if (index == -1) {
            System.out.println("テキストの中にパターンは存在しません");
        } else {
            int length = 0;
            for (int i = 0; i < index; i++) {
                length += text.substring(i, i + 1).getBytes().length;
            }
            length += pattern.length();
            System.out.println((index + 1) + "文字目にマッチします!");
            System.out.println("text   : " + text);
            System.out.printf(String.format("pattern: %%%ds\n", length), pattern);
        }
    }
}

実行した結果は、以下のようになる。

-----------------
patternの文字は:u
textの文字は:n
検索対象の文字列の位置は・・・
new members coupon
|
-----------------
patternの文字は:u
textの文字は:e
検索対象の文字列の位置は・・・
new members coupon
 |
-----------------
patternの文字は:u
textの文字は:w
検索対象の文字列の位置は・・・
new members coupon
  |

(省略)

-----------------
textの文字は:o
検索対象の文字列の位置は・・・
new members coupon
                + MATCH!
15文字目にマッチします
text   : new members coupon
pattern:               upo

読んだ本

明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造

Javaでアルゴリズムの勉強をする際の定番。宝箱と並行して読んでる。
アルゴリズムとデザインパターンは、何度も何度も繰り返し色んな本を通じて勉強して、全てのプログラミング言語の一つ上のメタなプログラミング能力として、身に付けていきたい。

感謝のプログラミング

今回で感謝のプログラミングは【691時間目】
10000時間まで、あと【9309時間】