[發明專利]檢索裝置以及檢索方法

有效

• 申請號: 200880130230.2
• 申請日: 2008-07-01
• 公開（公告）號: CN102084357A
• 公開（公告）日: 2011-06-01
• 發明（設計）人: 葛毅;多湖真一郎
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京東方億思知識產權代理有限責任公司 11258
• 代理人: 柳春雷

技術領域

本申請涉及檢索裝置以及檢索方法，尤其涉及從作為輸入字符串的文本中檢索作為任意字符串的模式(pattern)的檢索裝置以及檢索方法，其中輸入字符串是應用自動機處理技術而提供的。

背景技術

近年來，在各種各樣的領域，信息量爆炸性地增長。并且，根據領域，信息量從千兆字節量級(gigabate?order)變成兆兆字節量級(terabyte?order)，從這樣浩瀚的數據中難以在短時間內取出所期望的數據。

從所提供的文本中檢索任意類型模式的模式匹配被應用于字符處理軟件或數據庫檢索等各種領域中。

即，近年來，對以XML數據庫為主的需要模式匹配(檢索)處理的應用程序的需求具有增長的趨勢，并且為了使其高速化而提出了將進行模式匹配的自動機匹配裝置(檢索核)安裝在處理器上的方法。

并且，以往在具有多個這樣的匹配裝置的處理器系統中，研究了對一個應匹配的文本如何高速地進行匹配。

具體來說，以往提出了使用具有多個匹配裝置的處理器系統來一次對多個字符進行匹配的方法。

并且，以往為了使用具有多個匹配裝置的處理器系統來執行并行處理還提出了分割匹配文本的方法。

專利文獻1：日本專利文獻特開2005-242672號公報；

專利文獻2：日本專利申請特許第2865831號公報。

發明內容

發明要解決的問題

以往，提出了使用具有多個匹配裝置的處理器系統來進行文本的匹配的技術方案。

然而，例如在數據庫直接由多個XML文本群構成的XML數據庫系統的匹配(檢索)處理中，若從一開始就進行模式匹配，則由于各XML文本之間并行程度高，因此通過增加匹配裝置的安裝數量等來并行地執行匹配處理，從而能夠容易地提高處理速度。然而這會增加CPU利用該匹配結果所進行的后處理的比重。

此外，當使匹配處理和CPU的后處理并行進行時，用于減少其開銷的數據傳遞方法以及控制方式對于提高檢索(匹配)系統整體的速度來說很重要。

并且還需要規定在保持各匹配結果的文本單位的順序關系的同時通過CPU進行后處理的機制。例如，在XML數據庫系統中的檢索中，如果XML文本的CPU處理順序與在XML數據庫中管理的順序每次都不同，則檢索結果每次都按不同的順序顯示，從而對于用戶來說是難以使用的系統。

因此，還需要規定基于通過并行動作按不同順序完成匹配的匹配結果而在可按記錄順序進行后處理的階段并行處理的有效的機制。

本申請就是鑒于上述現有以及相關技術中的問題而完成的，其目的在于，提供一種可減少各匹配裝置(檢索核)和CPU處理的并行動作的開銷來進行數據交接并可實現系統的高速化的檢索裝置以及檢索方法。

用于解決問題的手段

根據第一實施方式，提供一種檢索裝置，包括：CPU；以及具有調度器和多個檢索核的加速器。所述CPU按照被輸入的檢索表達式來生成自動機，所述調度器將處理對象文本以被排序的記錄的單位分配給所述各檢索核。并且，所述各檢索核對所述被分配的各記錄分別并行地進行自動機匹配，所述CPU按所述各記錄的所述排序的順序對所述各記錄單位的匹配結果進行邏輯表達式評價。

根據第二實施方式，提供一種使用了檢索裝置的檢索方法，其中所述檢索裝置包括CPU、以及具有調度器和多個檢索核的加速器。所述CPU按照被輸入的檢索表達式來生成自動機，所述調度器將處理對象文本以被排序的記錄的單位分配給所述各檢索核。并且，所述各檢索核對所述被分配的各記錄分別并行地進行匹配處理，所述CPU按所述各記錄的所述排序的順序對所述各記錄單位的匹配結果進行邏輯表達式評價。

根據第三的實施方式，提供一種使計算機執行以下步驟的檢索程序，其中，所述計算機包括：CPU；以及具有調度器和多個檢索核的加速器，所述步驟包括：使所述CPU按照被輸入的檢索表達式來生成自動機的步驟；使所述調度器將處理對象文本以被排序的記錄的單位分配給所述各檢索核的步驟；使所述各檢索核對所述被分配的各記錄分別并行地進行自動機匹配的步驟；以及使所述CPU按所述各記錄的所述排序的順序對所述各記錄單位的匹配結果進行邏輯表達式評價的步驟。

發明效果

根據各實施方式，能夠提供可減少各匹配裝置和CPU處理的并行動作的開銷來進行數據交接并可實現系統的高速化的檢索裝置以及檢索方法。

附圖說明

圖1A是用于說明作為自動機的關鍵詞檢索算法的一個例子的σ(Sigma)算法的圖(之一)；