-
Notifications
You must be signed in to change notification settings - Fork 77
程式架構_Gramambular
Gramambular 是小麥注音當中的選字引擎。由於對於小麥的開發者來說，想要蒐集 Ngram 的資料相當困難，我們只整理出了 Unigram 的詞庫，Gramambular 的演算法也只支援 Unigram。
Gramambular 的主要資料結構包括 Node、Span、Grid 等。
- Node：用來代表一個字詞（平時大概會用 Phrase 或 Syllable 稱呼），包含這個詞的讀音、對應到的中文字詞、以及出現的頻率等資訊。
- Span：代表相同長度的詞的集合，比方說，當我們有一個長度為 3 的 Span，代表這個 Span 下會有多個三字詞的 Node。
- Grid：是 Span 的集合。比方說，我們現在在輸入緩衝區當中，輸入了十個注音，那麼這個 Grid 的大小就是 10，而在 1 到 10 的位置上。就會插入多個長度不一的 Span。
Grid 包含 Span，Span 內包含 Node。
比方說，如果我們想輸入下面這個句子：「在我平凡無奇的日子裡」，那麼 Grid 就會呈現成以下的結果：
| 注音 | ㄗㄞ ˋ | ㄨㄛ ˇ | ㄆㄧㄥ ˊ | ㄈㄢ ˊ | ㄨ ˊ | ㄑㄧ ˊ | ㄉㄜ ˙ | ㄖ ˋ | ㄗ ˙ | ㄌㄧ ˇ |
|---|---|---|---|---|---|---|---|---|---|---|
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 4 字 Span | 平凡無奇 | |||||||||
| 3 字 Span | 日子裡 | |||||||||
| 2 字 Span | 平凡 | 凡無 | 日子 | 梓里 | ||||||
| 1 字 Span | 在 | 我 | 平 | 繁 | 無 | 其 | 的 | 日 | 子 | 理 |
Gramambular 當中還有另外一個叫做 Walker 的 class，則從這樣的結構中，找出各種可能的路徑，找出每個路徑上的分數，並且將分數最蒿的路徑當成最後的結果。以上面的例子來說，就會有以下結果：
| 分數 | 路徑 |
|---|---|
| -18.65265033 | 在(-2.23651546) -> 我(-2.27257609) -> 平凡無奇(-6.67803313) -> 的(-1.62142821) -> 日子裡(-5.84409744) |
| -20.058111410000002 | 在(-2.23651546) -> 我(-2.27257609) -> 平凡無奇(-6.67803313) -> 的(-1.62142821) -> 日子(-4.31095122) -> 理(-2.9386073) |
| -21.45032334 | 在(-2.23651546) -> 我(-2.27257609) -> 平凡無奇(-6.67803313) -> 的(-1.62142821) -> 日(-2.91157897) -> 子(-2.79158418) -> 理(-2.9386073) |
| -23.07941185 | 在(-2.23651546) -> 我(-2.27257609) -> 平凡(-5.13953417) -> 無(-3.06378057) -> 其(-2.90147991) -> 的(-1.62142821) -> 日子裡(-5.84409744) |
| -24.48487293 | 在(-2.23651546) -> 我(-2.27257609) -> 平凡(-5.13953417) -> 無(-3.06378057) -> 其(-2.90147991) -> 的(-1.62142821) -> 日子(-4.31095122) -> 理(-2.9386073) |
| -25.34441624 | 在(-2.23651546) -> 我(-2.27257609) -> 平(-3.26688126) -> 繁(-4.1376573) -> 無(-3.06378057) -> 其(-2.90147991) -> 的(-1.62142821) -> 日子裡(-5.84409744) |
| -25.409617339999997 | 在(-2.23651546) -> 我(-2.27257609) -> 平(-3.26688126) -> 凡無(-7.26663897) -> 其(-2.90147991) -> 的(-1.62142821) -> 日子裡(-5.84409744) |
| -25.87708486 | 在(-2.23651546) -> 我(-2.27257609) -> 平凡(-5.13953417) -> 無(-3.06378057) -> 其(-2.90147991) -> 的(-1.62142821) -> 日(-2.91157897) -> 子(-2.79158418) -> 理(-2.9386073) |
| -26.749877320000003 | 在(-2.23651546) -> 我(-2.27257609) -> 平(-3.26688126) -> 繁(-4.1376573) -> 無(-3.06378057) -> 其(-2.90147991) -> 的(-1.62142821) -> 日子(-4.31095122) -> 理(-2.9386073) |
| -26.81507842 | 在(-2.23651546) -> 我(-2.27257609) -> 平(-3.26688126) -> 凡無(-7.26663897) -> 其(-2.90147991) -> 的(-1.62142821) -> 日子(-4.31095122) -> 理(-2.9386073) |
| -28.142089249999998 | 在(-2.23651546) -> 我(-2.27257609) -> 平(-3.26688126) -> 繁(-4.1376573) -> 無(-3.06378057) -> 其(-2.90147991) -> 的(-1.62142821) -> 日(-2.91157897) -> 子(-2.79158418) -> 理(-2.9386073) |
| -28.20729035 | 在(-2.23651546) -> 我(-2.27257609) -> 平(-3.26688126) -> 凡無(-7.26663897) -> 其(-2.90147991) -> 的(-1.62142821) -> 日(-2.91157897) -> 子(-2.79158418) -> 理(-2.9386073) |
總共有 12 種組合。由於「在|我|平凡無奇|的|日子裡」的分數最高，所以我們就當成最後的計算結果。
因為我們只有 Unigram 的資料，所以即使讀音是「ㄗㄞ ˋ」的字詞還包括「再」、「載」等，但我們就直接挑選分數最蒿的「在」，無法考慮在某些前後文當中更有可能是「再」或「載」。一些比較容易連續出現的字詞，我們直接簡單地合併成多字詞，像是上面例子中的「日子裡」。
每個字詞是這個字詞在整個語言模型，也就是小麥注音作者所能夠蒐集到的中文語料中，這個字詞出現可能性，是一個 Log 值。以「在」這個詞來看，分數是 -2.23651546，是 10 的 -2.23651546 次方，換算成十進位數字，大概是 0.005800755226466948。如果我們有一份一百萬字的語料，就是「在」出現了 5800 次。而整條路徑的最後分數，其實都是非常小的數字。
請參考我們之前在 X 上的說明
當用戶進行選字之後，我們會把被選擇的 Node 的分數設定成正值，確保其他的 Node 不可能比被選擇的字詞的分數更高。當我們發現某個 index 有這樣的 Node 時，就直接採用這個 Node。
- 用戶先輸入一個正確的注音組合
- 擴大 Grid 大小
- 根據輸入的注音組合與鄰近的注音，從語言模型中，搜尋是否有符合的字詞
- 根據不同長度的字詞建立 Span，然後在 Span 內插入 Node
- 執行 Walker 計算最佳路徑
- 清除特定位置的所有 Span
- 縮小 Grid 大小
- 執行 Walker 計算最佳路徑