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

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

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

文字列探索のKMP法を考えた人すごいと思う。

<スポンサーリンク>

読書メモ

人間を模倣し、徐々に人間に取って代わっていくようなアルゴリズムを作り出せる能力が、これからの百年を支配するスキルだ。
この能力を持つ人が増えれば増えるほど、仕事はなくなり、人生は今までと異なるものになり、産業は生まれ変わることを余儀なくされるだろう。
アルゴリズムが世界を支配する』 34ページより

前の記事では文字列探索の「力まかせ法」を実装してみた。
力まかせ法はクールとは言い難い、本当に文字通り力まかせに検索する強引なプログラムだった。
この力まかせな感じは、モテない男が女の子にひたすらアピールして結局玉砕するような、そんな醜さを感じた。

それに比べて、KMP法は実に優雅な検索方法だ。
これぞイケメンの検索法だと思った。

KMP法はD.E.KnuthとV.R.Prattと、J.H.Morrisがほぼ同時期に考案した。
三人の頭文字を取って、KMP法という。
KMP法はテキストとパターンの重なっている部分をうまく見つけ出して、照合を再会する位置を求め、なるべくパターンの移動を大きくしようとするアルゴリズムのこと。

まず、KMP法で文字列を探索するサンプルはこちら。

package sample.search.kmp;

public class KmpMatch {
    public static void main(String[] args) {
        //String text = "私は死ぬ前にたった一人で好いから、他(ひと)を信用して死にたいと思っている。あなたはそのたった一人になれますか。なってくれますか。";
        //String pattern = "好いから";
        String text = "A man falls in love through his eyes, a woman through her ears";
        String pattern = "eyes";
        int index = kmpMatcher(text, pattern);
        System.out.println(index + "文字目が一致します。");
        
        String blank = getSomeBlank(index);
        System.out.println(text);
        System.out.print(blank);
        for(int i=0; i < pattern.length(); i++) {
            System.out.print("+");
        }
    }
    
    private static String getSomeBlank(int num) {
        StringBuffer buf = new StringBuffer();
        for (int i=0; i < num; i++) {
            buf.append(" ");
        }
        return buf.toString();
    }
    
    private static int kmpMatcher(String text, String pattern) {
        int txtCsl = 1;
        int ptnCsl = 0;
        
        int[] skip = new int[pattern.length() + 1];
        
        skip[txtCsl] = 0;
        
        //検索対象の文字列の最後まで
        while (txtCsl != pattern.length()) {
            //テキストのカーソル位置の文字
            if (pattern.charAt(txtCsl) == pattern.charAt(ptnCsl)) {
                skip[++txtCsl] = ++ptnCsl;
            } else if (ptnCsl == 0) {
                skip[++txtCsl] = ptnCsl;
            } else {
                ptnCsl = skip[ptnCsl];
            }
        }
        
        System.out.println("--------探索開始!--------");
        txtCsl = ptnCsl = 0;
        while (txtCsl != text.length() && ptnCsl != pattern.length()) {
            if (text.charAt(txtCsl) == pattern.charAt(ptnCsl)) {
                txtCsl++;
                ptnCsl++;
            } else if (ptnCsl == 0) {
                txtCsl++;
            } else {
                ptnCsl = skip[ptnCsl];
            }
        }
        
        if (ptnCsl == pattern.length()) {
            return txtCsl - ptnCsl;
        } else {
            return -1;
        }
        
    }
}

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

--------探索開始!--------
32文字目が一致します。
A man falls in love through his eyes, a woman through her ears
                                ++++

さて、このアルゴリズムをちゃんと見ていこう。
みんなが嫌いなエクセルを使って。
f:id:sho322:20131101173220p:plain

読んだ本

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

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

感謝のプログラミング

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