ダブル配列の検索（改）

ArrayMain2.java

package study.doublearray;

import java.util.HashMap;
import java.util.Map;

/**
 * ダブル配列の実装 （参考:http://d.hatena.ne.jp/takeda25/20120219/1329634865）
 * E_Mattsanさん方法で単語終端を表現
 * （参考:http://d.hatena.ne.jp/torazuka/20120228/doublearray#c1330526080）
 * 
 */
public class ArrayMain2 {

	private static final int DICTIONARY_SIZE = 13;

	// ace,ad,ade,cab,dab,dadという文字が入ったダブル配列を使う
	private static final int[] allBase; // 文字のずらし量
	private static final int[] allCheck; // 親ノードの位置（2倍して格納、単語終端の場合は1を足す）

	static {
		allBase = new int[DICTIONARY_SIZE];
		allBase[0] = 1;
		allBase[1] = 3;
		allBase[2] = 9;
		allBase[3] = 2;
		allBase[4] = 8;
		allBase[5] = 7;
		allBase[6] = 8;
		allBase[7] = -1;
		allBase[8] = 6;
		allBase[9] = -1;
		allBase[10] = -1;
		allBase[11] = -1;
		allBase[12] = -1;

		allCheck = new int[DICTIONARY_SIZE];
		allCheck[0] = -1 * 2;
		allCheck[1] = 0 * 2;
		allCheck[2] = 3 * 2;
		allCheck[3] = 0 * 2;
		allCheck[4] = 0 * 2;
		allCheck[5] = 1 * 2;
		allCheck[6] = 1 * 2 + 1; // 単語終端
		allCheck[7] = 8 * 2 + 1; // 単語終端
		allCheck[8] = 4 * 2;
		allCheck[9] = 8 * 2 + 1; // 単語終端
		allCheck[10] = 2 * 2 + 1; // 単語終端
		allCheck[11] = 5 * 2 + 1; // 単語終端
		allCheck[12] = 6 * 2 + 1; // 単語終端
	}

	public static void main(String[] args) {
		if (args.length != 1) {
			System.out.println("検索単語を1つ入力してください。（例）ace, ca, bad");
			return;
		}

		String searchKey = args[0];
		if (isExist(searchKey)) {
			System.out.println("「" + searchKey + "」が見つかりました。");
		} else {
			System.out.println("「" + searchKey + "」は見つかりませんでした。");
		}
	}

	/**
	 * 単語がダブル配列（もどき）に存在するかどうかを返す。
	 */
	protected static boolean isExist(final String word) {

		boolean result = false;

		// 根の位置は 0 とし、0を 現在の位置とする
		int currentPosi = 0;
		// 現在のずらし量の初期化
		int currentBase = -1;

		for (int i = 0; i < word.length(); i++) {

			// 検索単語の途中にもかかわらず、現在位置が辞書内の単語終端であれば、検索終了
			if (isInEndOfWord(currentPosi)) {
				return false;
			}

			// 現在の位置のずらし量を取得する
			currentBase = allBase[currentPosi];
			// ずらし量が負数、つまり、子ノードを持たない場合は、検索終了
			if (currentBase < 0) {
				return false;
			}

			// 現在のずらし量に、検索文字のi番目に対応する文字コードを足し、子ノードの位置候補を取得する
			int candidates = currentBase + convertCharToCode(word.charAt(i));

			// 子ノードの位置候補が、真に子ノードであれば、現在の位置とする
			if (isRealChild(currentPosi, candidates)) {
				currentPosi = candidates;
			} else {
				// 一致しない場合、現在のノードから次の検索文字へ至るエッジはないので終了
				return false;
			}
		}

		// 検索単語末まできた場合、この行に到達。それが辞書内の単語終端であれば、単語発見
		if (isInEndOfWord(currentPosi)) {
			result = true;
		}
		return result;
	}

	/**
	 * 現在の位置（currentPosi）が、辞書内の単語の終端かを返す。trueは終端。
	 * 
	 * @param currentPosi
	 */
	private static boolean isInEndOfWord(int currentPosi) {
		return (allCheck[currentPosi] % 2) != 0;
	}

	/**
	 * 子ノードの位置候補（candidates）の親ノードが、現在のノードの位置（currentPosi）と一致するかを返す
	 * 
	 * @param currentPosi
	 * @param candidates
	 */
	private static boolean isRealChild(int currentPosi, int candidates) {
		// 配列には、終端か否かで+1されている可能性があるが、2で割った結果には影響しない
		return allCheck[candidates] / 2 == currentPosi;
	}

	/**
	 * 文字と疑似文字コードの対応表を返す（文字がキー）
	 */
	protected static final Map<Character, Integer> getCharDictionary() {
		Map<Character, Integer> result = new HashMap<Character, Integer>();
		result.put('a', 0);
		result.put('b', 1);
		result.put('c', 2);
		result.put('d', 3);
		result.put('e', 4);
		return result;
	}

	/**
	 * 文字を文字コードに変換して返す
	 */
	protected static int convertCharToCode(char c) {
		Map<Character, Integer> charDic = getCharDictionary();
		return charDic.get(c);
	}

}