基于Android系統(tǒng)的聯(lián)系人最大匹配檢索算法設(shè)計與實現(xiàn)*

王超

（1.廣州華商職業(yè)學(xué)院 2.中山大學(xué)）

0 引言

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

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

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

1 Android聯(lián)系人存儲介紹

自Android2.0（API Level 5）以后，聯(lián)系人數(shù)據(jù)主要被安排存儲在3個表中：Contacts，Raw Contacts和Data。這3個表對應(yīng)的關(guān)系結(jié)構(gòu)如圖1所示。

圖1 Android聯(lián)系人存儲表結(jié)構(gòu)表

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

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

1) 聯(lián)系人URI：

2) 聯(lián)系人電話URI:

3) 聯(lián)系人郵箱URI：

4) 聯(lián)系人組信息URI：

5) 聯(lián)系人地址信息URI：

6) 聯(lián)系人個人主頁信息：

7) Data表URI:

2 Android聯(lián)系人的庫函數(shù)檢索介紹

系統(tǒng)在實現(xiàn)聯(lián)系人檢索時，對外提供的主要檢索方式如下：

針對聯(lián)系人的查詢：

//查找聯(lián)系人名字

//查找聯(lián)系人電話

//查找聯(lián)系人郵箱

//查找聯(lián)系人地址

3 Android聯(lián)系人庫函數(shù)檢索原理分析

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

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

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

3.1 漢字檢索

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

3.2 全拼檢索

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

3.3 拼音模糊檢索

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

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

4 Android聯(lián)系人非庫函數(shù)檢索

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

4.1 Android平臺限制

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

4.2 算法運行環(huán)境

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

4.3 檢索原理

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

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

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

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

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

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

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

4.4 算法實現(xiàn)原理

算法的匹配可以按照數(shù)據(jù)庫方式實現(xiàn)，進行l(wèi)ike操作：

查詢語句如下：

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

4.5 算法流程

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

圖2 最長匹配流程圖

5 實驗結(jié)果和分析

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

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

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

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

圖3 算法性能比較圖

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

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

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

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

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

5.1 算法優(yōu)化

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

5.2 算法適用范圍

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

6 算法總結(jié)

本算法難點在于拼音分詞、混合模糊匹配以及處理多音字碼表?；旌夏：ヅ鋵斎氲臄?shù)字、拼音或者漢字，進行檢索，其中對數(shù)字按照T9鍵盤進行轉(zhuǎn)化，與對應(yīng)數(shù)字鍵上字母組合進行正則表達式匹配，同時需要對多音字進行特別處理。

[1]焦明飛.基于安卓系統(tǒng)的桌面搜索引擎的設(shè)計與實現(xiàn)[D].廣州:華南理工大學(xué),2013.

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

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

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

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

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

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

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

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