[發明專利]一種基于后綴數組的短信查找方法及系統

在審

• 申請號: 201710224648.0
• 申請日: 2017-04-07
• 公開（公告）號: CN107038230A
• 公開（公告）日: 2017-08-11
• 發明（設計）人: 邵長飛;勞斌
• 申請（專利權）人: 廣東順德中山大學卡內基梅隆大學國際聯合研究院;中山大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/27
• 代理公司: 廣州粵高專利商標代理有限公司44102
• 代理人: 林麗明

技術領域

本發明涉及數據查找領域，更具體地，涉及一種基于后綴數組的短信查找方法及系統。

背景技術

后綴數組最初是作為后綴樹的一種替代被提出的，與后綴樹相比，存儲后綴數組所需的空間更少，應用范圍更廣。在后綴數組被提出后，后綴數組作為一種重要的索引數據結構，被廣泛的應用于生物信息學、全文索引、字符串匹配、頻繁字符串挖掘以及順序分析和聚類分析等領域。

目前，即時通訊設備一般都提供模糊查找短信的功能。模糊查找是指查找時不必以搜索目標的全稱為關鍵詞進行查找，而是可以以搜索目標的部分名稱為關鍵詞進行查找的過程。如何實現快速模糊查找短信對用戶而言至關重要，尤其是當短信息數量越來越大時，會極大地影響用戶的體驗。現有的查找短信的方案是根據關鍵詞對短信內容列表進行逐字符的多次遍歷，文本的模式匹配多采用精確匹配的模式，這種模式在查找時需要耗費較長的時間。隨著時間的推移，尤其是對模糊匹配的需求，這些技術都不太適合現實的需求。

發明內容

本發明為解決以上現有技術提供的短信查找方法耗時較長的缺陷，提供了一種基于后綴數組的短信查找方法。

為實現以上發明目的，采用的技術方案是：

一種基于后綴數組的短信查找方法，包括以下步驟：

S1.為短信列表中的每條短信根據其短信字符串內容構建后綴數組，然后按照預設的規則對構造得到的所有后綴數組中的各個后綴數組項進行排序；

S2.當接收到一個查找短信的關鍵詞時，按照接收字符的順序，將接收到的關鍵詞中的各個字符依次作為二分查找的索引；

S3.使用關鍵詞中的第i個字符作為索引在已排序的所有后綴數組項中進行二分查找，將首字符為該索引的后綴數組項對應的后綴數組作為第i次查找的結果；i的初始值為1；

S4.令i＝i+1然后使用關鍵詞中的第i個字符作為索引在第i-1次查找結果包含的后綴數組項中進行二分查找，然后將首字符為該索引的后綴數組項對應的后綴數組作為第i次查找的結果；

S5.重復執行步驟S4直至第i>n，此時將第i次查找的結果對應的短信作為短信查找結果進行輸出，n為關鍵詞包含的字符數。

上述方案中，本發明提供的方法具有查詢速度快的特點，在進行查找時無需遍歷每條短信，其查詢效率高；尤其是當查詢的關鍵詞較長時，查找的速度提升明顯。

優選地，所述步驟S1在對各個后綴數組項進行排序時，根據各個后綴數組項首字符的拼音首字母進行排序。

同時，本發明還提供了一種應用以上方法的系統，其具體的方案如下：

包括字符串讀取模塊、構造模塊、排序模塊和查找模塊；

其中字符串讀取模塊用于讀取短信列表中的每條短信的字符串內容；

構造模塊用于為短信列表中的每條短信構建后綴數組；

排序模塊用于對構造得到的所有后綴數組中的各個后綴數組項進行排序；

查找模塊用于根據關鍵詞在已排序的所有后綴數組項中進行二分查找，然后將查找得到的后綴數組項對應的后綴數組作為查找的結果。

與現有技術相比，本發明的有益效果是：

本發明提供的方法具有查詢速度快的特點，在進行查找時無需遍歷每條短信，其查詢效率高；尤其是當查詢的關鍵詞較長時，查找的速度提升明顯。

附圖說明

圖1為方法的流程示意圖。

圖2為系統的結構示意圖。

具體實施方式

附圖僅用于示例性說明，不能理解為對本專利的限制；

以下結合附圖和實施例對本發明做進一步的闡述。

實施例1

如圖1所示，本發明提供的方法包括以下步驟：

S1.為短信列表中的每條短信根據其短信字符串內容構建后綴數組，然后按照預設的規則對構造得到的所有后綴數組中的各個后綴數組項進行排序；

S2.當接收到一個查找短信的關鍵詞時，按照接收字符的順序，將接收到的關鍵詞中的各個字符依次作為二分查找的索引；

S3.使用關鍵詞中的第i個字符作為索引在已排序的所有后綴數組項中進行二分查找，將首字符為該索引的后綴數組項對應的后綴數組作為第i次查找的結果；i的初始值為1；

S4.令i＝i+1然后使用關鍵詞中的第i個字符作為索引在第i-1次查找結果包含的后綴數組項中進行二分查找，然后將首字符為該索引的后綴數組項對應的后綴數組作為第i次查找的結果；