特許
J-GLOBAL ID：200903028769277738

文字列検索装置

発明者：
中村 隆顕

中村 隆顕 について

, 
郡 光則

郡 光則 について


出願人/特許権者：
三菱電機株式会社

三菱電機株式会社 について


代理人 (1件)： 溝井 章司
公報種別：公開公報
出願番号（国際出願番号）：特願2005-124860
公開番号（公開出願番号）：特開2006-302082
出願日： 2005年04月22日
公開日（公表日）： 2006年11月02日
要約：
【課題】 電子化されたテキストに、正規表現を用いて記述された所定の文字列が含まれるか否かを判定し、その位置を求める検索装置において、テキストを構成する部分文字列を圧縮ブロックに置換することにより圧縮した圧縮ブロック列からの検索を、効率よく高速に行う。【解決手段】 検索に、DFA(有限オートマトン)を利用する。圧縮ブロック列(符号列)から圧縮ブロック(符号)を取得し(S21)、その圧縮ブロックに対応する部分文字列が初出なら、部分文字列に展開して、DFAに入力し、そのときのDFAの状態遷移の履歴(状態履歴)を記憶しておく(S261〜S264)。同じ部分文字列に対応する圧縮ブロックは展開せず、状態履歴を参照して、DFAの状態を更新する(S251〜S254)。【選択図】 図15
請求項（抜粋）：
状態を保持し、文字を入力し、上記保持した状態と上記入力した文字とに基づいて遷移先状態を算出し、上記保持した状態を上記算出した遷移先状態に更新するオートマトンであって、所定の文字列を構成する文字を入力した場合に、上記記憶した状態が所定の状態となるか否かを判別することにより、所定の検索パターンに対応する検索文字列が上記文字列に含まれるか否かを判別できるよう構成したオートマトンを実行することによって、 上記文字列に含まれる部分文字列を上記部分文字列に対応する所定の符号に置換した符号列を取得して、上記文字列から上記検索文字列を検索する文字列検索装置において、 上記オートマトンを実行するオートマトン実行部と、 上記オートマトンが保持した状態を状態履歴として記憶する履歴記憶部と、 上記符号列を構成する符号を取得する符号取得部と、 上記オートマトンが保持する状態と上記履歴記憶部が記憶した状態履歴と上記符号取得部が取得した符号とに基づいて、第一の条件及び第二の条件を満たすか否かを判断する条件判断部と、 上記条件判断部が第一の条件を満たすと判断した場合に、上記履歴記憶部が記憶した状態履歴に基づいて遷移先状態を算出し、上記オートマトンが保持した状態を、算出した遷移先状態に更新する遷移先算出部と、 上記条件判断部が第二の条件を満たすと判断した場合に、上記符号取得部が取得した符号に対応する部分文字列を復元し、上記部分文字列を構成する文字を上記オートマトンに入力する文字列復元部と、 を有することを特徴とする文字列検索装置。
IPC (1件)：
G06F 17/30
FI (2件)：
G06F17/30 170H ,  G06F17/30 170A
Fターム (4件)：
5B075ND03 ,  5B075PP23 ,  5B075QM10 ,  5B075QS13
引用特許：
出願人引用 (1件)
  • 圧縮検索方式
    公報種別：公開公報   出願番号：特願平9-065915   出願人：株式会社日立製作所
審査官引用 (4件)
全件表示
引用文献：
審査官引用 (2件)

前のページに戻る

TOP

BOTTOM