用贪婪法解决翻译匹配的问题（大量字符串替换）

Question

例如有两个文件original，translation 
original代表被翻译的文件 
translation代表翻译使用的数据文件 
对应关系如下 
Sample Translation Table 
（ 
'dog'=>'pero' 
'small'=>'micro' 
'small pig'=>'mini peroes' 
'joe is man'=>'el jpse' 
） 
要求优先匹配大字符串，既如有small和small pig要先匹配small pig 
因为两个文件都有可能比较大，所以同时要求尽量要求算法的效率。算法要求用贪婪法。 
急求解答，不甚感激！！！

Answer 1

这个你可以用hash表.key里存original,value里存translation 然后记录下最长的一个original是有多少个单词,这个数为maxWords,第一次从文件第一个词取maxWords个词,到hash表里找,如果找到就返回translation的值,如果没找到就减一个词,取到maxWords-1个,直到等于key为止.记录下当前的位置,从单前位置开始继续用这个步骤取.

Answer 2

public class Translation {

private static HashMap<String, String> dictionary = new HashMap<String, String>();
static {
dictionary.put("abc", "111");
dictionary.put("abc def", "222");
dictionary.put("abc def xyz", "333");
dictionary.put("def", "777");
dictionary.put("def xyz", "888");
dictionary.put("xyz", "999");
}

private static String text = "111 abcd xyz def xyzd abc def xyz xyz";

public static String translate(String text) {
StringBuilder resultBuffer = new StringBuilder();
String temp = " " + text+" ";
int[] prefixs = computePrefix(temp);
if (prefixs.length == 0)
return text;
int index = 0;
LOOP:
do {
for (int i = prefixs.length - 1; i > index; i--) {
String key = temp.substring(prefixs[index] + 1, prefixs[i]);
if (dictionary.containsKey(key)) {
resultBuffer.append(dictionary.get(key)).append(" ");
index = i;
continue LOOP;
}
}
resultBuffer.append(temp.substring(prefixs[index]+1, prefixs[index+1])).append(" ");
index++;
}while (index < prefixs.length - 1);

return resultBuffer.substring(0, resultBuffer.length() - 1).toString();
}

private static int[] computePrefix(String text) {
ArrayList<Integer> list = new ArrayList<Integer>();
boolean inWord = false;
int first = -1;
for(int i = 0; i < text.length(); i++) {
if (text.charAt(i) != ' ') {
first = i;
list.add(first - 1);
inWord = true;
break;
}

}
if (first == -1)
return new int[0];
for (int i = first ; i < text.length(); i++) {
if (text.charAt(i) == ' ') {
if (inWord) {
list.add(i);
inWord = false;
}
} else if (!inWord) {
inWord = true;
}
}
int[] results = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
results[i] = list.get(i);
}
return results;
}

public static void main(String[] args) {
System.out.println(translate(text));
}}