Created
February 28, 2012 10:15
-
-
Save torazuka/1931737 to your computer and use it in GitHub Desktop.
ダブル配列の検索
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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