Pat
J-GLOBAL ID：200903028769277738

文字列検索装置

Inventor：
中村 隆顕

About 中村 隆顕

, 
郡 光則

About 郡 光則


Applicant, Patent owner：
三菱電機株式会社

About 三菱電機株式会社


Agent (1)： 溝井 章司
Gazette classification：公開公報
Application number (International application number)：2005124860
Publication number (International publication number)：2006302082
Application date： Apr. 22, 2005
Publication date： Nov. 02, 2006
Summary：
【課題】 電子化されたテキストに、正規表現を用いて記述された所定の文字列が含まれるか否かを判定し、その位置を求める検索装置において、テキストを構成する部分文字列を圧縮ブロックに置換することにより圧縮した圧縮ブロック列からの検索を、効率よく高速に行う。【解決手段】 検索に、DFA(有限オートマトン)を利用する。圧縮ブロック列(符号列)から圧縮ブロック(符号)を取得し(S21)、その圧縮ブロックに対応する部分文字列が初出なら、部分文字列に展開して、DFAに入力し、そのときのDFAの状態遷移の履歴(状態履歴)を記憶しておく(S261〜S264)。同じ部分文字列に対応する圧縮ブロックは展開せず、状態履歴を参照して、DFAの状態を更新する(S251〜S254)。【選択図】 図15
Claim (excerpt)：
状態を保持し、文字を入力し、上記保持した状態と上記入力した文字とに基づいて遷移先状態を算出し、上記保持した状態を上記算出した遷移先状態に更新するオートマトンであって、所定の文字列を構成する文字を入力した場合に、上記記憶した状態が所定の状態となるか否かを判別することにより、所定の検索パターンに対応する検索文字列が上記文字列に含まれるか否かを判別できるよう構成したオートマトンを実行することによって、 上記文字列に含まれる部分文字列を上記部分文字列に対応する所定の符号に置換した符号列を取得して、上記文字列から上記検索文字列を検索する文字列検索装置において、 上記オートマトンを実行するオートマトン実行部と、 上記オートマトンが保持した状態を状態履歴として記憶する履歴記憶部と、 上記符号列を構成する符号を取得する符号取得部と、 上記オートマトンが保持する状態と上記履歴記憶部が記憶した状態履歴と上記符号取得部が取得した符号とに基づいて、第一の条件及び第二の条件を満たすか否かを判断する条件判断部と、 上記条件判断部が第一の条件を満たすと判断した場合に、上記履歴記憶部が記憶した状態履歴に基づいて遷移先状態を算出し、上記オートマトンが保持した状態を、算出した遷移先状態に更新する遷移先算出部と、 上記条件判断部が第二の条件を満たすと判断した場合に、上記符号取得部が取得した符号に対応する部分文字列を復元し、上記部分文字列を構成する文字を上記オートマトンに入力する文字列復元部と、 を有することを特徴とする文字列検索装置。
IPC (1)：
G06F 17/30
FI (2)：
G06F17/30 170H ,  G06F17/30 170A
F-Term (4)：
5B075ND03 ,  5B075PP23 ,  5B075QM10 ,  5B075QS13
Patent cited by the Patent：
Cited by applicant (1)
  • 圧縮検索方式
    Gazette classification：公開公報   Application number：特願平9-065915   Applicant：株式会社日立製作所
Cited by examiner (4)
Show all
Article cited by the Patent：
Cited by examiner (2)

Return to Previous Page

TOP

BOTTOM