nota.lukhnos.org

速度

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

在進入正文之前,要岔題解釋一下這個資料檔的作用。小麥注音的資料檔有一個很炫的正式稱呼,叫語言模型 (language model1)。語言模型賦予每一個字或詞單元一個機率。如果我們蒐集夠多具有代表性的文字紀錄,並根據這些紀錄計算出語言模型,我們就可以拿這個模型來作許多自然語言處理相關的工作。一個常見的工作是根據前面幾個字詞,預測接下來會出現的字詞。如果我們把每個字詞賦予讀音,把讀音當作外顯觀察到的事件,而把書面語的字詞當作隱藏狀態,那麼我們可以把語言模型當成一個隱藏馬可夫模型 (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 秒,應該算是不錯了吧?

我們還希望再快一點。

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

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

以讀取檔案來說,與其透過標準程式庫的串流物件,利用作業系統的記憶體映射檔 (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) 的檢查,通常這會需要起碼的加總檢查,更敏感一點的場合甚至需要使用密碼學等級的雜湊演算法。加上了這些額外的動作,跟直接解析原始檔並同時建表比起來,能夠節省的時間就不多了。同時序列二進位檔需要撰寫額外的程式碼,在必要的時候(例如原始檔更新時)重建二進位檔,這些都是額外的維護及測試成本。


  1. n-gram 語言模型以及如何將 HMM 應用到語言模型,可參考 Dan Jurafsky 與 James Martin 的教科書 "Speech and Language Processing" (2008)。