用霍夫曼編碼改善多鍵鍵盤輔具之輸入速度

一般市面上最多人用的QWERTY鍵盤幾乎每個字符都只要按一個按鍵就能完成輸入，但近百字符擠在鍵盤上造成按鍵間距非常地小，所以不適用於上肢有障礙的使用者。上肢障礙使用者所用的輔具鍵盤按鍵間距必須夠大才不會錯按字符，所以必須減少鍵盤上的按鍵數，但按鍵數減少會造成許多字符需要兩個以上的按鍵組合才能完成輸入，這時鍵盤所用的輸入法就顯得非常的重要，好的輸入法可以增快打字輸入速度，進而幫使用者節省許多時間和體力。本研究係特別為一位重度徐動型腦性麻痺的上肢障礙者量身打造一套適合的12鍵輸入法。我們使用霍夫曼演算法來為每個字符編碼，因為輔具鍵盤有12個按鍵，所以霍夫曼演算法的根設為12。12個按鍵對應到12種編碼，每個字符為這12種按鍵編碼的不同組合。霍夫曼演算法根據受測者平常記錄的每個字符出現頻率來決定它的編碼，越常出現的字符編碼的長度就會越短。最常用的幾個字符甚至編碼長度只有1，也就是這些常用字符只需要一個按鍵就能完成輸入。我們用霍夫曼演算法為每個字符編完碼後，套入每個字符出現的頻率，每個字符平均只要1.48個按鍵就能完成輸入，省下使用者許多要打的按鍵數量。在本論文中我們使用粒子群最佳化演算法(Particle Swarm Optimization) 處理鍵盤配置的問題，依據受測者之前記錄的每個按鍵被按的相關機率和每個按鍵被按所需的相關時間來作為評估函數，找出鍵盤按鍵近似於最佳的配置，以節省受測者使用鍵盤所需的體力和時間。在本研究中我們比較三種不同的輸入法，包括霍夫曼輸入法、雙擊輸入法、還有此一受測者慣用的六鍵摩斯碼輸入法鍵盤。最後我們請受測者使用英文打字速度檢定軟體來比較三種輸入法的輸入速度。此軟體會使用平均每分鐘幾個字(word) 來分出不同輸入法速度的快慢。經過了逐天的測驗，實驗結果顯示到了最後霍夫曼輸入法平均每分鐘字數會比雙擊輸入法和摩斯碼輸入法還多。因此對於本實驗的受測者來說，使用我們所設計的霍夫曼輸入法鍵盤的打字速度會是最快的。

關鍵字

霍夫曼演算法；輸入法；打字輸入速度；按鍵配置

並列摘要

In a conventional keyboard, like a QWERTY keyboard, there are too many keys such that the spaces between neighboring keys are too small for physical disabled. In this study we propose a novel prosthetic keyboard with reduced number of keys such that the space between neighboring keys is sufficient for physically disabled. Given only 12 keys in the designed keyboard, multiple keystrokes are required for inputting a character. Each character in encoded by using radix-12 Huffman algorithm. The code set of each character is determined by its appearance frequency in a typical typing task. The higher appearance frequency of a character, the shorter its code set. Experiments with a subject with cerebral palsy showed that the average code length of all characters is 1.48 keys per character. Given the codes sets, this study further propose a method to find the optimal keyboard arrangement using Particle Swarm Optimization (PSO) algorithm. Given the appearance frequency of each key in a typical typing task, the objective function is based on the total time required for the subject to press the keys. The optimal keyboard arrangement is one that minimizes the objective function using PSO algorithm. Experiments were conducted to compare the performances of three different input methods, including the proposed Huffman method, the dual key method, and a 6-key Mose Code method. The Mose Code input method has been used by the subject for years. A commonly-used typing speed test software was used to record the typing speed of the subject. Results showed that the proposed Huffman method can help the subject to achieve more words per minutes than other two methods.