漢字輸入的聯(lián)想功能的實(shí)現(xiàn)方法學(xué)士學(xué)位論文

1、目 錄摘要-引言-一、軟件規(guī)劃原則-1.1程序設(shè)計(jì)思路-1.2容器類(lèi)型選取-1.3用戶(hù)詞庫(kù)建立-二、程序流程及具體實(shí)現(xiàn)-2.1 流程圖-2.2程序具體實(shí)現(xiàn)-三、程序測(cè)試-總結(jié)-參考文獻(xiàn)-摘要該程序預(yù)先將所有的詞組儲(chǔ)存在一文本中，再將這些詞組行列位置建立成map容器.當(dāng)處理器接收到通過(guò)輸入裝置所輸入的中文字時(shí)，該處理器可通過(guò)地址表找到該中文字在數(shù)據(jù)庫(kù)的位置，而至該數(shù)據(jù)庫(kù)中，搜尋以該字為詞首所有組成的詞組，再通過(guò)顯示裝置將所有搜尋到的詞組顯示出來(lái)，供使用者選擇，如此不僅減少輸入的時(shí)間，且減少處理器辨識(shí)文字的過(guò)程，具有運(yùn)用簡(jiǎn)便，節(jié)省時(shí)間的優(yōu)點(diǎn)。關(guān)鍵詞：聯(lián)想 文本查詢(xún) 關(guān)聯(lián)容器 map set Abs

2、tractThis program first put all phrases into a database,then builds a map container with the position of these phrases.When the CPU got the input word,it can find the words position in the database through the address table,then find all the phrases where this word is in the head,and then output the

3、m to the sreen and wait users to choose.It can reduce the input process,is simple and save time. Keywords: legend text query associate container map set漢字輸入的聯(lián)想功能的實(shí)現(xiàn)方法 引言聯(lián)想是將漢字的字音、字形與字義結(jié)合的結(jié)果，它分析漢字在單字、詞之間的聯(lián)系，靠字與字之間各種不同程度的聯(lián)系，以聯(lián)想的方式，或離散重碼，或減少擊鍵次數(shù)，以提高輸入速度。目前稱(chēng)為聯(lián)想技術(shù)的多為以字義聯(lián)想為基礎(chǔ)的構(gòu)詞聯(lián)想法，其利用詞的使用頻度和漢語(yǔ)詞法，在輸入完一個(gè)漢字

4、 后，則在屏幕提示行顯示多個(gè)可與該漢字組成詞組的下一個(gè)漢字的字，供操作人員選擇。這種方式可以敲一次鍵而輸入一個(gè)單字，減少了鍵數(shù)。 早在1968年，中科院計(jì)算所六室顯示組已在717機(jī)上首先實(shí)現(xiàn)了漢字顯示，后來(lái)在SK-1光筆圖形顯示器上有了發(fā)展。在輸入方面，倪光南等人首次提出了利用上下文的關(guān)聯(lián)由計(jì)算機(jī)輔助漢字輸入，即聯(lián)想輸入方法, 也就是從單字處理進(jìn)步到了“字詞”處理。聯(lián)想輸入法發(fā)展二十年至今，已經(jīng)相當(dāng)成熟。由于聯(lián)想輸入法是按以字組詞的方法來(lái)提高輸入效率，使得它可以?huà)旖佑诟鞣N輸入方案之中，目前各種流行的輸入法都附帶了聯(lián)想輸入，其功能也大同小異。中科院計(jì)算所的聯(lián)想輸入法是目前最有代表性的輸入方法，它

5、包含有字到詞，詞到詞和字的聯(lián)想功能。例如，輸入“中”后，屏幕上提示區(qū)出現(xiàn)：“Q國(guó) W波A和 S華Z國(guó)科學(xué)院計(jì)算技術(shù)研究所 X國(guó)共產(chǎn)黨”如按“Q”鍵，即輸入“國(guó)”，提示區(qū)又出現(xiàn)“國(guó)”和“中國(guó)”的聯(lián)想字和聯(lián)想詞：“Q境 W土 E產(chǎn) A家 S界 Z科學(xué)院 X人民“這種聯(lián)想法一次最多可出現(xiàn)123多個(gè)聯(lián)想字和聯(lián)想詞，但與需要輸入的字和詞的直接關(guān)系的不多，較繁瑣，也影響輸入速度。目前聯(lián)想技術(shù)的工作重心已經(jīng)集中到如下方面：1.通過(guò)復(fù)合檢索精確判斷所需要的詞匯，過(guò)濾不相關(guān)的詞句；2.通過(guò)構(gòu)建數(shù)據(jù)庫(kù)，盡量節(jié)省處理時(shí)間，達(dá)到快速輸入目的；3建立專(zhuān)業(yè)詞庫(kù)，并利用詞頻使用程度，提高輸入效率；4將聯(lián)想輸入運(yùn)用于專(zhuān)門(mén)方面

6、，如移動(dòng)設(shè)備，個(gè)人辦公設(shè)備等。本次程序?qū)崿F(xiàn)了聯(lián)想輸入法的基本功能，包含有字到詞，詞到詞和字的聯(lián)想功能，但不像中科院聯(lián)想輸入法智能判斷前文所輸詞組，而是通過(guò)由用戶(hù)直接輸入待聯(lián)想字詞，確定后進(jìn)行聯(lián)想，某一方面說(shuō)提高了效率，但不利于連續(xù)打字，僅作于一般參考之用。通過(guò)建立數(shù)據(jù)庫(kù)而后進(jìn)行搜索的方法，使聯(lián)想功能獨(dú)立而成為一個(gè)程序，可掛接于各種輸入法；設(shè)計(jì)思路明晰，程序簡(jiǎn)潔明了，可進(jìn)一步修改以提高效率；采用文本詞庫(kù)，方便用戶(hù)建立和修改。種輸入法，詞庫(kù)建立修改方便，程序簡(jiǎn)單。一、 軟件規(guī)劃原則對(duì)于一個(gè)軟件，最終用戶(hù)的滿(mǎn)意就是軟件的成功。所以在開(kāi)發(fā)軟件的時(shí)候，對(duì)軟件的人性化設(shè)計(jì)，易用性等進(jìn)行了考慮。特別是對(duì)于用

7、戶(hù)的各種操作包括規(guī)范的操作或責(zé)不規(guī)范的操作可能引起的bug進(jìn)行考慮。1.1程序設(shè)計(jì)思路目前Windows輸入法編程一般采用的是Input Method Editor ，簡(jiǎn)稱(chēng)IME，輸入法的程序名稱(chēng)為*.ime，數(shù)據(jù)文件名稱(chēng)為*.MB,即通常說(shuō)的輸入法編碼表(字典)。Windows系統(tǒng)下漢字輸入法實(shí)際上是將輸入的標(biāo)準(zhǔn)ascii字符串按照一定的編碼規(guī)則轉(zhuǎn)換為漢字或漢字串，進(jìn)入到目的地。由于應(yīng)用程序各不相同，用戶(hù)不可能自己去設(shè)計(jì)轉(zhuǎn)換程序，因此，漢字輸入自然而然落到WINDOWS系統(tǒng)管理中。輸入法與系統(tǒng)的關(guān)系： 鍵盤(pán)事件應(yīng)用程序 Windows的USER.EXE 輸入法管理器 輸入法 系統(tǒng)的鍵盤(pán)事件有

8、windows的user.exe軟件接收后，user.exe在將鍵盤(pán)事件傳導(dǎo)輸入法管理器(Input Method Manager,簡(jiǎn)稱(chēng)IMM)中，管理器 再將鍵盤(pán)事件傳到輸入法中，輸入法根據(jù)用戶(hù)編碼字典，翻譯鍵盤(pán)事件為對(duì)應(yīng)的漢字(或漢字串)，然后再反傳到user.exe中，user.exe再將翻譯后的鍵盤(pán)事件傳給當(dāng)前正運(yùn)行的應(yīng)用程序，從而完成漢字的輸入。實(shí)際上IME文件是一個(gè)動(dòng)態(tài)連接庫(kù)程序（DLL），它與dll文件沒(méi)有區(qū)別，只是名稱(chēng)不同而已。IME類(lèi)是實(shí)現(xiàn)IME用戶(hù)界面部分的預(yù)定義全局窗口類(lèi)?！癐ME”類(lèi)與預(yù)定義的公共控制窗口類(lèi)有許多相同的特點(diǎn)，IME窗口實(shí)例與靜態(tài)控制一樣通過(guò)CreateW

9、indowEx函數(shù)創(chuàng)建，IME類(lèi)窗口自己不響應(yīng)用戶(hù)輸入，取而代之的是接收不同類(lèi)型的控制消息實(shí)現(xiàn)全部IME用戶(hù)接口。應(yīng)用程序可以使用IME類(lèi)創(chuàng)建自己的IME窗口，還可以使用ImmGetDefaultIMEWnd函數(shù)獲取缺省IME窗口。創(chuàng)建自己的IME窗口或者使用缺省IME窗口的應(yīng)用程序被稱(chēng)為IME支持應(yīng)用程序，具有以下優(yōu)點(diǎn)： 包括候選字列表窗口（候選窗口），每一個(gè)應(yīng)用程序可以有自己的用戶(hù)界面窗口實(shí)例，使得用戶(hù)可以在任何輸入過(guò)程的中途停止并切換到另一個(gè)應(yīng)用程序。 因?yàn)镮ME用戶(hù)界面窗口包括應(yīng)用程序窗口句柄，IME用戶(hù)界面窗口可以為應(yīng)用程序提供缺省行為。例如當(dāng)應(yīng)用程序移動(dòng)時(shí)IME用戶(hù)界面窗口自動(dòng)移動(dòng)

10、，自動(dòng)跟隨窗口中的插入符號(hào)位置，為每一個(gè)應(yīng)用程序標(biāo)示模式等等。盡管如此，對(duì)于本次編程來(lái)說(shuō)，仍不采用IME編程，基于如下原因：1、聯(lián)想輸入法與普通輸入法機(jī)制不同，不是將用戶(hù)輸入的鍵盤(pán)事件轉(zhuǎn)換成漢字編碼進(jìn)行取字，而是在已經(jīng)輸入的上下文的基礎(chǔ)上進(jìn)行聯(lián)想，在IME中，這是通過(guò)碼表中詞組的建立構(gòu)成的，相當(dāng)于其它輸入法的一個(gè)附加功能，因此，很難將聯(lián)想輸入法作為一個(gè)獨(dú)立的IME編程予以實(shí)現(xiàn)。2、IME編程屬于MFC范疇，較之一般C語(yǔ)言編程，過(guò)程復(fù)雜得多。同時(shí)需要調(diào)用大量API函數(shù)，就需要對(duì)這些函數(shù)及其參數(shù)設(shè)置有全面的了解。本次論文時(shí)間有限，很難編出一個(gè)完整的程序。同時(shí)作為漢字聯(lián)想功能的基本實(shí)現(xiàn)，如果采用IM

11、E編程，相當(dāng)于遵尋一個(gè)既定的框架，對(duì)各種函數(shù)進(jìn)行堆砌組合，在個(gè)人編程思路上體現(xiàn)不多。3、在詞庫(kù)的建立和修改方面，IME中采用的是mb格式文件，不支持直接的建立和修改，需要用到Windows下自帶的輸入法生成器對(duì)詞庫(kù)和文本進(jìn)行互轉(zhuǎn)換，在用戶(hù)使用層面上并不理想。 在排除IME編程后，剩下的方案只能是通過(guò)自建數(shù)據(jù)庫(kù)，并對(duì)其進(jìn)行查詢(xún)輸出，以實(shí)現(xiàn)聯(lián)想，這里的關(guān)鍵就是數(shù)據(jù)庫(kù)的建立，由于漢字詞庫(kù)的龐大（動(dòng)轍上萬(wàn)個(gè)），顯然不可能手工建立，最理想的是將文本直接進(jìn)行處理。因此，本程序?qū)嶋H使用的是一個(gè)文本查詢(xún)系統(tǒng)。由兩部分構(gòu)成：1、用戶(hù)指定的任意文本文件2、一個(gè)邏輯查詢(xún)機(jī)制，用戶(hù)可以通過(guò)它查詢(xún)文本中的單詞或相鄰的單

12、詞序列我們的程序需要支持哪些任務(wù)呢？1、它必須允許用戶(hù)指明要打開(kāi)的文本文件的名字2、它必須在內(nèi)部組織文本文件以便能夠識(shí)別出每個(gè)詞組在文本中出現(xiàn)的次數(shù)以及在該文本中的位置我們給出的實(shí)現(xiàn)是把單詞項(xiàng)及其相關(guān)聯(lián)的行列位置當(dāng)作一個(gè)map， 之后建立set解決文本文件的檢索和存儲(chǔ)問(wèn)題。而在文本的讀入和存儲(chǔ)過(guò)程中我們使用了順序容器,原因見(jiàn)下文：1.3容器類(lèi)型選取首先，讓我們了解一下什么叫容器：順序容器(sequence container):擁有由單一類(lèi)型元素組成的一個(gè)有序集合。兩個(gè)主要的順序容器是list 和vector。第三個(gè)順序容器為雙端隊(duì)列deque，它提供了與vector 相同的行為，但是對(duì)于首元

13、素的有效插入和刪除提供了特殊的支持。例如，在實(shí)現(xiàn)隊(duì)列時(shí)，deque 比vector 更為合適。關(guān)聯(lián)容器（associative container）支持查詢(xún)一個(gè)元素是否存在，并且可以有效地獲取元素。兩個(gè)基本的關(guān)聯(lián)容器類(lèi)型是map（映射）和（set）集合map 是一個(gè)鍵/值（key/value） 對(duì)：鍵（key）用于查詢(xún)而值（value）包含我們希望使用的數(shù)據(jù)。例如，map可以很好地支持電話(huà)目錄，鍵是人名，值是相關(guān)聯(lián)的電話(huà)號(hào)碼。set包含一個(gè)單一鍵值,有效支持關(guān)于元素是否存在的查詢(xún)。例如當(dāng)我們要?jiǎng)?chuàng)建一個(gè)單詞數(shù)據(jù)庫(kù)，且它包含在某個(gè)文本中出現(xiàn)的單詞時(shí)，文本查詢(xún)系統(tǒng)對(duì)能會(huì)生成一個(gè)單詞集合以排除。程序?qū)?/p>

14、順次讀取文本中的每個(gè)單詞檢查它是否屬于被排除單詞的集合，并根據(jù)查詢(xún)的結(jié)果將其丟棄或者放入數(shù)據(jù)庫(kù)中。map和set都只包含每個(gè)鍵的惟一出現(xiàn)，即每個(gè)鍵只允許出現(xiàn)一次。Multimap（多映射）和multiset（多集合）支持同一個(gè)鍵的多次出現(xiàn)。例如，電話(huà)目錄可能需要為單個(gè)用戶(hù)支持多個(gè)列表，一種實(shí)現(xiàn)方法是使用multimap我們的程序必須要做的第一件事情是存儲(chǔ)來(lái)自文本文件的未知數(shù)目的詞組。這些詞組將被依次存儲(chǔ)為string 對(duì)象,我們的第一個(gè)問(wèn)題是應(yīng)該把單詞存儲(chǔ)在順序容器還是關(guān)聯(lián)容器中?從某種意義上講,我們需要支持查詢(xún)?cè)~組是否存在，如果存在的話(huà)還要獲取到它在文本中相關(guān)的出現(xiàn)位置，因?yàn)槲覀冃枰檎也@

15、取一個(gè)值，所以關(guān)聯(lián)容器map 是最合適的容器類(lèi)型。但是在此之前，我們只需要簡(jiǎn)單地把輸入文本存儲(chǔ)起來(lái)以供后續(xù)處理。對(duì)于這個(gè)前處理過(guò)程，我們只需要順序容器而不是關(guān)聯(lián)容器。問(wèn)題是它應(yīng)該是vector 還是list？vector以及l(fā)ist 都是動(dòng)態(tài)增長(zhǎng)的，在這兩者之中選擇的準(zhǔn)則主要是關(guān)注插入特性以及對(duì)元素的后續(xù)訪(fǎng)問(wèn)要求。vector 表示一段連續(xù)的內(nèi)存區(qū)域，每個(gè)元素被順序存儲(chǔ)在這段內(nèi)存中。對(duì)vector 的隨機(jī)訪(fǎng)問(wèn)，比如先訪(fǎng)問(wèn)元素5 ，然后訪(fǎng)問(wèn)15 ，然后再訪(fǎng)問(wèn)7等等，效率很高，因?yàn)槊看卧L(fǎng)問(wèn)離vector起始處的位移都是固定的。但是，在任意位置而不是在vector 末尾插人元素則效率很低，因?yàn)樗枰?/p>

16、把待插入元素右邊的每個(gè)元素都拷貝一遍。類(lèi)似地，刪除任意一個(gè)而不是vector的最后一個(gè)元素效率同樣很低，因?yàn)榇齽h除元素右邊的每個(gè)元素都必須被復(fù)制一遍。這種代價(jià)對(duì)于大型的復(fù)雜的類(lèi)對(duì)象來(lái)說(shuō)尤其大。list 表示非連續(xù)的內(nèi)存區(qū)域，并通過(guò)一對(duì)指向首尾元素的指針雙向鏈接起來(lái)，從而允許向前和向后兩個(gè)方向進(jìn)行遍歷。在list 的任意位置插入和刪除元素的效率都很高，指針必須被重新賦值，但是不需要用拷貝元素來(lái)實(shí)現(xiàn)移動(dòng)。另一方面它對(duì)隨機(jī)訪(fǎng)問(wèn)的支持并不好。訪(fǎng)問(wèn)一個(gè)元素，需要遍歷中間的元素。另外，每個(gè)元素還有兩個(gè)指針的額外空間開(kāi)銷(xiāo)。下面是選擇順序容器類(lèi)型的一些準(zhǔn)則：1、如果我們需要隨機(jī)訪(fǎng)問(wèn)一個(gè)容器，則vector 要

17、比list 好得多。2、如果我們已知要存儲(chǔ)元素的個(gè)數(shù)，則vector 又是一個(gè)比list 好的選擇。3、如果我們需要的不只是在容器兩端插入和刪除元素，則list 顯然要比vector 好。需要注意的是，為了提高效率,實(shí)際上vector并不是隨每一個(gè)元素的插入而增長(zhǎng)自己,而是當(dāng)vector 需要增長(zhǎng)自身時(shí),它實(shí)際分配的空間比當(dāng)前所需的空間要多一些,也就是說(shuō)它分配了一些額外的內(nèi)存容量,或者說(shuō)它預(yù)留了這些存儲(chǔ)區(qū)(分配的額外容量的確切數(shù)目由具體實(shí)現(xiàn)定義),這個(gè)策略使容器的增長(zhǎng)效率更高。對(duì)于小的數(shù)據(jù)類(lèi)型，vector的性能要比list好得多而對(duì)于大型的數(shù)據(jù)類(lèi)型則相反，list 的性能要好得多。區(qū)別是由于

18、vector 需要重新增長(zhǎng)以及拷貝元素，但是，數(shù)據(jù)類(lèi)型的長(zhǎng)度不是影響容器性能的惟一標(biāo)準(zhǔn)。數(shù)據(jù)類(lèi)型的復(fù)雜性也會(huì)影響到元素插入的性能：無(wú)論是list 還是vector,對(duì)于已定義拷貝構(gòu)造函數(shù)的類(lèi)來(lái)說(shuō),插入這樣的類(lèi)的元素都需要調(diào)用拷貝構(gòu)造函數(shù)。這正說(shuō)明了在簡(jiǎn)單類(lèi)和string 的鏈表之間插入代價(jià)的區(qū)別。簡(jiǎn)單類(lèi)對(duì)象和大型簡(jiǎn)單類(lèi)對(duì)象通過(guò)按位拷貝插入，而string 類(lèi)對(duì)象和大型復(fù)雜類(lèi)對(duì)象通過(guò)調(diào)用拷貝構(gòu)造函數(shù)來(lái)插入。另外隨著每次重新分配內(nèi)存vector 必須為每個(gè)元素調(diào)用拷貝構(gòu)造函數(shù)而且在釋放原來(lái)的內(nèi)存時(shí)它要為每個(gè)元素調(diào)用其相關(guān)類(lèi)型的析構(gòu)函數(shù)。vector 的動(dòng)態(tài)自我增長(zhǎng)越頻繁元素插入的開(kāi)銷(xiāo)就越大。 對(duì)于

19、我們的文本查詢(xún)系統(tǒng)，將使用一個(gè)vector 來(lái)包含string 對(duì)象，并且使用與它相關(guān)聯(lián)的缺省容量。雖然當(dāng)我們插入未知數(shù)目的string時(shí)vector會(huì)動(dòng)態(tài)增長(zhǎng)，但是正如前文所示,其實(shí)際使用性能仍然優(yōu)于list。 關(guān)聯(lián)類(lèi)型容器的選取將在下文程序?qū)崿F(xiàn)中說(shuō)明。1.4用戶(hù)詞庫(kù)建立既然使用的是文本查詢(xún)系統(tǒng)，理論上，所有的文本文件都可以作為詞庫(kù)被使用，但在實(shí)際用途中需要注意：1、 分詞處理，在一個(gè)雜亂的文本中，我們只能是通過(guò)標(biāo)點(diǎn)，空格或回車(chē)等符號(hào)對(duì)詞組進(jìn)行標(biāo)示，一方面加大程序的負(fù)擔(dān)，提高出錯(cuò)率；另一方面分詞效率不高，可能會(huì)造成很多無(wú)用詞組或錯(cuò)誤詞組。2、 本程序是對(duì)中文進(jìn)行處理，而在VC中，是將中文字符

20、作為字符串進(jìn)行處理。則不同的編碼規(guī)則可能會(huì)造成程序識(shí)別錯(cuò)誤。對(duì)應(yīng)上述，為了簡(jiǎn)化程序，并降低不同文本可能造成的程序錯(cuò)誤，對(duì)詞庫(kù)建立制定如下規(guī)則：1、詞組分行排列，即一個(gè)詞組占一行，如此一方面結(jié)構(gòu)清晰，便于修改；另一方面可以簡(jiǎn)化單詞處理，不用對(duì)文本進(jìn)行分詞，減少出錯(cuò)率。同時(shí)也簡(jiǎn)化輸出程序，只需要按單詞行號(hào)進(jìn)行輸出，不需記錄單詞所在列信息。2、文本統(tǒng)一采用ANSI編碼，這是VC環(huán)境下支持的中文編碼。二、 程序流程及具體實(shí)現(xiàn)2.1 流程圖2.2 程序具體實(shí)現(xiàn)在這一節(jié)里，將先分開(kāi)介紹實(shí)現(xiàn)不同功能的各項(xiàng)函數(shù)，最后整合成完整的程序。第一個(gè)任務(wù)是讀入用戶(hù)需要查詢(xún)的文本文件。需要獲取下列信息：每個(gè)單字，這些單字

21、的位置，即所在行數(shù)，這要求最后按行號(hào)保留文本。程序采用getline()函數(shù)讀取istream對(duì)象，向string對(duì)象插入字符，直到文件結(jié)束。此功能由名為retrieve_text()的函數(shù)實(shí)現(xiàn)：/返回值為指向string vector的指針vector*retrieve_text()string file_name;cout file_name;提示用戶(hù)輸入詞庫(kù)讀入文本將其按行儲(chǔ)存詞庫(kù)是否存在?退出程序計(jì)算單詞行位置并存儲(chǔ)生成文本位置map輸入待聯(lián)想字 詞對(duì)map進(jìn)行索引同時(shí)生成set輸出詞組提示用戶(hù)選擇輸出所選詞組 程序流程圖 /打開(kāi)文本文件以便輸入ifstream infile( fil

22、e_name.c_str(), ios:in );if ( !infile ) cerr 錯(cuò)誤，沒(méi)有這樣的詞庫(kù)n 再見(jiàn)n;exit( - 1 );else cout請(qǐng)稍候;cout n;lines_of_text = new vector;string textline;while ( getline( infile, textline, n )lines_of_text-push_back( textline );return lines_of_text;接下來(lái)，需要對(duì)詞組進(jìn)行處理，將str插入到代表文本的字符串vector中。同時(shí)計(jì)算各單字的位置（對(duì)以后基于位置的文本查詢(xún)的支持中將需要這些

23、信息。這一實(shí)現(xiàn)由函數(shù)separate_word()完成,其中使用了find_first_of()函數(shù)標(biāo)記出文本內(nèi)嵌空格，同時(shí)為了防止程序沒(méi)找到空格時(shí)結(jié)束循環(huán)，對(duì)每一行最后一個(gè)單詞都進(jìn)行了處理。typedef pair location; typedef vector loc; typedef vector text; typedef pair text_loctext_loc*separate_words(const vector *text_file)/words:包含獨(dú)立單詞的集合/locations:包含相關(guān)的行/列信息vector *words = new vector;vector

24、*locations =new vector;/重復(fù)完成每一行for ( short line_pos = 0; /當(dāng)前行數(shù)line_pos size();line_pos+ ) /textline:待處理的當(dāng)前文本行/word_pos：文本行中的當(dāng)列列位置short word_pos = 0;string textline = (*lines_of_text) line_pos ;string:size_type eol = textline.length();string:size_type pos = 0, prev_pos = 0;while ( pos = textline.find

25、_first_of( , pos )!= string:npos )/存儲(chǔ)當(dāng)前子串的拷貝words-push_back(textline.substr( prev_pos,pos - prev_pos);/將行/列信息存儲(chǔ)為pairlocations-push_back(make_pair( line_pos, word_pos );/為下一次迭代修改位置信息word_pos+; pos+; prev_pos = pos;/處理最后一個(gè)單詞words-push_back(textline.substr( prev_pos,pos - prev_pos);locations -push_back

26、(make_pair(line_pos,word_pos);text_locations = new text_loc( words, locations );到現(xiàn)在為止我們的程序的控制流如下int main()vector *text_file = retrieve_text);text_loc *text_locations = separate_words( text_file );/ .下一步需要為文本中每個(gè)單字建立一個(gè)行列位置集合，這里引入關(guān)聯(lián)容器類(lèi)型map，這在希望存儲(chǔ)（或修改）一個(gè)相關(guān)的值時(shí)，最為有用。在map中，元素以有序關(guān)系存儲(chǔ)，以此支持高效率的存儲(chǔ)和檢索。本程序只提供了ma

27、p的建立和檢索，可以通過(guò)加入刪除添加功能以實(shí)現(xiàn)在程序中對(duì)詞庫(kù)的修改功能。在map中，程序提供一個(gè)“鍵/值”對(duì)：鍵用來(lái)索引map，而值用作被存儲(chǔ)和檢索的數(shù)據(jù)。本程序中，每個(gè)string對(duì)象用作鍵，行列的vector用作值。為訪(fǎng)問(wèn)位置vector，用下標(biāo)操作符索引map。為使用map，須包含相關(guān)頭文件#include 首先定義并生成map上文sepatate_words()創(chuàng)建了兩個(gè)vector：文本中所有詞的字符串vector，以及相應(yīng)的行列對(duì)的位置vector。對(duì)于字符串vector中的每個(gè)單詞元素，位置vector 中的等價(jià)元素都分別給出了該詞的行列信息。字符串vector為文本map提供了

28、鍵的集合，而位置vector 提供相關(guān)聯(lián)的值集合。separate_words()返回一個(gè)pair對(duì)象它擁有指向這兩個(gè)vector的指針。這個(gè)pair對(duì)象是我們的函數(shù)build_word_map()的參數(shù)。返回值是文本位置map或指向它的指針：typedef pair location;typedef vector loc;typedef vector text;typedef pair text_loc;extern map*build_word_map( const text_loc *text_locations );第一個(gè)準(zhǔn)備工作是從空閑存儲(chǔ)區(qū)中分配一個(gè)空map,以及從作為參數(shù)的pai

29、r對(duì)象中分離出字符串和位置vector:map *word_map = new map;vector *text_words = text_locations -first;vector *text_locs = text_locations -second;接下來(lái),我們需要并行迭代兩個(gè)vector.有兩種情況需要考慮: 1、map中還沒(méi)有單詞在這種情況下需要插入鍵/值對(duì)。2、單詞已經(jīng)被插入。在這種情況下，需要用另外的行列信息修改該項(xiàng)的位置vector。下面是實(shí)現(xiàn)代碼：register int elem_cnt = text_words -size();for ( int ix = 0; ix

30、 elem_cnt; +ix )string textword = ( *text_words ) ix ;/ 排除策略: 如果少于1 個(gè)字符,則不輸入到map 中.if ( textword.size() count(*text_words)ix ) /沒(méi)有，添加loc *ploc = new vector;ploc-push_back( (*text_locs)ix );word_map-insert( value_type( (*text_words)ix, ploc );else/ 修改該項(xiàng)的位置向量(*word_map)(*text_words)ix-push_back(*text_

31、locs)ix);對(duì)于這個(gè)語(yǔ)法復(fù)雜的表達(dá)式:(*word_map)(*text_words)ix-push_back(*text_locs)ix);其實(shí)包含四個(gè)語(yǔ)句：/ 得到要修改的單詞string word = (*text_word)ix;/ 得到位置向量vector *ploc = (*word_map) word ;/ 得到行列對(duì)location loc = (*text_locs)ix; / 插入新的行列對(duì)ploc-push_back(loc);其余的語(yǔ)法復(fù)雜性是因?yàn)椴倏v指針而導(dǎo)致的并不是因?yàn)関ector本身。因?yàn)橹苯討?yīng)用下標(biāo)操作符我們不能寫(xiě)：string word = text_w

32、ordsix; / 錯(cuò)誤相反我們必須先解除指針的引用string word = (*text_words)ix; / 正確 最后build_word_map 返回內(nèi)部建好的mapreturn word_map; 下面給出怎樣在main()函數(shù)中調(diào)用它int main()/ 讀入并分離文本vector *text_file = retrieve_text();text_loc *text_locations = separate_words( text_file);/ 處理單詞/ ./ 生成單詞/位置對(duì)并提示查詢(xún)mapstring,loc*,less*text_map = build_word_

33、map( text_locations );/ .最簡(jiǎn)單獲取一個(gè)值的方法是下標(biāo)操作符。但只有當(dāng)所搜鍵值存在時(shí)，才會(huì)正常運(yùn)行，當(dāng)鍵值實(shí)例不存在時(shí)，使用下標(biāo)操作符會(huì)引起插入一個(gè)實(shí)例。 有兩個(gè)map 操作能夠發(fā)現(xiàn)一個(gè)鍵元素是否存在而且在鍵元素不存在時(shí)也不會(huì)引起插入實(shí)例:1、 Count(keyValue):count()返回map 中keyValue出現(xiàn)的次數(shù)。（當(dāng)然，對(duì)于map而言，返回值只能是0或1）如果返回值非0。我們就可以安全地使用下標(biāo)操作符。2、Find(keyValue)：如果實(shí)例存在，則find()返回指向該實(shí)例的iterator。如果不存在則返回等于end()的iterator。本文

34、使用的是直接進(jìn)行字符串比對(duì)。指向map中元素的iterator指向一個(gè)pair對(duì)象，其中first 擁有鍵，second 擁有值。從map中刪除元素的erase()操作有三種變化形式。為了刪除一個(gè)獨(dú)立的元素，可以傳遞給erase()一個(gè)鍵值或iterator。為了刪除一列元素，傳遞給erase()一對(duì)lieator 。當(dāng)程序搜索到包含聯(lián)想詞的行以后，將這些行組成一個(gè)集合，而該集合的排列采用了set關(guān)聯(lián)容器。map 中鍵/值對(duì)構(gòu)成，好比一個(gè)地址和電話(huà)號(hào)碼以人名為鍵值。相反地set只是鍵的集合。當(dāng)我們只想知道一個(gè)鍵值是否存在時(shí)，set最有用處。與map一樣，set中元素也是以有序關(guān)系存儲(chǔ)的，支持高

35、效率存儲(chǔ)和檢索。為了定義和使用關(guān)聯(lián)容器類(lèi)型set，必須包含其相關(guān)頭文件：#include 可以通過(guò)insert操作將單個(gè)元素插入到set中，也可以通過(guò)向insert()提供一對(duì)iterator以插入一個(gè)元素序列。見(jiàn)下列代碼段，包含set的建立和放入元素：/ 獲得指向位置向量的指針loc *ploc = (*text_map) query_text ;/ 對(duì) 位置項(xiàng)對(duì) 進(jìn)行迭代/ 把每行插入到set 中set occurrence_lines;loc:iterator liter = ploc-begin(),liter_end = ploc-end();while ( liter != lit

36、er_end ) occurrence_lines.insert( occurrence_lines.end(),(*liter).first );+liter;查詢(xún)set對(duì)象中是否存在一個(gè)值的兩個(gè)操作是find()和count()。如果元素存在，則find()返回指向這個(gè)元素的iterator，否則返回一個(gè)等于end()的iterator，表示該元素不存在。如果找到元素，count()返回1 ，如果元素不存在則返回0。若要顯示詞組所在文本行，只需迭代set： register int size = occurrence_lines.size();cout n query_text occur

37、s size (size = 1 time: : times:) nn;set:iterator it=occurrence_lines.begin();for ( ; it != occurrence_lines.end(); +it ) int line = *it;cout t( line line + 1 ) (*text_file)line endl;綜上，可以得到文本查詢(xún)輸出函數(shù)query_text()：void:query_text()string query_text;coutendl;do cout ;cin query_text;if ( query_text.size()

38、 1 ) break;if(query_text=q)return;/建立字母大小寫(xiě)轉(zhuǎn)換，忽略輸入狀態(tài)下的大小寫(xiě)string caps( ABCDEFGHIJKLMNOPQRSTUVWXYZ );string:size_type pos = 0;while ( pos = query_text.find_first_of( caps, pos )!= string:npos )query_text pos = tolower( query_textpos );/ 如果對(duì)map 索引, 輸入query_text, 如無(wú)/ 說(shuō)明沒(méi)有要找的詞int len=query_text.length();

39、set occurrence_lines;map:iterator mapit=(*word_map).begin();while(mapit!=(*word_map).end()if(mapit-first.substr(0,len)=query_text)for(loc:iterator liter = (*(mapit-second).begin(),liter_end = (*(mapit-second).end();liter!=liter_end;liter+)occurrence_lines.insert(occurrence_lines.end(), (*liter).firs

40、t);mapit+;if ( occurrence_lines.empty() cout n對(duì)不起，沒(méi)有可聯(lián)想的詞 .nn;continue;register int size = occurrence_lines.size();cout n query_text的詞組有 size 個(gè) nn;set:iteratorit=occurrence_lines.begin();/記錄行數(shù)int j=0;/設(shè)定數(shù)組存儲(chǔ)行號(hào)int a8; for ( ; it != occurrence_lines.end(); +it ) ; /設(shè)定每頁(yè)顯示八行 if (j=8) getchar(); /j重置 j=

41、0; 定義用戶(hù)選擇行號(hào)，字符類(lèi)型防止輸入字符造成誤操作 char k; coutk; /與0-9比較，9退出，1-8輸出，0繼續(xù) if(k48&k57) coutn(*lines_of_text)ak-48nendl;break; if(k=57) break; j+; coutj ;int line = *it;cout t (*lines_of_text)line endl;aj=line;/j不為0說(shuō)明聯(lián)想詞組不足八行，另處理if(j!=0) char k; coutk; if(k48&kj+49) coutn(*lines_of_text)ak-48nendl;/文本為空，退出whil

42、e ( ! query_text.empty() );cout 謝謝使用，再見(jiàn)n;程序的完整形式在附錄中給出，這里引入了一個(gè)類(lèi)TextQuery將數(shù)據(jù)結(jié)構(gòu)和函數(shù)進(jìn)行封裝：使用C+的類(lèi)機(jī)制用戶(hù)能夠定義自己的數(shù)據(jù)類(lèi)型。因此，類(lèi)經(jīng)常被稱(chēng)為用戶(hù)定義的類(lèi)型（user-defined type, UDT）。通過(guò)類(lèi)，我們可以向一個(gè)已有的類(lèi)型添加功能。類(lèi)也可以用來(lái)引入新的類(lèi)型如Screen類(lèi)和Account類(lèi)。在典型情況下，類(lèi)也可被用來(lái)定義“不能與內(nèi)置數(shù)據(jù)類(lèi)型建立自然映射的抽象”。在類(lèi)定義中：使用信息隱藏（information hiding）來(lái)把類(lèi)的內(nèi)部表示和實(shí)現(xiàn)聲明為私有的（private）,而把在類(lèi)對(duì)象

43、上執(zhí)行的操作聲明為公有的(public).私有內(nèi)部表示被稱(chēng)為是封裝的(encapsulated)而類(lèi)的公有部分被稱(chēng)為類(lèi)接口(class interface)。三、 程序測(cè)試在本次測(cè)試測(cè)試環(huán)境為：WindowsXP中文操作系統(tǒng)、AMD Duron800MHZ CPU、256M SDRAM，同時(shí)開(kāi)有WORD、IE、Adobe Reader、QQ、Winamp等若干程序。測(cè)試中所使用的詞庫(kù)依程序規(guī)則，采用Windows下拼音輸入法碼表中的詞組制作而成。合計(jì)28745個(gè)詞組，排列成28745行，9列，包含全部常用詞組和大多數(shù)不常用詞組，因此本次測(cè)試可以檢驗(yàn)程序在一般使用中的效果。將詞庫(kù)與程序置于同一目

44、錄下，雙擊程序，出現(xiàn)如圖1所示DOS界面：圖1首先，程序提示用戶(hù)輸入詞庫(kù)，本次詞庫(kù)名為通用，若輸入不存在詞庫(kù)，程序自動(dòng)退出。輸入詞庫(kù)后，程序開(kāi)始讀入文本，建立數(shù)據(jù)庫(kù)，此時(shí)出現(xiàn)“請(qǐng)稍候”字樣。之后提示輸入待聯(lián)想字詞，并提示按q退出。這一過(guò)程大約需要8-10秒時(shí)間，首先測(cè)試字的聯(lián)想功能：輸入“國(guó)”字后，程序首先列出聯(lián)想詞組數(shù)目有222個(gè)，而后以分頁(yè)方式，每頁(yè)列出八個(gè)詞組，并提示用戶(hù)繼續(xù)或是退出。此過(guò)程耗時(shí)極短，幾乎沒(méi)有任何停頓。此時(shí)用戶(hù)選0，程序繼續(xù)列出下頁(yè)詞組。此時(shí)用戶(hù)選7，輸出詞組國(guó)防教育，并自動(dòng)轉(zhuǎn)到查詢(xún)狀態(tài)。接下來(lái)測(cè)試詞組聯(lián)想：輸入“國(guó)防部”，程序列出兩個(gè)詞組備選。此時(shí)輸入0跳出。若輸入詞無(wú)

45、可聯(lián)想詞，如輸入“國(guó)防大學(xué)”，則提示用戶(hù)無(wú)可聯(lián)想詞，同時(shí)轉(zhuǎn)到查詢(xún)狀態(tài)。最后按q，程序退出。測(cè)試結(jié)果：程序在最初導(dǎo)入詞庫(kù)耗時(shí)較多，應(yīng)該是由于詞庫(kù)較大原因，以目前詞庫(kù)規(guī)模，應(yīng)該不會(huì)有超過(guò)10秒的情況。故暫定10秒為讀入詞庫(kù)需時(shí)上限。在接下來(lái)查詢(xún)過(guò)程中，程序運(yùn)行十分流暢，相信是map的作用，在功能實(shí)現(xiàn)方面，暫無(wú)BUG顯示，完成情況良好?？傮w測(cè)試結(jié)果令人滿(mǎn)意。總結(jié) 本輸入法程序與流行的IME編程不同，主要使用關(guān)聯(lián)容器建立了一個(gè)文本查詢(xún)系統(tǒng)，用以進(jìn)行詞組聯(lián)想，具有簡(jiǎn)單，易用，可改進(jìn)的特點(diǎn)。由于時(shí)間原因，不能對(duì)軟件進(jìn)行多次測(cè)試，所以軟件可能存在未知的bug。同時(shí)，由于本人編程水平的限制，對(duì)該軟件的功能開(kāi)發(fā)

46、仍不完全，有待日后不斷完善，擴(kuò)充。附錄完整程序:/標(biāo)準(zhǔn)庫(kù)頭文件#include #include #include #include #include #include /標(biāo)準(zhǔn)C+之前的iostream頭文件#include #include /標(biāo)準(zhǔn)C頭文件#include #include #include /使用標(biāo)準(zhǔn)類(lèi)空間using namespace std;/typedefs使聲明更簡(jiǎn)單typedef pair location; typedef vector loc; typedef vector text; typedef pair text_loc;class TextQuery

47、 public:TextQuery() memset( this, 0, sizeof( TextQuery ); static voidfilter_elements( string felems ) filt_elems = felems; void query_text();void doit() retrieve_text();separate_words();build_word_map();private:void retrieve_text();void separate_words();void build_word_map();private:vector *lines_of

48、_text;text_loc *text_locations;map *word_map;static string filt_elems;voidTextQuery:retrieve_text()string file_name;cout file_name;ifstream infile( file_name.c_str(), ios:in );if ( !infile ) cerr 錯(cuò)誤，沒(méi)有這樣的詞庫(kù)n 再見(jiàn)n;exit( - 1 );else cout請(qǐng)稍候;cout n;lines_of_text = new vector;string textline;while ( getline( infile, textline, n )lines_of_text-push_back( textli