输入法核心数据结构及算法的设计

输入法只需要实现三个非常重要的函数即可：

1. /** 
2.      * 插入一个单词 
3.      *  
4.      * @param term 
5.      *            要插入的单词 
6.      */  
7. public void insert(String term);  
8.   
9. /** 
10.      * 删除一个单词 
11.      *  
12.      * @param term 
13.      *            要删除的单词 
14.      */  
15. public void delete(String term);  
16. /** 
17.      * 获取提示的词条 
18.      *  
19.      * @param preTerm 
20.      *            用户已输入的词条 
21.      * @return 提示词条 
22.      */  
23. public List<String> promptsTerms(String preTerm);  

当然在考虑删除某个单词的时候，由于有很多单词共享相同的前缀，所以不能轻易删除，具体删除的情况可以分为三种：完全独立型、完全共享型、部分共享型。大家自己去思考吧，还是很简单的，我就不说了~

其中一种实现思路可以为每个单词节点设计一个计数器，delete的时候就把计数减1，当计数为0时就删除。但这种方法有个缺陷：即每个节点都要多设置一个计数的空间，节点当然不少，无形中对空间会造成比较大的浪费。而且对于输入法而言delete函数并不常用，为了一个极少使用的函数浪费这么多空间肯定是不合适的。特别是对于手机而言，本身内存就已经很少了，这样的设计肯定是bad smell。那么，我们采用另外一种方法去解决了这个问题~

废话我就不太多说了，我觉得用代码描述更为直观，大家有什么问题直接研究代码吧~

1. package com.algorithm;  
2.   
3. import java.util.ArrayList;  
4. import java.util.HashMap;  
5. import java.util.List;  
6. import java.util.Map;  
7. import java.util.Stack;  
8.   
9. /** 
10.  * 共享前缀树PrefixTree 
11.  *  
12.  * E-mail:530025983@qq.com 2011-5-28 
13.  *  
14.  * @author MONKEY_D_MENG 
15.  *  
16.  */  
17. public class PrefixTree  
18. {  
19.     /* 利用Hash表能够O(1)时间内找到下一个字符的位置 */  
20.     private Map<Byte, PrefixTree> wordTable = new HashMap<Byte, PrefixTree>();  
21.   
22.     /* 到这个节点为止是否是一个完整的单词 */  
23.     private boolean isWord = false;  
24.   
25.     /** 
26.      * 插入一个单词 
27.      *  
28.      * @param term 
29.      *            要插入的单词 
30.      */  
31.     public void insert(String term)  
32.     {  
33.         if (null == term)  
34.         {  
35.             return;  
36.         }  
37.   
38.         /* 将单词转化为字符串处理 */  
39.         byte[] termChars = term.getBytes();  
40.         PrefixTree current = this;  
41.         for (byte ch : termChars)  
42.         {  
43.             if (!current.wordTable.containsKey(ch))  
44.             {  
45.                 PrefixTree next = new PrefixTree();  
46.                 current.wordTable.put(ch, next);  
47.                 current = next;  
48.             }  
49.             else  
50.             {  
51.                 current = (PrefixTree) current.wordTable.get(ch);  
52.             }  
53.         }  
54.   
55.         /* 设置到该节点止为单词的标志 */  
56.         current.isWord = true;  
57.     }  
58.   
59.     /** 
60.      * 删除一个单词 
61.      *  
62.      * @param term 
63.      *            要删除的单词 
64.      */  
65.     public void delete(String term)  
66.     {  
67.         if (null == term)  
68.         {  
69.             return;  
70.         }  
71.   
72.         /* 将单词转化为字符串处理 */  
73.         byte[] termChars = term.getBytes();  
74.         PrefixTree current = this;  
75.         PrefixTree fromDelete = this;  
76.         PrefixTree next = this;  
77.         int indexDelete = 0;  
78.         int index = 0;  
79.   
80.         for (index = 0; index < termChars.length; ++index)  
81.         {  
82.             if (!current.wordTable.containsKey(termChars[index]))  
83.             {  
84.                 return;  
85.             }  
86.             else  
87.             {  
88.                 current = (PrefixTree) current.wordTable.get(termChars[index]);  
89.             }  
90.             /* 记录要删除的节点位置，注意不能到最后才判断，因为要删除这个单词最后的节点的isWord肯定被转为了true */  
91.             if (current.isWord && index != termChars.length - 1)  
92.             {  
93.                 fromDelete = current;  
94.                 indexDelete = index + 1;  
95.             }  
96.         }  
97.   
98.         /* 有后缀节点，说明被其他单词共享了前缀 */  
99.         if (current.wordTable.size() != 0)  
100.         {  
101.             current.isWord = false;  
102.             return;  
103.         }  
104.   
105.         /* 删除所有不共享的后缀节点 */  
106.         for (current = fromDelete, index = indexDelete; index < termChars.length; ++index)  
107.         {  
108.             next = current.wordTable.get(termChars[index]);  
109.             current.wordTable.remove(termChars[index]);  
110.             current = next;  
111.             current.isWord = false;  
112.         }  
113.     }  
114.   
115.     /** 
116.      * 获取提示的词条 
117.      *  
118.      * @param preTerm 
119.      *            用户已输入的词条 
120.      * @return 提示词条 
121.      */  
122.     public List<String> promptsTerms(String preTerm)  
123.     {  
124.         if (null == preTerm)  
125.         {  
126.             return null;  
127.         }  
128.   
129.         PrefixTree current = this;  
130.         List<String> words = new ArrayList<String>();  
131.         Stack<Byte> stack = new Stack<Byte>();  
132.   
133.         /* 将单词转化为字符串处理 */  
134.         byte[] termChars = preTerm.getBytes();  
135.         for (byte ch : termChars)  
136.         {  
137.             if (!current.wordTable.containsKey(ch))  
138.             {  
139.                 return null;  
140.             }  
141.             else  
142.             {  
143.                 current = (PrefixTree) current.wordTable.get(ch);  
144.             }  
145.         }  
146.   
147.         /* 如果本身输入的已经是一个单词了，需要先记录，由于后面处理时要加前缀，这个地方只给个空串即可 */  
148.         if (current.isWord)  
149.         {  
150.             words.add("");  
151.         }  
152.   
153.         /* 递归地遍历，寻找所有匹配的单词 */  
154.         this.traversalTree(current, stack, words);  
155.   
156.         /* 将每个单词都加上前缀 */  
157.         for (int index = 0; index < words.size(); ++index)  
158.         {  
159.             words.set(index, preTerm + words.get(index));  
160.         }  
161.   
162.         return words;  
163.     }  
164.   
165.     /** 
166.      * 递归生成所有后缀的单词 
167.      *  
168.      * @param current 
169.      *            当前的根节点 
170.      * @param words 
171.      *            单词列表 
172.      */  
173.     private void traversalTree(PrefixTree current, Stack<Byte> stack,  
174.             List<String> words)  
175.     {  
176.         for (byte ch : current.wordTable.keySet())  
177.         {  
178.             stack.push(ch);  
179.   
180.             /* 遇到是单词的标志 */  
181.             if (current.wordTable.get(ch).isWord)  
182.             {  
183.                 /* 记录单词 */  
184.                 words.add(stackToWord(stack));  
185.             }  
186.   
187.             /* 如果还有后续节点则递归 */  
188.             if (current.wordTable.get(ch).wordTable.size() != 0)  
189.             {  
190.                 this.traversalTree(current.wordTable.get(ch), stack, words);  
191.             }  
192.             stack.pop();  
193.         }  
194.     }  
195.   
196.     /** 
197.      * 输出从栈底到栈顶的一条路径，即为一个单词 
198.      *  
199.      * @param stack 
200.      *            栈 
201.      * @return 栈中所存储的单词 
202.      */  
203.     private String stackToWord(Stack<Byte> stack)  
204.     {  
205.         String word = "";  
206.         for (byte ch : stack)  
207.         {  
208.             word += (char) ch;  
209.         }  
210.         return word;  
211.     }  
212. }  
213. package com.algorithm;  
214.   
215. import java.util.List;  
216.   
217. /** 
218.  * 测试代码 
219.  *  
220.  * E-mail:530025983@qq.com 2011-5-28 
221.  *  
222.  * @author MONKEY_D_MENG 
223.  *  
224.  */  
225. public class Main  
226. {  
227.     public static void main(String[] args)  
228.     {  
229.         PrefixTree prefixTree = new PrefixTree();  
230.         List<String> words;  
231.   
232.         prefixTree.insert("mon");  
233.         prefixTree.insert("money");  
234.         prefixTree.insert("monkey");  
235.         prefixTree.insert("monkey1");  
236.         prefixTree.insert("monkey2");  
237.         prefixTree.insert("monkey3");  
238.         prefixTree.insert("monkey4");  
239.         prefixTree.insert("monkey5");  
240.   
241.         prefixTree.delete("money");  
242.         words = prefixTree.promptsTerms("mon");  
243.   
244.         for (String word : words)  
245.         {  
246.             System.out.println(word);  
247.         }  
248.     }  
249. }