速度

前陣子在參與小麥注音改版的時候，花了一點時間改進資料檔的載入速度。

在進入正文之前，要岔題解釋一下這個資料檔的作用。小麥注音的資料檔有一個很炫的正式稱呼，叫語言模型 (language model¹)。語言模型賦予每一個字或詞單元一個機率。如果我們蒐集夠多具有代表性的文字紀錄，並根據這些紀錄計算出語言模型，我們就可以拿這個模型來作許多自然語言處理相關的工作。一個常見的工作是根據前面幾個字詞，預測接下來會出現的字詞。如果我們把每個字詞賦予讀音，把讀音當作外顯觀察到的事件，而把書面語的字詞當作隱藏狀態，那麼我們可以把語言模型當成一個隱藏馬可夫模型 (Hidden Markov Model; HMM)，利用 Viterbi 演算法找出最可能符合此一外顯事件的隱藏狀態序列。也就是說：給予一串注音讀音（外顯事件），找出最可能的字詞序列（隱藏狀態），這就是自動選字注音輸入法的問題定義。

小麥注音的資料檔，在執行完資料的 Makefile 步驟後，會編出 data.txt，長相如下：

詞表 ㄘˊ-ㄅㄧㄠˇ -6.67765129
詞條 ㄘˊ-ㄊㄧㄠˊ -6.07559130
...
耶誕 ㄧㄝ-ㄉㄢˋ -4.85467302
公共場所 ㄍㄨㄥ-ㄍㄨㄥˋ-ㄔㄤˇ-ㄙㄨㄛˇ -4.61331063

這個檔案每一行有三個欄位，第一欄是詞，第二欄是讀音，第三欄是該詞在語料中的對數機率。語言模型一般都採用對數機率，這是為了作機率相乘的時候，避免數值過小，導致因算術下溢 (underflow) 造成精度不足的問題。

一般說來，要解析 (parse) 這樣的文字檔並存入記憶體的語言模型中，最方便的方法，是採用以下的虛擬碼：

model = new TreeMap
f = open("data.txt")
while not eof(f):
    line = readline(f)
    writing = read_token(line)
    reading = read_token(line)
    logProb = read_token(line)
    if model.has_key(reading):
        model[reading].add(pair(writing, logProb))
    else:
        model[reading] = array()
        model[reading].add(pair(writing, logProb))

用 C 或 C++ 來寫的話，實際寫出來的程式跟上述相差不會太多。要讀取一個詞項 (token)，通常大家就是用 fscanf()，或是用 std::cin >> token 這樣的方式。

目前的小麥注音大約有 14 萬條目。現在的桌上型電腦，尤其是像晚近推出的 Mac，因為使用了 SSD，再加上現代作業系統通常都採用積極的快取策略，C/C++ 的標準程式庫在檔案串流讀寫上也都有足夠的緩衝處理，根據上述虛擬碼寫出的程式，執行效能也都不會太差了。在我的 2009 年 MacBook Pro，配合 Seagate Momentus XT 混合式硬碟，讀取 14 萬條詞條在小麥注音的 Debug mode 上大約要 1 秒，在 Release mode 大約要 0.7 秒，應該算是不錯了吧？

我們還希望再快一點。

上述的虛擬碼做了很多事情：

• 必須從檔案物件中讀取每一行，這會用到標準程式庫的緩衝區，然後每一次讀取都要建立一個字串（如果用 C++）
• 每個字串都要再被解析為三個詞項
• 字串要被存入搜尋樹中，根據實作不同，搜尋樹可能又會把鍵碼跟鍵值都再作一份拷貝

以上三個項目都各有改進的方法。

以讀取檔案來說，與其透過標準程式庫的串流物件，利用作業系統的記憶體映射檔 (memory-mapped file; mmap)，我們可以跳過標準程式庫的緩衝處理，直接跟作業系統要檔案內容。記憶體映射檔的想法是這樣的：作業系統既然已經有虛擬記憶體的設計，把有限的實體記憶體當作窗口，用來存取比實體記憶體大的次級記憶裝置（磁碟），那麼我們可以指定一段實體記憶體區域，直接對應到某個檔案。mmap 通常是作業系統上讀取檔案最快的方法。

要減少字串拷貝，最好的方法，就是直接使用我們剛剛拿到的那塊記憶體。我們可以使用指標來取代字串物件，用指標指向每一個字串所在位置。不過這樣一來，我們還得利用 C 語言字串以 null (空字符) 結尾的特性，把檔案內容的空白及換行字元，代換為 null。我們仍然免不了要創建指標跟搜尋樹，但是這所涉及的資料量會遠比原來的作法小。

最後的問題是要怎麼直接解析一整塊記憶體，並將空白及換行字元代換為 null。

寫入記憶體的問題簡單。我們在跟作業系統要 mmap 的時候，只要指名我們要的是一塊能寫入的記憶體就行了。

解析的話，我們就沒有程式庫可以幫忙了。我們需要用一個確定有限狀態自動機 (deterministic finite automaton; DFA) 來解決這個問題。解析器的本質是辨識器 (recognizer)：給予特定文法，如果辨識的字串合文法，就正常結束程式，否則就回報錯誤。小麥注音的資料檔，用正則表達式 (regular expression) 來寫，檔案格式的文法是：

\n*(\w+\s\w+\s\w+\n+)*

也就是說，我們的檔案可以有空行，每一行以換行字元 (\n) 結尾，每一行有三個詞項，每個詞項至少要有一個字元，詞項與詞項之間只以一個空白符號作分隔，空白不可以出現在其他地方。為了方便起見，我們只用空白字元 (0x20) 作為空白符號。一般語法的正則表達式 \s 還包括了 tab。

我們可以稍微改寫一下上述的正則表達式，把 a+ （一個或多個 a）改寫成 aa* （一個 a，然後是零個或多個 a），也就是將有用到 + 算子的正則表達式，改寫成只有 Kleene star 的形式：

\n*(\w\w*\s\w\w*\s\w\w*\n\n*)*

然後我們就可以很輕易地將上述正則表達式轉換為 DFA，並且加上紀錄指標的動作。利用辨識器的狀態，加上輸出動作，將一種格式的輸入轉換為另一種消化過的資料，有一個正式的稱呼叫「以語法主導的翻譯」(syntax-directed translation)。我們在辨識過程中，遇到任何不合文法的輸入，就直接回報錯誤並終止解析。

以下就是與上面這則正則表達式相等的 DFA ，我們加上了錯誤狀態（Graphviz 原始碼，點圖可放大）：

接下來我們就可以依據 DFA 來撰寫 C 程式碼，這就是小麥注音的 FastLM.cpp作的事情。在這裡我們還做了一件事情，就是只存三個欄位的字串指標。我們並不在此轉換浮點數，而是在需要的時候才呼叫 atof() 。這是因為每次我們搜尋語言模型時，花在轉換浮點數的時間遠小於搜尋。這樣一來我們可以節省在解析時作轉換的負荷。我們等於是將本來要一開始花費的轉換成本 (也就是所謂的 upfront cost) 延遲到後期來分攤償還 (所謂的 amortize)。

改進之後，小麥注音讀取 14 萬詞條，在我同一台機器上，Debug mode 只需要 0.3 秒，Release mode 只需要 0.25 秒，也就是大約得到了 2.8x-3.3x 的效能提升。

最後一提的是，過去還有一個常用提升效能的方法，是在第一次使用原始資料時，將原始資料讀入資料結構（例如雜湊表或搜尋樹），然後將該資料結構的記憶區塊直接序列化 (serialize) 輸出成二進位檔案。之後使用時，只要直接將該二進位檔讀入，然後將資料結構開頭的指標指向該記憶體區塊就可以。這個作法在這個年代最大的問題是：任何輸入資料都應該要經過驗證（也就是說，任何輸入資料都應該是預設為不可信賴的）。驗證有好幾個作用，例如避免檔案損毀、避免被其他程式有意或無意竄改等等。因此讀入任何序列化檔案，仍然都還是應該作資料完整跟可信度 (integrity) 的檢查，通常這會需要起碼的加總檢查，更敏感一點的場合甚至需要使用密碼學等級的雜湊演算法。加上了這些額外的動作，跟直接解析原始檔並同時建表比起來，能夠節省的時間就不多了。同時序列二進位檔需要撰寫額外的程式碼，在必要的時候（例如原始檔更新時）重建二進位檔，這些都是額外的維護及測試成本。