第六章 漢字輸入技術(shù)

第六章漢字輸入技術(shù)

內(nèi)容漢字輸入技術(shù)概述漢字鍵盤輸入技術(shù)漢字鍵盤輸入系統(tǒng)Windows漢字輸入技術(shù)Linux下的漢字輸入系統(tǒng)

一、漢字輸入技術(shù)概述內(nèi)容漢字輸入發(fā)展史漢字輸入分類漢字輸入技術(shù)發(fā)展和應(yīng)用1、問題提出早期，計算機主要通過鍵盤輸入文字信息在計算機出現(xiàn)以前，西文打字機的鍵盤早已定型，計算機很自然地利用了打字機鍵盤這一錄入工具。在鍵盤上沒有漢字，那么如何才能將漢字輸入到計算機中？2、大鍵盤方案設(shè)計一個漢字大鍵盤。這個漢字大鍵盤上有幾千個按鍵，每個按鍵對應(yīng)一個漢字，漢字按照偏旁部首在鍵盤上分區(qū)排列，以便于快速檢字。大鍵盤的思想經(jīng)過實踐證明是失敗的，它存在的問題主要是在鍵盤上找字困難，不能輸入鍵盤上沒有的漢字，設(shè)備本身價格太高等。3、基于西文鍵盤的漢字編碼輸入這是到目前為止最成功的計算機漢字輸入方法。漢字編碼輸入是最早的漢字輸入方法，已知最早的計算機漢字編碼輸入始于20世紀(jì)50年代的俄漢機器翻譯研究，但只能用電報碼或四角號碼做漢字編碼。在大陸，1978年5月上海電工儀器研究所部工程師支秉彝創(chuàng)造了一種“見字識碼”法，并被上海市內(nèi)電話局采用，從而率先使計算機的漢字輸入進入了實用階段。在港臺及海外，以“王安三角”為發(fā)端，陸續(xù)涌現(xiàn)出“倉頡”、“嘸蝦米”、“行列”、“唯物”等一大批繁體漢字輸入法。進入80年代后，在聯(lián)想漢字、四通中文電腦打字機之后中國的漢字編碼出現(xiàn)了“萬馬奔騰”的局面。在大陸涌現(xiàn)出了五筆、自然碼、鄭碼、拼音、智能ABC、智能狂拼、縱橫等上千種的輸入法。4、語音輸入用了多年的鍵盤輸入方式，在1997年左右突然受到猛烈的沖擊，各大廠商包括IBM、微軟、摩托羅拉、中自、紫光等公司紛紛推出自己的非特定人語音輸入系統(tǒng)或者連筆字手寫輸入系統(tǒng)。美國微軟公司于1997年9月在北京推出中文非特定人連續(xù)語音識別系統(tǒng)ViaVoice。ViaVoice是目前在市場上占據(jù)統(tǒng)治地位的語音輸入系統(tǒng)。5、手寫體漢字識別輸入通過書寫漢字記錄信息已經(jīng)有幾千年的歷史，這也是使用漢字的中國人的普遍習(xí)慣，所以手寫識別輸入是符合中國人記錄信息習(xí)慣的。在1997年以后就已經(jīng)有基本實用的手寫漢字識別輸入系統(tǒng)，其中佼佼者為中自公司的“漢王99”、摩托羅拉公司的“慧筆”和清華紫光公司的“紫光筆”等。6、印刷體漢字識別輸入我國對印刷體漢字識別(簡稱OCR，OpticalCharacterRecognition)的研究始于70年代末80年代初，經(jīng)過科研人員幾十多年的辛勤努力，印刷體漢字識別技術(shù)的發(fā)展和應(yīng)用，已經(jīng)有了長足進步。清華大學(xué)電子工程系、中國科學(xué)院計算所智能中心、北京信息工程學(xué)院、沈陽自動化研究所等單位分別研制開發(fā)出實用化的印刷體漢字識別系統(tǒng)。清華大學(xué)電子工程系研制的清華TH-OCR產(chǎn)品，占據(jù)著最大的市場份額，代表著中文OCR技術(shù)發(fā)展的潮流。內(nèi)容漢字輸入發(fā)展史漢字輸入分類

漢字輸入技術(shù)發(fā)展和應(yīng)用1、分類漢字的輸入兩大類：編碼輸入自然輸入語音識別輸入字形識別輸入手寫體識別輸入印刷體識別輸入2、鍵盤編碼輸入

鍵盤編碼輸入首先把需要輸入計算機的所有漢字用鍵盤上的若干個按鍵編碼，這些按鍵組成的序列稱為對應(yīng)漢字的輸入碼。通過在鍵盤上輸入某個按鍵序列，并由計算機中的輸入系統(tǒng)把這個序列轉(zhuǎn)換為對應(yīng)的漢字，從而達(dá)到輸入漢字的目的。優(yōu)點：輸入快速、無需添加額外設(shè)備缺陷：輸入方式和人們使用語言文字的習(xí)慣不符、用戶需要化額外的時間學(xué)習(xí)等。3、語音識別輸入

漢字語音識別輸入利用產(chǎn)生聲音的物理模型，通過語音分析手段，預(yù)先將一些語音的特征提取出來，并存儲在處理系統(tǒng)中。當(dāng)語音信號輸入時，處理系統(tǒng)根據(jù)對該信號所提取的特征參數(shù)和所存儲的參考特征進行比較，通過邏輯判斷方法和“距離”測量法對語音進行識別。3、語音識別輸入（續(xù)）自然界的聲音和人講話的語音，都是模擬信號，不能直接輸入計算機，因此在語音輸入的過程中，我們必須通過語音卡（聲卡）等設(shè)備，把模擬的語音信號轉(zhuǎn)換為數(shù)字語音信號輸入計算機。然后計算機利用程序?qū)斎氲臄?shù)字語音信號進行統(tǒng)計、判斷和識別，并最終把它翻譯成計算機能夠理解的漢字的內(nèi)碼信息。語音識別輸入技術(shù)有著廣闊的應(yīng)用前景缺點：由于不同人的口音差別較大，語音的準(zhǔn)確識別比較困難4、漢字識別輸入漢字識別輸入根據(jù)模式識別原理，通過漢字的字形信息識別，產(chǎn)生漢字的內(nèi)碼，實現(xiàn)漢字的識別輸入。漢字識別輸入的原理是通過抽取代表未知漢字模式本質(zhì)的表達(dá)形式與預(yù)先存儲在計算機中的標(biāo)準(zhǔn)漢字的模式表達(dá)形式的集合逐一進行匹配，用一定的準(zhǔn)則進行判別，找出最接近輸入漢字的那個標(biāo)準(zhǔn)漢字。漢字識別輸入技術(shù)可分為印刷體漢字識別輸入和手寫體漢字識別輸入兩大類。5、手寫體漢字識別輸入手寫體識別輸入方法把手寫字的位置信息首先轉(zhuǎn)換成二進制的數(shù)字編碼信息，并對手寫字進行智能化的識別，并產(chǎn)生與之匹配的數(shù)字編碼的中文或英文字符，同時所產(chǎn)生的字符也送給顯示屏顯示，最后經(jīng)過輸入者確認(rèn)后才作為正確的輸入結(jié)果?？煞譃槁?lián)機手寫漢字識別輸入和脫機手寫漢字識別輸入5、手寫體漢字識別輸入（續(xù)）手寫體識別輸入難于印刷體識別輸入脫機手寫體識別輸入又難于聯(lián)機手寫體識別輸入聯(lián)機手寫體識別輸入是一種人工實時地把漢字輸入計算機的方法，它利用書寫板把筆畫變?yōu)殡娦盘?，輸入計算機的是以坐標(biāo)點序列表示的筆尖移動軌跡，因而被處理的是一維的線條（筆畫）串，這些線條串含有筆畫數(shù)目、筆畫走向、筆順和書寫速度等信息。脫機手寫漢字識別處理的僅是二維的漢字點陣圖象，是漢字識別領(lǐng)域中最后一個十分困難的問題，目前仍然處于實驗室研究階段。5、手寫體漢字識別輸入（續(xù)）6、印刷體識別輸入印刷體識別輸入是利用掃描器對已有的文書資料進行掃描，將掃描結(jié)果送入計算機中，計算機對所得圖像進行去污點和干擾、行字切分、二值化、細(xì)化、抽取輪廓、平滑和規(guī)范化等處理，然后再由計算機根據(jù)所得圖像的輪廓與計算機字庫中的漢字點陣進行匹配，從而轉(zhuǎn)換成相應(yīng)的漢字的技術(shù)。應(yīng)用范圍：圖像處理、桌面排版、印刷出版、字符識別、圖文數(shù)據(jù)庫、廣告美術(shù)設(shè)計、多媒體圖文通訊和辦公自動化等。6、印刷體識別輸入(續(xù))TH-OCR20006、印刷體識別輸入(續(xù))內(nèi)容漢字輸入發(fā)展史漢字輸入分類漢字輸入技術(shù)發(fā)展和應(yīng)用

1、漢字輸入計算機的主流技術(shù)－漢字鍵盤輸入技術(shù)鍵盤輸入使用的是人的十個手指，靈活方便，符合人體工程學(xué)原理，絕大多數(shù)人愿意接受這一輸入方式。鍵盤輸入具有輸入快速、省力、方便等其它輸入方式無法比擬的優(yōu)點。隨著計算機技術(shù)的發(fā)展，軟件技術(shù)彌補了漢字編碼的很多不足。句子輸入、詞組輸入、智能輸入等技術(shù)使鍵盤漢字輸入系統(tǒng)更加好用，輸入更加快速方便。2、廣泛的應(yīng)用途徑－語音識別輸入技術(shù)語音識別技術(shù)的滲透性很強，在未來它將無處不在語音撥號語音查詢工業(yè)控制傷殘人設(shè)備家電計算機輔助教育……3、數(shù)字化時代的新寵－漢字識別輸入技術(shù)

隨著手機的普及應(yīng)用，“拇指經(jīng)濟”迅速升溫，人們越來越尋求短信輸入的快捷和方便，手寫又成為一種時尚，受到人們的青睞。隨著各種掌上型信息終端及各種智能化、數(shù)字化產(chǎn)品的普及，在人們生活的許多地方，如掌上電腦、新型智能固定電話、各類平板電腦，甚至是街頭的POS機及銀行、車站等的觸摸屏等，都已大規(guī)模地應(yīng)用了手寫輸入技術(shù)。二、漢字鍵盤輸入技術(shù)

內(nèi)容鍵盤漢字鍵盤輸入原理鍵盤漢字輸入的總體流程

輸入碼對照表的設(shè)計1、鍵盤123456789101112131415161718192021222324252627435830313233343536373839402942444546474849505152535457

69535574717273787576777980812982832、掃描碼（ScanCode）外部設(shè)備必須通過控制器和主機連接，所以鍵盤本身有一個控制器。鍵盤控制器完成的主要工作是：加電或系統(tǒng)需要時對鍵盤進行檢測，掃描鍵盤、消除重鍵和自動重發(fā)，保存掃描代碼，與主機進行雙向通信，以及向主機傳送按鍵的掃描碼（ScanCode）等。所謂掃描碼是指根據(jù)按鍵在鍵盤上的位置按照從左到右，從上到下的原則從1開始給按鍵編的代碼。3、鍵盤工作原理當(dāng)用戶在鍵盤上按下一個按鍵后，控制器就能通過掃描矩陣得到按鍵的位置，從而把這個位置信息轉(zhuǎn)換為該按鍵的掃描碼，并存儲在控制器的緩沖區(qū)中。然后控制器產(chǎn)生一個鍵盤的硬件中斷，由這個硬件中斷通過端口從鍵盤控制器的緩沖區(qū)中取得這個按鍵的掃描碼，并把它轉(zhuǎn)換為對應(yīng)的ASCII碼，最后把2個字節(jié)的掃描碼和ASCII碼存儲到計算機內(nèi)存的鍵盤緩沖區(qū)中，供系統(tǒng)使用。4、部分掃描碼和ASCII碼表表6.1按鍵掃描碼和ASCII碼對照表（十六進制）按鍵掃描碼ASCII按鍵掃描碼ASCII按鍵掃描碼ASCIIA1E4190A39[1A5BB3042`2960INSERTE0,52C2E43-0C2DHOMEE0,47D2044=0D3DPGUPE0,49E1245\2B5CDELETEE0,53F2146BKSP0E08ENDE0,4FG2247SPACE3920PGDNE0,51H2348TAB0F09UARROWE0,48I1749CAPS3ALARROWE0,4BJ244ALSHFT2ADARROWE0,50內(nèi)容鍵盤

漢字鍵盤輸入原理鍵盤漢字輸入的總體流程

輸入碼對照表的設(shè)計1、西文字符的輸入使用的鍵盤是西文鍵盤，英文或歐洲語系等拼音文字，由于文字總數(shù)一般為幾十個，所以鍵盤上的按鍵就足以對映到每一個文字。用西文打字時，敲入的按鍵就可以直接根據(jù)當(dāng)前的代碼頁（CodePage）轉(zhuǎn)換為西文字符的內(nèi)碼從而顯示在當(dāng)前應(yīng)用程序的窗口中。如當(dāng)前是英文鍵盤，那么在鍵盤上按下按鍵“A”后，計算機就可以根據(jù)英文鍵盤的布局把這個按鍵轉(zhuǎn)換為字符“A”的ASCII碼，并送給應(yīng)用程序，從而在界面上顯示這個字符“A”。2、漢字的編碼輸入舉例3、漢字編碼輸入的前提要實現(xiàn)把輸入碼轉(zhuǎn)換成機內(nèi)碼這個功能必須具備一個前提條件，那就是輸入系統(tǒng)必須先于應(yīng)用程序得到用戶按鍵的掃描碼或ASCII碼，否則如果應(yīng)用程序先得到的話，那它就會對按鍵進行處理，那樣輸入系統(tǒng)就沒有辦法進行工作了。從鍵盤接收的按鍵消息是操作系統(tǒng)的I/O模塊處理的，它肯定先于應(yīng)用程序得到按鍵的掃描碼，然后由它負(fù)責(zé)把這些掃描碼轉(zhuǎn)換為ASCII碼，存放在鍵盤緩沖區(qū)中，那么只要保證輸入系統(tǒng)先于應(yīng)用程序拿到鍵盤緩沖區(qū)中的內(nèi)容就可以了。4、鍵盤HOOK一般而言，應(yīng)用程序從鍵盤緩沖區(qū)讀字符，總會調(diào)用系統(tǒng)的讀字符功能來實現(xiàn)的。通過系統(tǒng)提供的HOOK（鉤子）機制來實現(xiàn)輸入系統(tǒng)先于應(yīng)用程序得到鍵盤按鍵。鍵盤hook實現(xiàn)原理：假設(shè)原來的讀字符功能調(diào)用是GetChar(…)設(shè)計了一個輸入系統(tǒng)，里面由一個函數(shù)NewGetChar(…)把NewGetChar作為一個鉤子鉤到GetChar上，那么以后應(yīng)用程序調(diào)用函數(shù)GetChar實際調(diào)用的是NewGetChar在NewGetChar中，它實現(xiàn)調(diào)用原來的GetChar函數(shù)從緩沖區(qū)讀到字符，然后把這些字符傳遞給輸入系統(tǒng)，讓輸入系統(tǒng)處理，輸入系統(tǒng)處理完后，把結(jié)果給NewGetChar，由它把結(jié)果返回給應(yīng)用程序。需要注意的是NewGetChar和GetChar的參數(shù)和返回值應(yīng)該一致。5、鍵盤HOOK原理圖6、Windows下的HOOKHHOOKSetWindowsHookEx(intidHook,HOOKPROClpfn,HINSTANCEhMod,DWORDdwThreadId);其中，idHook指定鉤子的類型，常用的有WH_MOUSE、WH_KEYBOARD、WH_GETMESSAGE等，鍵盤操作應(yīng)該設(shè)定為WH_KEYBOARDlpfn標(biāo)識鉤子函數(shù)的入口地址，當(dāng)鉤子鉤到任何消息后便調(diào)用這個函數(shù)，即當(dāng)不管系統(tǒng)的哪個窗口有鍵盤輸入馬上會引起lpfn指向的函數(shù)的動作；hMod是鉤子函數(shù)所在模塊的句柄，我們可以很簡單的設(shè)定其為本應(yīng)用程序的實例句柄dwThreadId是鉤子相關(guān)函數(shù)的ID用以指定想讓鉤子去鉤哪個線程，為0時則攔截整個系統(tǒng)的消息。內(nèi)容鍵盤

漢字鍵盤輸入原理鍵盤漢字輸入的總體流程

輸入碼對照表的設(shè)計1、總體流程圖2、工作流程用戶在鍵盤上輸入漢字的輸入碼；鍵盤控制器在檢測到按鍵后，根據(jù)按鍵的位置產(chǎn)生它們的掃描碼，然后存入鍵盤內(nèi)的緩沖區(qū)中，并觸發(fā)一個鍵盤的硬件中斷；鍵盤中斷處理程序從鍵盤內(nèi)的緩沖區(qū)中取出掃描碼；鍵盤中斷處理程序把掃描碼轉(zhuǎn)換為ASCII碼，和掃描碼一起存儲在內(nèi)存的鍵盤緩沖區(qū)中；應(yīng)用程序調(diào)用取字符模塊取字符，實際調(diào)用的是漢字輸入處理模塊，漢字輸入處理模塊從內(nèi)存的鍵盤緩沖區(qū)取得掃描碼和ASCII碼。在西文系統(tǒng)中，應(yīng)用程序可以直接通過取字符模塊從鍵盤緩沖區(qū)獲得西文字符（⑤），從而結(jié)束輸入過程；2、工作流程（續(xù)）漢字輸入處理模塊判斷讀到的字符，是輸入系統(tǒng)需要處理的嗎？是則把輸入碼傳送給代碼轉(zhuǎn)換模塊；不是則直接返回給應(yīng)用程序（⑥）（如F1、Insert等按鍵，輸入系統(tǒng)不需要處理），結(jié)束；代碼轉(zhuǎn)換模塊根據(jù)輸入碼查輸入碼對照表；代碼轉(zhuǎn)換模塊從輸入碼對照表獲得對應(yīng)的漢字機內(nèi)碼；代碼轉(zhuǎn)換模塊把漢字機內(nèi)碼交漢字處理模塊；漢字處理模塊通過用戶干預(yù)后，把漢字機內(nèi)碼交應(yīng)用程序，結(jié)束。內(nèi)容鍵盤

漢字鍵盤輸入原理鍵盤漢字輸入的總體流程

輸入碼對照表的設(shè)計1、輸入碼對照表輸入碼對照表是漢字鍵盤輸入中的一個重要數(shù)據(jù)結(jié)構(gòu)，是漢字輸入碼到機內(nèi)碼轉(zhuǎn)換的核心，它反映了漢字輸入碼和機內(nèi)碼之間的映射關(guān)系。一般來說，系統(tǒng)有一種輸入法，就需要為它配備一張對照表，但內(nèi)碼輸入法是一個特例，它可以根據(jù)輸入碼計算出機內(nèi)碼，所以不需要對照表。對照表是以文件的形式存儲在計算機中的，一般一張對照表就是一個文件，當(dāng)然也有是由一系列的文件組成的。對照表一般有兩種類型：字對照表和詞對照表。在字對照表中，表示的是一個一個漢字和輸入碼的映射關(guān)系，而詞對照表則表示詞（組）和輸入碼的映射關(guān)系。2、輸入碼對照表結(jié)構(gòu)的分類定長結(jié)構(gòu)變長結(jié)構(gòu)計算結(jié)構(gòu)索引結(jié)構(gòu)其它4、定長結(jié)構(gòu)定長結(jié)構(gòu)的每個表項的長度固定。每個表項一般由有兩個域組成：一個域存放漢字或詞（組）的機內(nèi)碼，另一個表項存放此漢字或詞（組）的輸入碼。每個域的長度是固定的。如一個表項固定長度為6個字節(jié)，其中輸入碼占4個字節(jié)，漢字占2個字節(jié)。由于一個漢字的機內(nèi)碼一般由2個字節(jié)構(gòu)成，所以字對照表可以采用定長結(jié)構(gòu)。詞對照表一般不會采用這種結(jié)構(gòu)，是因為詞組長度不一，容易造成存儲空間的浪費。4、定長結(jié)構(gòu)（續(xù)）－結(jié)構(gòu)4、定長結(jié)構(gòu)（續(xù)）檢索方法掃描法二分法假設(shè)需要檢索的輸入碼為S，對照表的表項數(shù)為N，分別用IC[i]，HZ[i]表示第i表項的輸入碼和漢字。4、定長結(jié)構(gòu)（續(xù)）掃描法：首先，為了方便檢索，需要把對照表按照輸入碼的大小從小到大排序。掃描法是指每次查找都從頭開始，一直找到和S相同的輸入碼項i；然后繼續(xù)往后查找，找到和S不同的輸入碼項j；那么，第i項到第j-1項，共j-i項對應(yīng)的漢字就是輸入碼S對應(yīng)的重碼集。最大的比較次數(shù)為N，最小的比較次數(shù)為1，平均為（N+1）/2。4、定長結(jié)構(gòu)（續(xù)）－掃描法4、定長結(jié)構(gòu)（續(xù)）二分法：二分算法描述如下：①設(shè)置一個值B=0，E=N；②如果B>E，算法失敗結(jié)束；否則M=[(B+E)/2]；③然后把IC[M]和S比較；④如果相等，則說明找到了一項，由于輸入碼相等的漢字是相鄰存放的，所以只要進行前后的掃描，可以得到所有的輸入碼為S的漢字，結(jié)束；⑤如果IC[M]小于S，則B=M+1，轉(zhuǎn)②；⑥如果IC[M]大于S，則E=M-1，轉(zhuǎn)②。4、定長結(jié)構(gòu)（續(xù)）－檢索算法4、定長結(jié)構(gòu)（續(xù)）二分法的最大的比較次數(shù)為[log2N]，最小的比較次數(shù)為1，平均約為[log2N]-1。假設(shè)N=20902，則掃描法的平均比較次數(shù)為[(20902+1)/2]=10452，而二分法的比較次數(shù)為（[log220902]-1＝14，明顯比掃描法好。定長結(jié)構(gòu)的對照表具有表結(jié)構(gòu)簡單，容易構(gòu)建，檢索算法簡單等優(yōu)點，但在存儲空間上存在缺陷。 5、計算結(jié)構(gòu)

計算結(jié)構(gòu)常用于設(shè)計字對照表。每個表項對應(yīng)一個漢字，表項等長，內(nèi)容為該漢字對應(yīng)的輸入碼。這種結(jié)構(gòu)的對照表的表項必須按照漢字的特定序列進行排列，不能無序。一般情況，都是按照漢字內(nèi)碼進行排序，從而方便確定每個表項對應(yīng)的漢字機內(nèi)碼。5、計算結(jié)構(gòu)（續(xù)）輸入碼……0123n5、計算結(jié)構(gòu)（續(xù)）計算結(jié)構(gòu)舉例縱橫碼的碼元集合為：{1234567890}碼長為1－4，是不等長碼。字符集采用Unicode/ISO10646-1993。Unicode內(nèi)碼從4E00H到9FA5H共20902個漢字。每個表項的內(nèi)容是輸入碼，為1－4個數(shù)字，每個數(shù)字可以用BCD碼來表示，需要3位（bits），4個數(shù)字則需要3×4＝12位，用2個字節(jié)表示。如果數(shù)字不足4位，用全“1”位填充。5、計算結(jié)構(gòu)（續(xù)）表項結(jié)構(gòu)每個表項的大小為2個字節(jié)。整張對照表總共需要2×20902=41804個字節(jié)，按照機內(nèi)碼的大小從小到大排列。表項2個字節(jié)輸入碼2個字節(jié)輸入碼……2個字節(jié)輸入碼2個字節(jié)輸入碼……2個字節(jié)輸入碼2個字節(jié)輸入碼……2個字節(jié)輸入碼2個字節(jié)輸入碼序號01

……255256…………2090020901內(nèi)碼4E004E01……4EFF4F009EFF9F009FA49FA51514131211109876543210第一位碼元第二位碼元第三位碼元第四位碼元5、計算結(jié)構(gòu)（續(xù)）假設(shè)漢字的內(nèi)碼hz可以表示為：hz={hzhhzl|hzh∈R1,hzl∈R2}R1={R|4EH≤R≤FFH}R2={R|00H≤R≤FFH}從上表我們可以得到序號i和內(nèi)碼hz的關(guān)系： i=(hzh-4EH)*0FFH+hzl

則hzh＝[i/0FFH]+4EH//[]表示取整hzl=imod0FFH那么，對照表的檢索過程就是遍歷表的過程，也就是當(dāng)發(fā)現(xiàn)第i項表項和當(dāng)前輸入碼的BCD碼一致時，可以通過上面的計算得到該漢字的機內(nèi)碼，從而實現(xiàn)轉(zhuǎn)換過程。5、計算結(jié)構(gòu)（續(xù)）優(yōu)點是節(jié)省空間上例中的對照表比采用等長結(jié)構(gòu)可以節(jié)省一半的空間（省了20902個漢字的空間），但存在需要遍歷整張對照表的問題,比較次數(shù)為N。當(dāng)一個漢字有多個編碼時，就存在問題了，需要設(shè)置附加表。6、變長結(jié)構(gòu)

每個表項對應(yīng)一個輸入碼。每個表項有兩個域：一個域存放輸入碼，另一個域存放和該輸入碼對應(yīng)的所有重碼字或詞組集合。由于第二個表項的內(nèi)容不定，所以長度無法確定，造成表項不等長。這種結(jié)構(gòu)的輸入碼對照表減少了表項的數(shù)目，不需要為每個漢字存放輸入碼，所以存儲空間相當(dāng)?shù)乳L結(jié)構(gòu)有明顯的減少。6、變長結(jié)構(gòu)（續(xù)）以20902個漢字的縱橫碼對照表為例，定長結(jié)構(gòu)需要（2＋2）×20902＝83608（字節(jié)）（2個字節(jié)的BCD輸入碼，2個字節(jié)的漢字機內(nèi)碼），而變長結(jié)構(gòu)只需要20902×2＋6123×2＝54050（字節(jié)）（20902個漢字和6123個BCD輸入碼），比定長結(jié)構(gòu)少了近30K，超過三分之一。這種結(jié)構(gòu)存在的問題是檢索時間相對也較長，一般采用掃描法，需要遍歷整張對照表。6、變長結(jié)構(gòu)（續(xù)）6、變長結(jié)構(gòu)（續(xù)）縱橫碼的不等長對照表結(jié)構(gòu)描述：<對照表>::=<表項>[<表項>]<表項表>::=<輸入碼><漢字集><輸入碼>::=<2個字節(jié)的BCD碼><漢字集>::=<1個字節(jié)漢字集長度><漢字重碼><漢字重碼>::=<2個字節(jié)的漢字內(nèi)碼>[<2個字節(jié)的漢字內(nèi)碼>]假設(shè)需要檢索的輸入碼為S，對照表的表項數(shù)為K，分別用ICi，LENi，HZi表示第i表項的輸入碼、漢字集長度和漢字重碼集合。6、變長結(jié)構(gòu)（續(xù)）6、變長結(jié)構(gòu)（續(xù)）假設(shè)輸入碼的個數(shù)為K，那么最大的比較次數(shù)為K，最小的比較次數(shù)為1，所以比較次數(shù)依舊平均為（K+1）/2。由于K比N小，所以比較次數(shù)比等長結(jié)構(gòu)少。如縱橫碼的例子，變長結(jié)構(gòu)的平均比較次數(shù)是(6123+1)/2=3062次，而等長結(jié)構(gòu)如采用掃描法則需要（20902＋1）/2＝10452，是變長結(jié)構(gòu)的3倍！7、索引結(jié)構(gòu)

索引是一種最常用的對照表結(jié)構(gòu)，也是一種高效率的檢索結(jié)構(gòu)。一般索引結(jié)構(gòu)的對照表分成兩部分：索引表和碼表。索引表的表項由兩部分組成：輸入碼和指針（指向碼表中輸入碼對應(yīng)的漢字和詞組的首址）。碼表的結(jié)構(gòu)基本和變長結(jié)構(gòu)類似。7、索引結(jié)構(gòu)（續(xù)）7、索引結(jié)構(gòu)（續(xù)）每個索引表項對應(yīng)一個碼表項，而且是一對一的關(guān)系，有多少個索引項就有多少個碼表項。一般而言，索引表中的每一個表項是等長的，而碼表中的每一個表項長度是不相等的。索引結(jié)構(gòu)結(jié)合了等長和變長的優(yōu)點，通過把輸入碼和漢字串分開的方法，使得索引表組織類似等長結(jié)構(gòu)（輸入碼域和指針域的長度一般固定），而碼表組織類似于變長結(jié)構(gòu)，從而提高了檢索效率，也節(jié)省了空間。7、索引結(jié)構(gòu)（續(xù)）－二分法7、索引結(jié)構(gòu)（續(xù)）-舉例拼音輸入碼為例：比較等長、變長和索引結(jié)構(gòu)的對照表的對照表大小和檢索效率。由于拼音由21個聲母和35個韻母組成，不考慮聲調(diào)。所以可以采用壓縮方法來存放輸入碼，用1－21表示21個聲母，可以用5位來表示，用1－35表示35個韻母，可以用6位來表示，一共11位，為了方便起見，共用兩個字節(jié)存放（如果無聲母或韻母，用0表示）。7、索引結(jié)構(gòu)（續(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、索引結(jié)構(gòu)（續(xù)）-舉例等長結(jié)構(gòu)：<對照表>::=<表項>[<表項>]<表項表>::=<輸入碼><漢字><輸入碼>::=<1個字節(jié)的聲母><一個字節(jié)的韻母><漢字>::=<2個字節(jié)機內(nèi)碼>變長結(jié)構(gòu)：<對照表>::=<表項>[<表項>]<表項表>::=<輸入碼><漢字集><輸入碼>::=<1個字節(jié)的聲母><一個字節(jié)的韻母><漢字集>::=<1個字節(jié)漢字集長度><漢字重碼><漢字重碼>::=<2個字節(jié)的漢字內(nèi)碼>[<2個字節(jié)的漢字內(nèi)碼>]7、索引結(jié)構(gòu)（續(xù)）-舉例索引結(jié)構(gòu)：<對照表>::=<索引表><碼表><索引表>::=<表項>[<表項>]<表項表>::=<輸入碼><指針><輸入碼>::=<1個字節(jié)的聲母><一個字節(jié)的韻母><指針>::=<2個字節(jié)的整數(shù)><碼表>::=<1個字節(jié)漢字集長度><漢字重碼><漢字重碼>::=<2個字節(jié)的漢字內(nèi)碼>[<2個字節(jié)的漢字內(nèi)碼>]7、索引結(jié)構(gòu)（續(xù)）-舉例

三種結(jié)構(gòu)比較表對照表結(jié)構(gòu)碼本大小平均檢索次數(shù)等長結(jié)構(gòu)20902×4＝83608[log220902]-1＝14(二分法)變長結(jié)構(gòu)20902×2＋417×（2＋1）＝43055（417＋1）/2＝209索引結(jié)構(gòu)20902×2＋417×（2＋2）＝43472log2417-1=87、索引結(jié)構(gòu)（續(xù)）－稀疏索引

7、索引結(jié)構(gòu)（續(xù)）－稀疏索引省略了索引表中的輸入碼部分索引表的表項是對應(yīng)于整個編碼空間的，也就是即使這個輸入碼沒有對應(yīng)的漢字，仍作為一個表項存在于索引表中如某個輸入法的碼元集合為26個字母，碼長為4，則應(yīng)該有26×26×26×26＝456976個表項表項的排列是按照輸入碼由小到大的次序來排列，也就是從“aaaa”到“zzzz”，假如某個輸入碼是S1S2S3S4，我們可以計算得到此輸入碼對應(yīng)的索引表表項的序號i：i=(S1-’a’)×263＋(S2-’a’)×262＋(S3-’a’)×26＋S4-’a’把序號乘以每個表項的大小就得到了此輸入碼指向碼表的指針在碼表中的首址7、索引結(jié)構(gòu)（續(xù)）－稀疏索引問題:可能索引表過大如上面舉的例子，如果每個表項長度為6個字節(jié)，那么索引表長度為456976×6字節(jié)，約2.6M字節(jié)的空間。為了節(jié)省空間，我們一般采用部分索引的技術(shù)取一個輸入碼中的部分編碼進行索引7、索引結(jié)構(gòu)（續(xù)）－稀疏索引假設(shè)碼元集合中的碼元數(shù)為m，輸入碼的長度為n，則每個索引項的長度2（假設(shè)指針大小為2個字節(jié)），如果對i（i<=n）個字節(jié)輸入碼作索引，那么索引表的長度TL為：TL=mi*2即TL=mi*2則i=logmTL/2一般TL的大小在10k左右當(dāng)采用數(shù)字編碼時m=10，則i=3當(dāng)采用字母編碼時m=26，則i=2三、漢字鍵盤輸入系統(tǒng)內(nèi)容漢字輸入系統(tǒng)的分類漢字輸入系統(tǒng)的功能漢字鍵盤輸入系統(tǒng)的工作流程1、按系統(tǒng)在計算機中實現(xiàn)的層次可以分為：系統(tǒng)層的輸入系統(tǒng)應(yīng)用層的輸入系統(tǒng)2、按操作系統(tǒng)平臺主要有：DOS下的輸入系統(tǒng)Windows下的輸入系統(tǒng)Linux下的輸入系統(tǒng)Unix下的輸入系統(tǒng)MacSystem下的輸入系統(tǒng)嵌入系統(tǒng)種的的輸入系統(tǒng)……3、按漢字內(nèi)碼的簡繁分為：簡體輸入系統(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)內(nèi)容漢字輸入系統(tǒng)的分類漢字輸入系統(tǒng)的功能漢字鍵盤輸入系統(tǒng)的工作流程1、漢字/詞組輸入單字輸入我你的詞組輸入我們計算機短語、短句輸入我的非常多不明白科技是第一生產(chǎn)力句子輸入我到飯店去吃飯。2、候選字/詞提示和選擇重碼不可避免輸入系統(tǒng)必須具備候選字/詞提示的功能應(yīng)該常用用字、詞在前提高容錯的功能3、中英文狀態(tài)切換存在中文和英文兩種狀態(tài)在中文狀態(tài)，可以通過輸入漢字輸入碼輸出漢字在英文文狀態(tài)下，整個鍵盤都是西文符號4、翻頁當(dāng)輸入的漢字輸入碼對應(yīng)的候選字/詞比較多時，輸入系統(tǒng)無法在候選框中顯示所有的候選字/詞，只能通過分頁方式顯示?？墒褂玫椒撴I顯示上/下一頁的候選字/詞。常用的翻頁鍵分為前翻頁鍵和后翻頁鍵，一般輸入系統(tǒng)的前/后翻頁鍵為“-”和“+”、“,”和“.”、“[”和“]”、“PageUp”和“PageDown”等。5、輸入碼清除、刪除、結(jié)束鍵當(dāng)輸入的輸入碼有誤時，可以通過輸入碼刪除鍵刪除剛輸入的這個輸入碼符，也可以通過輸入碼清除鍵刪除所有輸入的輸入碼。實際上這兩個鍵的作用是提供一種輸入碼的簡單編輯功能。絕大多數(shù)的輸入系統(tǒng)不需要輸入碼結(jié)束符，只有輸入碼鍵和選擇鍵沖突時才需要輸入碼結(jié)束符來區(qū)分兩種狀態(tài)。6、聯(lián)想當(dāng)用戶輸入了一個漢字后，系統(tǒng)提示以這個漢字為首字的詞組供用戶選擇（不包括首字），這種技術(shù)稱為聯(lián)想技術(shù)。如用戶輸入了“計”，則系統(tǒng)提示以“計”作為首字的詞組剩余部分，如“算機”、“劃”和“策”等8、全角和半角鍵盤上的西文字符在輸入計算機時有全角和半角兩種方式。在早期DOS系統(tǒng)下，ASCII字符是中文字符的一半大小，所以稱ASCII字符為半角字符采用雙字節(jié)內(nèi)碼、和中文等寬的西文字符為全角字符。如半角字符“0”的ASCII碼是30H，而全角字符“０”的Unicode內(nèi)碼是0FF10H。在Windows等系統(tǒng)中，由于是圖形界面，所有的字符不是等寬字符，所以一個ASCII字符不再是一個中文內(nèi)碼字符的一半。9、符號輸入符號按鍵符號按鍵符號按鍵。.？?“”“”，,：:‘’‘’、\；;！!《<￥$×*》>％%內(nèi)容漢字輸入系統(tǒng)的分類漢字輸入系統(tǒng)的功能漢字鍵盤輸入系統(tǒng)的工作流程1、流程圖2、中文輸入和西文輸入的差異從以上的流程我們可以發(fā)現(xiàn)，在西文環(huán)境下，用戶每按下一個按鍵應(yīng)用程序都會接收到。而在中文環(huán)境下，用戶按下一個按鍵后，應(yīng)用程序可能接收不到任何的東西，因為輸入系統(tǒng)還沒有機內(nèi)碼返回，需要更多的按鍵后才能有機內(nèi)碼返回。如圖6.7所示，用戶輸入“w”和“o”后，輸入系統(tǒng)沒有輸出漢字“我”，必須等到用戶再輸入“1”后，才有漢字輸出。這也是漢字輸入和西文輸入的最大差異。Windows漢字輸入技術(shù)內(nèi)容Windows漢字輸入技術(shù)概述Windows下漢字輸入原理在SDK和DDK環(huán)境下開發(fā)輸入系統(tǒng)1、界面2、概念輸入法Windows中的漢字輸入法稱為IME(InputMethodEditor)，它的本質(zhì)是一個轉(zhuǎn)換引擎，通過查字典方式，把鍵盤輸入的按鍵消息轉(zhuǎn)換為各種語言的文字信息。另外，它還提供和用戶、操作系統(tǒng)的接口。輸入法管理器輸入法管理器簡稱為IMM（InputMethodManager），它是一個管理各種IME，并在IME和應(yīng)用程序間進行通信的系統(tǒng)部件。它不僅為程序員提供了開發(fā)輸入法的接口，還為用戶提供了管理輸入法的界面。2、概念（續(xù)）2、概念（續(xù)）多文種環(huán)境（Multi-lingualEnvironment）所謂多文種環(huán)境是指系統(tǒng)可以為使