[發明專利]用于文本間匹配的方法

有效

• 申請號: 201711441800.7
• 申請日: 2017-12-27
• 公開（公告）號: CN108304467B
• 公開（公告）日: 2021-08-10
• 發明（設計）人: 王琪;何東杰;劉為懷;蔣丹妮;葉家煒;宋昊
• 申請（專利權）人: 中國銀聯股份有限公司
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/33
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 王星;楊美靈

本發明涉及一種用于文本間匹配的方法，包括如下各步驟：基于至少一個標識構建待匹配文本；基于感興趣信息形成目標文本的集合；將待匹配文本按樹結構進行解析；其中，樹結構的根節點的每一個子節點對應于待匹配文本的至少一個字符；基于樹結構來構建存儲表；其中，存儲表記錄每個標識在樹結構中所對應的至少一個節點，以及其中每個節點的節點位置以及節點狀態；以及、基于存儲表與目標文本的集合進行多模式匹配。其能夠顯著提升匹配運算的效率，并更高效地確定多個許可證所涉及的風險信息或不兼容信息，為開源軟件開發企業提供可靠的風險防范措施。

技術領域

本發明涉及一種用于文本間匹配的方法。

背景技術

在字符串模式匹配技術領域，主要的算法有：BM(Boyer-Moore)、Horspool、Sunday、KMP、KR、AC算法等，其中BM、Horspool、Sunday、KMP都為單模式匹配算法。設文本長度為n，集合P中字符串平均長度為k，單模式匹配最快可以做到O(m+k)的復雜度，但是，在多模式匹配的場合下，則需要O(mn+km)的復雜度；對于KR算法而言，最壞情況下需要O(k*m*n)的復雜度。可見，在多模式匹配的場合中，匹配效率存在惡化的趨勢。

另一方面，隨著開源軟件的不斷發展和完善，其地位日益重要，開源軟件的許可證也伴隨著開源軟件而產生。然而，由于對開源軟件的不正確使用，產生了許多法律上的問題，給開源軟件的開發企業帶來了很大的風險或隱患。

同時，許多開源軟件都依賴其他的開源軟件，而這些彼此依賴的開源軟件使用的許可證復雜且不同，而這些許可證之間、及許可條款之間可能又存在各種兼容性問題，這也是使用開源軟件的隱患。

發明內容

本發明的目的在于提供一種用于文本間匹配的方法，其能夠提高多模式匹配的效率。

為實現上述目的，本發明提供一種技術方案如下：

一種用于文本間匹配的方法，包括如下各步驟：a)、基于至少一個標識構建待匹配文本；b)、基于感興趣信息形成目標文本的集合；c)、將待匹配文本按樹結構進行解析；其中，樹結構的根節點的每一個子節點對應于待匹配文本的至少一個字符；d)、基于樹結構來構建存儲表；其中，存儲表記錄每個標識在樹結構中所對應的至少一個節點，以及其中每個節點的節點位置以及節點狀態；以及e)、基于存儲表與目標文本的集合進行多模式匹配。

優選地，存儲表基于二維數組結構來構建。

優選地，步驟c)中：基于Aho-Corasick算法將待匹配文本按樹結構進行解析。

優選地，存儲表包括：每個節點對應的節點字符；每個節點所在的數組位置；每個節點的各子節點所在的數組位置；每個節點的各兄弟節點所在的數組位置；每個節點的輸出狀態；以及每個節點的FAIL節點所在的數字位置。

優選地，樹結構按如下方式來定義：根節點的各直接子節點與各標識的首字符一一對應；各標識對應的字符串分別定義為樹結構的相應子樹。

優選地，標識為開源軟件的許可證的鍵，感興趣信息為開源軟件所涉及的風險信息和/或不兼容信息。

本發明進一步提供一種確定開源軟件的許可證是否存在風險或不兼容的方法，其包括：利用如上所述的多模式匹配方法來進行至少一個許可證的鍵與風險信息和/或不兼容信息之間的匹配。

本發明還公開一種文本間多模式匹配系統，包括：待匹配文本構建單元，用于基于至少一個標識構建待匹配文本；樹結構形成單元，與待匹配文本構建單元耦合，用于將待匹配文本按樹結構進行解析；其中，樹結構的根節點的每一個子節點對應于待匹配文本的至少一個字符；表存儲單元，與樹結構形成單元耦合，用于基于樹結構來構建存儲表；其中，存儲表記錄每個標識在樹結構中所對應的至少一個節點，以及其中每個節點的節點位置以及節點狀態；以及多模式匹配單元，與表存儲單元耦合，用于基于存儲表與目標文本的集合進行多模式匹配。