ダブル配列の検索

ArrayMain.java

package study.doublearray;

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

/**
 * ダブル配列もどきの実装 （参考:http://d.hatena.ne.jp/takeda25/20120219/1329634865）
 * 
 */
public class ArrayMain {

	private static final int DICTIONARY_SIZE = 13;

	// ace,ad,ade,cab,dab,dadという文字が入ったダブル配列もどきを使う
	// 単語終端を表す余分な配列を持っているから「もどき」・・・
	private static final int[] allBase2; // 文字のずらし量
	private static final int[] allCheck2; // 親ノードの位置
	private static final boolean[] allEndFlag2; // 単語終端かのフラグ。trueが終端

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

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

		allEndFlag2 = new boolean[DICTIONARY_SIZE];
		allEndFlag2[0] = false;
		allEndFlag2[1] = false;
		allEndFlag2[2] = false;
		allEndFlag2[3] = false;
		allEndFlag2[4] = false;
		allEndFlag2[5] = false;
		allEndFlag2[6] = true;
		allEndFlag2[7] = true;
		allEndFlag2[8] = false;
		allEndFlag2[9] = true;
		allEndFlag2[10] = true;
		allEndFlag2[11] = true;
		allEndFlag2[12] = true;
	}

	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 = allBase2[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 allEndFlag2[currentPosi];
	}

	/**
	 * 子ノードの位置候補（candidates）の親ノードが、現在のノードの位置（currentPosi）と一致するかを返す
	 * 
	 * @param currentPosi
	 * @param candidates
	 */
	private static boolean isRealChild(int currentPosi, int candidates) {
		return allCheck2[candidates] == 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);
	}

}

TableMain.java

package study.doublearray;

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

/**
 * テーブルの実装 （参考:http://d.hatena.ne.jp/takeda25/20120219/1329634865）
 * 
 */
public class TableMain {

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

		// ace,ad,ade,cab,dab,dadという文字が入ったテーブルを得る
		Map<Character, Map<Integer, Map<Character, Boolean>>> table = getTable();

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

	/**
	 * 単語がテーブル（辞書）に存在するかどうかを返す。
	 */
	protected static boolean isExist(
			Map<Character, Map<Integer, Map<Character, Boolean>>> table,
			String word) {

		boolean result = false;

		// 根の行を取得し、現在の行に設定する
		Map<Integer, Map<Character, Boolean>> rootLow = table.get('イ');
		Map<Integer, Map<Character, Boolean>> currentLow = rootLow;

		Map<Character, Boolean> nextCharMap = null;
		Character nextCh = null;
		for (int i = 0; i < word.length(); i++) {
			// 現在の行で、検索文字のi番目に対応する文字コード列に、文字が書き込まれているかを調べる
			char ch = word.charAt(i);
			nextCharMap = getFoundChar(currentLow, ch);
			if (nextCharMap != null) {
				// 文字が書きこまれていた場合、その文字の行を現在の行とする
				Set<Character> keySet = nextCharMap.keySet();
				Object[] array = keySet.toArray();
				nextCh = (Character) array[0];
				currentLow = table.get(nextCh);
			} else {
				// 文字が書き込まれていない場合、探す単語は存在しないので終了
				return false;
			}
		}
		// 検索単語末まできた場合、この行に到達。それが辞書内の単語終端であれば、単語発見
		if (nextCharMap.get(nextCh)) {
			result = true;
		}
		return result;
	}

	/**
	 * 現在の行に、ある文字が書きこまれているかを調べる。 書きこまれている場合、文字と単語終端かどうかのMap（1要素）を返す。
	 * 書きこまれていない場合、nullを返す。
	 */
	protected static Map<Character, Boolean> getFoundChar(
			Map<Integer, Map<Character, Boolean>> currentLow, char ch) {
		int code = convertCharToCode(ch);
		return currentLow.get(code);
	}

	/**
	 * 文字と疑似文字コードの対応表を返す（文字がキー）
	 */
	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);
	}

	/**
	 * 検索対象とするテーブル（辞書）を返す
	 */
	protected static final HashMap<Character, Map<Integer, Map<Character, Boolean>>> getTable() {
		HashMap<Character, Map<Integer, Map<Character, Boolean>>> result = new HashMap<Character, Map<Integer, Map<Character, Boolean>>>();

		Map<Integer, Map<Character, Boolean>> low00 = new HashMap<Integer, Map<Character, Boolean>>();
		low00.put(0, getOneNode('ロ', false));
		low00.put(1, null);
		low00.put(2, getOneNode('ハ', false));
		low00.put(3, getOneNode('ニ', false));
		low00.put(4, null);

		Map<Integer, Map<Character, Boolean>> low01 = new HashMap<Integer, Map<Character, Boolean>>();
		low01.put(0, null);
		low01.put(1, null);
		low01.put(2, getOneNode('ホ', false));
		low01.put(3, getOneNode('ヘ', true));
		low01.put(4, null);

		Map<Integer, Map<Character, Boolean>> low02 = new HashMap<Integer, Map<Character, Boolean>>();
		low02.put(0, getOneNode('ト', false));
		low02.put(1, null);
		low02.put(2, null);
		low02.put(3, null);
		low02.put(4, null);

		Map<Integer, Map<Character, Boolean>> low03 = new HashMap<Integer, Map<Character, Boolean>>();
		low03.put(0, getOneNode('チ', false));
		low03.put(1, null);
		low03.put(2, null);
		low03.put(3, null);
		low03.put(4, null);

		Map<Integer, Map<Character, Boolean>> low04 = new HashMap<Integer, Map<Character, Boolean>>();
		low04.put(0, null);
		low04.put(1, null);
		low04.put(2, null);
		low04.put(3, null);
		low04.put(4, getOneNode('リ', true));

		Map<Integer, Map<Character, Boolean>> low05 = new HashMap<Integer, Map<Character, Boolean>>();
		low05.put(0, null);
		low05.put(1, null);
		low05.put(2, null);
		low05.put(3, null);
		low05.put(4, getOneNode('ヌ', true));

		Map<Integer, Map<Character, Boolean>> low06 = new HashMap<Integer, Map<Character, Boolean>>();
		low06.put(0, null);
		low06.put(1, getOneNode('ル', true));
		low06.put(2, null);
		low06.put(3, null);
		low06.put(4, null);

		Map<Integer, Map<Character, Boolean>> low07 = new HashMap<Integer, Map<Character, Boolean>>();
		low07.put(0, null);
		low07.put(1, getOneNode('ヲ', true));
		low07.put(2, null);
		low07.put(3, getOneNode('ワ', true));
		low07.put(4, null);

		Map<Integer, Map<Character, Boolean>> low08 = new HashMap<Integer, Map<Character, Boolean>>();
		low08 = getEmptyLow(5);
		Map<Integer, Map<Character, Boolean>> low09 = new HashMap<Integer, Map<Character, Boolean>>();
		low09 = getEmptyLow(5);
		Map<Integer, Map<Character, Boolean>> low10 = new HashMap<Integer, Map<Character, Boolean>>();
		low10 = getEmptyLow(5);
		Map<Integer, Map<Character, Boolean>> low11 = new HashMap<Integer, Map<Character, Boolean>>();
		low11 = getEmptyLow(5);
		Map<Integer, Map<Character, Boolean>> low12 = new HashMap<Integer, Map<Character, Boolean>>();
		low12 = getEmptyLow(5);

		result.put('イ', low00);
		result.put('ロ', low01);
		result.put('ハ', low02);
		result.put('ニ', low03);
		result.put('ホ', low04);
		result.put('へ', low05);
		result.put('ト', low06);
		result.put('チ', low07);
		result.put('リ', low08);
		result.put('ヌ', low09);
		result.put('ル', low10);
		result.put('ヲ', low11);
		result.put('ワ', low12);

		return result;
	}

	/**
	 * テーブル作成のUtil. 文字と単語終端かどうかを受け取り、Mapにして返す。
	 */
	protected static Map<Character, Boolean> getOneNode(Character ch,
			boolean isEndNode) {
		Map<Character, Boolean> result = new HashMap<Character, Boolean>();
		result.put(ch, isEndNode);
		return result;
	}

	/**
	 * テーブル作成のUtil. 文字が書きこまれていない行を返す。
	 */
	protected static Map<Integer, Map<Character, Boolean>> getEmptyLow(
			int columNum) {
		Map<Integer, Map<Character, Boolean>> result = new HashMap<Integer, Map<Character, Boolean>>();
		for (int i = 0; i < columNum; i++) {
			result.put(i, null);
		}
		return result;
	}

}