package autocomplete;
import java.util.Set;
public interface PrefixMatcher {
Set<String> obtainMatchedWords(String inputText);
} 2. 定义抽象类 package autocomplete;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public abstract class AbstractPrefixMatcher implements PrefixMatcher {
protected final String[] javaKeywords = new String[] {
"abstract", "assert",
"boolean", "break", "byte",
"case", "catch", "char", "class", "const", "continue",
"default", "do", "double",
"else", "enum", "extends",
"final", "finally", "float", "for",
"goto",
"if", "implements", "import", "instanceof", "int", "interface",
"long",
"native", "new",
"package", "private", "protected", "public",
"return",
"strictfp", "short", "static", "super", "switch", "synchronized",
"this", "throw", "throws", "transient", "try",
"void", "volatile",
"while"
};
protected Map<String, Set<String>> prefixMatchers = new HashMap<String, Set<String>>();
abstract void dynamicAddNew(String inputText);
public Set<String> obtainMatchedWords(String inputText) {
Set<String> matchers = prefixMatchers.get(inputText);
if (matchers == null) {
Set<String> input = new HashSet<String>();
input.add(inputText);
dynamicAddNew(inputText);
return input;
}
return matchers;
}
protected Map<String, Set<String>> obtainPrefixMatchers() {
return Collections.unmodifiableMap(prefixMatchers);
}
}
3. 简单的实现package autocomplete;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class SimpleWordMatcher extends AbstractPrefixMatcher {
public SimpleWordMatcher() {
prefixMatchers = buildPrefixMatchers(javaKeywords);
}
/**
* 将输入的单词组转化为前缀匹配的映射
* @param keywords
* @return
*
* eg. {"abc", "acd", "bcd"} ===>
* {"a": ["abc", "acd"], "ab": ["abc"], "abc": ["abc"],
* "ac": ["acd"], "acd": ["acd"], "b": ["bcd"], "bc": ["bcd"], "bcd": ["bcd"]
* }
*/
public Map<String, Set<String>> buildPrefixMatchers(String[] keywords) {
HashMap<String, Set<String>> prefixMatchers = new HashMap<String, Set<String>>();
for (String keyword: keywords) {
int wordLen = keyword.length();
for (int i=1; i < wordLen; i++) {
String prefix = keyword.substring(0, i);
for (String keyword2: javaKeywords) {
if (keyword2.startsWith(prefix)) {
Set<String> matchers = prefixMatchers.get(prefix);
if (matchers == null) {
matchers = new HashSet<String>();
}
matchers.add(keyword2);
prefixMatchers.put(prefix, matchers);
}
}
}
}
return prefixMatchers;
}
public static void main(String[] args) {
SimpleWordMatcher wordMatcher = new SimpleWordMatcher();
MapUtil.printMap(wordMatcher.obtainPrefixMatchers());
String[] prefixes = new String[] {"a", "b", "c", "d", "e", "f", "g", "i",
"l", "n", "p", "r", "s", "t", "v", "w", "do", "finally"};
for (String prefix: prefixes) {
System.out.println(wordMatcher.obtainMatchedWords(prefix));
}
}
@Override
void dynamicAddNew(String inputText) {
}
}
4. 性能更好的实现 package autocomplete;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class EffectiveWordMatcher extends AbstractPrefixMatcher {
public EffectiveWordMatcher() {
prefixMatchers = buildPrefixMatchers(javaKeywords);
}
static class Pair {
private String key;
private String value;
public Pair(String key, String value) {
this.key = key;
this.value = value;
}
public String getKey() {
return key;
}
public String getValue() {
return value;
}
public String toString() {
return "<" + key + "," + value + ">";
}
}
private Map<String, Set<String>> buildPrefixMatchers(String[] javakeywords) {
List<Pair> pairs = strarr2pairs(javakeywords);
return mergePairs(pairs);
}
/*
* 将 字符串数组转化为前缀匹配对
* eg. ["ab", "ac"] ===>
* [<"a","ab">, <"ab", "ab">, <"a", "ac">, <"ac", "ac">]
*/
private List<Pair> strarr2pairs(String[] javakeywords) {
List<Pair> pairs = new ArrayList<Pair>();
for (String keyword: javakeywords) {
int wordLen = keyword.length();
for (int i=1; i < wordLen; i++) {
String prefix = keyword.substring(0, i);
Pair pair = new Pair(prefix, keyword);
pairs.add(pair);
}
}
return pairs;
}
/*
* 将多个 <key,value> 合并为一个映射
* eg. [<"a", "abstract">, <"b", "boolean">, <"a", "assert">, <"b", "break">, <"c", "continue">] ===>
* {"a"=>["abstract", "assert", "b"=>["boolean", "break"], "c"=>["continue"]}
*/
private static Map<String, Set<String>> mergePairs(List<Pair> pairs) {
Map<String, Set<String>> result = new HashMap<String, Set<String>>();
if (pairs != null && pairs.size() > 0) {
for (Pair pair: pairs) {
String key = pair.getKey();
String value = pair.getValue();
Set<String> matchers = result.get(key);
if (matchers == null) {
matchers = new HashSet<String>();
}
matchers.add(value);
result.put(key, matchers);
}
}
return result;
}
@Override
void dynamicAddNew(String inputText) {
if (checkValid(inputText)) {
List<Pair> newpairs = strarr2pairs(new String[] {inputText});
Map<String, Set<String>> newPreixMatchers = mergePairs(newpairs);
mergeMap(newPreixMatchers, prefixMatchers);
}
}
private boolean checkValid(String inputText) {
return false;
}
private Map<String, Set<String>> mergeMap(Map<String, Set<String>> src, Map<String, Set<String>> dest) {
Set<Map.Entry<String, Set<String>>> mapEntries = src.entrySet();
Iterator<Map.Entry<String, Set<String>>> iter = mapEntries.iterator();
while (iter.hasNext()) {
Map.Entry<String, Set<String>> entry = iter.next();
String key = entry.getKey();
Set<String> newMatchers = entry.getValue();
if (dest.containsKey(key)) {
dest.get(key).addAll(newMatchers);
}
else {
dest.put(key, newMatchers);
}
}
return dest;
}
public static void main(String[] args) {
EffectiveWordMatcher wordMatcher = new EffectiveWordMatcher();
MapUtil.printMap(wordMatcher.obtainPrefixMatchers());
String[] prefixes = new String[] {"a", "b", "c", "d", "e", "f", "g", "i",
"l", "n", "p", "r", "s", "t", "v", "w", "do", "finally"};
for (String prefix: prefixes) {
System.out.println(wordMatcher.obtainMatchedWords(prefix));
}
}
}package servlets;
import java.io.IOException;
import java.util.Set;
import javax.servlet.ServletException;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import autocomplete.EffectiveWordMatcher;
import autocomplete.PrefixMatcher;
public class AutoCompleteServlet extends HttpServlet {
protected PrefixMatcher wordMatcher = new EffectiveWordMatcher();
public void doGet(HttpServletRequest req, HttpServletResponse resp)
throws ServletException, IOException {
doPost(req, resp);
}
public void doPost(HttpServletRequest req, HttpServletResponse resp)
throws ServletException, IOException {
resp.setContentType("text/plain;charset=UTF8");
String inputText = req.getParameter("inputText");
Set<String> matchers = wordMatcher.obtainMatchedWords(inputText);
StringBuilder sb = new StringBuilder();
for (String m: matchers) {
sb.append(m);
sb.append(' ');
}
sb.deleteCharAt(sb.length()-1);
resp.getWriter().print(sb.toString());
}
}
6. 前端交互 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>输入自动补全功能演示</title>
<script type="text/javascript" src="jquery-1.10.2.min.js"></script>
<script>
$(document).ready(function() {
var searchMatchers = function(keycode) {
var inputText = $('#inputText').val();
$.ajax(
{
url: 'servlets/AutoCompleteServlet',
data: { 'inputText': inputText },
dataType: 'text',
timeout: 10000,
success: function(data) {
if (keycode == 13) { // Enter
$('#inputText').val($('#matchedKeywords').val());
$('#resultRegion').empty();
return ;
}
if (keycode == 38 || keycode == 40) { // 上下箭头
$('#matchedKeywords').trigger('focus');
return ;
}
$('#resultRegion').empty();
var matchers = data.split(' ');
if (matchers.length > 0 && inputText != '') {
$('#resultRegion').append('<select id="matchedKeywords"></select>')
$('#matchedKeywords').append('<option value="' + '' + '">' + '' + '</option>');
for (i=0; i<matchers.length; i++) {
var keyword = matchers[i];
$('#matchedKeywords').append('<option value="' + keyword + '">' + keyword + '</option>');
}
$('#matchedKeywords').attr('size', matchers.length+1);
$('#matchedKeywords').height(20*(matchers.length+1));
$('#matchedKeywords').click(function() {
$('#inputText').val($('#matchedKeywords').val());
$('#resultRegion').empty();
});
}
}
}
);
}
$(this).bind("keyup", function(eventObj) {
var keycode = eventObj.which;
searchMatchers(keycode);
});
});
</script>
<style type="text/css">
#main {
margin: 15% 20% 0% 25%;
}
#inputText {
width: 450px;
height: 30px;
}
#matchedKeywords {
width: 450px;
height: 25px;
}
#resultRegion {
text-align: left;
margin: 0 0 0 128px;
}
</style>
</head>
<body>
<center>
<div id="main">
<h3> 输入自动补全功能演示，请输入Java关键字: </h3>
<input type="text" name="inputText" id="inputText" value=""/><br/>
<div id="resultRegion"></div>
</div>
</center>
</body>
</html> 