《漢字輸入技術》PPT課件.ppt

第五章 漢字輸入技術 延邊大學計算機科學與技術系 內容 漢字輸入技術概述 漢字鍵盤輸入技術 漢字鍵盤輸入系統(tǒng) Windows漢字輸入技術 Linux下的漢字輸入系統(tǒng) 一、漢字輸入技術概述 漢字輸入發(fā)展史 漢字輸入分類 漢字輸入技術發(fā)展和應用 1、問題提出 早期，計算機主要通過鍵盤輸入文字信息 在計算機出現以前，西文打字機的鍵盤早 已定型，計算機很自然地利用了打字機鍵 盤這一錄入工具。 在鍵盤上沒有漢字，那么如何才能將漢字 輸入到計算機中？ 2、大鍵盤方案 設計一個漢字大鍵盤。這個漢字大鍵盤上 有幾千個按鍵，每個按鍵對應一個漢字， 漢字按照偏旁部首在鍵盤上分區(qū)排列，以 便于快速檢字。 大鍵盤的思想經過實踐證明是失敗的，它 存在的問題主要是在鍵盤上找字困難，不 能輸入鍵盤上沒有的漢字，設備本身價格 太高等。 3、基于西文鍵盤的漢字編碼輸入 這是到目前為止最成功的計算機漢字輸入方法。 漢字編碼輸入是最早的漢字輸入方法，已知最早的計算機漢 字編碼輸入始于 20世紀 50年代的俄漢機器翻譯研究，但只能 用電報碼或四角號碼做漢字編碼。 在大陸， 1978年 5月上海電工儀器研究所部工程師支秉彝創(chuàng) 造了一種“見字識碼”法，并被上海市內電話局采用，從而 率先使計算機的漢字輸入進入了實用階段。 在港臺及海外，以“王安三角”為發(fā)端，陸續(xù)涌現出“倉 頡”、“嘸蝦米”、“行列”、“唯物”等一大批繁體漢字 輸入法 。 進入 80年代后，在聯(lián)想漢字、四通中文電腦打字機之后中國 的漢字編碼出現了“萬馬奔騰”的局面。在大陸涌現出了五 筆、自然碼、鄭碼、拼音、智能 ABC、智能狂拼、縱橫等上 千種的輸入法。 4、語音輸入 用了多年的鍵盤輸入方式，在 1997年左右 突然受到猛烈的沖擊，各大廠商包括 IBM、 微軟、摩托羅拉、中自、紫光等公司紛紛 推出自己的非特定人語音輸入系統(tǒng)或者連 筆字手寫輸入系統(tǒng)。 美國微軟公司于 1997年 9月在北京推出中文 非特定人連續(xù)語音識別系統(tǒng) ViaVoice。 ViaVoice是目前在市場上占據統(tǒng)治地位的語 音輸入系統(tǒng)。 5、手寫體漢字識別輸入 通過書寫漢字記錄信息已經有幾千年的歷 史，這也是使用漢字的中國人的普遍習慣， 所以手寫識別輸入是符合中國人記錄信息 習慣的。 在 1997年以后就已經有基本實用的手寫漢 字識別輸入系統(tǒng)，其中佼佼者為中自公司 的“漢王 99”、摩托羅拉公司的“慧筆”和 清華紫光公司的“紫光筆”等。 6、印刷體漢字識別輸入 我國對印刷體漢字識別 (簡稱 OCR， Optical Character Recognition)的研究始于 70年代末 80年 代初，經過科研人員幾十多年的辛勤努力，印刷 體漢字識別技術的發(fā)展和應用，已經有了長足進 步。 清華大學電子工程系、中國科學院計算所智能中 心、北京信息工程學院、沈陽自動化研究所等單 位分別研制開發(fā)出實用化的印刷體漢字識別系統(tǒng)。 清華大學電子工程系研制的清華 TH-OCR產品， 占據著最大的市場份額，代表著中文 OCR技術發(fā) 展的潮流。 內容 漢字輸入發(fā)展史 漢字輸入分類 漢字輸入技術發(fā)展和應用 1、分類 漢字的輸入兩大類： 編碼輸入 自然輸入 語音識別輸入 字形識別輸入 手寫體識別輸入 印刷體識別輸入 2、 鍵盤編碼輸入 鍵盤編碼輸入首先把需要輸入計算機的所 有漢字用鍵盤上的若干個按鍵編碼，這些 按鍵組成的序列稱為對應漢字的輸入碼。 通過在鍵盤上輸入某個按鍵序列，并由計 算機中的輸入系統(tǒng)把這個序列轉換為對應 的漢字，從而達到輸入漢字的目的。 優(yōu)點：輸入快速、無需添加額外設備 缺陷：輸入方式和人們使用語言文字的習 慣不符、用戶需要化額外的時間學習等。 3、 語音識別輸入 漢字語音識別輸入利用產生聲音的物理模 型，通過語音分析手段，預先將一些語音 的特征提取出來，并存儲在處理系統(tǒng)中。 當語音信號輸入時，處理系統(tǒng)根據對該信 號所提取的特征參數和所存儲的參考特征 進行比較，通過邏輯判斷方法和“距離” 測量法對語音進行識別。 3、 語音識別輸入（續(xù)） 自然界的聲音和人講話的語音，都是模擬信號， 不能直接輸入計算機，因此在語音輸入的過程中， 我們必須通過語音卡（聲卡）等設備，把模擬的 語音信號轉換為數字語音信號輸入計算機。然后 計算機利用程序對輸入的數字語音信號進行統(tǒng)計、 判斷和識別，并最終把它翻譯成計算機能夠理解 的漢字的內碼信息。 語音識別輸入技術有著廣闊的應用前景 缺點：由于不同人的口音差別較大，語音的準確 識別比較困難 4、 漢字識別輸入 漢字識別輸入根據模式識別原理，通過漢字的字 形信息識別，產生漢字的內碼，實現漢字的識別 輸入。漢字識別輸入的原理是通過抽取代表未知 漢字模式本質的表達形式與預先存儲在計算機中 的標準漢字的模式表達形式的集合逐一進行匹配， 用一定的準則進行判別，找出最接近輸入漢字的 那個標準漢字。 漢字識別輸入技術可分為印刷體漢字識別輸入和 手寫體漢字識別輸入兩大類 。 5、手寫體漢字識別輸入 手寫體識別輸入方法把手寫字的位置信息 首先轉換成二進制的數字編碼信息，并對 手寫字進行智能化的識別，并產生與之匹 配的數字編碼的中文或英文字符，同時所 產生的字符也送給顯示屏顯示，最后經過 輸入者確認后才作為正確的輸入結果。 可分為聯(lián)機手寫漢字識別輸入和脫機手寫 漢字識別輸入 5、手寫體漢字識別輸入（續(xù)） 手寫體識別輸入難于印刷體識別輸入 脫機手寫體識別輸入又難于聯(lián)機手寫體識別輸入 聯(lián)機手寫體識別輸入 是一種人工實時地把漢字輸 入計算機的方法，它利用書寫板把筆畫變?yōu)殡娦?號，輸入計算機的是以坐標點序列表示的筆尖移 動軌跡，因而被處理的是一維的線條（筆畫）串， 這些線條串含有筆畫數目、筆畫走向、筆順和書 寫速度等信息。 脫機手寫漢字識別 處理的僅是二維的漢字點陣圖 象，是漢字識別領域中最后一個十分困難的問題， 目前仍然處于實驗室研究階段。 5、手寫體漢字識別輸入（續(xù)） 6、印刷體識別輸入 印刷體識別輸入是利用掃描器對已有的文書資料 進行掃描，將掃描結果送入計算機中，計算機對 所得圖像進行去污點和干擾、行字切分、二值化、 細化、抽取輪廓、平滑和規(guī)范化等處理，然后再 由計算機根據所得圖像的輪廓與計算機字庫中的 漢字點陣進行匹配，從而轉換成相應的漢字的技 術。 應用范圍：圖像處理、桌面排版、印刷出版、字 符識別、圖文數據庫、廣告美術設計、多媒體圖 文通訊和辦公自動化等。 6、印刷體識別輸入 (續(xù) ) TH-OCR 2000 6、印刷體識別輸入 (續(xù) ) 內容 漢字輸入發(fā)展史 漢字輸入分類 漢字輸入技術發(fā)展和應用 1、 漢字輸入計算機的主流技術漢字鍵 盤輸入技術 鍵盤輸入使用的是人的十個手指，靈活方 便，符合人體工程學原理，絕大多數人愿 意接受這一輸入方式。 鍵盤輸入具有輸入快速、省力、方便等其 它輸入方式無法比擬的優(yōu)點。 隨著計算機技術的發(fā)展，軟件技術彌補了 漢字編碼的很多不足。句子輸入、詞組輸 入、智能輸入等技術使鍵盤漢字輸入系統(tǒng) 更加好用，輸入更加快速方便。 2、 廣泛的應用途徑語音識別輸入技術 語音識別技術的滲透性很強，在未來它將 無處不在 語音撥號 語音查詢 工業(yè)控制 傷殘人設備 家電 計算機輔助教育 3、 數字化時代的新寵漢字識別輸入技 術 隨著手機的普及應用，“拇指經濟”迅速升溫， 人們越來越尋求短信輸入的快捷和方便，手寫又 成為一種時尚，受到人們的青睞。 隨著各種掌上型信息終端及各種智能化、數字化 產品的普及，在人們生活的許多地方，如掌上電 腦、新型智能固定電話、各類平板電腦，甚至是 街頭的 POS機及銀行、車站等的觸摸屏等，都已 大規(guī)模地應用了手寫輸入技術。 二、漢字鍵盤輸入技術 鍵盤 漢字鍵盤輸入原理 鍵盤漢字輸入的總體流程 輸入碼對照表的設計 1、鍵盤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 43 58 30 31 32 33 34 35 36 37 38 39 40 29 42 44 45 46 47 48 49 50 51 52 53 54 57 69 53 55 74 71 72 73 78 75 76 77 79 80 81 29 82 83 2、掃描碼（ Scan Code） 外部設備必須通過控制器和主機連接，所以鍵盤 本身有一個控制器。 鍵盤控制器完成的主要工作是：加電或系統(tǒng)需要 時對鍵盤進行檢測，掃描鍵盤、消除重鍵和自動 重發(fā)，保存掃描代碼，與主機進行雙向通信，以 及向主機傳送按鍵的掃描碼（ Scan Code）等。 所謂掃描碼是指根據按鍵在鍵盤上的位置按照從 左到右，從上到下的原則從 1開始給按鍵編的代碼。 3、鍵盤工作原理 當用戶在鍵盤上按下一個按鍵后，控制器就能通 過掃描矩陣得到按鍵的位置，從而把這個位置信 息轉換為該按鍵的掃描碼，并存儲在控制器的緩 沖區(qū)中。然后控制器產生一個鍵盤的硬件中斷， 由這個硬件中斷通過端口從鍵盤控制器的緩沖區(qū) 中取得這個按鍵的掃描碼，并把它轉換為對應的 ASCII碼，最后把 2個字節(jié)的掃描碼和 ASCII碼存 儲到計算機內存的鍵盤緩沖區(qū)中，供系統(tǒng)使用。 4、部分掃描碼和 ASCII碼表 表 6.1按鍵掃描碼和 ASCII碼對照表（十六進制） 按鍵 掃描 碼 ASCII 按鍵 掃描 碼 ASCII 按鍵 掃描 碼 ASCII A 1E 41 9 0A 39 1A 5B B 30 42 29 60 INSERT E0,52 C 2E 43 - 0C 2D HOME E0,47 D 20 44 = 0D 3D PG UP E0,49 E 12 45 2B 5C DELETE E0,53 F 21 46 BKSP 0E 08 END E0,4F G 22 47 SPACE 39 20 PG DN E0,51 H 23 48 TAB 0F 09 U ARROW E0, 48 I 17 49 CAPS 3A L ARROW E0,4B J 24 4A L SHFT 2A D ARROW E0,50 內容 鍵盤 漢字鍵盤輸入原理 鍵盤漢字輸入的總體流程 輸入碼對照表的設計 1、西文字符的輸入 使用的鍵盤是西文鍵盤，英文或歐洲語系等拼音 文字，由于文字總數一般為幾十個，所以鍵盤上 的按鍵就足以對映到每一個文字。 用西文打字時，敲入的按鍵就可以直接根據當前 的代碼頁（ Code Page）轉換為西文字符的內碼 從而顯示在當前應用程序的窗口中。 如當前是英文鍵盤，那么在鍵盤上按下按鍵“ A” 后，計算機就可以根據英文鍵盤的布局把這個按 鍵轉換為字符“ A”的 ASCII碼，并送給應用程序， 從而在界面上顯示這個字符“ A”。 2、漢字的編碼輸入舉例 3、漢字編碼輸入的前提 要實現把輸入碼轉換成機內碼這個功能必須具備 一個前提條件，那就是輸入系統(tǒng)必須先于應用程 序得到用戶按鍵的掃描碼或 ASCII碼，否則如果應 用程序先得到的話，那它就會對按鍵進行處理， 那樣輸入系統(tǒng)就沒有辦法進行工作了。 從鍵盤接收的按鍵消息是操作系統(tǒng)的 I/O模塊處理 的，它肯定先于應用程序得到按鍵的掃描碼，然 后由它負責把這些掃描碼轉換為 ASCII碼，存放在 鍵盤緩沖區(qū)中，那么只要保證輸入系統(tǒng)先于應用 程序拿到鍵盤緩沖區(qū)中的內容就可以了。 4、鍵盤 HOOK 一般而言，應用程序從鍵盤緩沖區(qū)讀字符，總會調用系統(tǒng) 的讀字符功能來實現的。 通過系統(tǒng)提供的 HOOK（鉤子）機制來實現輸入系統(tǒng)先于 應用程序得到鍵盤按鍵。 鍵盤 hook實現原理： 假設原來的讀字符功能調用是 GetChar() 設計了一個輸入系統(tǒng)，里面由一個函數 NewGetChar() 把 NewGetChar作為一個鉤子鉤到 GetChar上，那么以后應用程序 調用函數 GetChar實際調用的是 NewGetChar 在 NewGetChar中，它實現調用原來的 GetChar函數從緩沖區(qū)讀到 字符，然后把這些字符傳遞給輸入系統(tǒng)，讓輸入系統(tǒng)處理，輸入 系統(tǒng)處理完后，把結果給 NewGetChar，由它把結果返回給應用 程序。 需要注意的是 NewGetChar和 GetChar的參數和返回值應該一致。 5、鍵盤 HOOK原理圖 6、 Windows下的 HOOK HHOOK SetWindowsHookEx(int idHook, HOOKPROC lpfn, HINSTANCE hMod, DWORD dwThreadId); 其中， idHook指定鉤子的類型，常用的有 WH_MOUSE、 WH_KEYBOARD、 WH_GETMESSAGE等，鍵盤操作應該設定為 WH_KEYBOARD lpfn標識鉤子函數的入口地址，當鉤子鉤到任何消息后便調用這個函 數，即當不管系統(tǒng)的哪個窗口有鍵盤輸入馬上會引起 lpfn指向的函數 的動作； hMod 是鉤子函數所在模塊的句柄，我們可以很簡單的設定其為本應 用程序的實例句柄 dwThreadId是鉤子相關函數的 ID用以指定想讓鉤子去鉤哪個線程，為 0時則攔截整個系統(tǒng)的消息。 內容 鍵盤 漢字鍵盤輸入原理 鍵盤漢字輸入的總體流程 輸入碼對照表的設計 1、總體流程圖 2、工作流程 用戶在鍵盤上輸入漢字的輸入碼； 鍵盤控制器在檢測到按鍵后，根據按鍵的位置產生它們 的掃描碼，然后存入鍵盤內的緩沖區(qū)中，并觸發(fā)一個鍵 盤的硬件中斷； 鍵盤中斷處理程序從鍵盤內的緩沖區(qū)中取出掃描碼； 鍵盤中斷處理程序把掃描碼轉換為 ASCII碼，和掃描碼 一起存儲在內存的鍵盤緩沖區(qū)中； 應用程序調用取字符模塊取字符，實際調用的是漢字輸 入處理模塊，漢字輸入處理模塊從內存的鍵盤緩沖區(qū)取 得掃描碼和 ASCII碼。在西文系統(tǒng)中，應用程序可以直 接通過取字符模塊從鍵盤緩沖區(qū)獲得西文字符（）， 從而結束輸入過程； 2、工作流程（續(xù)） 漢字輸入處理模塊判斷讀到的字符，是輸入系統(tǒng) 需要處理的嗎？是則把輸入碼傳送給代碼轉換模 塊；不是則直接返回給應用程序（）（如 F1、 Insert等按鍵，輸入系統(tǒng)不需要處理），結束； 代碼轉換模塊根據輸入碼查輸入碼對照表； 代碼轉換模塊從輸入碼對照表獲得對應的漢字機 內碼； 代碼轉換模塊把漢字機內碼交漢字處理模塊； 漢字處理模塊通過用戶干預后，把漢字機內碼交 應用程序，結束。 內容 鍵盤 漢字鍵盤輸入原理 鍵盤漢字輸入的總體流程 輸入碼對照表的設計 1、輸入碼對照表 輸入碼對照表是漢字鍵盤輸入中的一個重要數據結構，是 漢字輸入碼到機內碼轉換的核心，它反映了漢字輸入碼和 機內碼之間的映射關系。 一般來說，系統(tǒng)有一種輸入法，就需要為它配備一張對照 表，但內碼輸入法是一個特例，它可以根據輸入碼計算出 機內碼，所以不需要對照表。 對照表是以文件的形式存儲在計算機中的，一般一張對照 表就是一個文件，當然也有是由一系列的文件組成的。 對照表一般有兩種類型：字對照表和詞對照表。在字對照 表中，表示的是一個一個漢字和輸入碼的映射關系，而詞 對照表則表示詞（組）和輸入碼的映射關系。 2、 輸入碼對照表 結構的分類 定長結構 變長結構 計算結構 索引結構 其它 4、定長結構 定長結構的每個表項的長度固定。 每個表項一般由有兩個域組成：一個域存放漢字 或詞（組）的機內碼，另一個表項存放此漢字或 詞（組）的輸入碼。 每個域的長度是固定的。如一個表項固定長度為 6 個字節(jié)，其中輸入碼占 4個字節(jié)，漢字占 2個字節(jié)。 由于一個漢字的機內碼一般由 2個字節(jié)構成，所以 字對照表可以采用定長結構。 詞對照表一般不會采用這種結構，是因為詞組長 度不一，容易造成存儲空間的浪費。 4、定長結構（續(xù)）結構 4、定長結構（續(xù)） 檢索方法 掃描法 二分法 假設需要檢索的輸入碼為 S，對照表的表項 數為 N，分別用 ICi， HZi表示第 i表項的輸 入碼和漢字。 4、定長結構（續(xù)） 掃描法： 首先，為了方便檢索，需要把對照表按照輸入 碼的大小從小到大排序。掃描法是指每次查找 都從頭開始，一直找到和 S相同的輸入碼項 i； 然后繼續(xù)往后查找，找到和 S不同的輸入碼項 j； 那么，第 i項到第 j-1項，共 j-i項對應的漢字就是 輸入碼 S對應的重碼集。 最大的比較次數為 N，最小的比較次數為 1，平 均為（ N+1） /2。 4、定長結構（續(xù)）掃描法 4、定長結構（續(xù)） 二分法： 二分算法描述如下： 設置一個值 B=0， E=N； 如果 BE，算法失敗結束；否則 M=(B+E)/2； 然后把 ICM和 S比較； 如果相等，則說明找到了一項，由于輸入碼相等的 漢字是相鄰存放的，所以只要進行前后的掃描，可以 得到所有的輸入碼為 S的漢字，結束； 如果 ICM小于 S，則 B=M+1，轉； 如果 ICM大于 S，則 E=M-1，轉。 4、定長結構（續(xù)）檢索算法 4、定長結構（續(xù)） 二分法的最大的比較次數為 log2N，最小的比較 次數為 1，平均約為 log2N-1。 假設 N=20902，則掃描法的平均比較次數為 (20902+1)/2=10452，而二分法的比較次數為 （ log220902-1 14，明顯比掃描法好。 定長結構的對照表具有表結構簡單，容易構建， 檢索算法簡單等優(yōu)點，但在存儲空間上存在缺陷。 5、 計算結構 計算結構常用于設計字對照表。每個表項對應一 個漢字，表項等長，內容為該漢字對應的輸入碼。 這種結構的對照表的表項必須按照漢字的特定序 列進行排列，不能無序。 一般情況，都是按照漢字內碼進行排序，從而方 便確定每個表項對應的漢字機內碼。 5、 計算結構（續(xù)） 輸入碼 0 1 2 3 n 5、 計算結構（續(xù)） 計算結構舉例 縱橫碼的碼元集合為： 1234567890 碼長為 1 4，是不等長碼。字符集采用 Unicode/ISO 10646-1993。 Unicode內碼從 4E00H到 9FA5H共 20902個漢字。 每個表項的內容是輸入碼，為 1 4個數字，每個 數字可以用 BCD碼來表示，需要 3位（ bits）， 4 個數字則需要 3 4 12位，用 2個字節(jié)表示。如 果數字不足 4位，用全“ 1”位填充 。 5、 計算結構（續(xù)） 1 5 1 4 1 3 1 2 11 1 0 9 8 7 6 5 4 3 2 1 0 第一位碼 元 第二位碼 元 第三位碼 元 第四位碼 元 保留 表項結構 每個表項的大小為 2個字節(jié)。整張對照表總共需要 2 20902=41804個字節(jié)， 按照機內碼的大小從小到大排列。 表 項 2 個 字 節(jié) 輸 入 碼 2 個 字 節(jié) 輸 入 碼 2 個 字 節(jié) 輸 入 碼 2 個 字 節(jié) 輸 入 碼 2 個 字 節(jié) 輸 入 碼 2 個 字 節(jié) 輸 入 碼 2 個 字 節(jié) 輸 入 碼 2 個 字 節(jié) 輸 入 碼 序 號 0 1 25 5 25 6 20 90 0 20 90 1 內 碼 4E 00 4E 01 4E FF 4F 00 9E FF 9F 00 9F A4 9F A5 5、 計算結構（續(xù)） 假設漢字的內碼 hz可以表示為： hz= hzhhzl| hzh R1, hzl R2 R1=R|4EHRFFH R2=R|00HRFFH 從上表我們可以得到序號 i和內碼 hz的關系： i=( hzh-4EH)*0FFH+ hzl 則 hzh i/0FFH+4EH /表示取整 hzl =i mod 0FFH 那么，對照表的檢索過程就是遍歷表的過程，也就是當發(fā)現 第 i項表項和當前輸入碼的 BCD碼一致時，可以通過上面 的計算得到該漢字的機內碼，從而實現轉換過程。 5、 計算結構（續(xù)） 優(yōu)點是節(jié)省空間 上例中的對照表比采用等長結構可以節(jié)省一半的 空間（省了 20902個漢字的空間），但存在需要 遍歷整張對照表的問題 ,比較次數為 N。 當一個漢字有多個編碼時，就存在問題了，需要 設置附加表。 6、 變長結構 每個表項對應一個輸入碼。每個表項有兩 個域：一個域存放輸入碼，另一個域存放 和該輸入碼對應的所有重碼字或詞組集合。 由于第二個表項的內容不定，所以長度無 法確定，造成表項不等長。 這種結構的輸入碼對照表減少了表項的數 目，不需要為每個漢字存放輸入碼，所以 存儲空間相當等長結構有明顯的減少。 6、 變長結構（續(xù)） 以 20902個漢字的縱橫碼對照表為例，定長結構 需要（ 2 2） 20902 83608（字節(jié)）（ 2個字 節(jié)的 BCD輸入碼， 2個字節(jié)的漢字機內碼），而 變長結構只需要 20902 2 6123 2 54050 （字節(jié)）（ 20902個漢字和 6123個 BCD輸入碼）， 比定長結構少了近 30K，超過三分之一。 這種結構存在的問題是檢索時間相對也較長，一 般采用掃描法，需要遍歷整張對照表 。 6、 變長結構（續(xù)） 6、 變長結構（續(xù)） 縱橫碼的不等長對照表結構描述： := := := := := 假設需要檢索的輸入碼為 S，對照表的表項數為 K， 分別用 ICi， LENi， HZi表示第 i表項的輸入碼、漢 字集長度和漢字重碼集合。 6、 變長結構（續(xù)） 6、 變長結構（續(xù)） 假設輸入碼的個數為 K，那么最大的比較次 數為 K，最小的比較次數為 1，所以比較次 數依舊平均為（ K+1） /2。 由于 K比 N小，所以比較次數比等長結構少。 如縱橫碼的例子，變長結構的平均比較次 數是 (6123+1)/2=3062次，而等長結構如采 用掃描法則需要（ 20902 1） /2=10452， 是變長結構的 3倍！ 7、 索引結構 索引是一種最常用的對照表結構，也是一 種高效率的檢索結構。 一般索引結構的對照表分成兩部分：索引 表和碼表。 索引表的表項由兩部分組成：輸入碼和指 針（指向碼表中輸入碼對應的漢字和詞組 的首址）。 碼表的結構基本和變長結構類似。 7、 索引結構（續(xù)） 7、 索引結構（續(xù)） 每個索引表項對應一個碼表項，而且是一對一的 關系，有多少個索引項就有多少個碼表項。 一般而言，索引表中的每一個表項是等長的，而 碼表中的每一個表項長度是不相等的。 索引結構結合了等長和變長的優(yōu)點，通過把輸入 碼和漢字串分開的方法，使得索引表組織類似等 長結構（輸入碼域和指針域的長度一般固定）， 而碼表組織類似于變長結構，從而提高了檢索效 率，也節(jié)省了空間。 7、 索引結構（續(xù)）二分法 7、 索引結構（續(xù)） -舉例 拼音輸入碼為例： 比較等長、變長和索引結構的對照表的對照表大 小和檢索效率。 由于拼音由 21個聲母和 35個韻母組成，不考慮聲 調。所以可以采用壓縮方法來存放輸入碼，用 1 21表示 21個聲母，可以用 5位來表示，用 1 35表 示 35個韻母，可以用 6位來表示，一共 11位，為 了方便起見，共用兩個字節(jié)存放（如果無聲母或 韻母，用 0表示）。 7、 索引結構（續(xù)） -舉例 聲母 b(1) p(2) m(3) f(4) d(5) t(6) n(7) l(8) g(9) k(10) h(11) j(12) q(13) x(14) zh(15) ch(16) sh(17) r(18) z(19) c(20) s(21) 韻母 a(1) o(2) e(3) ai(4) ei(5) ao(6) ou(7) an(8) en(9) ang(10) eng(11) ong(12) i(13) ia(14) ie(15) iao(16) iou(17) ian(18) in(19) iang(20) ing(21) iong(22) u(23) ua(24) uo(25) uai(26) uei(27) uan(28) uen(29) uang(30) ueng(31) v(32) ve(33) van(34) vn(35) 無聲母（ 0） 7、 索引結構（續(xù)） -舉例 等長結構： := := := := 變長結構： := := := := := 7、 索引結構（續(xù)） -舉例 索引結構： := := := := := := := 7、 索引結構（續(xù)） -舉例 三種結構比較表 對照表結構 碼本大小 平均檢索次數 等長結構 20902 4 83608 log220902-1 14(二分法 ) 變長結構 20902 2 417 （ 2 1） 43055 （ 417 1） /2 209 索引結構 20902 2 417 （ 2 2） 43472 log2417-1=8 7、 索引結構（續(xù)）稀疏索引 7、 索引結構（續(xù)）稀疏索引 省略了索引表中的輸入碼部分 索引表的表項是對應于整個編碼空間的，也就是 即使這個輸入碼沒有對應的漢字，仍作為一個表 項存在于索引表中 如某個輸入法的碼元集合為 26個字母，碼長為 4，則應 該有 26 26 26 26 456976個表項 表項的排列是按照輸入碼由小到大的次序來排列，也 就是從“ aaaa”到“ zzzz”， 假如某個輸入碼是 S1S2S3S4，我們可以計算得到此輸 入碼對應的索引表表項的序號 i： i= (S1-a ) 263 (S2-a) 262 (S3-a) 26 S4-a 把序號乘以每個表項的大小就得到了此輸入碼指 向碼表的指針在碼表中的首址 7、 索引結構（續(xù)）稀疏索引 問題 :可能索引表過大 如上面舉的例子，如果每個表項長度為 6個 字節(jié)，那么索引表長度為 456976 6字節(jié)， 約 2.6M字節(jié)的空間。 為了節(jié)省空間，我們一般采用部分索引的 技術 取一個輸入碼中的部分編碼進行索引 7、 索引結構（續(xù)）稀疏索引 假設碼元集合中的碼元數為 m，輸入碼的長度為 n，則每 個索引項的長度 2（假設指針大小為 2個字節(jié)），如果對 i （ i<=n）個字節(jié)輸入碼作索引，那么索引表的長度 TL為： TL=mi*2 即 TL=mi*2 則 i=logmTL/2 一般 TL的大小在 10k左右 當采用數字編碼時 m=10，則 i=3 當采用字母編碼時 m=26，則 i=2 三、漢字鍵盤輸入系統(tǒng) 漢字輸入系統(tǒng)的分類 漢字輸入系統(tǒng)的功能 漢字鍵盤輸入系統(tǒng)的工作流程 1、按系統(tǒng)在計算機中實現的層次 可以分為： 系統(tǒng)層的輸入系統(tǒng) 應用層的輸入系統(tǒng) 2、按操作系統(tǒng)平臺 主要有： DOS下的輸入系統(tǒng) Windows下的輸入系統(tǒng) Linux下的輸入系統(tǒng) Unix下的輸入系統(tǒng) Mac System下的輸入系統(tǒng) 嵌入系統(tǒng)種的的輸入系統(tǒng) 3、按漢字內碼的簡繁 可以分為： 簡體輸入系統(tǒng) 繁體輸入系統(tǒng) 4、按漢字的字符集 分為： GB2312的輸入系統(tǒng) GBK的輸入系統(tǒng) GB18030的輸入系統(tǒng) BIG-5的輸入系統(tǒng) ISO10646的輸入系統(tǒng) 5、按輸入碼類別 分為： 音碼輸入系統(tǒng) 形碼輸入系統(tǒng) 音形碼輸入系統(tǒng) 流水碼輸入系統(tǒng) 內容 漢字輸入系統(tǒng)的分類 漢字輸入系統(tǒng)的功能 漢字鍵盤輸入系統(tǒng)的工作流程 1、漢字 /詞組輸入 單字輸入 我 你 的 詞組輸入 我們 計算機 短語、短句輸入 我的 非常多 不明白 科技是第一生產力 句子輸入 我到飯店去吃飯。 2、候選字 /詞提示和選擇 重碼不可避免 輸入系統(tǒng)必須具備候選字 /詞提示的功能 應該常用用字、詞在前 提高容錯的功能 3、中英文狀態(tài)切換 存在中文和英文兩種狀態(tài) 在中文狀態(tài)，可以通過輸入漢字輸入碼輸 出漢字 在英文文狀態(tài)下，整個鍵盤都是西文符號 4、翻頁 當輸入的漢字輸入碼對應的候選字 /詞比較 多時，輸入系統(tǒng)無法在候選框中顯示所有 的候選字 /詞，只能通過分頁方式顯示。 可使用到翻頁鍵顯示上 /下一頁的候選字 /詞。 常用的翻頁鍵分為前翻頁鍵和后翻頁鍵， 一般輸入系統(tǒng)的前 /后翻頁鍵為“ -”和“ +”、 “ ,”和“ .”、“ ”和“ ”、“ PageUp”和 “ PageDown”等。 5、輸入碼清除、刪除、結束鍵 當輸入的輸入碼有誤時，可以通過輸入碼 刪除鍵刪除剛輸入的這個輸入碼符，也可 以通過輸入碼清除鍵刪除所有輸入的輸入 碼。實際上這兩個鍵的作用是提供一種輸 入碼的簡單編輯功能。 絕大多數的輸入系統(tǒng)不需要輸入碼結束符， 只有輸入碼鍵和選擇鍵沖突時才需要輸入 碼結束符來區(qū)分兩種狀態(tài)。 6、聯(lián)想 當用戶輸入了一個漢字后，系統(tǒng)提示以這 個漢字為首字的詞組供用戶選擇（不包括 首字），這種技術稱為聯(lián)想技術。 如用戶輸入了“計”，則系統(tǒng)提示以“計” 作為首字的詞組剩余部分，如“算機”、 “劃”和“策”等 8、全角和半角 鍵盤上的西文字符在輸入計算機時有全角和半角 兩種方式。 在早期 DOS系統(tǒng)下， ASCII字符是中文字符的一 半大小，所以稱 ASCII字符為半角字符 采用雙字節(jié)內碼、和中文等寬的西文字符為全角 字符。 如半角字符“ 0”的 ASCII碼是 30H，而全角字符 “”的 Unicode內碼是 0FF10H。 在 Windows等系統(tǒng)中，由于是圖形界面，所有的 字符不是等寬字符，所以一個 ASCII字符不再是一 個中文內碼字符的一半。 9、符號輸入 符號 按鍵 符號 按鍵 符號 按鍵 。 . ？ ? “” “” ， , ： : 、 ； ; ！ ! % 內容 漢字輸入系統(tǒng)的分類 漢字輸入系統(tǒng)的功能 漢字鍵盤輸入系統(tǒng)的工作流程 1、流程圖 2、中文輸入和西文輸入的差異 從以上的流程我們可以發(fā)現，在西文環(huán)境下，用 戶每按下一個按鍵應用程序都會接收到。而在中 文環(huán)境下，用戶按下一個按鍵后，應用程序可能 接收不到任何的東西，因為輸入系統(tǒng)還沒有機內 碼返回，需要更多的按鍵后才能有機內碼返回。 如圖 6.7所示，用戶輸入“ w”和“ o”后，輸入系統(tǒng) 沒有輸出漢字“我”，必須等到用戶再輸入“ 1” 后，才有漢字輸出。這也是漢字輸入和西文輸入 的最大差異。 Windows漢字輸入技術 Windows漢字輸入技術概述 Windows下漢字輸入原理 在 SDK和 DDK環(huán)境下開發(fā)輸入系統(tǒng) 1、界面 2、概念 輸入法 Windows中的漢字輸入法稱為 IME(Input Method Editor)，它的本質是一個轉換引擎，通過查字典方式， 把鍵盤輸入的按鍵消息轉換為各種語言的文字信息。 另外，它還提供和用戶、操作系統(tǒng)的接口。 輸入法管理器 輸入法管理器簡稱為 IMM（ Input Method Manager）， 它是一個管理各種 IME，并在 IME和應用程序間進行通 信的系統(tǒng)部件。它不僅為程序員提供了開發(fā)輸入法的 接口，還為用戶提供了管理輸入法的界面。 2、 概念（續(xù)） 2、 概念（續(xù)） 多文種環(huán)境（ Multi-lingual Environment） 所謂多文種環(huán)境是指系統(tǒng)可以為使用各種不同語言文字體系的用 戶提供了支撐他們母語的操作環(huán)境。 Windows的輸入體系支持多 文種環(huán)境，包括中文、日文、韓文、法語和德語等上百種不同的 語言體系。也就是說，在 Windows下，不僅可以輸入漢字，也可 以輸入其它語言文字。漢語言文字僅是其中的一個環(huán)境而言。 鍵盤布局（ Keyboard Layout） 鍵盤布局規(guī)定了鍵盤上每個按鍵的物理位置以及每個按鍵對應的 字符。每個鍵盤布局對應于一種語言，從而根據這種語言的定義 和當前的輸入法把按鍵轉換為該語言的文字信息。 在 Windows中，提供了多種不同的鍵盤布局，其中就包括各種中 文的鍵盤布局。每個漢字輸入法就是一個鍵盤布局，如輸入法 “智能 ABC”的鍵盤布局是“ E004804”，通過注冊表編輯器可以查 看各種輸入法的鍵盤布局 2、 概念（續(xù)） 3、特點 每個輸入法只是整個多文種環(huán)境的一個部件而已， 一個多文種環(huán)境包含多個輸入法，如在 Windows XP中，多文種環(huán)境可以包含中文（中國大陸）、 中文（中國香港）、中文（中國臺灣）、日文、 韓文等環(huán)境，每個環(huán)境可以有自己的輸入法； 每個應用程序都擁有自己的一個活動輸入法，也 就是說，輸入法不再為所有的應用程序所共有， 同樣的一個輸入法，可能運行多個實例； 應用程序和輸入法之間可以進行消息的傳遞，應 用程序可以控制輸入法的工作； 支持從漢字詞組到編碼的反向轉換。 內容 Windows漢字輸入技術概述 Windows下漢字輸入原理 在 SDK和 DDK環(huán)境下開發(fā)輸入系統(tǒng) 1、 Windows漢字輸入模型 2、 Windows漢字輸入系統(tǒng)基本結構 3、 Windows漢字輸入原理 當用戶在鍵盤上按下一個鍵后，在應用程序調用 GetMessage/PeekMessage前，系統(tǒng)首先調用輸入法的接口函數 ImeProcessKey，通過這個函數判別輸入法是否需要處理這個鍵， 把這個鍵吃掉； 如果返回 TRUE，表示輸入法需要處理這個鍵，那么系統(tǒng)設置虛鍵 的值為 VK_PROCESSKEY，然后應用程序接收到消息 WM_KEYDOWN，其中的值為 VK_PROCESSKEY；如果返回 FALSE，則表示輸入法不需要處理這個鍵，直接返回此鍵給應用程 序，結束； 當應用程序接收到消息 WM_KEYDOWN后，在調用函數 TranslateMessage時，系統(tǒng)把用戶按下鍵的掃描碼和虛鍵傳遞給輸 入法的接口函數 ImeToAsciiEx。 輸入法在處理了按鍵后，根據處理方法的不同把各種消息存放在消 息緩沖區(qū)中，這個緩沖區(qū)是作為函數 ImeToAsciiEx的一個參數傳遞 過來的。 應用程序在消息隊列中得到由輸入法產生的消息，進行相應的處理。 如果應用程序不處理這些消息，則把它傳遞給默認窗口（ Default Window），然后由系統(tǒng)就把消息傳遞給默認的 IME窗口，由它來 處理這些消息。 內容 Windows漢字輸入技術概述 Windows下漢字輸入原理 在 SDK和 DDK環(huán)境下開發(fā)輸入系統(tǒng) 在 SDK和 DDK環(huán)境下開發(fā)輸入系統(tǒng) 為了方便編程人員開發(fā)基于 Windows的各種驅動 程序， Microsoft提供了一套用于開發(fā)的 DDK工具 包，利用這套工具包就可以開發(fā)輸入法。在 DDK 中，不僅提供了輸入法的開發(fā)環(huán)境，還提供了相 關文檔以及一個區(qū)位輸入法的實例代碼。這個區(qū) 位輸入法經編譯后，可以安裝在 Windows中。 在 DDK中的區(qū)位輸入法的代碼，為我們設計其它 的輸入法提供了基礎，我們設計新的輸入法主要 就是在這個區(qū)位輸入法的代碼基礎上進行修改， 這樣可以大大節(jié)省開發(fā)時間。