[發明專利]目標文本的匹配方法和裝置、存儲介質及電子設備

有效

• 申請號: 202010525837.3
• 申請日: 2020-06-10
• 公開（公告）號: CN111680489B
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 習自;趙學敏
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F40/194
• 分類號: G06F40/194;G06F9/50;G06F40/279
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 周婷婷

本發明公開了一種目標文本的匹配方法和裝置、存儲介質及電子設備。其中，該方法包括：對目標文件中當前待匹配的字符串進行匹配，首先在預先建立的目標搜索樹中查找到與字符串匹配的實體，獲取實體的實體名稱和實體編號，再根據實體編號在信息數組中獲取實體的實體類型和指代信息，實體確定為包括實體名稱和實體類型以及指代信息的目的，可以理解為，將單類型有指代信息的實體的唯一的類型信息存儲到對應的目標搜索樹中，可以減少了與目標文本中當前待匹配字符串進行匹配的實體信息數組所占內存，提高目標文本的匹配速度，進而解決了現有技術中，目標文本匹配的內存占用較大以及效率較低的技術問題。

技術領域

本發明涉及計算機技術領域，具體而言，涉及一種目標文本的匹配方法和裝置、存儲介質及電子設備。

背景技術

現有多模匹配方法主要有Trie樹、AC算法、VM算法等。其中，Trie樹算法將每個待搜索模式串當成一個節點，由此建立前綴樹，并且為每個節點都記錄了一個失敗節點，這樣在匹配失敗的時候，不是直接回溯到根節點，而是跳轉到失敗節點繼續匹配，這樣做的好處是避免不必要的回溯，保證匹配一直先前進行，從而可以大量減少匹配時間。Trie樹算法的主要缺點是數據結構復雜，存儲空間浪費大。

AC算法同樣是借助trie樹，通過建立轉換函數、失敗函數、輸出函數來達到快速匹配的目的，AC算法比Trie樹算法數據結構簡單、匹配效率高，但同樣需要占用比較大的內存，并且啟動時間較長。VM算法的核心是建立三張表：跳轉表、哈希表、前綴表，其中哈希表和前綴表用于決定是否匹配成功，跳轉表則用于決定匹配失敗時的跳轉步數。VM算法同樣數據結構簡單、匹配效率高，但受模式的長度分布影響比較大，要求所有模式長度應基本相同。

另外，在實際應用場景中，我們還常常關注模式對應的信息。例如，在實體抽取任務中，我們需要了解輸入的用戶問句中包含的實體以及實體的類別、指代等信息。一種常見的做法是：將所有實體存儲在一個方便查找的數據結構中，再將所有實體所對應的信息存儲到另外一個數據結構中。例如，可以將所有實體構建成一個trie樹，該trie樹不僅存儲了實體的文本內容，并且還將每個實體與一個數字(即id)關聯起來；其次，將所有實體的類別、指代信息存儲到一個數組中，數組的元素是同類型的。查找的過程便是匹配的過程，對于待匹配的單個詞，首先在trie樹中查找，如果查找成功則返回該詞對應的id，然后取出實體信息數組中下標等于該id的元素內容作為該詞的實體信息；對于輸入的一個用戶問句，則可以采用滑窗的形式，依次查找以每個字開頭的所有候選實體，并最終對這些候選實體進行過濾。

可見，現有三種多模匹配技術(Trie樹、AC算法、VM算法)主要有以下幾個缺點：1、數據結構復雜(Trie樹算法)；2、占用內存大(Trie樹算法、AC算法)；3、依賴模式長度分布(VM算法)；4、將所有實體的信息都存儲在同一個類型的數據結構中，這樣會造成大量的內存浪費。

針對上述的問題，目前尚未提出有效的解決方案。

發明內容

本發明實施例提供了一種目標文本的匹配方法和裝置、存儲介質及電子設備，以至少解決現有技術中，目標文本匹配的內存占用較大以及效率較低的技術問題。

根據本發明實施例的一個方面，提供了一種目標文本的匹配方法，包括：獲取目標文本中當前待匹配的第一字符串，其中，所述第一字符串包括所述目標文本中的一個或連續多個字符；在目標搜索樹中查找到與所述第一字符串匹配的第一實體，根據所述目標搜索樹返回的查找結果獲取所述第一實體的實體名稱和實體編號；在根據所述實體編號確定出所述第一實體為單類型有指代信息的實體的情況下，在實體信息數組中獲取所述第一實體的實體類型和指代信息，并將所述第一實體確定為包括所述實體名稱和所述實體類型以及所述指代信息。