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)
*
*/
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);
}
}
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;
}
}
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.