字串遊戲 -- 如何快速計算文章中每個字出現的次數?

最近讀了 Bentley 所寫的 Programming Pearls 的專欄15，討論的主題為字串。這本書在台灣的能見度似乎不高，基峰出了一本中譯本之後很快就絕版了，想買都買不到，現在我手上是一本英文版加上朋友從借來的中譯版:)
這本是值得一看的好書，強烈推薦。

看完專欄15後，忍不住手癢動手實驗一下。
第一小節的問題是，給你英文聖經的電子檔，請找出書中一共有多少個單字? 出現頻率最高的單字為何?

首先我到 http://printkjv.ifbweb.com/ 下載整本文字檔格式的聖經
此版本的聖經共有 4,397,206 個字元。

書中提供的第一個小程式是 C++ 版本，使用 map 作為存放單字的資料結構。map 的實作為平衡二元搜尋樹，所以加入單字或是尋找已出現過的單字的複雜度都為 O(log n)。
以下的程式是我稍微修改過的版本:

inline bool isletter(char c)
{
  return (c>='a' && c<='z') || (c>='A' && c<='Z');
}
string trim_nonword_char(string s)
{
  string sout;
  for(unsigned int a=0; a<s.size(); a++)
    if (isletter(s[a]))
  sout.push_back(s[a]);
  return sout;
}
void main(void)
  typedef map<string, int> mymap;
  mymap M;
  mymap::iterator j;
  string t;
  while(cin >> t)
  {
    string tb = trim_nonword_char(t);
    if (tb.size() > 0)
      M[tb]++;
  }
  int totalwords = 0;
  for (j=M.begin(); j != M.end(); j++)
  {
    cout << j->first << " " << j->second << "\n";
    totalwords += j->second;
  }
  cout << "Total number of words = " << totalwords << endl;
}

我們的mymap中，key的型態是string，而value的型態是int，用來儲存出現次數。18~23行從標準輸入讀入一個word，去除非英文字母字元後放入map之中。利用了map的強大能力，緊緊短短數行程式就完成了這個工作。25~29行印出每個word和他出現的次數，由於採用二元搜尋樹的實作，你會發現 word 是依照順序由小到大排序的。

至於第二個問題，如何依照找出頻率最高的單字，Bentley 建議可以使用另外一個map，使用頻率做為key，出現的單字做為value。由於數個單字有可能出現相同次數，所以我們使用 vector<string> 做為value來儲存這些單字。依此實做的C++程式僅有四行。

map<int, vector<string>> cmap;
for (j=M.begin(); j != M.end(); j++)
{
    cmap[j->second].push_back(j->first);
}

注意map的順序是由小到大，所以cmap裡面最後面才是出現字數最多的單字。

現在我們可以回答開頭的問題:此檔案共有804875個單字，其中有14683個不重複單字，出現頻率最高的十個單字為:


62910 the
39290 and
35055 of
13783 to
12884 that
12863 And
12547 in
9773 shall
9756 he
8985 unto

在我的電腦上處理這個檔案所花的時間為1.1秒，拜硬體的進步所賜，比起 Bentley 十年前所得到的7.6秒快了近十倍。

這就是最快的方法了嗎? 非也，Bentley在書中提到可以用 hash 取代 map 來加快速度。