《《漢字輸入技術(shù)》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《漢字輸入技術(shù)》PPT課件.ppt（108頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第五章漢字輸入技術(shù),延邊大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,內(nèi)容,漢字輸入技術(shù)概述漢字鍵盤輸入技術(shù)漢字鍵盤輸入系統(tǒng)Windows漢字輸入技術(shù)Linux下的漢字輸入系統(tǒng),一、漢字輸入技術(shù)概述,漢字輸入發(fā)展史漢字輸入分類漢字輸入技術(shù)發(fā)展和應(yīng)用,1、問題提出,早期，計(jì)算機(jī)主要通過鍵盤輸入文字信息在計(jì)算機(jī)出現(xiàn)以前，西文打字機(jī)的鍵盤早已定型，計(jì)算機(jī)很自然地利用了打字機(jī)鍵盤這一錄入工具。在鍵盤上沒有漢字，那么如何才能將漢字輸入到計(jì)算機(jī)中？,2、大鍵盤方案,設(shè)計(jì)一個(gè)漢字大鍵盤。這個(gè)漢字大鍵盤上有幾千個(gè)按鍵，每個(gè)按鍵對(duì)應(yīng)一個(gè)漢字，漢字按照偏旁部首在鍵盤上分區(qū)排列，以便于快速檢字。大鍵盤的思想經(jīng)過實(shí)踐證明是失敗的，它存在的問題主要是在鍵盤上找字困難，不能輸入鍵盤上沒有的漢字，設(shè)備本身價(jià)格太高等。,3、基于西文鍵盤的漢字編碼輸入,這是到目前為止最成功的計(jì)算機(jī)漢字輸入方法。漢字編碼輸入是最早的漢字輸入方法，已知最早的計(jì)算機(jī)漢字編碼輸入始于20世紀(jì)50年代的俄漢機(jī)器翻譯研究，但只能用電報(bào)碼或四角號(hào)碼做漢字編碼。在大陸，1978年5月上海電工儀器研究所部工程師支秉彝創(chuàng)造了一種“見字識(shí)碼”法，并被上海市內(nèi)電話局采用，從而率先使計(jì)算機(jī)的漢字輸入進(jìn)入了實(shí)用階段。在港臺(tái)及海外，以“王安三角”為發(fā)端，陸續(xù)涌現(xiàn)出“倉頡”、“嘸蝦米”、“行列”、“唯物”等一大批繁體漢字輸入法。進(jìn)入80年代后，在聯(lián)想漢字、四通中文電腦打字機(jī)之后中國的漢字編碼出現(xiàn)了“萬馬奔騰”的局面。在大陸涌現(xiàn)出了五筆、自然碼、鄭碼、拼音、智能ABC、智能狂拼、縱橫等上千種的輸入法。,4、語音輸入,用了多年的鍵盤輸入方式，在1997年左右突然受到猛烈的沖擊，各大廠商包括IBM、微軟、摩托羅拉、中自、紫光等公司紛紛推出自己的非特定人語音輸入系統(tǒng)或者連筆字手寫輸入系統(tǒng)。美國微軟公司于1997年9月在北京推出中文非特定人連續(xù)語音識(shí)別系統(tǒng)ViaVoice。ViaVoice是目前在市場(chǎng)上占據(jù)統(tǒng)治地位的語音輸入系統(tǒng)。,5、手寫體漢字識(shí)別輸入,通過書寫漢字記錄信息已經(jīng)有幾千年的歷史，這也是使用漢字的中國人的普遍習(xí)慣，所以手寫識(shí)別輸入是符合中國人記錄信息習(xí)慣的。在1997年以后就已經(jīng)有基本實(shí)用的手寫漢字識(shí)別輸入系統(tǒng)，其中佼佼者為中自公司的“漢王99”、摩托羅拉公司的“慧筆”和清華紫光公司的“紫光筆”等。,6、印刷體漢字識(shí)別輸入,我國對(duì)印刷體漢字識(shí)別(簡(jiǎn)稱OCR，OpticalCharacterRecognition)的研究始于70年代末80年代初，經(jīng)過科研人員幾十多年的辛勤努力，印刷體漢字識(shí)別技術(shù)的發(fā)展和應(yīng)用，已經(jīng)有了長(zhǎng)足進(jìn)步。清華大學(xué)電子工程系、中國科學(xué)院計(jì)算所智能中心、北京信息工程學(xué)院、沈陽自動(dòng)化研究所等單位分別研制開發(fā)出實(shí)用化的印刷體漢字識(shí)別系統(tǒng)。清華大學(xué)電子工程系研制的清華TH-OCR產(chǎn)品，占據(jù)著最大的市場(chǎng)份額，代表著中文OCR技術(shù)發(fā)展的潮流。,內(nèi)容,漢字輸入發(fā)展史漢字輸入分類漢字輸入技術(shù)發(fā)展和應(yīng)用,1、分類,漢字的輸入兩大類：編碼輸入自然輸入語音識(shí)別輸入字形識(shí)別輸入手寫體識(shí)別輸入印刷體識(shí)別輸入,2、鍵盤編碼輸入,鍵盤編碼輸入首先把需要輸入計(jì)算機(jī)的所有漢字用鍵盤上的若干個(gè)按鍵編碼，這些按鍵組成的序列稱為對(duì)應(yīng)漢字的輸入碼。通過在鍵盤上輸入某個(gè)按鍵序列，并由計(jì)算機(jī)中的輸入系統(tǒng)把這個(gè)序列轉(zhuǎn)換為對(duì)應(yīng)的漢字，從而達(dá)到輸入漢字的目的。優(yōu)點(diǎn)：輸入快速、無需添加額外設(shè)備缺陷：輸入方式和人們使用語言文字的習(xí)慣不符、用戶需要化額外的時(shí)間學(xué)習(xí)等。,3、語音識(shí)別輸入,漢字語音識(shí)別輸入利用產(chǎn)生聲音的物理模型，通過語音分析手段，預(yù)先將一些語音的特征提取出來，并存儲(chǔ)在處理系統(tǒng)中。當(dāng)語音信號(hào)輸入時(shí)，處理系統(tǒng)根據(jù)對(duì)該信號(hào)所提取的特征參數(shù)和所存儲(chǔ)的參考特征進(jìn)行比較，通過邏輯判斷方法和“距離”測(cè)量法對(duì)語音進(jìn)行識(shí)別。,3、語音識(shí)別輸入（續(xù)）,自然界的聲音和人講話的語音，都是模擬信號(hào)，不能直接輸入計(jì)算機(jī)，因此在語音輸入的過程中，我們必須通過語音卡（聲卡）等設(shè)備，把模擬的語音信號(hào)轉(zhuǎn)換為數(shù)字語音信號(hào)輸入計(jì)算機(jī)。然后計(jì)算機(jī)利用程序?qū)斎氲臄?shù)字語音信號(hào)進(jìn)行統(tǒng)計(jì)、判斷和識(shí)別，并最終把它翻譯成計(jì)算機(jī)能夠理解的漢字的內(nèi)碼信息。語音識(shí)別輸入技術(shù)有著廣闊的應(yīng)用前景缺點(diǎn)：由于不同人的口音差別較大，語音的準(zhǔn)確識(shí)別比較困難,4、漢字識(shí)別輸入,漢字識(shí)別輸入根據(jù)模式識(shí)別原理，通過漢字的字形信息識(shí)別，產(chǎn)生漢字的內(nèi)碼，實(shí)現(xiàn)漢字的識(shí)別輸入。漢字識(shí)別輸入的原理是通過抽取代表未知漢字模式本質(zhì)的表達(dá)形式與預(yù)先存儲(chǔ)在計(jì)算機(jī)中的標(biāo)準(zhǔn)漢字的模式表達(dá)形式的集合逐一進(jìn)行匹配，用一定的準(zhǔn)則進(jìn)行判別，找出最接近輸入漢字的那個(gè)標(biāo)準(zhǔn)漢字。漢字識(shí)別輸入技術(shù)可分為印刷體漢字識(shí)別輸入和手寫體漢字識(shí)別輸入兩大類。,5、手寫體漢字識(shí)別輸入,手寫體識(shí)別輸入方法把手寫字的位置信息首先轉(zhuǎn)換成二進(jìn)制的數(shù)字編碼信息，并對(duì)手寫字進(jìn)行智能化的識(shí)別，并產(chǎn)生與之匹配的數(shù)字編碼的中文或英文字符，同時(shí)所產(chǎn)生的字符也送給顯示屏顯示，最后經(jīng)過輸入者確認(rèn)后才作為正確的輸入結(jié)果?？煞譃槁?lián)機(jī)手寫漢字識(shí)別輸入和脫機(jī)手寫漢字識(shí)別輸入,5、手寫體漢字識(shí)別輸入（續(xù)）,手寫體識(shí)別輸入難于印刷體識(shí)別輸入脫機(jī)手寫體識(shí)別輸入又難于聯(lián)機(jī)手寫體識(shí)別輸入聯(lián)機(jī)手寫體識(shí)別輸入是一種人工實(shí)時(shí)地把漢字輸入計(jì)算機(jī)的方法，它利用書寫板把筆畫變?yōu)殡娦盘?hào)，輸入計(jì)算機(jī)的是以坐標(biāo)點(diǎn)序列表示的筆尖移動(dòng)軌跡，因而被處理的是一維的線條（筆畫）串，這些線條串含有筆畫數(shù)目、筆畫走向、筆順和書寫速度等信息。脫機(jī)手寫漢字識(shí)別處理的僅是二維的漢字點(diǎn)陣圖象，是漢字識(shí)別領(lǐng)域中最后一個(gè)十分困難的問題，目前仍然處于實(shí)驗(yàn)室研究階段。,5、手寫體漢字識(shí)別輸入（續(xù)）,6、印刷體識(shí)別輸入,印刷體識(shí)別輸入是利用掃描器對(duì)已有的文書資料進(jìn)行掃描，將掃描結(jié)果送入計(jì)算機(jī)中，計(jì)算機(jī)對(duì)所得圖像進(jìn)行去污點(diǎn)和干擾、行字切分、二值化、細(xì)化、抽取輪廓、平滑和規(guī)范化等處理，然后再由計(jì)算機(jī)根據(jù)所得圖像的輪廓與計(jì)算機(jī)字庫中的漢字點(diǎn)陣進(jìn)行匹配，從而轉(zhuǎn)換成相應(yīng)的漢字的技術(shù)。應(yīng)用范圍：圖像處理、桌面排版、印刷出版、字符識(shí)別、圖文數(shù)據(jù)庫、廣告美術(shù)設(shè)計(jì)、多媒體圖文通訊和辦公自動(dòng)化等。,6、印刷體識(shí)別輸入(續(xù)),TH-OCR2000,6、印刷體識(shí)別輸入(續(xù)),內(nèi)容,漢字輸入發(fā)展史漢字輸入分類漢字輸入技術(shù)發(fā)展和應(yīng)用,1、漢字輸入計(jì)算機(jī)的主流技術(shù)－漢字鍵盤輸入技術(shù),鍵盤輸入使用的是人的十個(gè)手指，靈活方便，符合人體工程學(xué)原理，絕大多數(shù)人愿意接受這一輸入方式。鍵盤輸入具有輸入快速、省力、方便等其它輸入方式無法比擬的優(yōu)點(diǎn)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，軟件技術(shù)彌補(bǔ)了漢字編碼的很多不足。句子輸入、詞組輸入、智能輸入等技術(shù)使鍵盤漢字輸入系統(tǒng)更加好用，輸入更加快速方便。,2、廣泛的應(yīng)用途徑－語音識(shí)別輸入技術(shù),語音識(shí)別技術(shù)的滲透性很強(qiáng)，在未來它將無處不在語音撥號(hào)語音查詢工業(yè)控制傷殘人設(shè)備家電計(jì)算機(jī)輔助教育……,3、數(shù)字化時(shí)代的新寵－漢字識(shí)別輸入技術(shù),隨著手機(jī)的普及應(yīng)用，“拇指經(jīng)濟(jì)”迅速升溫，人們?cè)絹碓綄で蠖绦泡斎氲目旖莺头奖?，手寫又成為一種時(shí)尚，受到人們的青睞。隨著各種掌上型信息終端及各種智能化、數(shù)字化產(chǎn)品的普及，在人們生活的許多地方，如掌上電腦、新型智能固定電話、各類平板電腦，甚至是街頭的POS機(jī)及銀行、車站等的觸摸屏等，都已大規(guī)模地應(yīng)用了手寫輸入技術(shù)。,二、漢字鍵盤輸入技術(shù),鍵盤漢字鍵盤輸入原理鍵盤漢字輸入的總體流程輸入碼對(duì)照表的設(shè)計(jì),1、鍵盤,1234567891011121314,1516171819202122232425262743,58303132333435363738394029,424445464748495051525354,57,69535574,71727378,757677,79808129,8283,,,2、掃描碼（ScanCode）,外部設(shè)備必須通過控制器和主機(jī)連接，所以鍵盤本身有一個(gè)控制器。鍵盤控制器完成的主要工作是：加電或系統(tǒng)需要時(shí)對(duì)鍵盤進(jìn)行檢測(cè)，掃描鍵盤、消除重鍵和自動(dòng)重發(fā)，保存掃描代碼，與主機(jī)進(jìn)行雙向通信，以及向主機(jī)傳送按鍵的掃描碼（ScanCode）等。所謂掃描碼是指根據(jù)按鍵在鍵盤上的位置按照從左到右，從上到下的原則從1開始給按鍵編的代碼。,3、鍵盤工作原理,當(dāng)用戶在鍵盤上按下一個(gè)按鍵后，控制器就能通過掃描矩陣得到按鍵的位置，從而把這個(gè)位置信息轉(zhuǎn)換為該按鍵的掃描碼，并存儲(chǔ)在控制器的緩沖區(qū)中。然后控制器產(chǎn)生一個(gè)鍵盤的硬件中斷，由這個(gè)硬件中斷通過端口從鍵盤控制器的緩沖區(qū)中取得這個(gè)按鍵的掃描碼，并把它轉(zhuǎn)換為對(duì)應(yīng)的ASCII碼，最后把2個(gè)字節(jié)的掃描碼和ASCII碼存儲(chǔ)到計(jì)算機(jī)內(nèi)存的鍵盤緩沖區(qū)中，供系統(tǒng)使用。,4、部分掃描碼和ASCII碼表,表6.1按鍵掃描碼和ASCII碼對(duì)照表（十六進(jìn)制）,內(nèi)容,鍵盤漢字鍵盤輸入原理鍵盤漢字輸入的總體流程輸入碼對(duì)照表的設(shè)計(jì),1、西文字符的輸入,使用的鍵盤是西文鍵盤，英文或歐洲語系等拼音文字，由于文字總數(shù)一般為幾十個(gè)，所以鍵盤上的按鍵就足以對(duì)映到每一個(gè)文字。用西文打字時(shí)，敲入的按鍵就可以直接根據(jù)當(dāng)前的代碼頁（CodePage）轉(zhuǎn)換為西文字符的內(nèi)碼從而顯示在當(dāng)前應(yīng)用程序的窗口中。如當(dāng)前是英文鍵盤，那么在鍵盤上按下按鍵“A”后，計(jì)算機(jī)就可以根據(jù)英文鍵盤的布局把這個(gè)按鍵轉(zhuǎn)換為字符“A”的ASCII碼，并送給應(yīng)用程序，從而在界面上顯示這個(gè)字符“A”。,2、漢字的編碼輸入舉例,3、漢字編碼輸入的前提,要實(shí)現(xiàn)把輸入碼轉(zhuǎn)換成機(jī)內(nèi)碼這個(gè)功能必須具備一個(gè)前提條件，那就是輸入系統(tǒng)必須先于應(yīng)用程序得到用戶按鍵的掃描碼或ASCII碼，否則如果應(yīng)用程序先得到的話，那它就會(huì)對(duì)按鍵進(jìn)行處理，那樣輸入系統(tǒng)就沒有辦法進(jìn)行工作了。從鍵盤接收的按鍵消息是操作系統(tǒng)的I/O模塊處理的，它肯定先于應(yīng)用程序得到按鍵的掃描碼，然后由它負(fù)責(zé)把這些掃描碼轉(zhuǎn)換為ASCII碼，存放在鍵盤緩沖區(qū)中，那么只要保證輸入系統(tǒng)先于應(yīng)用程序拿到鍵盤緩沖區(qū)中的內(nèi)容就可以了。,4、鍵盤HOOK,一般而言，應(yīng)用程序從鍵盤緩沖區(qū)讀字符，總會(huì)調(diào)用系統(tǒng)的讀字符功能來實(shí)現(xiàn)的。通過系統(tǒng)提供的HOOK（鉤子）機(jī)制來實(shí)現(xiàn)輸入系統(tǒng)先于應(yīng)用程序得到鍵盤按鍵。鍵盤hook實(shí)現(xiàn)原理：假設(shè)原來的讀字符功能調(diào)用是GetChar(…)設(shè)計(jì)了一個(gè)輸入系統(tǒng)，里面由一個(gè)函數(shù)NewGetChar(…)把NewGetChar作為一個(gè)鉤子鉤到GetChar上，那么以后應(yīng)用程序調(diào)用函數(shù)GetChar實(shí)際調(diào)用的是NewGetChar在NewGetChar中，它實(shí)現(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下的HOOK,HHOOKSetWindowsHookEx(intidHook,HOOKPROClpfn,HINSTANCEhMod,DWORDdwThreadId);其中，idHook指定鉤子的類型，常用的有WH_MOUSE、WH_KEYBOARD、WH_GETMESSAGE等，鍵盤操作應(yīng)該設(shè)定為WH_KEYBOARDlpfn標(biāo)識(shí)鉤子函數(shù)的入口地址，當(dāng)鉤子鉤到任何消息后便調(diào)用這個(gè)函數(shù)，即當(dāng)不管系統(tǒng)的哪個(gè)窗口有鍵盤輸入馬上會(huì)引起lpfn指向的函數(shù)的動(dòng)作；hMod是鉤子函數(shù)所在模塊的句柄，我們可以很簡(jiǎn)單的設(shè)定其為本應(yīng)用程序的實(shí)例句柄dwThreadId是鉤子相關(guān)函數(shù)的ID用以指定想讓鉤子去鉤哪個(gè)線程，為0時(shí)則攔截整個(gè)系統(tǒng)的消息。,內(nèi)容,鍵盤漢字鍵盤輸入原理鍵盤漢字輸入的總體流程輸入碼對(duì)照表的設(shè)計(jì),1、總體流程圖,2、工作流程,用戶在鍵盤上輸入漢字的輸入碼；鍵盤控制器在檢測(cè)到按鍵后，根據(jù)按鍵的位置產(chǎn)生它們的掃描碼，然后存入鍵盤內(nèi)的緩沖區(qū)中，并觸發(fā)一個(gè)鍵盤的硬件中斷；鍵盤中斷處理程序從鍵盤內(nèi)的緩沖區(qū)中取出掃描碼；鍵盤中斷處理程序把掃描碼轉(zhuǎn)換為ASCII碼，和掃描碼一起存儲(chǔ)在內(nèi)存的鍵盤緩沖區(qū)中；應(yīng)用程序調(diào)用取字符模塊取字符，實(shí)際調(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ù)輸入碼查輸入碼對(duì)照表；代碼轉(zhuǎn)換模塊從輸入碼對(duì)照表獲得對(duì)應(yīng)的漢字機(jī)內(nèi)碼；代碼轉(zhuǎn)換模塊把漢字機(jī)內(nèi)碼交漢字處理模塊；漢字處理模塊通過用戶干預(yù)后，把漢字機(jī)內(nèi)碼交應(yīng)用程序，結(jié)束。,內(nèi)容,鍵盤漢字鍵盤輸入原理鍵盤漢字輸入的總體流程輸入碼對(duì)照表的設(shè)計(jì),1、輸入碼對(duì)照表,輸入碼對(duì)照表是漢字鍵盤輸入中的一個(gè)重要數(shù)據(jù)結(jié)構(gòu)，是漢字輸入碼到機(jī)內(nèi)碼轉(zhuǎn)換的核心，它反映了漢字輸入碼和機(jī)內(nèi)碼之間的映射關(guān)系。一般來說，系統(tǒng)有一種輸入法，就需要為它配備一張對(duì)照表，但內(nèi)碼輸入法是一個(gè)特例，它可以根據(jù)輸入碼計(jì)算出機(jī)內(nèi)碼，所以不需要對(duì)照表。對(duì)照表是以文件的形式存儲(chǔ)在計(jì)算機(jī)中的，一般一張對(duì)照表就是一個(gè)文件，當(dāng)然也有是由一系列的文件組成的。對(duì)照表一般有兩種類型：字對(duì)照表和詞對(duì)照表。在字對(duì)照表中，表示的是一個(gè)一個(gè)漢字和輸入碼的映射關(guān)系，而詞對(duì)照表則表示詞（組）和輸入碼的映射關(guān)系。,2、輸入碼對(duì)照表結(jié)構(gòu)的分類,定長(zhǎng)結(jié)構(gòu)變長(zhǎng)結(jié)構(gòu)計(jì)算結(jié)構(gòu)索引結(jié)構(gòu)其它,4、定長(zhǎng)結(jié)構(gòu),定長(zhǎng)結(jié)構(gòu)的每個(gè)表項(xiàng)的長(zhǎng)度固定。每個(gè)表項(xiàng)一般由有兩個(gè)域組成：一個(gè)域存放漢字或詞（組）的機(jī)內(nèi)碼，另一個(gè)表項(xiàng)存放此漢字或詞（組）的輸入碼。每個(gè)域的長(zhǎng)度是固定的。如一個(gè)表項(xiàng)固定長(zhǎng)度為6個(gè)字節(jié)，其中輸入碼占4個(gè)字節(jié)，漢字占2個(gè)字節(jié)。由于一個(gè)漢字的機(jī)內(nèi)碼一般由2個(gè)字節(jié)構(gòu)成，所以字對(duì)照表可以采用定長(zhǎng)結(jié)構(gòu)。詞對(duì)照表一般不會(huì)采用這種結(jié)構(gòu)，是因?yàn)樵~組長(zhǎng)度不一，容易造成存儲(chǔ)空間的浪費(fèi)。,4、定長(zhǎng)結(jié)構(gòu)（續(xù)）－結(jié)構(gòu),4、定長(zhǎng)結(jié)構(gòu)（續(xù)）,檢索方法掃描法二分法假設(shè)需要檢索的輸入碼為S，對(duì)照表的表項(xiàng)數(shù)為N，分別用IC[i]，HZ[i]表示第i表項(xiàng)的輸入碼和漢字。,4、定長(zhǎng)結(jié)構(gòu)（續(xù)）,掃描法：首先，為了方便檢索，需要把對(duì)照表按照輸入碼的大小從小到大排序。掃描法是指每次查找都從頭開始，一直找到和S相同的輸入碼項(xiàng)i；然后繼續(xù)往后查找，找到和S不同的輸入碼項(xiàng)j；那么，第i項(xiàng)到第j-1項(xiàng)，共j-i項(xiàng)對(duì)應(yīng)的漢字就是輸入碼S對(duì)應(yīng)的重碼集。最大的比較次數(shù)為N，最小的比較次數(shù)為1，平均為（N+1）/2。,4、定長(zhǎng)結(jié)構(gòu)（續(xù)）－掃描法,4、定長(zhǎng)結(jié)構(gòu)（續(xù)）,二分法：二分算法描述如下：①設(shè)置一個(gè)值B=0，E=N；②如果B>E，算法失敗結(jié)束；否則M=[(B+E)/2]；③然后把IC[M]和S比較；④如果相等，則說明找到了一項(xiàng)，由于輸入碼相等的漢字是相鄰存放的，所以只要進(jìn)行前后的掃描，可以得到所有的輸入碼為S的漢字，結(jié)束；⑤如果IC[M]小于S，則B=M+1，轉(zhuǎn)②；⑥如果IC[M]大于S，則E=M-1，轉(zhuǎn)②。,4、定長(zhǎng)結(jié)構(gòu)（續(xù)）－檢索算法,4、定長(zhǎng)結(jié)構(gòu)（續(xù)）,二分法的最大的比較次數(shù)為[log2N]，最小的比較次數(shù)為1，平均約為[log2N]-1。假設(shè)N=20902，則掃描法的平均比較次數(shù)為[(20902+1)/2]=10452，而二分法的比較次數(shù)為（[log220902]-1＝14，明顯比掃描法好。定長(zhǎng)結(jié)構(gòu)的對(duì)照表具有表結(jié)構(gòu)簡(jiǎn)單，容易構(gòu)建，檢索算法簡(jiǎn)單等優(yōu)點(diǎn)，但在存儲(chǔ)空間上存在缺陷。,5、計(jì)算結(jié)構(gòu),計(jì)算結(jié)構(gòu)常用于設(shè)計(jì)字對(duì)照表。每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)漢字，表項(xiàng)等長(zhǎng)，內(nèi)容為該漢字對(duì)應(yīng)的輸入碼。這種結(jié)構(gòu)的對(duì)照表的表項(xiàng)必須按照漢字的特定序列進(jìn)行排列，不能無序。一般情況，都是按照漢字內(nèi)碼進(jìn)行排序，從而方便確定每個(gè)表項(xiàng)對(duì)應(yīng)的漢字機(jī)內(nèi)碼。,5、計(jì)算結(jié)構(gòu)（續(xù)）,輸入碼,,,,,,,,,0123n,5、計(jì)算結(jié)構(gòu)（續(xù)）,計(jì)算結(jié)構(gòu)舉例縱橫碼的碼元集合為：{1234567890}碼長(zhǎng)為1－4，是不等長(zhǎng)碼。字符集采用Unicode/ISO10646-1993。Unicode內(nèi)碼從4E00H到9FA5H共20902個(gè)漢字。每個(gè)表項(xiàng)的內(nèi)容是輸入碼，為1－4個(gè)數(shù)字，每個(gè)數(shù)字可以用BCD碼來表示，需要3位（bits），4個(gè)數(shù)字則需要34＝12位，用2個(gè)字節(jié)表示。如果數(shù)字不足4位，用全“1”位填充。,5、計(jì)算結(jié)構(gòu)（續(xù)）,,表項(xiàng)結(jié)構(gòu)每個(gè)表項(xiàng)的大小為2個(gè)字節(jié)。整張對(duì)照表總共需要220902=41804個(gè)字節(jié)，按照機(jī)內(nèi)碼的大小從小到大排列。,5、計(jì)算結(jié)構(gòu)（續(xù)）,假設(shè)漢字的內(nèi)碼hz可以表示為：hz={hzhhzl|hzh∈R1,hzl∈R2}R1={R|4EH≤R≤FFH}R2={R|00H≤R≤FFH}從上表我們可以得到序號(hào)i和內(nèi)碼hz的關(guān)系：i=(hzh-4EH)*0FFH+hzl則hzh＝[i/0FFH]+4EH//[]表示取整hzl=imod0FFH那么，對(duì)照表的檢索過程就是遍歷表的過程，也就是當(dāng)發(fā)現(xiàn)第i項(xiàng)表項(xiàng)和當(dāng)前輸入碼的BCD碼一致時(shí)，可以通過上面的計(jì)算得到該漢字的機(jī)內(nèi)碼，從而實(shí)現(xiàn)轉(zhuǎn)換過程。,5、計(jì)算結(jié)構(gòu)（續(xù)）,優(yōu)點(diǎn)是節(jié)省空間上例中的對(duì)照表比采用等長(zhǎng)結(jié)構(gòu)可以節(jié)省一半的空間（省了20902個(gè)漢字的空間），但存在需要遍歷整張對(duì)照表的問題,比較次數(shù)為N。當(dāng)一個(gè)漢字有多個(gè)編碼時(shí)，就存在問題了，需要設(shè)置附加表。,6、變長(zhǎng)結(jié)構(gòu),每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)輸入碼。每個(gè)表項(xiàng)有兩個(gè)域：一個(gè)域存放輸入碼，另一個(gè)域存放和該輸入碼對(duì)應(yīng)的所有重碼字或詞組集合。由于第二個(gè)表項(xiàng)的內(nèi)容不定，所以長(zhǎng)度無法確定，造成表項(xiàng)不等長(zhǎng)。這種結(jié)構(gòu)的輸入碼對(duì)照表減少了表項(xiàng)的數(shù)目，不需要為每個(gè)漢字存放輸入碼，所以存儲(chǔ)空間相當(dāng)?shù)乳L(zhǎng)結(jié)構(gòu)有明顯的減少。,6、變長(zhǎng)結(jié)構(gòu)（續(xù)）,以20902個(gè)漢字的縱橫碼對(duì)照表為例，定長(zhǎng)結(jié)構(gòu)需要（2＋2）20902＝83608（字節(jié)）（2個(gè)字節(jié)的BCD輸入碼，2個(gè)字節(jié)的漢字機(jī)內(nèi)碼），而變長(zhǎng)結(jié)構(gòu)只需要209022＋61232＝54050（字節(jié)）（20902個(gè)漢字和6123個(gè)BCD輸入碼），比定長(zhǎng)結(jié)構(gòu)少了近30K，超過三分之一。這種結(jié)構(gòu)存在的問題是檢索時(shí)間相對(duì)也較長(zhǎng)，一般采用掃描法，需要遍歷整張對(duì)照表。,6、變長(zhǎng)結(jié)構(gòu)（續(xù)）,6、變長(zhǎng)結(jié)構(gòu)（續(xù)）,縱橫碼的不等長(zhǎng)對(duì)照表結(jié)構(gòu)描述：::=[]::=::=::=::=[]假設(shè)需要檢索的輸入碼為S，對(duì)照表的表項(xiàng)數(shù)為K，分別用ICi，LENi，HZi表示第i表項(xiàng)的輸入碼、漢字集長(zhǎng)度和漢字重碼集合。,6、變長(zhǎng)結(jié)構(gòu)（續(xù)）,6、變長(zhǎng)結(jié)構(gòu)（續(xù)）,假設(shè)輸入碼的個(gè)數(shù)為K，那么最大的比較次數(shù)為K，最小的比較次數(shù)為1，所以比較次數(shù)依舊平均為（K+1）/2。由于K比N小，所以比較次數(shù)比等長(zhǎng)結(jié)構(gòu)少。如縱橫碼的例子，變長(zhǎng)結(jié)構(gòu)的平均比較次數(shù)是(6123+1)/2=3062次，而等長(zhǎng)結(jié)構(gòu)如采用掃描法則需要（20902＋1）/2=10452，是變長(zhǎng)結(jié)構(gòu)的3倍！,7、索引結(jié)構(gòu),索引是一種最常用的對(duì)照表結(jié)構(gòu)，也是一種高效率的檢索結(jié)構(gòu)。一般索引結(jié)構(gòu)的對(duì)照表分成兩部分：索引表和碼表。索引表的表項(xiàng)由兩部分組成：輸入碼和指針（指向碼表中輸入碼對(duì)應(yīng)的漢字和詞組的首址）。碼表的結(jié)構(gòu)基本和變長(zhǎng)結(jié)構(gòu)類似。,7、索引結(jié)構(gòu)（續(xù)）,7、索引結(jié)構(gòu)（續(xù)）,每個(gè)索引表項(xiàng)對(duì)應(yīng)一個(gè)碼表項(xiàng)，而且是一對(duì)一的關(guān)系，有多少個(gè)索引項(xiàng)就有多少個(gè)碼表項(xiàng)。一般而言，索引表中的每一個(gè)表項(xiàng)是等長(zhǎng)的，而碼表中的每一個(gè)表項(xiàng)長(zhǎng)度是不相等的。索引結(jié)構(gòu)結(jié)合了等長(zhǎng)和變長(zhǎng)的優(yōu)點(diǎn)，通過把輸入碼和漢字串分開的方法，使得索引表組織類似等長(zhǎng)結(jié)構(gòu)（輸入碼域和指針域的長(zhǎng)度一般固定），而碼表組織類似于變長(zhǎng)結(jié)構(gòu)，從而提高了檢索效率，也節(jié)省了空間。,7、索引結(jié)構(gòu)（續(xù)）－二分法,7、索引結(jié)構(gòu)（續(xù)）-舉例,拼音輸入碼為例：比較等長(zhǎng)、變長(zhǎng)和索引結(jié)構(gòu)的對(duì)照表的對(duì)照表大小和檢索效率。由于拼音由21個(gè)聲母和35個(gè)韻母組成，不考慮聲調(diào)。所以可以采用壓縮方法來存放輸入碼，用1－21表示21個(gè)聲母，可以用5位來表示，用1－35表示35個(gè)韻母，可以用6位來表示，一共11位，為了方便起見，共用兩個(gè)字節(jié)存放（如果無聲母或韻母，用0表示）。,7、索引結(jié)構(gòu)（續(xù)）-舉例,7、索引結(jié)構(gòu)（續(xù)）-舉例,等長(zhǎng)結(jié)構(gòu)：::=[]::=::=::=變長(zhǎng)結(jié)構(gòu)：::=[]::=::=::=::=[],7、索引結(jié)構(gòu)（續(xù)）-舉例,索引結(jié)構(gòu)：::=::=[]::=::=::=::=::=[],7、索引結(jié)構(gòu)（續(xù)）-舉例,三種結(jié)構(gòu)比較表,7、索引結(jié)構(gòu)（續(xù)）－稀疏索引,7、索引結(jié)構(gòu)（續(xù)）－稀疏索引,省略了索引表中的輸入碼部分索引表的表項(xiàng)是對(duì)應(yīng)于整個(gè)編碼空間的，也就是即使這個(gè)輸入碼沒有對(duì)應(yīng)的漢字，仍作為一個(gè)表項(xiàng)存在于索引表中如某個(gè)輸入法的碼元集合為26個(gè)字母，碼長(zhǎng)為4，則應(yīng)該有26262626＝456976個(gè)表項(xiàng)表項(xiàng)的排列是按照輸入碼由小到大的次序來排列，也就是從“aaaa”到“zzzz”，假如某個(gè)輸入碼是S1S2S3S4，我們可以計(jì)算得到此輸入碼對(duì)應(yīng)的索引表表項(xiàng)的序號(hào)i：i=(S1-’a’)263＋(S2-’a’)262＋(S3-’a’)26＋S4-’a’把序號(hào)乘以每個(gè)表項(xiàng)的大小就得到了此輸入碼指向碼表的指針在碼表中的首址,7、索引結(jié)構(gòu)（續(xù)）－稀疏索引,問題:可能索引表過大如上面舉的例子，如果每個(gè)表項(xiàng)長(zhǎng)度為6個(gè)字節(jié)，那么索引表長(zhǎng)度為4569766字節(jié)，約2.6M字節(jié)的空間。為了節(jié)省空間，我們一般采用部分索引的技術(shù)取一個(gè)輸入碼中的部分編碼進(jìn)行索引,7、索引結(jié)構(gòu)（續(xù)）－稀疏索引,假設(shè)碼元集合中的碼元數(shù)為m，輸入碼的長(zhǎng)度為n，則每個(gè)索引項(xiàng)的長(zhǎng)度2（假設(shè)指針大小為2個(gè)字節(jié)），如果對(duì)i（i<=n）個(gè)字節(jié)輸入碼作索引，那么索引表的長(zhǎng)度TL為：TL=mi*2即TL=mi*2則i=logmTL/2一般TL的大小在10k左右當(dāng)采用數(shù)字編碼時(shí)m=10，則i=3當(dāng)采用字母編碼時(shí)m=26，則i=2,三、漢字鍵盤輸入系統(tǒng),漢字輸入系統(tǒng)的分類漢字輸入系統(tǒng)的功能漢字鍵盤輸入系統(tǒng)的工作流程,1、按系統(tǒng)在計(jì)算機(jī)中實(shí)現(xiàn)的層次,可以分為：系統(tǒng)層的輸入系統(tǒng)應(yīng)用層的輸入系統(tǒng),2、按操作系統(tǒng)平臺(tái),主要有：DOS下的輸入系統(tǒng)Windows下的輸入系統(tǒng)Linux下的輸入系統(tǒng)Unix下的輸入系統(tǒng)MacSystem下的輸入系統(tǒng)嵌入系統(tǒng)種的的輸入系統(tǒng)……,3、按漢字內(nèi)碼的簡(jiǎn)繁,可以分為：簡(jiǎn)體輸入系統(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、漢字/詞組輸入,單字輸入我你的詞組輸入我們計(jì)算機(jī)短語、短句輸入我的非常多不明白科技是第一生產(chǎn)力句子輸入我到飯店去吃飯。,2、候選字/詞提示和選擇,重碼不可避免輸入系統(tǒng)必須具備候選字/詞提示的功能應(yīng)該常用用字、詞在前提高容錯(cuò)的功能,3、中英文狀態(tài)切換,存在中文和英文兩種狀態(tài)在中文狀態(tài)，可以通過輸入漢字輸入碼輸出漢字在英文文狀態(tài)下，整個(gè)鍵盤都是西文符號(hào),4、翻頁,當(dāng)輸入的漢字輸入碼對(duì)應(yīng)的候選字/詞比較多時(shí)，輸入系統(tǒng)無法在候選框中顯示所有的候選字/詞，只能通過分頁方式顯示?？墒褂玫椒撴I顯示上/下一頁的候選字/詞。常用的翻頁鍵分為前翻頁鍵和后翻頁鍵，一般輸入系統(tǒng)的前/后翻頁鍵為“-”和“+”、“,”和“.”、“[”和“]”、“PageUp”和“PageDown”等。,5、輸入碼清除、刪除、結(jié)束鍵,當(dāng)輸入的輸入碼有誤時(shí)，可以通過輸入碼刪除鍵刪除剛輸入的這個(gè)輸入碼符，也可以通過輸入碼清除鍵刪除所有輸入的輸入碼。實(shí)際上這兩個(gè)鍵的作用是提供一種輸入碼的簡(jiǎn)單編輯功能。絕大多數(shù)的輸入系統(tǒng)不需要輸入碼結(jié)束符，只有輸入碼鍵和選擇鍵沖突時(shí)才需要輸入碼結(jié)束符來區(qū)分兩種狀態(tài)。,6、聯(lián)想,當(dāng)用戶輸入了一個(gè)漢字后，系統(tǒng)提示以這個(gè)漢字為首字的詞組供用戶選擇（不包括首字），這種技術(shù)稱為聯(lián)想技術(shù)。如用戶輸入了“計(jì)”，則系統(tǒng)提示以“計(jì)”作為首字的詞組剩余部分，如“算機(jī)”、“劃”和“策”等,8、全角和半角,鍵盤上的西文字符在輸入計(jì)算機(jī)時(shí)有全角和半角兩種方式。在早期DOS系統(tǒng)下，ASCII字符是中文字符的一半大小，所以稱ASCII字符為半角字符采用雙字節(jié)內(nèi)碼、和中文等寬的西文字符為全角字符。如半角字符“0”的ASCII碼是30H，而全角字符“０”的Unicode內(nèi)碼是0FF10H。在Windows等系統(tǒng)中，由于是圖形界面，所有的字符不是等寬字符，所以一個(gè)ASCII字符不再是一個(gè)中文內(nèi)碼字符的一半。,9、符號(hào)輸入,內(nèi)容,漢字輸入系統(tǒng)的分類漢字輸入系統(tǒng)的功能漢字鍵盤輸入系統(tǒng)的工作流程,1、流程圖,2、中文輸入和西文輸入的差異,從以上的流程我們可以發(fā)現(xiàn)，在西文環(huán)境下，用戶每按下一個(gè)按鍵應(yīng)用程序都會(huì)接收到。而在中文環(huán)境下，用戶按下一個(gè)按鍵后，應(yīng)用程序可能接收不到任何的東西，因?yàn)檩斎胂到y(tǒng)還沒有機(jī)內(nèi)碼返回，需要更多的按鍵后才能有機(jī)內(nèi)碼返回。如圖6.7所示，用戶輸入“w”和“o”后，輸入系統(tǒng)沒有輸出漢字“我”，必須等到用戶再輸入“1”后，才有漢字輸出。這也是漢字輸入和西文輸入的最大差異。,Windows漢字輸入技術(shù),Windows漢字輸入技術(shù)概述Windows下漢字輸入原理在SDK和DDK環(huán)境下開發(fā)輸入系統(tǒng),1、界面,2、概念,輸入法Windows中的漢字輸入法稱為IME(InputMethodEditor)，它的本質(zhì)是一個(gè)轉(zhuǎn)換引擎，通過查字典方式，把鍵盤輸入的按鍵消息轉(zhuǎn)換為各種語言的文字信息。另外，它還提供和用戶、操作系統(tǒng)的接口。輸入法管理器輸入法管理器簡(jiǎn)稱為IMM（InputMethodManager），它是一個(gè)管理各種IME，并在IME和應(yīng)用程序間進(jìn)行通信的系統(tǒng)部件。它不僅為程序員提供了開發(fā)輸入法的接口，還為用戶提供了管理輸入法的界面。,2、概念（續(xù)）,2、概念（續(xù)）,多文種環(huán)境（Multi-lingualEnvironment）所謂多文種環(huán)境是指系統(tǒng)可以為使用各種不同語言文字體系的用戶提供了支撐他們母語的操作環(huán)境。Windows的輸入體系支持多文種環(huán)境，包括中文、日文、韓文、法語和德語等上百種不同的語言體系。也就是說，在Windows下，不僅可以輸入漢字，也可以輸入其它語言文字。漢語言文字僅是其中的一個(gè)環(huán)境而言。鍵盤布局（KeyboardLayout）鍵盤布局規(guī)定了鍵盤上每個(gè)按鍵的物理位置以及每個(gè)按鍵對(duì)應(yīng)的字符。每個(gè)鍵盤布局對(duì)應(yīng)于一種語言，從而根據(jù)這種語言的定義和當(dāng)前的輸入法把按鍵轉(zhuǎn)換為該語言的文字信息。在Windows中，提供了多種不同的鍵盤布局，其中就包括各種中文的鍵盤布局。每個(gè)漢字輸入法就是一個(gè)鍵盤布局，如輸入法“智能ABC”的鍵盤布局是“E004804”，通過注冊(cè)表編輯器可以查看各種輸入法的鍵盤布局,2、概念（續(xù)）,3、特點(diǎn),每個(gè)輸入法只是整個(gè)多文種環(huán)境的一個(gè)部件而已，一個(gè)多文種環(huán)境包含多個(gè)輸入法，如在WindowsXP中，多文種環(huán)境可以包含中文（中國大陸）、中文（中國香港）、中文（中國臺(tái)灣）、日文、韓文等環(huán)境，每個(gè)環(huán)境可以有自己的輸入法；每個(gè)應(yīng)用程序都擁有自己的一個(gè)活動(dòng)輸入法，也就是說，輸入法不再為所有的應(yīng)用程序所共有，同樣的一個(gè)輸入法，可能運(yùn)行多個(gè)實(shí)例；應(yīng)用程序和輸入法之間可以進(jìn)行消息的傳遞，應(yīng)用程序可以控制輸入法的工作；支持從漢字詞組到編碼的反向轉(zhuǎn)換。,內(nèi)容,Windows漢字輸入技術(shù)概述Windows下漢字輸入原理在SDK和DDK環(huán)境下開發(fā)輸入系統(tǒng),1、Windows漢字輸入模型,2、Windows漢字輸入系統(tǒng)基本結(jié)構(gòu),3、Windows漢字輸入原理,當(dāng)用戶在鍵盤上按下一個(gè)鍵后，在應(yīng)用程序調(diào)用GetMessage/PeekMessage前，系統(tǒng)首先調(diào)用輸入法的接口函數(shù)ImeProcessKey，通過這個(gè)函數(shù)判別輸入法是否需要處理這個(gè)鍵，把這個(gè)鍵吃掉；如果返回TRUE，表示輸入法需要處理這個(gè)鍵，那么系統(tǒng)設(shè)置虛鍵的值為VK_PROCESSKEY，然后應(yīng)用程序接收到消息WM_KEYDOWN，其中的值為VK_PROCESSKEY；如果返回FALSE，則表示輸入法不需要處理這個(gè)鍵，直接返回此鍵給應(yīng)用程序，結(jié)束；當(dāng)應(yīng)用程序接收到消息WM_KEYDOWN后，在調(diào)用函數(shù)TranslateMessage時(shí)，系統(tǒng)把用戶按下鍵的掃描碼和虛鍵傳遞給輸入法的接口函數(shù)ImeToAsciiEx。輸入法在處理了按鍵后，根據(jù)處理方法的不同把各種消息存放在消息緩沖區(qū)中，這個(gè)緩沖區(qū)是作為函數(shù)ImeToAsciiEx的一個(gè)參數(shù)傳遞過來的。應(yīng)用程序在消息隊(duì)列中得到由輸入法產(chǎn)生的消息，進(jìn)行相應(yīng)的處理。如果應(yīng)用程序不處理這些消息，則把它傳遞給默認(rèn)窗口（DefaultWindow），然后由系統(tǒng)就把消息傳遞給默認(rèn)的IME窗口，由它來處理這些消息。,內(nèi)容,Windows漢字輸入技術(shù)概述Windows下漢字輸入原理在SDK和DDK環(huán)境下開發(fā)輸入系統(tǒng),在SDK和DDK環(huán)境下開發(fā)輸入系統(tǒng),為了方便編程人員開發(fā)基于Windows的各種驅(qū)動(dòng)程序，Microsoft提供了一套用于開發(fā)的DDK工具包，利用這套工具包就可以開發(fā)輸入法。在DDK中，不僅提供了輸入法的開發(fā)環(huán)境，還提供了相關(guān)文檔以及一個(gè)區(qū)位輸入法的實(shí)例代碼。這個(gè)區(qū)位輸入法經(jīng)編譯后，可以安裝在Windows中。在DDK中的區(qū)位輸入法的代碼，為我們?cè)O(shè)計(jì)其它的輸入法提供了基礎(chǔ)，我們?cè)O(shè)計(jì)新的輸入法主要就是在這個(gè)區(qū)位輸入法的代碼基礎(chǔ)上進(jìn)行修改，這樣可以大大節(jié)省開發(fā)時(shí)間。,