[發明專利]一種信息匹配方法及裝置

在審

• 申請號: 201510922330.0
• 申請日: 2015-12-14
• 公開（公告）號: CN106874294A
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 黎久希
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京新知遠方知識產權代理事務所(普通合伙)11397
• 代理人: 侯俊麗

技術領域

本申請涉及計算機技術領域，尤其涉及一種信息匹配方法及裝置。

背景技術

隨著信息技術的不斷發展，越來越多的應用場景需要進行信息匹配，例如：搜索引擎的檢索詞匹配、論文的相似度匹配、拼寫檢查等。

目前，信息匹配技術通常為利用java語言的index of函數實現關鍵字匹配，即，建立預先寫有若干關鍵字的文件，將用戶在客戶端輸入的內容與該文件中所含的每個關鍵字進行匹配。假設預先建立的文件中包括100個關鍵字，那么，則需要進行100次的全文掃描才能完成對用戶輸入內容的信息匹配。在這個信息爆炸的時代，采用上述匹配方式進行匹配的效率非常低，無法適應信息量較大的場景。

現有技術不足在于：

現有的信息匹配方式效率低下，不能適應信息量較大的場景。

發明內容

本申請實施例提出了一種信息匹配方法及裝置，以解決現有技術中信息匹配方式效率低下，不能適應信息量較大的場景的技術問題。

本申請實施例提供了一種信息匹配方法，包括如下步驟：

按照待匹配信息的字符順序接收所述待匹配信息；

將待匹配信息在預先構建的有窮狀態機DFA中進行匹配，所述DFA由預 設的關鍵字構成，所述DFA中每個狀態的輸出列表包含所述狀態的子孫失敗狀態的輸出列表，所述狀態的子孫失敗狀態與所述狀態的字符相同；

在匹配過程中，如果當前狀態沒有與所述待匹配信息的字符相匹配的下一狀態，跳轉到所述當前狀態的失敗狀態繼續匹配。

本申請實施例提供了一種信息匹配裝置，包括：

接收模塊，用于按照待匹配信息的字符順序接收所述待匹配信息；

匹配模塊，用于將待匹配信息在預先構建的有窮狀態機DFA中進行匹配，所述DFA由預設的關鍵字構成，所述DFA中每個狀態的輸出列表包含所述狀態的子孫失敗狀態的輸出列表，所述狀態的子孫失敗狀態與所述狀態的字符相同；在匹配過程中，如果當前狀態沒有與所述待匹配信息的字符相匹配的下一狀態，跳轉到所述當前狀態的失敗狀態繼續匹配。

有益效果如下：

本申請實施例所提供的信息匹配方法及裝置，預先構建由預設關鍵字構成的有窮狀態機DFA，將待匹配信息在所述DFA中進行匹配，由此關鍵字的匹配即變成了狀態機的跳轉；由于本申請實施例中所述DFA每個狀態的輸出列表包含所述狀態的子孫失敗狀態的輸出列表，在匹配過程中，如果當前狀態沒有與所述待匹配信息的字符相匹配的下一狀態，則跳轉到所述當前狀態的失敗狀態繼續匹配，所述待匹配信息的匹配過程只需要隨著所述DFA狀態一步一步地往下一狀態跳轉，無需返回上一狀態以匹配其他關鍵字，從而可以確保所述待匹配信息只需要掃描一遍即可完成匹配，極大地提高了匹配效率。

附圖說明

下面將參照附圖描述本申請的具體實施例，其中：

圖1示出了本申請實施例中信息匹配方法實施的流程示意圖；

圖2示出了本申請實施例中DFA結構示意圖；

圖3示出了本申請實施例中DFA初始化時的示意圖；

圖4示出了本申請實施例中DFA構建完成后的結構示意圖；

圖5示出了本申請實施例中群組聊天限制的DFA示意圖；

圖6示出了本申請實施例中信息匹配裝置的結構示意圖。

具體實施方式

為了使本申請的技術方案及優點更加清楚明白，以下結合附圖對本申請的示例性實施例進行進一步詳細的說明，顯然，所描述的實施例僅是本申請的一部分實施例，而不是所有實施例的窮舉。并且在不沖突的情況下，本說明中的實施例及實施例中的特征可以互相結合。

針對現有技術的不足，本申請實施例提出了一種信息匹配方法及裝置，下面進行說明。

圖1示出了本申請實施例中信息匹配方法實施的流程示意圖，如圖所示，所述信息匹配方法可以包括如下步驟：

步驟101、按照待匹配信息的字符順序接收所述待匹配信息；

步驟102、將待匹配信息在預先構建的有窮狀態機(DFA，Deterministic Finite Automata)中進行匹配，所述DFA由預設的關鍵字構成，所述DFA中每個狀態的輸出列表包含所述狀態的子孫失敗狀態的輸出列表，所述狀態的子孫失敗狀態與所述狀態的字符相同；

步驟103、在匹配過程中，如果當前狀態沒有與所述待匹配信息的字符相匹配的下一狀態，跳轉到所述當前狀態的失敗狀態繼續匹配。