基于Android系統的聯系人最大匹配檢索算法設計與實現*

王超

（1.廣州華商職業學院 2.中山大學）

0 引言

隨著手機技術的迅速發展，搭載了開源手機操作系統Android的手機已經成為人們生活中密不可分的一部分。Android平臺作為開發平臺，由Linux內核、函數庫、虛擬機、中間件、用戶界面和應用軟件組成。Android平臺提供了四大組件：Activity、Service、Content Provider和Broadcast Receiver廣播接收器[1]。其中Content Provider提供應用程序指定的數據集合給其它應用程序訪問。

手機聯系人資料存儲在contacts2.db數據庫中，作為記錄通訊地址的集合，包含多項內容：姓名、電話、單位電話、移動電話、家庭電話、傳真、電子郵件、QQ、MSN/個人主頁、公司、生日、郵編、頭像、skype、街道地址等[2]。用戶使用手機搜索聯系人時，期望包含全方位的檢索結果。基于Android系統的聯系人檢索算法可分為利用系統庫函數檢索和非系統庫函數檢索兩種實現方式，本文討論非系統庫函數的聯系人檢索算法。

研究手機聯系人檢索算法在Java環境下，使用編譯軟件eclipse和谷歌提供的Android SDK、ADT集成環境完成。

1 Android聯系人存儲介紹

自Android2.0（API Level 5）以后，聯系人數據主要被安排存儲在3個表中：Contacts，Raw Contacts和Data。這3個表對應的關系結構如圖1所示。

圖1 Android聯系人存儲表結構表

Contacts表是聯系人信息的集合；Raw Contacts記錄的是聯系人來自某信息源的信息，例如本地輸入，來自google等；Data則是具體的信息存儲，包含聯系電話、家庭電話、手機號碼等。每一個 Data都存放一個具體的信息[3]。

Android聯系人檢索庫函數是通過 Content Provider，即內容提供者完成。對外提供訪問的途徑是URI，主要包含以下7種：

1) 聯系人URI：

2) 聯系人電話URI:

3) 聯系人郵箱URI：

4) 聯系人組信息URI：

5) 聯系人地址信息URI：

6) 聯系人個人主頁信息：

7) Data表URI:

2 Android聯系人的庫函數檢索介紹

系統在實現聯系人檢索時，對外提供的主要檢索方式如下：

針對聯系人的查詢：

//查找聯系人名字

//查找聯系人電話

//查找聯系人郵箱

//查找聯系人地址

3 Android聯系人庫函數檢索原理分析

在contacts2.db數據庫contacts表中有一個字段lookup，該字段提供快速檢索的集合，將需要查詢的lookup Key和lookup字段值進行數據庫的查詢操作，并將符合條件的結果在Cursor中返回。

lookup字段主要有3種：1) 提供漢字快速檢索；2) 提供漢字首字母組合；3) 是電話號碼數字的快速檢索。如數據庫語句：

由以上分析可以得出在進行檢索時，匹配的過程實際為進行關鍵字的漢字檢索、全拼檢索以及拼音模糊檢索。

3.1 漢字檢索

漢字檢索[4]比較快速，用戶只需輸入名字中的一個或多個字，即可檢索出結果。但是漢字的輸入比較麻煩，目前手機采用T9輸入法，除了輸入拼音以外，還需手動選擇對應拼音的漢字，甚至還需翻頁查找，這樣極大地浪費了用戶查找的時間。而且由于一些用戶方言或者拼音不準，使用此檢索方法無法滿足其需求。

3.2 全拼檢索

用戶需要輸入名字的拼音全拼進行全拼檢索[5]以匹配到聯系人。使用該方法檢索速度比較快，且比漢字檢索更簡單，只需要輸入拼音，而無需手動選擇漢字。但是如果用戶拼音不準，同樣使用困難。

3.3 拼音模糊檢索

拼音模糊檢索[6]極大地方便了用戶，減少了用戶多余的手動選擇和輸入，同時將查找的任務給了計算機程序代碼，節約了用戶的時間。但同時也會增加計算時間的開銷。

以上查找方法都有各自的局限：1) 如果用戶沒有清楚的記得聯系人姓名或者姓名首字母時，進行全拼查找和首字母查找將無法查找到；2) 非連續的首字母檢索和漢字首字母混合模糊檢索是無法檢索出結果的；3) 中國漢字有多音字，一些單個漢字對應多個拼音，尤其有一些常用漢字會作為姓名中的字出現，在進行檢索時，需要做進一步的算法處理。

4 Android聯系人非庫函數檢索

如何提高信息檢索速度以便有效降低擊鍵次數，提高查詢效率，一直是開發人員研究的熱點問題[7]，本文介紹的聯系人最大匹配算法，即能有效降低用戶擊鍵次數，又能提供基于全拼、首字母查找以及介于這兩者之間的混合部分拼音查找，同時可以進行多音字的檢索，在時間開銷和性能開銷上都能滿足Android平臺的要求和限制，完全達到商用的標準。

4.1 Android平臺限制

由于Android都運行于移動設備，這些設備的內存比較有限[8]，對于一個app來說，系統在內存分配上原則上不超過24M，程序占用內存也應在此限定范圍內。同時移動設備的性能相較個人PC或者大型計算機，性能較差，要求的算法復雜度低。

4.2 算法運行環境

算法運行在Java jdk1.5，Android sdk2.0，adt10上，使用編譯軟件為 eclipse juno，運行環境為Android2.2。

4.3 檢索原理

本算法檢索原理是基于混合最大匹配，允許用戶輸入數字、漢字以及拼音，按照這些組合和T9鍵盤進行模糊最大匹配。

用戶輸入數字則進行電話號碼匹配，同時按照T9鍵盤[9]轉化數字為對應字母組合，通過正則表達式進行拼音檢索，同時將檢索結果集進行去重，最后顯示給用戶。

用戶輸入漢字則進行漢字匹配，檢索聯系人名字，通過Java的String.contains(String str)將符合檢索條件的聯系人顯示給用戶。

用戶輸入拼音則進行拼音分詞，按照聲母和韻母進行最大匹配。算法對聲母記錄聯系人列表中的位置，實現快速定位的功能。

用拼音檢索聯系人時，首先要獲知每個漢字的拼音。算法根據漢字拼音對照表查找對應漢字的拼音，生成對應聯系人姓名的全拼表和首字母拼音表，然后按照輸入的字母進行匹配，與全拼表和首字母拼音表匹配，如果匹配，則加入到結果集，否則查找下一條記錄。

漢字拼音對照表既可以使用操作系統的微軟全拼碼表文件 winpy.mb，將其逆轉成為碼表源文件winpy.txt[10]。漢字拼音對照表又可使用Android平臺上類HanZiToPinYin，使用該類時，需要增加常用漢字的多音字拼音。

使用數據庫作為查詢的來源，可以預先在數據庫中添加輔助字段，比如全拼和首字母簡寫，這樣在查詢的時候直接使用查詢語句即可。

4.4 算法實現原理

算法的匹配可以按照數據庫方式實現，進行like操作：

查詢語句如下：

也可以按照Java代碼，String類的匹配方式進行：

4.5 算法流程

算法主要是通過字符串的String進行匹配，按照最大匹配進行檢索，直到檢索字符串長度為0。搜索字符串是指每次經過匹配后剩余的字符串，流程圖如圖2所示。

圖2 最長匹配流程圖

5 實驗結果和分析

該算法運行在Android手機，硬件配置為聯發科雙核1.0 G處理器，512 MB內存，Android版本為4.1.2，按照圖3所示進行測試。

圖3橫坐標代表聯系人數目，縱坐標為時間開銷，單位為秒，4條曲線分別代表：算法平均搜索時間、拼音檢索花費時間、漢字檢索花費時間以及首字母檢索花費時間。

圖3反映了本算法和其它幾種算法的效率比較。

當聯系人條目數為100條、200條、500條、600條、1000條時，本文算法平均檢索時間為0.102秒、0.121秒、0.287秒、0.309秒、0.352秒、0.422秒，消耗時間都少于拼音檢索、漢字檢索以及首字母檢索，說明本文算法性能比較高。

圖3 算法性能比較圖

實驗結果表明：本算法處理性能比拼音檢索、首字母檢索更快。

以n代表用戶輸入的字符串長度，本文中算法在最優的情況下一次就可以查詢到，也就是0(n)=1，這樣的情況也就是用戶直接輸入全拼的時候，字符串剛好和拼音完全匹配。最差的情況下匹配的復雜度是0(n)=n,也就是用戶輸入的字符串剛好是要查找聯系人的姓名首字母簡寫，這樣，算法先從輸入字符串長度n開始由后往前依次減掉最后一位字符，最終匹配到第一位，再從第一位往后，依次到所有字符串都匹配完成。因為算法對首字母做了字母索引映射表，所以可以快速檢索。因此最差的情況下：

0(n)=n-α=n ；α為通過首字母索引表快速檢索減少的匹配次數；

其余情況在這兩者之間。而用戶一般在查找（中文名）聯系人時，通常輸入的字符串長度不會超過5個，因此查找的次數為5，

0 ＜ 0(n) ＜ 5；在效率上滿足Android的要求，而在使用內存上，既不需要產生其它的數據庫，也不會增加系統的開銷和修改系統數據庫。

5.1 算法優化

建立首字母位置索引表，避免每次都開始位置檢索，以便更快地檢索出結果；在連續輸入時，檢索應該把上一次檢索結果集作為檢索內容。同時使用StringBuilder來減少String開銷，優化內存使用狀態。使用檢索字母索引映射表，有效地避免了內存消耗過大的情況。

5.2 算法適用范圍

本文算法適用于Android平臺聯系人檢索：聯系人拼音檢索、漢字檢索、英文名檢索、模糊檢索、混合檢索以及多音字檢索。

6 算法總結

本算法難點在于拼音分詞、混合模糊匹配以及處理多音字碼表。混合模糊匹配對輸入的數字、拼音或者漢字，進行檢索，其中對數字按照T9鍵盤進行轉化，與對應數字鍵上字母組合進行正則表達式匹配，同時需要對多音字進行特別處理。

[1]焦明飛.基于安卓系統的桌面搜索引擎的設計與實現[D].廣州:華南理工大學,2013.

[2]劉建.基于Android的手機通訊錄開發的探究與實現[J].電子測試,2013(8):17-19,161.

[3]宗桂華.數據庫管理系統漢字拼音首字母檢索碼的生成與使用[J].聲學與電子工程,1999(3):45-49.

[4]李琦.基于漢字拼音首字母的信息查詢法的分析與實現[J].四川輕化工學院學報, 2003,14(4):71-74.

[5]劉峰.基于 Android的語句級智能漢字輸入法研究[D].哈爾濱:哈爾濱工業大學,2010.

[6]黎邦群.OPAC拼音搜索功能的設計與實現[J].現代圖書情報技術,2011(9): 88-93.

[7]陳璟,陳平華,李文亮. Android內核分析[J].現代計算機 專業版,2009(11):112-115.

[8]呂翌,賈焰.基于IMS移動終端的即時通信聯系人列表管理器[J].微計算機信息,2010,26(5-3):40-41,63.

[9]周建欽,趙志遠.隨機分組查找算法[J].科學通報,1990(24):1905-1906.