/**
 * Java中提供一個非常棒的HashMap函數(shù)，只需要一步就可以統(tǒng)計單詞的頻率
 */


import java.util.HashMap;

public class WordMap {

	public static void main(String[] args) {
		String input = "a1,b2,3c,d4d,a1,b2,a1";
		String[] ws = input.split(",");
		// 做的單詞分割，
		// 如果你要空格分割 String[] ws = input.split(" ");
		HashMap<String, Integer> hm = new HashMap<String, Integer>();
		// 初始化HashMap
		for (String s : ws) {
			if (s.matches("[a-zA-Z]\\w+"))
			// 這里是一個正則表達式，
			// 判斷的是第一個必須是字母，
			// 后面的是一個字母或多個字母，
			// 一個數(shù)字或多個數(shù)字
			{
				Integer cou = hm.get(s);
				// get()方法將產(chǎn)生一個與鍵相關聯(lián)的Integer值，
				// 然后這個值被遞增，為的是記錄標識符的個數(shù)
				hm.put(s, cou == null ? 1 : cou + 1);
				// 保存到HashMap中以單詞做key,判斷單詞是否為空，空為1，或則加1
			}
		}
		System.out.println(hm);
		// 打印HashMap
	}
}

public class WordCount {
    private String word;
    
    private int count;
    public int getCount() {
        return count;
    }
    public void setCount(int count) {
        this.count = count;
    }
    public String getWord() {
        return word;
    }
    public void setWord(String word) {
        this.word = word;
    }
}

public class WordCountService {
    
    /**
     * 根據(jù)文章生成單詞樹
     * @param text
     * @return
     */
    private static CharTreeNode geneCharTree(String text){
        CharTreeNode root = new CharTreeNode();
        CharTreeNode p = root;
        char c = ' ';
        for(int i = 0; i < text.length(); ++i){
            c = text.charAt(i);
            if(c >= 'A' && c <= 'Z')
                c = (char)(c + 'a' - 'A');
            if(c >= 'a' && c <= 'z'){
                if(p.children[c-'a'] == null)
                    p.children[c-'a'] = new CharTreeNode();
                p = p.children[c-'a'];
            }
            else{
                p.cnt ++;
                p = root;
            }
        }
        if(c >= 'a' && c <= 'z')
            p.cnt ++;
        return root;
    }
    
    /**
     * 使用深度優(yōu)先搜索遍歷單詞樹并將對應單詞放入結果集中
     * @param result
     * @param p
     * @param buffer
     * @param length
     */
    private static void getWordCountFromCharTree(List result,CharTreeNode p, char[] buffer, int length){
        for(int i = 0; i < 26; ++i){
            if(p.children[i] != null){
                buffer[length] = (char)(i + 'a');
                if(p.children[i].cnt > 0){
                    WordCount wc = new WordCount();
                    wc.setCount(p.children[i].cnt);
                    wc.setWord(String.valueOf(buffer, 0, length+1));
                    result.add(wc);
                }
                getWordCountFromCharTree(result,p.children[i],buffer,length+1);
            }
        }
    }
    
    private static void getWordCountFromCharTree(List result,CharTreeNode p){
        getWordCountFromCharTree(result,p,new char[100],0);
    }
    
    /**
     * 得到詞頻表的主算法,供外部調用
     * @param article
     * @return
     */
    public static List getWordCount(String article){
        CharTreeNode root = geneCharTree(article);
        List result = new ArrayList();//此處也可用LinkedList鏈表,以避免數(shù)組滿了擴容導致的性能損失
        getWordCountFromCharTree(result,root);
        Collections.sort(result, new Comparator(){
            public int compare(Object o1, Object o2) {
                WordCount wc1 = (WordCount)o1;
                WordCount wc2 = (WordCount)o2;
                return wc2.getCount() - wc1.getCount();
            }
        });
        return result;
    }
}
/**
 * 單詞樹結點的定義
 * @author FlameLiu
 *
 */
class CharTreeNode{
    int cnt = 0;
    CharTreeNode[] children = new CharTreeNode[26];
}