JAva実装sundayアルゴリズムの例共有

文字列整合ルックアップアルゴリズムの中で最も有名な2つはKMPアルゴリズム(Knuth−Morris−Pratt)とBMアルゴリズム(Boyer−Moore)である.両方のアルゴリズムは、最悪の場合、線形の検索時間を有する.しかし、実用的には、KMPアルゴリズムは最も簡単なCライブラリ関数strstr()よりもそれほど速くないが、BMアルゴリズムはKMPアルゴリズムより3〜5倍速いことが多い(実際には実践されていない).しかし、BMアルゴリズムはまだ最も速いアルゴリズムではありません.ここでは、BMアルゴリズムよりも速い検索アルゴリズムSundayアルゴリズムを紹介します.Sundayアルゴリズムの考え方はBMアルゴリズムの悪い文字の考え方とよく似ている.違いは、Sundayアルゴリズムがマッチングに失敗した後、ターゲット列の現在のPattern文字列に対応する部分の後ろの位置の文字を取り、悪い文字マッチングをすることにすぎない.マッチングに失敗したことが判明すると、親列における現在のオフセット+Pattern文字列長+1(K位置と仮定)の文字がPattern文字列に存在するか否かが判断される.存在する場合は、Pattern文字列の文字と位置を揃え、最初から一致させます.存在しない場合は、Pattern文字列を後ろに移動し、親列k+1の文字と位置合わせしてマッチングします.上の操作を見つけたり、親列が見つかったりするまで繰り返します.以下のアルゴリズムを実現するために小さな例を書いた.
コードでは,Sunday方式と通常の1ビットずつ移動する方式の2つの文字列マッチングアルゴリズムを実現し,両者の効率対比はmain関数にあり,いずれもナノ秒レベルである.アルゴリズムの詳細な手順は、コードに対応するコメントが追加されています.BMアルゴリズムについては、次回空になってから一緒に分析を照らし合わせています.

 
  
import java.util.HashMap; 
  
import java.util.LinkedList; 
  
import java.util.List; 
  
import java.util.Map; 
   
  
/** 
 * @author Scott
 * @date 2013 12 28  
 * @description
 */
public class SundySearch {
    String text = null;
    String pattern = null;
    int currentPos = 0;
 
  
    /**
     *                
     */
    List matchedPosList = new LinkedList();

    /**
     *      Map,           char    char       
     */
    Map map = new HashMap();
 
  
    public SundySearch(String text, String pattern) {
        this.text = text;
        this.pattern = pattern;
        this.initMap();
    };
 
  
    /**
     * Sunday   ，    Pattern              ，       
     */
    private void initMap() {
        for (int i = 0; i < pattern.length(); i++) {
            this.map.put(pattern.charAt(i), i);
 
  
        }
    }
 
  
    /**
     *           ，         
     */
    public List normalMatch() {
        //    ，     
        if (!matchFromSpecialPos(currentPos)) {
            currentPos += 1;
 
  
            if ((text.length() - currentPos) < pattern.length()) {
                return matchedPosList;
            }
            normalMatch();
        } else {
            //    ，    
            matchedPosList.add(currentPos);
            currentPos += 1;
            normalMatch();
        }

        return matchedPosList;
    }
 
  
    /**
     * Sunday  ，  Text  K      ：     +Pattern     +1
     */
    public List sundayMatch() {
        //         
        if (!matchFromSpecialPos(currentPos)) {
            //   Text K     Pattern      ，     Pattern     
            if ((currentPos + pattern.length() + 1) < text.length()
                    && !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
                currentPos += pattern.length();
            }else {
                //   Text K   Pattern      ，  Text K      Pattern           K       
                if ((currentPos + pattern.length() + 1) > text.length()) {
                    currentPos += 1;
                } else {
                    currentPos += pattern.length() - (Integer) map.get(text.charAt(currentPos + pattern.length()));
                }
            }

            //     ，             
            if ((text.length() - currentPos) < pattern.length()) {
                return matchedPosList;
            }

            sundayMatch();
        }else {
            //               
            matchedPosList.add(currentPos);
            currentPos += 1;
            sundayMatch();
        }
        return matchedPosList;
    }
 
  
    /**
     *    Text              Pattern  
     */
    public boolean matchFromSpecialPos(int pos) {
        if ((text.length()-pos) < pattern.length()) {
            return false;
        }
 
  
        for (int i = 0; i < pattern.length(); i++) {
            if (text.charAt(pos + i) == pattern.charAt(i)) {
                if (i == (pattern.length()-1)) {
                    return true;
                }
                continue;
            } else {
                break;
            }
        }

        return false;
    }
 
  
    public static void main(String[] args) {
        SundySearch sundySearch = new SundySearch("hello        adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");

        long begin = System.nanoTime();
        System.out.println("NormalMatch:" + sundySearch.normalMatch());
        System.out.println("NormalMatch:" + (System.nanoTime() - begin));

        begin = System.nanoTime();
        System.out.println("SundayMatch:" + sundySearch.sundayMatch());
        System.out.println("SundayMatch:" + (System.nanoTime() - begin));
 
  
    }
}