基于Trie樹的快速電子詞典開發

蔡琪　劉東霞

摘 要： 當今社會在步入一個大數據時代，時間和效率舉足輕重。因此設計和開發出一款能快速檢索目標詞匯的電子詞典具有十分重要的現實意義。開發的電子詞典系統運用Windows API開發，采用Trie樹的數據結構設計。結果表明：電子詞典實現了Trie樹結構的存取和快速Hash映射查詞，實現主流電子詞典常用功能，包括單詞查找、添加生詞、我的單詞本、課程設置、單詞測試和幫助等，可滿足大部分用戶的需求，具有良好的擴展性。

關鍵詞： 快速檢索； Trie樹； Hash查找； 電子詞典

中圖分類號： TN919?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2014）12?0090?03

Abstract： As a foreign language plays a more and more important role， a electronic dictionary for quick retrieval target vocabulary was designed and developed. The Windows API and Trie tree data structure are adopted in the electronic dictionary system design and development. The access and rapid HASH map check word of Trie tree structure were realized in the electronic dictionary. The common functions of the mainstream electronic dictionary， including word lookup， new words addition， my words book， curriculum setting， word test and help， were implemented. It can meet the needs of most users and has good scalability.

Keywords： rapid retrieval； Trie tree； Hash lookup； electronic dictionary

隨著外語發揮著越來越重要的作用，與此同時，社會正在步入一個大數據時代，時間和效率舉足輕重[1]。通過深入學習和研究程序設計技術、數據庫系統開發和應用，設計和開發出一款能夠滿足不同用戶需求的多功能電子詞典系統，以幫助英語學習者更方便、更快捷地查詢單詞、記憶單詞，既有效，又自由地對詞庫進行管理和操作[2?3]。采用Trie樹結構造單詞查找樹和快速Hash映射取詞，可在占用少量計算機硬件資源的基礎上，實現快速查詢目標詞匯的功能。因此設計和開發這款能快速檢索目標詞匯的電子詞典有十分重要的現實意義，能很好應對在大數據時代下有效地滿足了用戶需求。

1 Trie樹簡介

1.1 Trie樹簡介

Trie樹又稱為字典樹，是一種樹形結構，他是一種哈希樹的變種，是一種用于快速檢索的多叉樹數據結構[4]。典型應用是用于統計和排序、查詢大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本的詞頻統計等。Trie樹也有其缺點，Trie樹的內存消耗非常大。當然，用左兒子右兄弟的方法建樹，可能效果會好一些[5]。

1.2 Trie性質

很多人認為Trie的根節點不包含任何字符信息，在此認為習慣的Trie根節點卻包含信息，而這樣也方便，下面敘述Trie的性質 （基于本文所討論的簡單Trie樹）[6?7]：

（1） 字符的種數決定每個節點的出度，即branch數組（空間換時間思想）。

（2） branch數組的下標代表字符相對于a的相對位置。

（3） 采用標記的方法確定是否為字符串。

（4） 插入、查找的復雜度均為O（len），len為字符串長度。

1.3 Trie的示意圖

如圖1所示，該Trie樹存有abc，d，da，dda四個字符串，如果是字符串會在節點的尾部進行標記[8?10]。沒有后續字符的branch分支指向NULL。

2 設計與實現

2.1 系統設計思想

電子詞典軟件面向用戶時，重要的是其查詢效率與可信性，即用戶能迅速而又準確地查詢到詞語的相關注釋。設計本電子詞典主要是為了用于幫助用戶查找一些不懂的單詞及其相關內容。故本系統應該支持以下電子詞典的核心功能：

（1） 查詢單詞功能。具有很高的查詢效率。

（2） 單詞測試功能。分為知道英語單詞選擇中文解釋和知道中文解釋選擇英語單詞兩項功能。

（3） 生詞添加和新詞構造功能。分為單個添加和批量添加功能。

（4） 詞匯查看功能。核對和查看各詞庫詞匯及信息。

（5） 我的生詞本功能。自定義的詞庫及單詞測試功能。

（6） 課程設置功能。

2.2 系統功能結構問題

系統功能模塊圖如圖2所示。

2.2.1 單詞查詢

單詞查詢是電子詞典最基本也是最重要的功能，只要用戶輸入想要查詢的單詞，電子詞典將自動幫助用戶進行單詞查詢，當詞庫中有該詞匯，電子詞典將快速返回詞庫中關于該詞匯的相關信息給用戶。當用戶輸入時，應用程序能夠智能列出所有相近備選的單詞，這可以方便用戶在未完成整個單詞輸入的情況下查詢出目標詞匯結果。返回結果包括所查詢單詞的記性、音標和中文翻義等。同時，在電子詞典顯示板下方會智能地顯示部分相近的詞匯的查詢結果。實現方法：用戶敲擊鍵盤輸入某字符時，操作系統會發出一個WM_KEYDOWN的消息，然后電子詞典應用程序有相應的回調函數自動響應對所構造的單詞查找樹進行前序遍歷，遍歷到當前輸入的字符，得出查詢結果顯示在電子詞典顯示板上。然后把部分相近的單詞也綁定在結果顯示板上。

2.2.2 添加生詞

生詞添加分為單個添加和批量添加。單個單詞添加是在用戶界面上輸入要添加的新單詞及單詞相關的信息，然后保存到指定的生詞庫即可。而批量添加則是在用戶界面上選擇要添加單詞庫文件的路徑，單詞庫文件須事先按要求及格式準備好，然后點擊確定添加即可。

2.2.3 我的單詞本

我的單詞本包括以下幾個功能：添加詞匯功能（注意：此處的添加詞匯功能實現與上面的“添加詞匯”功能一致，只是所添加的詞匯是添加到“用戶自定義生詞本”上）；單詞查看功能；單詞測試功能。

（1） 添加生詞：與上面“添加詞庫”中的“單個添加”功能一致，只是重寫向的文件為“用戶自定義生詞本”。

（2） 詞匯查看。電子詞典詞庫存在出現遺漏、錯誤的可能性，也可能詞庫單詞不夠完善的情況。相應的電子詞典系統應該有一種可讓用戶查看詞庫內容的功能，因此把電子詞典設計成能隨時讓用戶查看任意詞庫的所有單詞和信息，以滿足用戶要添加或修改詞庫的意愿。詞匯查看功能主要就是選擇相應的詞庫，然后把詞庫中的單詞及信息呈現在用戶界面上，用戶可以按序地去核對詞庫，查看詞庫是否存在遺漏，或發生錯誤，或缺少一些詞匯。用戶也可以通過查詢來檢查該單詞是否存在生詞庫中。若發現詞庫存在遺漏，則可以及時添加；若詞庫中單詞發生錯誤，則可以及時個性；若發現一些詞匯不在詞庫中，則可以通過上述的添加功能添加進指定詞庫中。

（3） 單詞測試。單詞測試功能，能以游戲選擇的形式達到讓讀者輕松背誦或復習單詞的目的，該電子詞典針對不同用戶的不同需求可選擇不同生詞庫來進行單詞測試，從而讓用戶對自己的詞匯水平有一個大體的了解，同時用戶也達到了背誦和復習單詞的目的。

2.2.4 課程設置功能

在用戶未自定義詞庫之前，本電子詞典系統已經包括有考研詞庫、四級詞庫、六級詞庫、生詞庫、GRE的幾大詞庫。加上用戶自定義的詞庫，必然會讓詞庫變得更大，然后針對不同的用戶對象，會有不同的用戶需求，因此，在電子詞典系統進設計具有選擇詞庫，設置詞庫功能，可方便不同的用戶，提高用戶的學習效率，增強電子詞典軟件的友好度。

在初次設置課程時，程序會在本地的電子詞典的目錄下生成一個名詞“config.ini”的文件，里面存放用戶的課程設置情況。當初次運行時，在未設置課程前則系統無法進行單詞測試功能。在要重新選擇課程時，電子詞典應用程序會對該文件作出修改，修改成為當前所選的詞庫，以便于滿足不同的用戶需求。

在用戶要進行單詞測試或查看詞庫信息時，首先會到磁盤中找本電子詞典項目目錄下是否有“config.ini”這個文件。若沒有發現此文件，則要求用戶選設置課程，并將用戶所選課程信息生成“config.ini”文件，然后在該課程下進行單詞測試或查看詞匯信息即可。若在項目目錄下發現有此配置信息文件，直接從“config.ini”文件中讀取課程信息，然后以該信息進行單詞測試或查看詞匯信息即可。

2.2.5 幫助功能

作為一款面向用戶的應用軟件，提供軟件的操作說明和幫助是十分有必要的，是衡量軟件友好度的一個重要指標。當用戶初次接觸此軟件時，因為有了操作說明或者是幫助，能幫助他們快速上手，熟悉軟件界面，嘗試運用軟件實現功能達到合用軟件的目的。倘若沒有操作說明和幫助，那么用戶只能通過自己的摸索來對軟件進行操作。在摸索過程中，許多用戶因為缺乏耐心或軟件操作過于復雜而放棄使用此款軟件，這是軟件開發的一個大忌，無疑對軟件的推廣產生不良影響。因而，軟件提供一定的操作說明或幫助，能讓用戶用得方便舒服，軟件效益也能隨之得到提升。

3 結 語

本文論述了一個基于Trie樹的快速電子詞典的設計與實現，展現了本電子詞典在大數據時代中所能發揮出的優點。主要是采用基于Trie樹為數據結構，以本地文件為詞庫以及用Windows API進行編碼實現的電子詞典，通過程序構建本地文件流對象，將詞庫單詞讀入內存，并在內存中構建一棵字典查找樹，這樣使得單詞查詢只需在內存中進行，有效提高了查詢目標詞匯速度。

參考文獻

[1] KNOWLES F E. The Computer in lexicography [M]. [S.l.]： CiteULike， 1990： 1645?1672.

[2] ZHANG Yi?hua. Think for the development strategy of the electronic dictionary in our country [J]. Lexicographical Study， 2007（2）： 112?119.

[3] DE SCHRYVER Gilles?Maurice. Lexicographers` dreams in the eectronic?dctionary age [J]. International Journal of Lexicography， 2003， 16（2）： 143?199.

[4] BOGURAEV， B， BRISCO T. Computational lexicography for natural language processing [M]. [S.l.]： Longman， 1989.

[5] PUSTEJOVSKY J， BERGLER S. Lexical semantics and knowledge representation [J]. Lecture Notes in Artificial Intelligence， 1992， 627： 86?95.

[6] YOKOI Toshio. The EDR electronic dictionary [J]. Communications of the ACM， 1995， 38（11）： 42?44.

[7] 王博文.通用類Trie樹及自動生成[J].計算機應用，2000（12）：74?75.

[8] 朱文強.Trie樹和單字倒排相結合的漢英詞典查找機制[J].哈爾濱工業大學學報：自然科學版，2008（2）：182?185.

[9] 何鴻君.一種簡單高效的電子詞典組織策略[J].計算機科學，1996，23（2）：56?57.

[10] 李娜.用于文本智能處理的電子詞典的一種設計方法[J].南京師范大學學報，2003（3）：31?35.

2.2.2 添加生詞

生詞添加分為單個添加和批量添加。單個單詞添加是在用戶界面上輸入要添加的新單詞及單詞相關的信息，然后保存到指定的生詞庫即可。而批量添加則是在用戶界面上選擇要添加單詞庫文件的路徑，單詞庫文件須事先按要求及格式準備好，然后點擊確定添加即可。

2.2.3 我的單詞本

我的單詞本包括以下幾個功能：添加詞匯功能（注意：此處的添加詞匯功能實現與上面的“添加詞匯”功能一致，只是所添加的詞匯是添加到“用戶自定義生詞本”上）；單詞查看功能；單詞測試功能。

（1） 添加生詞：與上面“添加詞庫”中的“單個添加”功能一致，只是重寫向的文件為“用戶自定義生詞本”。

（2） 詞匯查看。電子詞典詞庫存在出現遺漏、錯誤的可能性，也可能詞庫單詞不夠完善的情況。相應的電子詞典系統應該有一種可讓用戶查看詞庫內容的功能，因此把電子詞典設計成能隨時讓用戶查看任意詞庫的所有單詞和信息，以滿足用戶要添加或修改詞庫的意愿。詞匯查看功能主要就是選擇相應的詞庫，然后把詞庫中的單詞及信息呈現在用戶界面上，用戶可以按序地去核對詞庫，查看詞庫是否存在遺漏，或發生錯誤，或缺少一些詞匯。用戶也可以通過查詢來檢查該單詞是否存在生詞庫中。若發現詞庫存在遺漏，則可以及時添加；若詞庫中單詞發生錯誤，則可以及時個性；若發現一些詞匯不在詞庫中，則可以通過上述的添加功能添加進指定詞庫中。

（3） 單詞測試。單詞測試功能，能以游戲選擇的形式達到讓讀者輕松背誦或復習單詞的目的，該電子詞典針對不同用戶的不同需求可選擇不同生詞庫來進行單詞測試，從而讓用戶對自己的詞匯水平有一個大體的了解，同時用戶也達到了背誦和復習單詞的目的。

2.2.4 課程設置功能

在用戶未自定義詞庫之前，本電子詞典系統已經包括有考研詞庫、四級詞庫、六級詞庫、生詞庫、GRE的幾大詞庫。加上用戶自定義的詞庫，必然會讓詞庫變得更大，然后針對不同的用戶對象，會有不同的用戶需求，因此，在電子詞典系統進設計具有選擇詞庫，設置詞庫功能，可方便不同的用戶，提高用戶的學習效率，增強電子詞典軟件的友好度。

在初次設置課程時，程序會在本地的電子詞典的目錄下生成一個名詞“config.ini”的文件，里面存放用戶的課程設置情況。當初次運行時，在未設置課程前則系統無法進行單詞測試功能。在要重新選擇課程時，電子詞典應用程序會對該文件作出修改，修改成為當前所選的詞庫，以便于滿足不同的用戶需求。

在用戶要進行單詞測試或查看詞庫信息時，首先會到磁盤中找本電子詞典項目目錄下是否有“config.ini”這個文件。若沒有發現此文件，則要求用戶選設置課程，并將用戶所選課程信息生成“config.ini”文件，然后在該課程下進行單詞測試或查看詞匯信息即可。若在項目目錄下發現有此配置信息文件，直接從“config.ini”文件中讀取課程信息，然后以該信息進行單詞測試或查看詞匯信息即可。

2.2.5 幫助功能

作為一款面向用戶的應用軟件，提供軟件的操作說明和幫助是十分有必要的，是衡量軟件友好度的一個重要指標。當用戶初次接觸此軟件時，因為有了操作說明或者是幫助，能幫助他們快速上手，熟悉軟件界面，嘗試運用軟件實現功能達到合用軟件的目的。倘若沒有操作說明和幫助，那么用戶只能通過自己的摸索來對軟件進行操作。在摸索過程中，許多用戶因為缺乏耐心或軟件操作過于復雜而放棄使用此款軟件，這是軟件開發的一個大忌，無疑對軟件的推廣產生不良影響。因而，軟件提供一定的操作說明或幫助，能讓用戶用得方便舒服，軟件效益也能隨之得到提升。

3 結 語

本文論述了一個基于Trie樹的快速電子詞典的設計與實現，展現了本電子詞典在大數據時代中所能發揮出的優點。主要是采用基于Trie樹為數據結構，以本地文件為詞庫以及用Windows API進行編碼實現的電子詞典，通過程序構建本地文件流對象，將詞庫單詞讀入內存，并在內存中構建一棵字典查找樹，這樣使得單詞查詢只需在內存中進行，有效提高了查詢目標詞匯速度。

參考文獻

[1] KNOWLES F E. The Computer in lexicography [M]. [S.l.]： CiteULike， 1990： 1645?1672.

[2] ZHANG Yi?hua. Think for the development strategy of the electronic dictionary in our country [J]. Lexicographical Study， 2007（2）： 112?119.

[3] DE SCHRYVER Gilles?Maurice. Lexicographers` dreams in the eectronic?dctionary age [J]. International Journal of Lexicography， 2003， 16（2）： 143?199.

[4] BOGURAEV， B， BRISCO T. Computational lexicography for natural language processing [M]. [S.l.]： Longman， 1989.

[5] PUSTEJOVSKY J， BERGLER S. Lexical semantics and knowledge representation [J]. Lecture Notes in Artificial Intelligence， 1992， 627： 86?95.

[6] YOKOI Toshio. The EDR electronic dictionary [J]. Communications of the ACM， 1995， 38（11）： 42?44.

[7] 王博文.通用類Trie樹及自動生成[J].計算機應用，2000（12）：74?75.

[8] 朱文強.Trie樹和單字倒排相結合的漢英詞典查找機制[J].哈爾濱工業大學學報：自然科學版，2008（2）：182?185.

[9] 何鴻君.一種簡單高效的電子詞典組織策略[J].計算機科學，1996，23（2）：56?57.

[10] 李娜.用于文本智能處理的電子詞典的一種設計方法[J].南京師范大學學報，2003（3）：31?35.

2.2.2 添加生詞

生詞添加分為單個添加和批量添加。單個單詞添加是在用戶界面上輸入要添加的新單詞及單詞相關的信息，然后保存到指定的生詞庫即可。而批量添加則是在用戶界面上選擇要添加單詞庫文件的路徑，單詞庫文件須事先按要求及格式準備好，然后點擊確定添加即可。

2.2.3 我的單詞本

我的單詞本包括以下幾個功能：添加詞匯功能（注意：此處的添加詞匯功能實現與上面的“添加詞匯”功能一致，只是所添加的詞匯是添加到“用戶自定義生詞本”上）；單詞查看功能；單詞測試功能。

（1） 添加生詞：與上面“添加詞庫”中的“單個添加”功能一致，只是重寫向的文件為“用戶自定義生詞本”。

（2） 詞匯查看。電子詞典詞庫存在出現遺漏、錯誤的可能性，也可能詞庫單詞不夠完善的情況。相應的電子詞典系統應該有一種可讓用戶查看詞庫內容的功能，因此把電子詞典設計成能隨時讓用戶查看任意詞庫的所有單詞和信息，以滿足用戶要添加或修改詞庫的意愿。詞匯查看功能主要就是選擇相應的詞庫，然后把詞庫中的單詞及信息呈現在用戶界面上，用戶可以按序地去核對詞庫，查看詞庫是否存在遺漏，或發生錯誤，或缺少一些詞匯。用戶也可以通過查詢來檢查該單詞是否存在生詞庫中。若發現詞庫存在遺漏，則可以及時添加；若詞庫中單詞發生錯誤，則可以及時個性；若發現一些詞匯不在詞庫中，則可以通過上述的添加功能添加進指定詞庫中。

（3） 單詞測試。單詞測試功能，能以游戲選擇的形式達到讓讀者輕松背誦或復習單詞的目的，該電子詞典針對不同用戶的不同需求可選擇不同生詞庫來進行單詞測試，從而讓用戶對自己的詞匯水平有一個大體的了解，同時用戶也達到了背誦和復習單詞的目的。

2.2.4 課程設置功能

在用戶未自定義詞庫之前，本電子詞典系統已經包括有考研詞庫、四級詞庫、六級詞庫、生詞庫、GRE的幾大詞庫。加上用戶自定義的詞庫，必然會讓詞庫變得更大，然后針對不同的用戶對象，會有不同的用戶需求，因此，在電子詞典系統進設計具有選擇詞庫，設置詞庫功能，可方便不同的用戶，提高用戶的學習效率，增強電子詞典軟件的友好度。

在初次設置課程時，程序會在本地的電子詞典的目錄下生成一個名詞“config.ini”的文件，里面存放用戶的課程設置情況。當初次運行時，在未設置課程前則系統無法進行單詞測試功能。在要重新選擇課程時，電子詞典應用程序會對該文件作出修改，修改成為當前所選的詞庫，以便于滿足不同的用戶需求。

在用戶要進行單詞測試或查看詞庫信息時，首先會到磁盤中找本電子詞典項目目錄下是否有“config.ini”這個文件。若沒有發現此文件，則要求用戶選設置課程，并將用戶所選課程信息生成“config.ini”文件，然后在該課程下進行單詞測試或查看詞匯信息即可。若在項目目錄下發現有此配置信息文件，直接從“config.ini”文件中讀取課程信息，然后以該信息進行單詞測試或查看詞匯信息即可。

2.2.5 幫助功能

作為一款面向用戶的應用軟件，提供軟件的操作說明和幫助是十分有必要的，是衡量軟件友好度的一個重要指標。當用戶初次接觸此軟件時，因為有了操作說明或者是幫助，能幫助他們快速上手，熟悉軟件界面，嘗試運用軟件實現功能達到合用軟件的目的。倘若沒有操作說明和幫助，那么用戶只能通過自己的摸索來對軟件進行操作。在摸索過程中，許多用戶因為缺乏耐心或軟件操作過于復雜而放棄使用此款軟件，這是軟件開發的一個大忌，無疑對軟件的推廣產生不良影響。因而，軟件提供一定的操作說明或幫助，能讓用戶用得方便舒服，軟件效益也能隨之得到提升。

3 結 語

本文論述了一個基于Trie樹的快速電子詞典的設計與實現，展現了本電子詞典在大數據時代中所能發揮出的優點。主要是采用基于Trie樹為數據結構，以本地文件為詞庫以及用Windows API進行編碼實現的電子詞典，通過程序構建本地文件流對象，將詞庫單詞讀入內存，并在內存中構建一棵字典查找樹，這樣使得單詞查詢只需在內存中進行，有效提高了查詢目標詞匯速度。

參考文獻

[1] KNOWLES F E. The Computer in lexicography [M]. [S.l.]： CiteULike， 1990： 1645?1672.

[2] ZHANG Yi?hua. Think for the development strategy of the electronic dictionary in our country [J]. Lexicographical Study， 2007（2）： 112?119.

[3] DE SCHRYVER Gilles?Maurice. Lexicographers` dreams in the eectronic?dctionary age [J]. International Journal of Lexicography， 2003， 16（2）： 143?199.

[4] BOGURAEV， B， BRISCO T. Computational lexicography for natural language processing [M]. [S.l.]： Longman， 1989.

[5] PUSTEJOVSKY J， BERGLER S. Lexical semantics and knowledge representation [J]. Lecture Notes in Artificial Intelligence， 1992， 627： 86?95.

[6] YOKOI Toshio. The EDR electronic dictionary [J]. Communications of the ACM， 1995， 38（11）： 42?44.

[7] 王博文.通用類Trie樹及自動生成[J].計算機應用，2000（12）：74?75.

[8] 朱文強.Trie樹和單字倒排相結合的漢英詞典查找機制[J].哈爾濱工業大學學報：自然科學版，2008（2）：182?185.

[9] 何鴻君.一種簡單高效的電子詞典組織策略[J].計算機科學，1996，23（2）：56?57.

[10] 李娜.用于文本智能處理的電子詞典的一種設計方法[J].南京師范大學學報，2003（3）：31?35.