JPH09198398A - パターン検索装置 - Google Patents

パターン検索装置

Info

Publication number
JPH09198398A
JPH09198398A JP8005236A JP523696A JPH09198398A JP H09198398 A JPH09198398 A JP H09198398A JP 8005236 A JP8005236 A JP 8005236A JP 523696 A JP523696 A JP 523696A JP H09198398 A JPH09198398 A JP H09198398A
Authority
JP
Japan
Prior art keywords
search
keywords
pattern
text
keyword
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP8005236A
Other languages
English (en)
Inventor
Nobuyuki Igata
伸之 井形
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP8005236A priority Critical patent/JPH09198398A/ja
Priority to US08/773,295 priority patent/US5963942A/en
Publication of JPH09198398A publication Critical patent/JPH09198398A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90344—Query processing by using string matching techniques
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • Y10S707/99935—Query augmenting and refining, e.g. inexact access
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • Y10S707/99936—Pattern matching access
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99937—Sorting

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】 【課題】 パターン検索装置、特に文字列検索装置に関
し、複数の検索方法のうちから最も検索効率のよい方法
を自動的に選択可能とする。 【解決手段】 検索対象内の検索パターンの検出を行う
パターン検索装置において、検索パターンの個数を含む
検索条件に対応して、複数の検索方法の中から１つの検
索方法を選択する手段１を備える。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は検索対象から検索パ
ターンを検出するパターン検索装置に係り、更に詳しく
はテキストとしての文字列の中から検索すべき文字列、
すなわちキーワードを検索する文字列検索装置に関す
る。
【０００２】最近のコード化された文章の増加に伴っ
て、文字列検索装置の必要性は一段と大きくなってい
る。また機械によって読むことができる文章の増加と共
に、ユーザの要求も多様化しつつあり、そのような多様
化するユーザの要求を満たすために、例えばキーワード
の数やその長さなどの検索条件に対応して検索効率を向
上させる必要性が大きくなっている。
【０００３】
【従来の技術】本発明は、検索対象内の検索パターンの
検出を行うパターン検索装置を一般的な対象とするが、
具体的には文字列検索装置を実施例として説明するの
で、ここでは文字列検索装置に関する従来技術を説明す
る。
【０００４】従来の文字列検索装置ではその装置の使用
目的に合わせて次に述べる文字列検索方法のうちの１つ
が用いられて文字列の検索が行われている。第１の方法
は検索文字列、すなわちキーワードの数が１つだけの場
合に効率的に検索を実行できるBoyer-Moore 法（以下Ｂ
Ｍ法と略称する）である。この方法は次の文献に与えら
れている。
【０００５】Boyer R.S., Moore J.S.: A Fast String
Searching Algorithm, CACM Vol.20, No.10, pp.762 (1
977) ここで具体例を用いてＢＭ法による検索について説明す
る。英文テキストを対象としてキーワード“ＡＴ−ＴＨ
ＡＴ”を検索する場合を考える。ＢＭ法では、まず最初
にテキストの先頭にキーワードの先頭が一致するように
キーワードがテキストに対応させられ、キーワードの一
番後の文字がテキストの対応する文字と比較（矢印で示
す）される。その様子を次に示す。
【０００６】
【数１】
【０００７】テキストの文字Ｆはキーワード中には存在
しないために、キーワード内の前の６文字をテキストの
対応する文字と比較することなく、キーワードを右側に
７つだけ移動させることができる。この状態を次に示
す。
【０００８】
【数２】
【０００９】再びキーワードの一番後の文字がテキスト
の対応する位置の文字と比較され、一致しないことが分
かる。ここでテキストの文字、すなわち“−”はキーワ
ード中で前から３文字目に存在するので、キーワードを
４つだけ右側に移動することができる。この状態を次に
示す。
【００１０】
【数３】
【００１１】ここでキーワードの一番後の文字がテキス
トと一致したため、その前の文字が比較される。ここで
はテキストの文字“Ｌ”はキーワード中には存在しない
ので、Ｌの位置から７つ、すなわち上の状態で６つだけ
キーワードが右側に移動される。この状態を次に示す。
【００１２】
【数４】
【００１３】ここでキーワードの最後とその前の文字は
テキストと一致するが、更にその前の文字は一致せず、
次に示すようにキーワードが５つだけ右側に移動され、
テキスト中からキーワードが検出される。
【００１４】
【数５】
【００１５】ＢＭ法でキーワードを右側に動かすべき量
は、キーワード自身と照合が失敗した時のテキスト上の
文字とから決まるため、照合を始める前にあらかじめそ
の量を示すテーブルを作っておき、文字列の検索を行う
ことができる。
【００１６】第２の方法は、ＢＭ法と同様にキーワード
の数が１つだけの場合を対象とするものであり、例えば
英語においてａやｅなどのアルファベットがｑやｘなど
に比べて出現頻度が多いことに着目して、出現頻度に応
じた検索を行うオプティマル・ミスマッチ法など、任意
の順序で文字比較を行えるようにＢＭ法を改良したSund
ay法である。この方法の文献を次に示す。
【００１７】Sunday D.M.: A very fast substring sea
rch algorithm, CACM, Vol.33, No.8,pp.132(1990) 第３の方法は、キーワードの数が複数である場合に有効
なAho-Corasick法（以下ＡＣ法と略称する）である。こ
の方法の文献を次に示す。
【００１８】Aho A.V., Corasick M.J.: Efficient Str
ing Matching:An Aid to Bibliographic Search, CACM,
Vol.18, No.6, pp.333(1975) ＡＣ法では、検索にあたって複数のキーワードに対応す
る状態遷移図が作られ、この状態遷移図を基にしてテキ
ストの最初から１文字ずつ検索が行われ、キーワードが
出力されるべき状態に達した時点で検索結果が出力され
る。
【００１９】図１６はキーワードが“ｈｅ”，“ｓｈ
ｅ”，“ｈｉｓ”、および“ｈｅｒｓ”の４つである場
合の状態遷移の説明図である。ある１つの状態、ここで
は０が最初の状態であり、ｈが検出された時点で状態が
１に遷移する。あるいはｓが検出された時点で状態は３
に遷移する。この状態遷移図に従って状態遷移が行わ
れ、図１６(b) に示すように状態、２，５，７、または
９に達した時点でキーワードの検出結果が出力される。
【００２０】図１６(c) はfailure 関数、すなわち状態
遷移だけが行われる場合の遷移先を示している。例えば
状態１でｅまたはｉが検出されない場合には、状態は０
に遷移する。状態４でｅが検出されない場合には、ｉが
検出されるか否かをチェックするために状態は１に遷移
する。状態５で“ｓｈｅ”が検出された時点で、その次
にｒが検出されるか否かをチェックするために状態は２
に遷移する。
【００２１】第４の方法としてのＦＡＳＴ法は、ＢＭ法
におけるキーワードの右端からの照合と、ＡＣ法の状態
遷移図を用いた複数キーワードの同時照合とを組み合わ
せたものである。
【００２２】図１７はＦＡＳＴ法におけるキーワード検
索例の説明図である。同図において、３つのキーワード
“ｓｔａｔｅ”，“ｅａｓｔ”および“ｓｍａｒｔ”を
用いてテキスト内のキーワードの検索が行われる。なお
このＦＡＳＴ法での状態遷移図は、図１５と異なり、キ
ーワードの左端から右端に向かって状態が遷移するので
はなく、逆にキーワードの右端から左端に向かって状態
が遷移する形式で作成される。
【００２３】このような状態遷移図が作成された後に、
図１７で示すように、まずテキストの先頭からキーワー
ドの中で最も短いキーワードの長さの分だけの部分文字
列を対象として、その部分文字列の右端の文字から３つ
のキーワードとの比較が行われる。図１６では部分文字
列の右端の文字ｍは３つのキーワードの右端の文字のい
ずれとも一致せず、またｓｍａｒｔというキーワードの
中にのみ存在するために、３つのキーワードを全て右側
に３文字分動かした後に照合を再開すればよいことが分
かる。なおこのＦＡＳＴ法の文献を以下に示す。
【００２４】浦谷則好：高速な複数文字列照合アルゴリ
ズム：ＦＡＳＴ、情報処理学会論文誌、Vol.30, No.9,
pp.1119(1989)
【００２５】
【発明が解決しようとする課題】従来においては、以上
で説明したような４つの方法のいずれかが用いられて文
字列検索が行われることが一般的であった。例えばワー
プロなどのようにキーワードを１つだけ用いて文字列検
索を行うことが多いような装置では、例えば前述のＢＭ
法が用いられ、大型データベースのように多数のキーワ
ードに対して一度で検索を行うような場合には、ＡＣ法
などが用いられていた。
【００２６】このようにキーワードの数などの検索条件
がある程度決まっている場合には、１つの文字列検索装
置において特定の検索方法を採用して検索を行うことに
より、比較的良好な検索効率を実現することができる
が、キーワードの数が不定であり、キーワードの長さも
様々であり、また対象テキストが和文、または英文のい
ずれかに限られることがないような場合には、このよう
な検索条件に対応して最適な検索方法を選択することが
できないという問題点があった。
【００２７】本発明は、一般にパターン検索装置におい
て検索条件に対応して複数の検索方法のうちから最も検
索効率のよい検索方法を選択可能とすることであり、特
に文字列検索装置では前述の４つの方法のいずれかのう
ちで最も検索効率のよい検索方法を自動的に選択可能と
することを目的とする。
【００２８】
【課題を解決するための手段】図１は本発明のパターン
検索装置の原理構成ブロック図である。同図は、検索す
べき検索パターンと検索対象とが与えられた時に、検索
対象内の検索パターンの検出を行うパターン検索装置の
原理構成ブロック図である。
【００２９】図１において、検索方法選択手段１は例え
ば文字列検索装置ではパターン照合方法選択装置であ
り、検索パターン、すなわち文字列としてのキーワード
の個数を含む検索条件に対応して、複数の検索方法、例
えば前述の４つの方法のうちから１つの検索方法を選択
するものである。
【００３０】前述のように、文字列検索においてはキー
ワードの数が１個のみであるか複数であるかによって、
選択すべき検索方法が限定される。また詳しくは後述す
るが、検索効率、すなわち検索時間はキーワードの長
さ、キーワードが複数ある場合にはその中で最短のキー
ワードの長さと、キーワードの数によって大きく異なっ
てくる傾向がある。
【００３１】このため本発明においては、最短のキーワ
ードの長さが非常に短い場合には、例えばＡＣ法が採用
される。最も短いキーワードの長さが比較的長く、また
キーワードの数が１個のみである場合には、例えば前述
のＢＭ法、またはSunday法が選択される。このうちテキ
ストが和文である場合にはＢＭ法が、また英文である場
合にはSunday法が選択される。
【００３２】更に最短のキーワードの長さが比較的長
く、しかもキーワードの数が複数である場合には、例え
ばそのキーワードの数と最短のキーワードの長さとに依
存する判別関数の値が求められ、その値に応じて前述の
ＡＣ法、またはＦＡＳＴ法が用いられる。
【００３３】以上のように本発明によればキーワードの
数、最短のキーワードの長さなどの検索条件に対応し
て、最適と考えられる検索方法が自動的に選択される。
【００３４】
【発明の実施の形態】以下の説明では、パターン検索装
置の実施例として、文字列としてのキーワードを検索対
象としてのテキストから検出する文字列検索装置につい
て説明する。
【００３５】図２は文字列検索装置の基本構成を示すブ
ロック図である。同図において文字列検索装置は、検索
対象としてのテキストを格納するテキストバッファ１
０、テキストバッファ１０に格納されたテキストの中か
らキーワードの検索を行うテキスト検索装置１１、テキ
スト検索装置１１によって検索された結果を出力するた
めの出力装置１２、および検索文字列、すなわちキーワ
ードの集合と、テキストバッファ１０に格納されている
テキストの形式、すなわちテキストが和文であるか英文
であるかに応じて、前述のＢＭ法、Sunday法、ＡＣ法、
ＦＡＳＴ法のいずれかの文字列検索方法を選択し、その
選択結果をテキスト検索装置１１に指示するパターン照
合方法選択装置１３から構成されている。
【００３６】図２において、テキストバッファ１０に格
納されたテキストの形式、すなわち和文であるか英文で
あるかがパターン照合方法選択装置１３に与えられる
と、パターン照合方法選択装置１３はキーワードの個数
や、その中で最短のキーワードの長さなどの検索条件に
応じて、前述の４つの方法のうちいずれかの方法を選択
し、その方法はテキスト検索装置１１に指示される。テ
キスト検索装置１１の内部には、前述の４つの方法を実
現するための４つのエンジン（ソフトウェア）が備えら
れており、指定された文字列検索方法に対応するエンジ
ンが使用されてテキスト内のキーワードが検索され、出
力装置１２はその検索結果をユーザの要求に従った形
式、例えばキーワードの他の文字列への置換を行った形
式としてユーザに出力する。
【００３７】ここで前述の４つの方法による文字列検索
の特徴について更に説明する。まず第１にＢＭ法と第２
のSunday法は共に効率のよい検索方法であるが、一度に
１つのキーワードしか検索することができない。第３の
ＡＣ法では同時に複数のキーワードの検索ができるが、
テキストを１文字ずつチェックして状態の遷移を追うた
めに、検索に比較的時間がかかる。
【００３８】第４の方法、すなわちＢＭ法とＡＣ法のそ
れぞれの長所を組み合わせたＦＡＳＴ法は、キーワード
の数が比較的少数の場合には検索効率がよい。しかしな
がら多数のキーワードを同時に検索する場合には、図１
７で説明したようにキーワードの右端の文字がテキスト
と一致した場合に左側に戻ってチェックするための時間
が長くなり、ＡＣ法よりも検索時間が長くなってしま
う。
【００３９】すなわちキーワードの数をｋ、キーワード
の平均長さを 外１ 、テキストの
【００４０】
【外１】
【００４１】長さをｎとした場合、第１のＢＭ法では１
個のキーワードに対する検索時間は一般に 外２ のオ
ーダーとなり、最悪の場合には 外３ のオーダーで与
えられ
【００４２】
【外２】
【００４３】
【外３】
【００４４】る。ｋ個のキーワードに対しては検索時間
は一般に 外４ のオーダーとなる。
【００４５】
【外４】
【００４６】第２のSunday法では、検索時間はＢＭ法と
同程度であるが、テキストが英文の場合には１０〜３０
％程度の検索速度の向上が期待できるものとされてい
る。しかしながら出願人の実験によると、テキストが和
文の場合には殆ど速度向上が期待できないことが判明し
た。
【００４７】第３のＡＣ法では、検索時間はキーワード
の数やキーワードの長さに一般的には依存せず、Ｏ
（ｎ）のオーダーでほぼ一定になる。第４のＦＡＳＴ法
では、キーワードの中で最も短いキーワードの長さをＬ
として検索時間の最良値はＯ（ｎ／Ｌ）のオーダーとな
り、キーワードの数が少ない場合にはよい値が期待でき
る。しかしながらキーワードの数が多くなると、検索時
間はＡＣ法に対するＯ（ｎ）よりも長くなる。ここで検
索時間がＡＣ法よりも長くなるキーワードの数は、後述
するように最短のキーワードの長さによってほぼ決定さ
れる。
【００４８】図３は本発明における検索方法選択処理の
フローチャートである。同図の処理は図２のパターン照
合方法選択装置１３によって実行される。図３において
検索文字列、すなわちキーワードの集合が与えられる
と、まずステップＳ１で最短の文字列（キーワード）の
長さが２バイト以上であるか否かが判定される。なお和
文の場合にはリターン文字などのような特殊な記号を除
いては１文字は２バイトで表され、これに対して英文で
はアルファベット１文字は１バイトで表される。このよ
うな１バイトの文字（記号）も当然キーワードとして使
用される。最短のキーワードの長さが２バイト以上でな
い、すなわち１バイトである場合にはキーワードの個数
の判定を行うことなく、ステップＳ２で直ちにＡＣ法が
選択され、その方法がテキスト検索装置１１に指示され
る。
【００４９】なお、ここでキーワードが１バイトのとき
ＡＣ法を無条件に選択するのは、ＦＡＳＴ法における
“キーワードの右端での比較”が実際には１文字ずつの
比較となり、ＦＡＳＴ法の利点（照合回数の減少）を得
られないためである。
【００５０】ステップＳ１で最短のキーワードの長さが
２バイト以上である時には、ステップＳ３で検索文字
列、すなわちキーワードの数が１個のみであるか否かが
判定され、１個のみである場合にはステップＳ４でテキ
ストが英文であるか否かが判定される。英文である場合
にはステップＳ５でSunday法が選択され、その方法がテ
キスト検索装置に指示される。英文でない場合にはステ
ップＳ６でＢＭ法が選択され、テキスト検索装置にその
方法が指示される。
【００５１】ステップＳ３で検索文字列、すなわちキー
ワードの数が１個のみでないと判定されると、ステップ
Ｓ７で判別関数ｆの値が求められ、その値が１未満であ
るか否かが判定される。この判別関数ｆについては後述
する。
【００５２】判別関数ｆの値が１未満である時にはステ
ップＳ８でＦＡＳＴ法が選択され、また１未満でない時
にはステップＳ２でＡＣ法が選択され、選択された方法
はそれぞれテキスト検索装置１１に指示される。
【００５３】図３における検索方法選択の根拠と、前述
の判別関数ｆについて実験結果に基づいて詳しく説明す
る。図４は日本語テキストを対象としてＢＭ法、ＡＣ
法、およびＦＡＳＴ法をそれぞれ用いた場合の検索時間
を、検索文字列、すなわちキーワードの数に対して示し
たものである。この実験に使用されたキーワードの長さ
は平均４．４バイト、最短２バイトであり、縦軸の検索
時間はキーワードの数が１個のみの時のＡＣ法による検
索時間を１として示した測定値である。
【００５４】ＡＣ法ではキーワードの数が増えても検索
時間は殆ど増加しないこと、ＢＭ法ではキーワードの数
が１０個程度以下の場合には検索時間はＡＣ法より短い
が、それ以上のキーワード数に対しては長くなること、
同様にＦＡＳＴ法ではキーワードの数が４０以下でＡＣ
法より検索時間が短く、４０以上で長くなることが分か
る。
【００５５】図５はＦＡＳＴ法を用いた場合の検索時間
を、ＡＣ法を用いた場合の検索時間を１とし、最短のキ
ーワードの長さをパラメータとして示したものである。
最短のキーワードの長さが短い場合には、ＡＣ法より検
索時間が長くなるキーワードの数、すなわち限界検索文
字列数は小さくなることが分かる。
【００５６】図６は、図５の結果に対して最小自乗法を
適用して、検索時間とキーワードの数との関係を直線化
した結果である。図７は、図６において最短のキーワー
ドの長さをパラメータとするそれぞれの直線がＡＣ法に
よる検索時間、すなわち１となる時のキーワードの数、
すなわち限界検索文字列数を求めたものである。図６に
示されていないキーワード、すなわち検索文字列の最短
のものの長さに対する限界検索文字列数は、図６の結果
に対してラグランジュ補間を適用することによって求め
られたものである。
【００５７】図８は、図７の結果をステップ的な関数と
して示したものである。横軸は最短検索文字列長であ
り、縦軸は検索文字列、すなわちキーワードの数であ
る。図のステップ関数より下の部分が、ＦＡＳＴ法によ
る検索時間がＡＣ法より短い範囲を示している。
【００５８】図４〜図８の実験結果は、後述する英文テ
キストに対する実験と同様に、テキスト内に存在するキ
ーワードの数が平均的な場合を対象として得られたもの
である。実験に使用されたテキストは大きさ７．５Ｍby
tes であり、Ａ４用紙１枚の容量を４〜５Ｋbytes とす
ると、1500〜2000ページの分量となるのでテキストの内
容はここに示さない。
【００５９】前述のように、ＡＣ法では検索時間はキー
ワードの数の増加につれてわずかに増加するのみでほぼ
一定と見なせる。特に最短のキーワードの長さは検索時
間に全く影響しない。ＦＡＳＴ法ではキーワード数と最
短キーワード長は検索時間に影響するが、キーワードの
平均の長さは殆ど影響を与えない。
【００６０】そこでテキスト内に存在するキーワード数
が平均的な場合には、例えば図８のステップ関数の形は
具体的なテキストやキーワードの相違によって大きく異
なることはなく、一般的に有効なものとして使用できる
と考えられる。
【００６１】ここで前述の判別関数ｆについて説明す
る。最短検索文字列長をＬ、限界検索文字列数をＫと
し、図７、または図８に示される関係を表す関数を Ｋ＝ｇ（Ｌ） と定義する。テキストの中で検索されるべきキーワード
の数をｋとすると、判別関数ｆは次式のように定義され
る。
【００６２】ｆ（ｋ，Ｌ）＝ｋ／ｇ（Ｌ）＝ｋ／Ｋ キーワードの数ｋが図８のステップ関数、すなわちＫよ
りも小さい時にＦＡＳＴ法による検索時間がＡＣ法によ
るよりも短くなるために、判別関数ｆが１未満である時
に図３でＦＡＳＴ法が、また１未満でない時にはＡＣ法
が選択される。
【００６３】日本語テキストを対象とするキーワードの
検索例を図９を用いて説明する。ここでキーワードとし
て“技術協力”、“技術動向”、および“技術交流”の
３つが指定され、日本語テキストとして次のものが与え
られたとする。
【００６４】
【外５】
【００６５】まずテキストがテキストバッファ１０に与
えられ、テキストバッファ１０はテキストが英文である
か和文であるかを判別する。この判別結果とキーワード
の集合に対応して、パターン照合方法選択装置１３は最
適なパターン照合方法を選択する。この場合キーワード
の数ｋは３、最短のキーワードの長さＬが日本語４文字
に対応する８バイトであることから、判別関数ｆの値が
３／83.43 、すなわち１より小さいことが判定され、図
３のステップＳ８でＦＡＳＴ法が選択される。
【００６６】この検索方法はテキスト検索装置１１に送
られ、テキスト内のキーワードの位置の検索が行われ
る。この場合テキストの文頭から５３バイト目、２１５
バイト目、２９０バイト目、および３３２バイト目、・
・・の位置が検索され、その検索結果は出力装置１２に
送られる。なお上のテキスト内で示されていないリター
ン記号は１バイトの長さに相当する。
【００６７】出力装置１２では、ユーザの要求に応じて
検索結果に必要な加工を行い、その加工結果を出力す
る。図９に示されるように技術協力をＸＸＸ、技術動向
をＹＹＹ、技術交流をＺＺＺに置換する置換ルールがユ
ーザから与えられた場合には、テキスト内の対応するキ
ーワードが指定された置換ルールを用いて置換され、ユ
ーザに対して出力される。
【００６８】次に英文テキストを対象とする検索の実施
例について説明する。前述の判別関数などを用いた検索
処理は和文テキストに対する場合とほぼ同様であるの
で、和文テキストとの相違点を中心に簡単に説明する。
【００６９】図１０は英文テキストを対象として図４と
同様の実験結果を示したものである。図４におけると同
様に、キーワードの数が１個のみの場合のＡＣ法の検索
時間を１とした場合の検索時間の値を縦軸に示してい
る。使用されたキーワードの長さは平均６．６バイト、
最短４バイト（キーワードが１個のみの場合も同じ）で
ある。図４と同様の傾向が示されているが、前述のよう
にSunday法を用いることによってＢＭ法よりも検索時間
が短くなることが示されている。
【００７０】図１１は、図５と同様に英文テキストに対
するＦＡＳＴ法による検索時間をＡＣ法の場合を１とし
て示したものである。図５におけると同様に、最短のキ
ーワードの長さが長くなるにつれて、限界検索文字列数
が大きくなることが示されている。なお図１０と異な
り、ここでは最短のキーワードの長さは、キーワード１
個のみの場合を含めて、２バイトである。
【００７１】図１２は、図６と同様に、図１１の結果を
最小自乗法を用いて線形化した結果を示す。図１３は、
図１２の結果およびラグランジュ補間を用いることによ
って、図７と同様に英文テキストに対する最短検索文字
列長と限界検索文字列数との関係を示したものである。
【００７２】図１４は、図１３の結果を、図８と同様に
ステップ関数の形式で表したものであり、このステップ
関数より下の部分がＦＡＳＴ法を用いた検索時間がＡＣ
法による検索時間よりも短くなる範囲である。
【００７３】ここで図１４と図８を比較すると、英文と
和文では判別関数の形にかなり相違があることが分か
る。この理由としては、日本語のような２バイト系文章
と比較して、英文のような１バイト系文章では使用され
るコードの種類が明らかに限定されることがあげられ
る。使用されるコードの種類の数はＦＡＳＴ法による検
索時間に対して大きな影響を与えることが知られてお
り、日本語文章および英語文章のそれぞれに対して判別
関数を求めておき、その判別関数を用いて本実施例のよ
うに検索方法の選択を行う必要がある。
【００７４】図１５は次の英文テキストを対象とするキ
ーワード検索の例の説明図である。
【００７５】
【外６】
【００７６】図９に対すると同様の動作が行われるが、
ここではキーワードの数が３個、キーワードの中で最短
のものの長さがアルファベット５文字、すなわち５バイ
トであることから判別関数ｆの値が３／56.68 となり、
１より小さくなることからＦＡＳＴ法が選択される。
【００７７】テキスト検索装置１１によって、テキスト
内のキーワードの位置がテキスト文頭から１８バイト
目、６９バイト目、１０７バイト目、および１４９バイ
ト目、・・・であること（なお、１行目の最後の“ｏ
ｒ”の後にリターン記号１バイト分がある）が検索さ
れ、その検索結果に応じてユーザによって指定された置
換ルールを用いてキーワードの置換が行われ、その結果
がユーザに出力される。
【００７８】
【発明の効果】以上詳細に説明したように、本発明によ
ればテキストの言語、キーワードの数、最短のキーワー
ドの長さなどの検索条件に対応して、最適な検索方法を
自動的に選択することが可能になり、文字列検索効率の
向上に寄与するところが大きい。ワープロなどのように
キーワードの数が１個のみの場合にも、大型データベー
スの場合のように多数のキーワードを一度に検索する場
合にも、キーワードの数に適した検索速度をあげること
ができる。また検索にあたってユーザが一度に検索すべ
きキーワードの数を考慮する必要がなくなり、ユーザの
負担も軽減される。
【図面の簡単な説明】
【図１】本発明の原理構成ブロック図である。
【図２】文字列検索装置の基本構成を示すブロック図で
ある。
【図３】文字列検索方法選択処理のフローチャートであ
る。
【図４】各種検索方法による検索時間の比較を示す図
（和文テキスト）である。
【図５】ＦＡＳＴ法における検索時間とキーワードの数
との関係を示す図（和文テキスト）である。
【図６】図５に対する線形化の結果を示す図である。
【図７】最短検索文字列長と限界検索文字列数との関係
を示す図（和文テキスト）である。
【図８】限界検索文字列数としてのステップ関数を示す
図（和文テキスト）である。
【図９】和文テキストに対するキーワード検索の例を説
明する図である。
【図１０】各種検索方法における検索時間の比較を示す
図（英文テキスト）である。
【図１１】ＦＡＳＴ法における検索時間とキーワードの
数との関係を示す図（英文テキスト）である。
【図１２】図１１に対する線形化の結果を示す図であ
る。
【図１３】最短検索文字列長と限界検索文字列数との関
係を示す図（英文テキスト）である。
【図１４】限界検索文字列数としてのステップ関数を示
す図（英文テキスト）である。
【図１５】英文テキストに対するキーワード検索の例を
説明する図である。
【図１６】ＡＣ法における状態遷移を説明する図であ
る。
【図１７】ＦＡＳＴ法による複数のキーワードの照合を
説明する図である。
【符号の説明】
１ 検索方法選択手段 １０ テキストバッファ １１ テキスト検索装置 １２ 出力装置 １３ パターン照合方法選択装置

Claims (10)

    【特許請求の範囲】
  1. 【請求項１】 検索対象と、該検索対象の中から検出す
    べき検索パターンとが与えられ、該検索対象内の検索パ
    ターンの検出を行うパターン検索装置において、 該検索パターンの個数を含む検索条件に対応して、複数
    の検索方法のうちから１つの検索方法を選択する検索方
    法選択手段を備え、検索効率の向上をはかることを特徴
    とするパターン検索装置。
  2. 【請求項２】 前記検索対象が文字列としてのテキスト
    であり、検索パターンが検索文字列としてのキーワード
    であることと、 前記検索条件が前記検索パターンとしてのキーワードの
    個数、該キーワードのうちで最短のキーワードの長さ、
    テキストが和文か英文かの指定を含むことを特徴とする
    請求項１記載のパターン検索装置。
  3. 【請求項３】 前記検索方法選択手段が、前記検索方法
    として、前記キーワードが１つのみである場合を対象と
    するBoyer-Moore 法、またはSunday法、キーワードが複
    数である場合を対象とするAho-Corasick法、またはＦＡ
    ＳＴ法のいずれかを選択することを特徴とする請求項２
    記載のパターン検索装置。
  4. 【請求項４】 前記検索条件において、前記キーワード
    の数が１個で、該キーワードの長さが２バイト以上であ
    り、かつ前記テキストが英文である時、前記検索方法選
    択手段が前記Sunday法を選択することを特徴とする請求
    項３記載のパターン検索装置。
  5. 【請求項５】 前記検索条件において、前記キーワード
    の数が１個で、該キーワードの長さが２バイト以上であ
    り、かつ前記テキストが和文である時、前記検索方法選
    択手段が前記Boyer-Moore 法を選択することを特徴とす
    る請求項３記載のパターン検索装置。
  6. 【請求項６】 前記検索条件において、前記キーワード
    の数が１個以上であり、該キーワードの中で最短のキー
    ワードの長さが１バイトである時、前記検索方法選択手
    段が前記Aho-Corasick法を選択することを特徴とする請
    求項３記載のパターン検索装置。
  7. 【請求項７】 前記検索条件において、前記キーワード
    の数が複数であり、該キーワードの中で最短のキーワー
    ドの長さが２バイト以上である時、前記検索方法選択手
    段が判別関数の値を評価し、該評価結果に応じて前記Ah
    o-Corasick法、またはＦＡＳＴ法のいずれかを選択する
    ことを特徴とする請求項３記載のパターン検索装置。
  8. 【請求項８】 前記判別関数が、前記検索条件に含まれ
    るキーワードの個数ｋと、該キーワードの中で最短のキ
    ーワードの長さＬに対応して前記Aho-Corasick法よりも
    前記ＦＡＳＴ法による検索所要時間が長くなる限界にお
    けるキーワード数の一般的な実験値Ｋとの比をｋ／Ｋと
    して与えられ、該判別関数の値が１より小さい時に前記
    検索方法選択手段がＦＡＳＴ法を、１以上である時Aho-
    Corasick法を選択することを特徴とする請求項７記載の
    パターン検索装置。
  9. 【請求項９】 前記パターン検索装置を構成する文字列
    検索装置が、前記検索方法選択手段を構成するパターン
    照合方法選択装置に加えて、 検索対象としてのテキストを格納するテキストバッファ
    と、 該テキストバッファとパターン照合方法選択装置との出
    力に応じて検索を実行するテキスト検索装置とを更に備
    えることを特徴とする請求項１記載のパターン検索装
    置。
  10. 【請求項１０】 前記文字列検索装置において、 前記テキスト検索装置による検索結果に対して、前記キ
    ーワードを各キーワードに対応する異なる文字列、また
    は記号に置換して出力する出力装置を更に備えることを
    特徴とする請求項９記載のパターン検索装置。
JP8005236A 1996-01-16 1996-01-16 パターン検索装置 Pending JPH09198398A (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP8005236A JPH09198398A (ja) 1996-01-16 1996-01-16 パターン検索装置
US08/773,295 US5963942A (en) 1996-01-16 1996-12-24 Pattern search apparatus and method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP8005236A JPH09198398A (ja) 1996-01-16 1996-01-16 パターン検索装置

Publications (1)

Publication Number Publication Date
JPH09198398A true JPH09198398A (ja) 1997-07-31

Family

ID=11605570

Family Applications (1)

Application Number Title Priority Date Filing Date
JP8005236A Pending JPH09198398A (ja) 1996-01-16 1996-01-16 パターン検索装置

Country Status (2)

Country Link
US (1) US5963942A (ja)
JP (1) JPH09198398A (ja)

Families Citing this family (53)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6708166B1 (en) * 1999-05-11 2004-03-16 Norbert Technologies, Llc Method and apparatus for storing data as objects, constructing customized data retrieval and data processing requests, and performing householding queries
US6357002B1 (en) * 1999-08-11 2002-03-12 Oracle Corporation Automated extraction of BIOS identification information for a computer system from any of a plurality of vendors
US6618724B1 (en) * 2000-04-17 2003-09-09 Sun Microsystems, Inc. Human-natural string compare for filesystems
US7737134B2 (en) * 2002-03-13 2010-06-15 The Texas A & M University System Anticancer agents and use
US7200024B2 (en) 2002-08-02 2007-04-03 Micron Technology, Inc. System and method for optically interconnecting memory devices
US7117316B2 (en) 2002-08-05 2006-10-03 Micron Technology, Inc. Memory hub and access method having internal row caching
US7149874B2 (en) 2002-08-16 2006-12-12 Micron Technology, Inc. Memory hub bypass circuit and method
US7836252B2 (en) 2002-08-29 2010-11-16 Micron Technology, Inc. System and method for optimizing interconnections of memory devices in a multichip module
US7102907B2 (en) 2002-09-09 2006-09-05 Micron Technology, Inc. Wavelength division multiplexed memory module, memory system and method
US7949732B1 (en) 2003-05-12 2011-05-24 Sourcefire, Inc. Systems and methods for determining characteristics of a network and enforcing policy
US7617202B2 (en) * 2003-06-16 2009-11-10 Microsoft Corporation Systems and methods that employ a distributional analysis on a query log to improve search results
US7120727B2 (en) * 2003-06-19 2006-10-10 Micron Technology, Inc. Reconfigurable memory module and method
US7260685B2 (en) 2003-06-20 2007-08-21 Micron Technology, Inc. Memory hub and access method having internal prefetch buffers
US7428644B2 (en) 2003-06-20 2008-09-23 Micron Technology, Inc. System and method for selective memory module power management
US7389364B2 (en) 2003-07-22 2008-06-17 Micron Technology, Inc. Apparatus and method for direct memory access in a hub-based memory system
US20050050237A1 (en) * 2003-08-28 2005-03-03 Jeddeloh Joseph M. Memory module and method having on-board data search capabilities and processor-based system using such memory modules
US7194593B2 (en) 2003-09-18 2007-03-20 Micron Technology, Inc. Memory hub with integrated non-volatile memory
US7120743B2 (en) 2003-10-20 2006-10-10 Micron Technology, Inc. Arbitration system and method for memory responses in a hub-based memory system
US7634500B1 (en) * 2003-11-03 2009-12-15 Netlogic Microsystems, Inc. Multiple string searching using content addressable memory
US7539681B2 (en) * 2004-07-26 2009-05-26 Sourcefire, Inc. Methods and systems for multi-pattern searching
US7496962B2 (en) * 2004-07-29 2009-02-24 Sourcefire, Inc. Intrusion detection strategies for hypertext transport protocol
JP2006072744A (ja) * 2004-09-02 2006-03-16 Canon Inc 文書処理装置、その制御方法、プログラム、及び記憶媒体
US7359895B2 (en) * 2004-11-18 2008-04-15 Industrial Technology Research Institute Spiral string matching method
US8316060B1 (en) 2005-01-26 2012-11-20 21st Century Technologies Segment matching search system and method
US20060184523A1 (en) * 2005-02-15 2006-08-17 Microsoft Corporation Search methods and associated systems
US7860844B2 (en) 2005-07-15 2010-12-28 Indxit Systems Inc. System and methods for data indexing and processing
US7353332B2 (en) * 2005-10-11 2008-04-01 Integrated Device Technology, Inc. Switching circuit implementing variable string matching
US8046833B2 (en) * 2005-11-14 2011-10-25 Sourcefire, Inc. Intrusion event correlation with network discovery information
US7733803B2 (en) * 2005-11-14 2010-06-08 Sourcefire, Inc. Systems and methods for modifying network map attributes
CN101346716A (zh) 2005-12-22 2009-01-14 国际商业机器公司 通过利用查找和替换输入的派生的查找和替换功能来编辑文本的方法和系统
GB2437560A (en) * 2006-04-28 2007-10-31 Roke Manor Research Constructing Aho Corasick trees
US7948988B2 (en) * 2006-07-27 2011-05-24 Sourcefire, Inc. Device, system and method for analysis of fragments in a fragment train
US7701945B2 (en) 2006-08-10 2010-04-20 Sourcefire, Inc. Device, system and method for analysis of segments in a transmission control protocol (TCP) session
US7783654B1 (en) 2006-09-19 2010-08-24 Netlogic Microsystems, Inc. Multiple string searching using content addressable memory
US20080196102A1 (en) * 2006-10-06 2008-08-14 Sourcefire, Inc. Device, system and method for use of micro-policies in intrusion detection/prevention
US7860849B1 (en) 2007-01-18 2010-12-28 Netlogic Microsystems, Inc. Optimizing search trees by increasing success size parameter
US8069352B2 (en) 2007-02-28 2011-11-29 Sourcefire, Inc. Device, system and method for timestamp analysis of segments in a transmission control protocol (TCP) session
EP2156290B1 (en) 2007-04-30 2020-03-25 Cisco Technology, Inc. Real-time awareness for a computer network
US8315482B2 (en) * 2007-06-26 2012-11-20 Microsoft Corporation Integrated platform for user input of digital ink
JP5335227B2 (ja) * 2007-12-10 2013-11-06 京セラ株式会社 情報端末装置
US20110225158A1 (en) * 2007-12-12 2011-09-15 21Ct, Inc. Method and System for Abstracting Information for Use in Link Analysis
US20090171936A1 (en) * 2007-12-28 2009-07-02 Sybase, Inc. System, Method, and Computer Program Product for Accelerating Like Conditions
US8474043B2 (en) 2008-04-17 2013-06-25 Sourcefire, Inc. Speed and memory optimization of intrusion detection system (IDS) and intrusion prevention system (IPS) rule processing
WO2010045089A1 (en) 2008-10-08 2010-04-22 Sourcefire, Inc. Target-based smb and dce/rpc processing for an intrusion detection system or intrusion prevention system
CA2789824C (en) 2010-04-16 2018-11-06 Sourcefire, Inc. System and method for near-real time network attack detection, and system and method for unified detection via detection routing
US8433790B2 (en) 2010-06-11 2013-04-30 Sourcefire, Inc. System and method for assigning network blocks to sensors
US8671182B2 (en) 2010-06-22 2014-03-11 Sourcefire, Inc. System and method for resolving operating system or service identity conflicts
US8601034B2 (en) 2011-03-11 2013-12-03 Sourcefire, Inc. System and method for real time data awareness
JP5799706B2 (ja) * 2011-09-26 2015-10-28 富士通株式会社 検索要求処理装置
US11120004B2 (en) * 2014-11-25 2021-09-14 Verizon Media Inc. Method and system for analyzing a user agent string
JP6737117B2 (ja) * 2016-10-07 2020-08-05 富士通株式会社 符号化データ検索プログラム、符号化データ検索方法および符号化データ検索装置
US10528556B1 (en) * 2017-12-31 2020-01-07 Allscripts Software, Llc Database methodology for searching encrypted data records
US11687534B2 (en) * 2021-06-17 2023-06-27 Huawei Technologies Co., Ltd. Method and system for detecting sensitive data

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR940003700B1 (ko) * 1986-02-14 1994-04-27 가부시기가이샤 히다찌세이사꾸쇼 검색방법 및 그 장치
GB8719572D0 (en) * 1987-08-19 1987-09-23 Krebs M S Sigscan text retrieval system
JP3270783B2 (ja) * 1992-09-29 2002-04-02 ゼロックス・コーポレーション 複数の文書検索方法
US5440482A (en) * 1993-03-25 1995-08-08 Taligent, Inc. Forward and reverse Boyer-Moore string searching of multilingual text having a defined collation order
JP2758826B2 (ja) * 1994-03-02 1998-05-28 株式会社リコー 文書検索装置
US5675819A (en) * 1994-06-16 1997-10-07 Xerox Corporation Document information retrieval using global word co-occurrence patterns

Also Published As

Publication number Publication date
US5963942A (en) 1999-10-05

Similar Documents

Publication Publication Date Title
JPH09198398A (ja) パターン検索装置
JP3689455B2 (ja) 情報処理方法及び装置
JP4717049B2 (ja) 文書のページ番号を検出する方法及びシステム
US7236923B1 (en) Acronym extraction system and method of identifying acronyms and extracting corresponding expansions from text
US6978419B1 (en) Method and apparatus for efficient identification of duplicate and near-duplicate documents and text spans using high-discriminability text fragments
JP5037965B2 (ja) 目次判別目的類似度リンク計算の高速化
US20020041713A1 (en) Document search and retrieval apparatus, recording medium and program
US20070244890A1 (en) Determining a known character string equivalent to a query string
JPH06131398A (ja) 複数の文書検索方法
CA2509496A1 (en) Search-enhanced trie-based syntactic pattern recognition of sequences
CN101128822A (zh) 权威性文档识别
JP4114600B2 (ja) 可変長文字列検索装置及び可変長文字列検索方法並びにプログラム
US20030158725A1 (en) Method and apparatus for identifying words with common stems
JP2001175661A (ja) 全文検索装置及び全文検索方法
WO2009113289A1 (ja) 新規事例生成装置、新規事例生成方法及び新規事例生成用プログラム
JP3260428B2 (ja) 情報検索処理装置
JPH07105237A (ja) 索引作成方法およびその装置と文書検索装置
JP3955410B2 (ja) 類似情報照合装置、類似情報照合方法、及び、類似情報照合プログラムを記録した記録媒体
US20080177729A1 (en) Apparatus, method and computer program product for searching document
JP2003242446A (ja) 文字列予測装置及び方法並びに当該方法を具現化するコンピュータ実行可能なプログラム
JPH06274701A (ja) 単語照合装置
JP2684138B2 (ja) 日本語形態素解析システム及び見出し切り出し方法
JPH0757059A (ja) 文字認識装置
JP3339879B2 (ja) 文字認識装置
JP2935533B2 (ja) 文字処理方法

Legal Events

Date Code Title Description
A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20010327