JPH10207912A

JPH10207912A - 文字，文字列検索方法及び該方法に用いる記録媒体

Info

Publication number: JPH10207912A
Application number: JP9247052A
Authority: JP
Inventors: Natsuki Yuasa; 夏樹湯浅
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1996-11-21
Filing date: 1997-09-11
Publication date: 1998-08-07
Anticipated expiration: 2017-09-11
Also published as: JP3231673B2; US5978801A

Abstract

(57)【要約】【課題】複数の種類のパターンから一つの決定性有限
オートマトンを作成し、文字列検索時には、その一つの
決定性有限オートマトンを使用するだけで、各種類のパ
ターンを一度に検索することができる文字列検索方法、
該方法における状態数の最適化法及び該方法の実行に用
いられるプログラム及びデータを記録した媒体を提供す
る。【解決手段】一度に照合したい複数の正規表現ｒ₁，
ｒ₂，…，ｒ_nを用意し（Ｓ１０１）、この用意された正
規表現から拡大正規表現（(ｒ₁)＃₁)|((ｒ₂)＃₂)|…|
((ｒ_n)＃_n）を作成し（Ｓ１０２）、状態のうち＃₁，＃
₂，…，＃_nに対応する位置を含む状態は、それぞれ受理
状態１，受理状態２，…，受理状態ｎとする（Ｓ１０
３）ことにより、複数の正規表現パターンを、どのパタ
ーンにマッチしたのか区別しながら一度に検索できる決
定性有限オートマトンを構成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、文字，文字列検索
方法に関し、より詳細には、文書や電子メール等から、
日時情報等のキー情報を抽出するキー情報抽出装置や、
文書データを要約する文書要約装置や、文書処理装置／
ワープロ／ＰＤＡ（Personal Digital Assistant）／フ
ァイリングシステムなどの分野に利用される当該方法に
関する。

【０００２】

【従来の技術】有限オートマトンを用いて文字列検索
（文字列照合）を行う手法については、従来から研究が
なされてきており、代表的なアルゴリズムについては、
サイエンス社発行の「コンパイラＩ原理・技法・ツー
ル」（Ａ.Ｖ.エイホ，Ｒ.セシイ，Ｊ.Ｄ.ウルマン共
著；原田賢一訳）に詳しい記述がある。詳細について
は、この文献を参照することにして、ここでは、図１
４，図１５に示したフローチャートを参照しながら簡単
に従来用いられているアルゴリズムを説明する。図１４
は、従来の決定性有限オートマトンの作成方法を示すフ
ローチャートである。図１４において、まず、文字列照
合を行いたい正規表現のパターンｒを用意する（ステッ
プＳ１４０１）。次に、この用意された正規表現から拡
大正規表現（ｒ）＃を作成する（ステップＳ１４０
２）。そして、この拡大正規表現の構文木Ｔを作成する
などして（詳細は、前出の参考文献「コンパイラＩ原理
・技法・ツール」を参照）状態集合と状態遷移表を作成
する（ステップＳ１４０３）。状態のうち＃に対応する
位置を含む状態を受理状態とする（ステップＳ１４０
４）。

【０００３】図１５は、従来の決定性有限オートマトン
の状態数最適化方法を示すフローチャートである。図１
５において、状態集合の最初のグループ分けΠとして、
受理状態のグループと、非受理状態のグループの２つの
グループを作る（ステップＳ１５０１）。次に、Πから
グループ分けできる限り（グループａ内にある状態ｓに
文字、或は文字列（Ｍ）を入力した時の遷移先がグルー
プｂ内の状態であるとすると、グループａ内の他の任意
の状態ｔに同じ文字、或は文字列（Ｍ）を入力した時の
遷移先がグループｂ内の状態でなかったら、状態ｓと状
態ｔが別のグループになるようにグループ分けを行
う）、新しいグループ分けΠ_newを作り、これ以上新し
いグループを作成できなくなったら、そのグループ分け
をΠ_finalとする（ステップＳ１５０２）。最終的なグ
ループ分けΠ_finalから、状態数が最適化された決定性
有限オートマトン（ＤＦＡ：Deterministic Finite Aut
omaton）Ｍ′を作成する（ステップＳ１５０３）。

【０００４】

【発明が解決しようとする課題】上記したように、従来
の有限オートマトンを利用した文字列照合では、受理状
態が一種類しかないことからもわかるように、文字列照
合が成功したか否かだけが問われており、どのパターン
に合致したかは問われなかった。従って、複数の種類の
パターンを検索する時には、別々の有限オートマトンを
用意して、それぞれの有限オートマトンによって、各種
類のパターンを別々に検索する必要があった。本発明
は、こうした従来技術における問題点に鑑みてなされた
もので、複数の種類のパターンから一つの決定性有限オ
ートマトンを作成し、文字列検索時には、その一つの決
定性有限オートマトンを使用するだけで、各種類のパタ
ーンを一度に検索することができる文字列検索方法、ま
た、状態数を最適化しても、複数パターンを一度に検索
できる状態にすることを可能にする文字列検索方法、及
び該検索方法の実行に用いられるプログラム及びデータ
を記録した記録媒体を提供することをその解決すべき課
題とする。

【０００５】

【課題を解決するための手段】請求項１の発明は、複数
のパターンを同時に検索する文字，文字列検索方法にお
いて、文字、或いは文字列を単位とし、複数（２，…，
ｎ）単位の各文字、或いは文字列の正規表現ｒ₁，ｒ₂，
…，ｒ_nそれぞれについて、終端記号＃₁，＃₂，…，＃_n
を付加した拡大正規表現（ｒ₁）＃₁，（ｒ₂）＃₂，…，
(ｒ_n)＃_nにもとづいた構文（(ｒ₁)＃₁)|((ｒ₂)＃₂)|…|
((ｒ_n)＃_n）を作成し、正規表現による該構文を構成す
る前記複数の正規表現ｒ₁，ｒ₂，…，ｒ_nに含まれる文
字、或いは文字列の各パターンを同時に検索対象に用い
て、＃₁，＃₂，…，＃_nに対応する状態をそれぞれ受理
状態１，受理状態２，…，受理状態ｎとすることによっ
て、複数のパターンを区別して検索するための決定性有
限オートマトンを構成するようにしたことを特徴とする
ものである。請求項１の決定性有限オートマトン作成方
法は、図１にフローチャートとして示す通りであり、ま
ず、一度に照合したい複数の正規表現ｒ₁，ｒ₂，…，ｒ
_nを用意する（ステップＳ１０１）。次に、この用意さ
れた正規表現から拡大正規表現（(ｒ₁)＃₁)|((ｒ₂)＃₂)
|…|((ｒ_n)＃_n）を作成する（ステップＳ１０２）。状
態のうち＃₁，＃₂，…，＃_nに対応する位置を含む状態
は、それぞれ受理状態１，受理状態２，…，受理状態ｎ
とする（ステップＳ１０３）、という手順による。

【０００６】請求項２の発明は、複数のパターンを同時
に検索する文字，文字列検索方法において、文字、或い
は文字列を単位とし、複数（２，…，ｎ）単位の各文
字、或いは文字列の正規表現ｒ₁，ｒ₂，…，ｒ_nそれぞ
れについて、共通の終端記号＃を付加した拡大正規表現
（ｒ₁）＃，（ｒ₂）＃，…，(ｒ_n)＃にもとづいて拡大
正規表現による構文（(ｒ₁)＃)|((ｒ₂)＃)|…|((ｒ_n)
＃）を作成し、正規表現による該構文を構成する前記複
数の正規表現ｒ₁，ｒ₂，…，ｒ_nに含まれる文字、或い
は文字列の各パターンを同時に検索対象に用い、その
際、＃の位置をもとに＃に対応する状態を受理状態の種
類としてそれぞれ受理状態１，受理状態２，…，受理状
態ｎとすることによって、複数のパターンを区別して検
索するための決定性有限オートマトンを構成するように
したことを特徴とするものである。請求項２の決定性有
限オートマトン作成方法は、図２にフローチャートとし
て示す通りであり、まず、一度に照合したい複数の正規
表現ｒ₁，ｒ₂，…，ｒ_nを用意する（ステップＳ２０
１）。次に、この用意された正規表現から拡大正規表現
（(ｒ₁)＃)|((ｒ₂)＃)|…|((ｒ_n)＃）を作成する（ステ
ップＳ２０２）。状態のうち＃に対応する位置を含む状
態は、位置の前の方から順番に、それぞれ受理状態１，
受理状態２，…，受理状態ｎとする（ステップＳ２０
３）、という手順による。

【０００７】請求項３の発明は、請求項１又は２の発明
において、前記拡大正規表現にもとづいた構文から状態
集合｛状態１，状態２，…｝とその状態遷移表を作成す
ることにより、前記複数の正規表現ｒ₁，ｒ₂，…，ｒ_n
に含まれる文字、或いは文字列の各パターンを同時に検
索対象に用いるようにしたことを特徴とするものであ
る。請求項３の決定性有限オートマトン作成方法は、図
３にフローチャートとして示す通りであり、まず、一度
に照合したい複数の正規表現ｒ₁，ｒ₂，…，ｒ_nを用意
する（ステップＳ３０１）。次に、この用意された正規
表現から拡大正規表現（(ｒ₁)＃₁)|((ｒ₂)＃₂)|…|((ｒ
_n)＃_n）あるいは、拡大正規表現（(ｒ₁)＃)|((ｒ₂)＃)|
…|((ｒ_n)＃）を作成する（ステップＳ３０２）。そし
て、この拡大正規表現の構文木Ｔを作成するなどして状
態集合と状態遷移表を作成する（ステップＳ３０３）。
前者の拡大正規表現を使用した場合は、状態のうち
＃₁，＃₂，…，＃_nに対応する位置を含む状態をそれぞ
れ受理状態１，受理状態２，…，受理状態ｎとし、後者
の拡大正規表現を使用した場合は、状態のうち＃に対応
する位置を含む状態を位置の前の方から順番に、それぞ
れ受理状態１，受理状態２，…，受理状態ｎとする（ス
テップＳ３０４）、という手順による。

【０００８】請求項４の発明は、請求項３の発明におい
て、前記状態集合において、状態数の最適化を行う場合
に、受理状態１，２，…，ｎに対応する種類によってＦ
₁，Ｆ₂，…，Ｆ_nにグループ分けし、これらのグループ
と受理状態以外の非受理状態と合わせて、全体を（ｎ＋
１）個にグループ分けすることを特徴とするものであ
る。請求項４の決定性有限オートマトン作成方法は、図
４にフローチャートとして示す通りであり、まず、状態
集合の最初のグループ分けΠとして、ｎ個の受理状態
（Ｆ₁，Ｆ₂，…，Ｆ_n）と、１個の非受理状態の合計
（ｎ＋１）個のグループを作る（ステップＳ４０１）。
そして、Πから、状態数が最適化された決定性有限オー
トマトンＭ′を作成する（ステップＳ４０２）、という
手順による。

【０００９】請求項５の発明は、請求項４の発明におい
て、前記（ｎ＋１）個のグループを各グループａについ
て、グループ内のある状態ｓに文字、或いは文字列
（Ｍ）を入力した時の遷移先が当該グループｂ内の状態
であるとすると、グループａ内の他の任意の状態ｔに同
じ文字、或いは文字列（Ｍ）を入力した時の遷移先もグ
ループｂ内の状態であるようになるまでグループ分けを
行い、得られたグループ分けをもとに状態遷移表を作成
し直すことを特徴とするものである。請求項５の決定性
有限オートマトン作成方法は、図５にフローチャートと
して示す通りであり、まず、状態集合の最初のグループ
分けΠとして、ｎ個の受理状態（Ｆ₁，Ｆ₂，…，Ｆ_n）
と、１個の非受理状態の合計（ｎ＋１）個のグループを
作る（ステップＳ５０１）。次に、Πから、グループ分
けができる限り、新しいグループ分けΠ_newを作り、こ
れ以上新しいグループを作成できなくなったら、そのグ
ループ分けをΠ_finalとする（ステップＳ５０２）。そ
して、最終的なグループ分けΠ_finalから、状態数が最
適化された決定性有限オートマトンＭ′を作成する（ス
テップＳ５０３）、という手順による。

【００１０】請求項６の発明は、請求項１ないし５のい
ずれか１記載の文字，文字列検索方法を実行するための
プログラム及びデータを記録したコンピュータ読み取り
可能な記録媒体である。請求項１ないし５のいずれか１
記載の文字，文字列検索方法を実行するためのプログラ
ムやデータをコンピュータ読み取り可能に記録した記録
媒体としては具体的にはＲＯＭ（リード・オンリー・メ
モリ），フラッシュメモリ，フロッピーディスク，ハー
ドディスク，光磁気ディスク，ＣＤ−ＲＯＭ等を含む。
文字，文字列検索用の装置は、これらの記録媒体からプ
ログラムやデータを読み出して文字や文字列の検索を実
行する。

【００１１】

【発明の実施の形態】本発明の決定性有限オートマトン
作成方法の手順が図３に示されている。図３において、
まず、一度に照合したい複数の正規表現ｒ₁，ｒ₂，…，
ｒ_nを用意する（ステップＳ３０１）。次に、この用意
された正規表現から拡大正規表現（(ｒ₁)＃₁)|((ｒ₂)＃
₂)|…|((ｒ_n)＃_n）を作成する（ステップＳ３０２）。
そして、この拡大正規表現の構文木Ｔを作成するなどし
て状態集合と状態遷移表を作成する（ステップＳ３０
３）。状態のうち＃₁，＃₂，…，＃_nに対応する位置を
含む状態は、それぞれ受理状態１，受理状態２，…，受
理状態ｎとする（ステップＳ３０４）。決定性有限オー
トマトンをこのように構成することによって、受理状態
が複数に分かれ、受理した場合にはどの受理状態にたど
り着いたかによって、どの正規表現パターンにマッチし
たかが即座に判断できるようになる。なお、本明細書中
では「記号」と「文字」は同じ意味で用いている。

【００１２】（実施例１）具体例をあげて上記手順をさ
らに説明するが、ここでは、正規表現パターンとして以
下の二つのパターンを区別して一括で検索したいとする
場合を仮定する（図３のステップＳ３０１に対応）。・パターン１ “（１|２)／(１|２）” ・パターン２ “（１|２)：(１|２）” すると、図３のステップＳ３０２で、以下の拡大正規表
現が作成される。・（((１|２)／(１|２))＃₁)|(((１|２)：(１|２))＃₂) この拡大正規表現の構文木は、図６で示される形にな
り、これをもとに状態集合と状態遷移表を図７のように
作成する（図３のステップＳ３０３に対応）なお、図６
において、構文木の葉位置を１から１２の数字で示して
いる。また、図７において、「状態集合」は、状態番号
で表わされた状態１から６に対応させて構文木の葉位置
の集合を示している。状態のうち、firstpos（root）
（構文木が生成する記号列の中で、最初の記号に対応す
る位置の集合を返す。この例では｛１，２，７，８｝と
なる。）で表される状態、この例では状態１が開始状態
となる。そして、状態のうち＃_iに対応する位置を含む
ものは「受理状態ｉ」とするので、最終的な状態集合と
状態遷移表は、図８で示されるものになる（図３のステ
ップＳ３０４に対応）。状態遷移表で空欄になっている
のは、「受理せずに停止」、つまり、文字列照合に失敗
したことを意味する。入力記号として、この表に存在し
ないもの（例えば、「３」）が出現した場合も、「受理
せずに停止」である。

【００１３】ここで、図８に示される状態遷移表に従っ
て、以下の文字列の文字列照合を行ってみる。・０１／２３１：２５８まず、開始状態である「状態１」から開始する。状態遷
移表を照合すると、「状態１」では、入力記号が「１」
か「２」ならば「状態２」へ遷移し、それ以外は「照合
失敗」である。上の例の文字列を見ると、最初の入力記
号は「０」なので、「照合失敗」となる。次に、入力文
字列を一つ進めて、再び開始状態「状態１」からやり直
す。すると、次の入力記号は「１」なので、状態遷移表
に従って「状態２」へと遷移する。「状態２」で、次の
入力記号は「／」なので、状態遷移表に従って「状態
３」へ遷移する。「状態３」で、次の入力記号は「２」
なので、状態遷移表に従って「状態５」へ遷移する。
「状態５」は、「受理状態１」なので、この時点で文字
列照合に成功し、パターン１がこの位置で検索されたこ
とがわかる。つまり、直前の開始記号の時点の入力記号
位置（「１」）から、受理状態１に遷移する時の入力記
号の位置（「２」）まで（「１／２」）が、パターン１
とマッチしたということである。

【００１４】「状態５」では、どんな入力記号が来ても
「照合失敗」となるので、再び開始状態の「状態１」か
ら開始する。この時、入力位置は直前の開始状態に対応
する位置から一つ進めた位置（つまり、この例では、
「／」）に設定する。ただし、すでにパターンマッチし
た文字列（この例では、「１／２」）と重なって検索さ
れる文字列については無視する場合は、入力位置は受理
状態に遷移する時の入力記号の位置から一つ進めた位置
（先頭から５文字目の「３」）に設定する。以下、同様
である。すると、「状態１」で入力記号「／」の場合は
「照合失敗」となり、再び開始位置を一つ進めて「２」
とし、「状態１」からやり直す。すると、「状態１」で
入力記号は「２」なので、「状態２」へ遷移する。次の
入力記号は「３」なので、「照合失敗」となり、また
「開始状態＝状態１」からやり直す。この時、入力位置
は直前の開始状態に対応する位置から一つ進めた位置
（つまり、この場合では、「３」）に設定する。する
と、「状態１」で、入力記号は「３」なので、また「照
合失敗」となり、また状態１からやり直す。次の入力記
号は「１」なので、状態遷移表に従って「状態２」へ遷
移する。「状態２」で、次の入力記号は「：」なので、
状態遷移表に従って「状態４」へ遷移する。「状態４」
で、次の入力記号は「２」なので、状態遷移表に従って
「状態６」へ遷移する。「状態６」は，「受理状態２」
なので、この時点で文字列照合に成功し、パターン２が
この位置で検索されたことがわかる。つまり、直前の開
始記号の時点の入力記号位置（「１」）から、受理状態
２に遷移する時の入力記号の位置（「２」）まで
（「１：２」）が、パターン２とマッチしたということ
である。

【００１５】「状態６」では、どんな入力記号が来ても
「照合失敗」となるので、再び開始状態の「状態１」か
ら開始する。この時、入力位置は直前の開始状態に対応
する位置から一つ進めた位置（つまり、この例で
は、「：」）に設定する。すると、「状態１」で、入力
記号「：」は「照合失敗」となり、再び開始位置を一つ
進めて「２」とし、「状態１」からやり直す。すると、
「状態１」で、入力記号「２」なので、「状態２」へ遷
移する。次の入力記号は「５」なので、「照合失敗」と
なり、再び開始位置を一つ進めて「５」とし、また「状
態１」からやり直す。すると、「状態１」で、入力記号
「５」なので、「照合失敗」となり、再び開始位置を一
つ進めて「８」とし、また「状態１」からやり直す。す
ると、「状態１」で、入力記号「８」なので、「照合失
敗」となる。この時点で入力文字列をすべて読み込んだ
ことになるので、処理を終了する。

【００１６】以上より、入力文字列を１回読んだだけ
で、すべてのパターンを（パターン１とパターン２と
に）区別して検索できることが確認できた。なお、この
例では、二つの受理状態のどちらもが「どんな入力記号
が来ても照合失敗」になっていたが、正規表現のパター
ンによっては、受理状態でも、なんらかの入力記号に対
して次の遷移先が定義される場合がある。この場合は、
文字列照合に成功した後も、開始状態に戻ることなく、
状態遷移を続ける。そして、再び受理状態に到達すれ
ば、同一の開始位置から、複数の（長さの異なる）パタ
ーンが検索できたことになる。もし、パターンの長さの
最長のものだけが得られれば良いのであれば、入力文字
列を全部読み込むか、「照合失敗」になるかする直前の
受理状態に到達するパターンのものだけを出力すれば良
い（照合失敗をはさまずに、受理状態に何度なったとし
ても、最後のものだけを本当の「照合成功」とみな
す）。このようなことが起こる具体例として、実施例２
をあげて次に説明する。

【００１７】（実施例２）ここでは、正規表現パターン
として以下の二つのパターンを区別して一括で検索した
いとする場合を仮定する（図３のステップＳ３０１に対
応）。・パターン１ “ａ” ・パターン２ “（ａｂｂ)|(ａ＊ｂｂ＊）” すると、図３のステップＳ３０２で、以下の拡大正規表
現が作成される。・（(ａ)＃₁)|(((ａｂｂ)|(ａ＊ｂｂ＊))＃₂）この拡大正規表現の構文木は、図９に示される形にな
り、これをもとに状態集合と状態遷移表を図１０のよう
に作成する（図３のステップＳ３０３に対応）。状態の
うち、firstpos（root）（構文木が生成する記号列の中
で、最初の記号に対応する位置の集合を返す。この例で
は｛１，３，６，７｝となる。）で表されるもの（この
例では、状態１）が開始状態となる。また、状態のう
ち、＃_iに対応する位置を含むものは、「受理状態ｉ」
とするので、最終的な状態集合と状態遷移表は、図１１
で示されるものになる（図３のステップＳ３０４に対
応）。状態遷移表で空欄になっているのは、「受理せず
に停止」、つまり、文字列照合に失敗したことを意味す
る。入力記号として、この表に存在しないもの（例え
ば、「ｃ」）が出現した場合も、「受理せずに停止」で
ある。

【００１８】この図１１に示される状態遷移表に従っ
て、以下の文字列照合を行ってみる。・ａａｂｂｂまず、開始状態である「状態１」から開始する。状態遷
移表を参照すると、「状態１」では、入力記号が「ａ」
ならば「状態２」へ遷移し、入力記号が「ｂ」ならば
「状態３」へ遷移し、それ以外は「照合失敗」である。
上の例の文字列を見ると、最初の入力記号は「ａ」なの
で、「状態２」へ遷移する。「状態２」は「受理状態
１」なので、開始状態からの文字列である「ａ」が、パ
ターン１とマッチしたことがわかる。次に、入力文字列
を一つ進めると、入力記号は「ａ」である。状態遷移表
を見ると、「状態２」で入力記号「ａ」の場合は、「状
態４」へ遷移することがわかる。「状態４」で、次の入
力記号は「ｂ」なので、状態遷移表に従って「状態３」
へ遷移する。「状態３」は「受理状態２」なので、開始
状態からの文字列である「ａａｂ」が、パターン２とマ
ッチしたことがわかる。

【００１９】次に、入力文字列を一つ進めると、入力記
号は「ｂ」である。状態遷移表を見ると、「状態３」で
入力記号「ｂ」の場合は、「状態３」へ遷移することが
わかる。「状態３」は「受理状態２」なので、開始状態
からの文字列である「ａａｂｂ」が、パターン２とマッ
チしたことがわかる。次に、入力文字列を一つ進める
と、入力記号は「ｂ」である。状態遷移表を見ると、
「状態３」で入力記号「ｂ」の場合は、「状態３」へ遷
移することがわかる。「状態３」は「受理状態２」なの
で、開始状態からの文字列である「ａａｂｂｂ」が、パ
ターン２とマッチしたことがわかる。これで、入力文字
列の読み込みを全部終了したことになる。パターンマッ
チした文字列を全部出力するのであれば、「ａ」がパタ
ーン１として、「ａａｂ」「ａａｂｂ」「ａａｂｂｂ」
が、パターン２として抽出される。同じ開始位置から始
まる文字列については、最長のものだけを出力する場合
は、「照合失敗」か「文字列の終了」になった時に、直
前の受理状態のものだけを出力すれば良いので、この例
では、「ａａｂｂｂ」のみがパターン２として抽出され
る。

【００２０】（実施例３）実施例１は、終端記号＃₁，
＃₂，…を付加した拡大正規表現を用いたが、終端記号
として＃のみを付加する拡大正規表現を用いたものの具
体例を以下に示す（図３のステップＳ３０２に対応）。・(((１｜２)／(１｜２))＃)｜(((１｜２)：(１｜２))
＃) この拡大正規表現の構文木は図１３で示される形とな
り、これをもとに状態集合と状態遷移表を作成すると、
図７のように作成される（図３のステップＳ３０３に対
応）。状態のうち、firstpos(root)（構文木が生成する
記号列の中で、最初の記号に対応する位置の集合を返
す。この例では｛１，２，７，８｝となる。）で表され
るもの（この例では状態１）が開始状態となる。また、
状態のうち＃に対応する位置（この例では６と１２）を
含むものは位置の前の方から順番に「受理状態１」「受
理状態２」とするので、最終的な状態集合と状態遷移表
は図８で示されるものになる（図３のステップＳ３０４
に対応）。

【００２１】本発明によって得られる処理速度について
の実験結果の一例を以下に示す。・実験環境： Sun SPARCstation 10 gcc-Ｏにてコンパイル・検索対象： 100文書全容量は382,458バイト対象とする文書の一例（部分）：『第５回検索基礎論研究会日時：６月２６日（月）発表申込期限３月１７日 ◇発表申込方法：必要事項（下記の申込フォーマット参
照）を記入の上、下記宛にEmail,FAX、または郵便でお
送り下さい。〒261 千葉市美浜区中瀬1-9-2 シャープ株式会社映像メディア研究所 Phone:(043)299-8710,FAX:(043)299-8709 Email:natch iml.mkhar.sharp.co.jp 』・正規表現の例：以下に「日付を検索するパターン」の
先頭部分を示す。 ((((19[0-9][0-9])|([1-9][0-9])) ?年?)?(([1-9])|(1
[0-2])|(0[1-9]))?月?(([1-9])|1[0-9])|(2[0-9])|(3[0
-1])|(0[1-9])) ?日?(＼((月|火|水|木|金|土|日)(曜日
|曜)?＼))??[,〜.ー−]?(([1-9])|1[0-9])|(2[0-9])|(3
[0-1])|(0[1-9])) ?日(?(＼((月|火|水|木|金|土|日)
(曜日|曜)?＼)))?)|((((19[0-9][0-9])|([1-9][0-9]))
?年?)?(([1-9])|(1[0-2])|(0[1-9])) ?月?(([1-9])|1[0
-9])|(2[0-9])|(3[0-1])|(0[1-9]) ?日?(＼((月|火|水|
木|金|土|日)(曜日|曜)?＼))??[,〜.ー−]?(([1-9])|1
[0-2])|(0[1-9])) ?月?(([1-9])|1[0-9])|(2[0-9])|(3
[0-1])|(0[1-9])) ?日(?(＼((月|火|水|木|金|土|日)
(曜日|曜)?＼)))?)|… ・ＤＦＡを使用した場合の検索時間：

【００２２】

【表１】

【００２３】以上より、正規表現を別々に検索した場合
は、上記の全パターンを検索するのに１０秒要するが、
本発明を利用すると５秒で検索できることが分かり、処
理速度の向上が確かめられた。

【００２４】本発明の決定性有限オートマトンの状態数
の最適化方法の手順が図５に示されている。図５におい
て、状態集合の最初のグループ分けΠとして、ｎ個の受
理状態（Ｆ₁，Ｆ₂，…，Ｆ_n）と、１個の非受理状態
の、合計（ｎ＋１）個のグループを作る（ステップＳ５
０１）。次に、Πから、グループ分けができる限り、新
しいグループ分けΠ_newを作り、これ以上新しいグルー
プを作成できなくなったら、そのグループ分けをΠ
_finalとする（ステップＳ５０２）。そして、最終的な
グループ分けΠ_finalから、状態数が最適化された決定
性有限オートマトンＭ′を作成する（ステップＳ５０
３）。決定性有限オートマトンをこのように構成するこ
とによって、受理状態が複数に分かれたままで、状態数
を最適化することができる。

【００２５】（実施例４）状態数削減方法の実施例につ
いて、前述の実施例２を用いて説明をする。図１１よ
り、状態集合の最初のグループ分けΠとして、・受理状態Ｆ１＝状態２・受理状態Ｆ２＝状態３，状態５・非受理状態＝状態１，状態４を作成する。次に、Πから新しいグループ分けΠ_newを
作成する。受理状態Ｆ１については、一つの状態しか含
んでいないので、このままである。受理状態Ｆ２につい
ては、状態３と状態５とで、すべての入力記号について
の遷移先を調べる。すると、入力記号「ｂ」では、どち
らも「状態３」へ遷移し、その他の入力記号の場合は
「照合失敗」である。従って、受理状態Ｆ２はこれ以上
分割する必要はないことがわかる。非受理状態について
は、入力記号「ａ」を考えると、状態１では「状態２＝
受理状態Ｆ１」へ遷移、状態４では、「状態４＝非受理
状態」へ遷移することになるので、同じ入力記号
（「ａ」）で同じ状態グループに遷移しない（片方は受
理状態Ｆ１、もう片方は非受理状態）ので、分割する必
要がある。

【００２６】以上より、新しい分割Π_newは以下のよう
になる。・受理状態Ｆ１＝状態２・受理状態Ｆ２＝状態３，状態５・非受理状態１＝状態１・非受理状態２＝状態４これ以上の分割は進められないので、これがΠ_finalと
なる。次に、Π_finalの各グループから代表として一つ
の状態を選ぶ。これはどのように選んでも良いが、ここ
では、受理状態Ｆ２の代表状態として状態３を選び、順
番を変更して、新たな状態を以下のように定義する。な
お、開始状態は、元の決定性有限性オートマトンの開始
状態を含むグループの代表となる。・状態１＝非受理状態１＝元の状態１＝開始状態・状態２＝受理状態Ｆ１＝元の状態２・状態３＝受理状態Ｆ２＝元の状態３・状態４＝非受理状態２＝元の状態４この新たな状態から、状態遷移表を作成し直すと、図１
２に示されるものになる。このように構成した決定性有
限オートマトンは、受理状態Ｆ１と受理状態Ｆ２とを区
別でき、しかも、最初（図１１）より状態数が最適化さ
れていることがわかる。

【００２７】本発明による文字，文字列検索方法を実行
するために用いるプログラムやデータを提供する手段に
ついて、その実施形態を以下に説明する。この手段は、
上記したところの文字，文字列検索方法を実行するため
のプログラムやデータを保存した記録媒体として提供さ
れる。記録媒体としては、具体的には、ＲＯＭ（リード
・オンリー・メモリー）、フラッシュメモリ、フロッピ
ーディスク、ハードディスク、光磁気ディスク、ＣＤ−
ＲＯＭ等が想定できる。そして、プログラムやデータを
記録した記録媒体を上記した形式のものとして流通させ
ることにより、当該方法の実施化を容易にする。コンピ
ュータ等の情報処理装置にこうした記録媒体をインスト
ールすることによって簡単に本文字，文字列検索方法を
実行できる装置を構成することができ、本装置により、
記録媒体から読み出されたかかるプログラムやデータに
したがって、文書データから文字，文字列を検索するこ
とができる。本発明は、単語検索や単語照合に用いるだ
けでなく、有限オートマトンを利用したアプリケーショ
ンで、区別できる複数の受理状態を持たせたい場合に利
用することができる。

【００２８】

【発明の効果】本発明は、文書データを一回読み込むだ
けで、複数の種類のパターンを一度に検索することがで
きる文字列検索方法を提供する。請求項１の発明では、
区別したい正規表現パターンに応じて、受理状態を複数
持たせることで、複数のパターンを一度に検索しても、
マッチしたパターンの区別ができる。請求項２の発明で
は、区別したい正規表現パターンに応じて、受理状態を
複数持たせることで、複数のパターンを一度に検索して
も、マッチしたパターンの区別ができるようにするもの
で、一種類の終端記号を共通に用い、請求項１の複数種
類を用いる方法と異なる方法を提供する。請求項３の発
明では、請求項１又は２の方法を実行するために有効な
具体化方法を提供する。請求項４の発明では、複数の種
類のパターンを区別しながら一度に検索できる本発明の
特徴を保持したまま、決定性有限オートマトン状態数を
最適化することができる。請求項５の発明では、請求項
４の方法を実行するために有効な具体化方法を提供す
る。請求項６の発明では、請求項１ないし５のいずれか
に記載の文字，文字列検索方法を実行するためのプログ
ラムやデータをコンピュータ読み取り可能な記録媒体に
記録することで、プログラムやデータが保持された記録
媒体を扱うコンピュータ等の情報処理装置で、文字，文
字列の当該検索方法を実行することが可能になる。

【図面の簡単な説明】

【図１】本発明の請求項１の決定性有限オートマトン作
成方法の手順を示すフローチャートである。

【図２】本発明の請求項２の決定性有限オートマトン作
成方法の手順を示すフローチャートである。

【図３】本発明の請求項３の決定性有限オートマトン作
成方法の手順を示すフローチャートである。

【図４】本発明の請求項４の決定性有限オートマトンの
状態数最適化方法の手順を示すフローチャートである。

【図５】本発明の請求項５の決定性有限オートマトンの
状態数最適化方法の手順を示すフローチャートである。

【図６】本発明の実施例１の拡大正規表現の構文木を示
す図である。

【図７】本発明の実施例１の拡大正規表現の状態集合と
状態遷移表を示すである。

【図８】図７の本発明の実施例１の拡大正規表現の状態
集合と状態遷移表に開始状態や受理状態を書き加えた図
である。

【図９】本発明の実施例２の拡大正規表現の構文木を示
す図である。

【図１０】本発明の実施例２の拡大正規表現の状態集合
と状態遷移表を示す図である。

【図１１】図１０の本発明の実施例２の拡大正規表現の
状態集合と状態遷移表に開始状態や受理状態を書き加え
た図である。

【図１２】本発明の実施例２の拡大正規表現の決定性有
限オートマトンの状態数を最適化した後の状態集合のグ
ループ分けと状態遷移表を示す図である。

【図１３】本発明の実施例３の拡大正規表現の構文木を
示す図である。

【図１４】従来の決定性有限オートマトン作成方法の手
順を示すフローチャートである。

【図１５】従来の決定性有限オートマトンの状態数最適
化方法の手順を示すフローチャートである。

Claims

【特許請求の範囲】

【請求項１】複数のパターンを同時に検索する文字，
文字列検索方法において、文字、或いは文字列を単位と
し、複数（２，…，ｎ）単位の各文字、或いは文字列の
正規表現ｒ₁，ｒ₂，…，ｒ_nそれぞれについて、終端記
号＃₁，＃₂，…，＃_nを付加した拡大正規表現（ｒ₁）＃
₁，（ｒ₂）＃₂，…，(ｒ_n)＃_nにもとづいた構文（(ｒ₁)
＃₁)|((ｒ₂)＃₂)|…|((ｒ_n)＃_n）を作成し、正規表現に
よる該構文を構成する前記複数の正規表現ｒ₁，ｒ₂，
…，ｒ_nに含まれる文字、或いは文字列の各パターンを
同時に検索対象に用いて、＃₁，＃₂，…，＃_nに対応す
る状態をそれぞれ受理状態１，受理状態２，…，受理状
態ｎとすることによって、複数のパターンを区別して検
索するための決定性有限オートマトンを構成するように
したことを特徴とする文字，文字列検索方法。
【請求項２】複数のパターンを同時に検索する文字，
文字列検索方法において、文字、或いは文字列を単位と
し、複数（２，…，ｎ）単位の各文字、或いは文字列の
正規表現ｒ₁，ｒ₂，…，ｒ_nそれぞれについて、共通の
終端記号＃を付加した拡大正規表現（ｒ₁）＃，（ｒ₂）
＃，…，(ｒ_n)＃にもとづいて拡大正規表現による構文
（(ｒ₁)＃)|((ｒ₂)＃)|…|((ｒ_n)＃）を作成し、正規表
現による該構文を構成する前記複数の正規表現ｒ₁，
ｒ₂，…，ｒ_nに含まれる文字、或いは文字列の各パター
ンを同時に検索対象に用い、その際、＃の位置をもとに
＃に対応する状態を受理状態の種類としてそれぞれ受理
状態１，受理状態２，…，受理状態ｎとすることによっ
て、複数のパターンを区別して検索するための決定性有
限オートマトンを構成するようにしたことを特徴とする
文字，文字列検索方法。
【請求項３】前記拡大正規表現にもとづいた構文から
状態集合｛状態１，状態２，…｝とその状態遷移表を作
成することにより、前記複数の正規表現ｒ₁，ｒ₂，…，
ｒ_nに含まれる文字、或いは文字列の各パターンを同時
に検索対象に用いるようにしたことを特徴とする請求項
１又は２記載の文字，文字列検索方法。
【請求項４】前記状態集合において、状態数の最適化
を行う場合に、受理状態１，２，…，ｎに対応する種類
によってＦ₁，Ｆ₂，…，Ｆ_nにグループ分けし、これら
のグループと受理状態以外の非受理状態と合わせて、全
体を（ｎ＋１）個にグループ分けすることを特徴とする
請求項３記載の文字，文字列検索方法。
【請求項５】前記（ｎ＋１）個のグループを各グルー
プについて、グループａ内のある状態ｓに文字、或いは
文字列（Ｍ）を入力した時の遷移先が当該グループｂ内
の状態であるとすると、グループａ内の他の任意の状態
ｔに同じ文字、或いは文字列（Ｍ）を入力した時の遷移
先もグループｂ内の状態であるようになるまでグループ
分けを行い、得られたグループ分けをもとに状態遷移表
を作成し直すことを特徴とする請求項４記載の文字，文
字列検索方法。
【請求項６】請求項１ないし５のいずれか１記載の文
字，文字列検索方法を実行するためのプログラム及びデ
ータを記録したコンピュータ読み取り可能な記録媒体。