Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ダブル配列の検索(改)
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.