図面 (/)

技術 パターン検索方法、パターン検索装置、パターン検索プログラムを記録したコンピュータ読み取り可能な記録媒体、パターン検索システムおよびパターン検索プログラム

出願人 富士通株式会社
発明者 安倍史郎松浦正卓永田真彦原泰久
出願日 2001年1月25日 (20年0ヶ月経過) 出願番号 2001-016576
公開日 2002年8月9日 (18年6ヶ月経過) 公開番号 2002-222194
状態 特許登録済
技術分野 検索装置
主要キーワード タグ式 磁気ファイル 実施確率 BM法 各依頼者 C言語 照合位置 項目タグ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2002年8月9日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

複数のユーザ端末と接続されたフルテキスサーチ検索装置において、各ユーザ端末からの検索要求が連続的に送られてきても、ユーザ端末と検索装置とが1対1である場合と略同じ応答時間で各ユーザ端末に検索結果を返すことのできる検索技術を提供すること。

解決手段

受信した検索条件端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、検索パターン変数テーブルと検索要求式変数テーブルを作成し、検索要求式変数テーブルに従って、検索対象データを格納した検索対象データデータベースを検索して複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、抽出された検索結果を複数の端末装置の各々に送信する。

概要

背景

従来、文字列照合方式を用いた全文検索システムが存在している。文字列照合方式を用いた全文検索システムとは、指定した文字列と検索対象テキストデータを、検索対象のテキストデータの先頭より後方に向かって逐次照合しながら、指定した文字列が検索対象のテキストデータ中に存在するか否かを調べるシステムである。

概要

複数のユーザ端末と接続されたフルテキスサーチ検索装置において、各ユーザ端末からの検索要求が連続的に送られてきても、ユーザ端末と検索装置とが1対1である場合と略同じ応答時間で各ユーザ端末に検索結果を返すことのできる検索技術を提供すること。

受信した検索条件端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、検索パターン変数テーブルと検索要求式変数テーブルを作成し、検索要求式変数テーブルに従って、検索対象データを格納した検索対象データデータベースを検索して複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、抽出された検索結果を複数の端末装置の各々に送信する。

目的

しかしながら、この文字列照合方式を用いた全文検索システムにおいては、システムのCPUがテキストデータスキャンの間中文字の照合動作を行なっており、その間他の処理を行なうことができない。このことは、例えば、ネットワークを介して複数のユーザ端末と検索装置とが接続されたシステムにおいて、複数のユーザ端末に検索サービス時分割に提供することが困難であるということを意味する。

本発明は、上記問題点に鑑みてなされたもので、複数のユーザ端末と接続されたフルテキストサーチの検索装置において、各ユーザ端末からの検索要求が連続的に送られてきても、ユーザ端末と検索装置とが1対1である場合と略同じ応答時間で各ユーザ端末に検索結果を返すことのできる検索方法、検索装置、検索プログラムを記録したコンピュータ読み取り可能な記録媒体検索システムおよび検索プログラムを提供することを目的とする。

また、本発明は、異なるユーザ端末から略同時期に同じ検索要求が来た場合に、無駄な検索処理を行なわずに検索処理を実行する検索方法、検索装置、検索プログラムを記録したコンピュータ読み取り可能な記録媒体、検索システムおよび検索プログラムを提供することを目的とする。

効果

実績

技術文献被引用数
4件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

ネットワークを介して複数の端末装置に接続されたパターン検索装置上で実行されるパターン検索方法において、前記複数の端末装置の各々から送信された、検索対象データ検索するための検索パターン検索式とを含む検索条件を、前記各端末装置を特定するための端末装置情報とともに受信し、前記受信した検索条件と端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、前記検索条件バッファに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと前記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成し、前記検索条件バッファに格納された検索式および端末装置情報と前記作成された検索パターン変数テーブルとに基づいて、前記検索パターンを前記第1の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数との対応、および前記端末装置情報と前記検索式を前記第2の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成し、前記作成された検索要求式変数テーブルに従って、前記検索対象データを格納した検索対象データデータベースを検索して前記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、前記抽出された検索結果を前記複数の端末装置の各々に送信することを特徴とするパターン検索方法。

請求項2

前記検索条件バッファは、実行中の検索処理が終了したことを判断するまで、前記検索条件を格納することを特徴とする請求項1に記載のパターン検索方法。

請求項3

前記検索条件バッファは、予め定めた時間または予め定めた容量に達するまで、前記検索条件を格納することを特徴とする請求項1に記載のパターン検索方法。

請求項4

前記検索は、複数個の検索パターンを同時に検索する手法であることを特徴とする請求項1乃至3の何れか1項に記載のパターン検索方法。

請求項5

前記検索は、Aho−Corasick(AC)法、Expanded−Boyer−Moore(EBM)法、またはShinohara−Arikawa(SA)法の何れかであることを特徴とする請求項1乃至3の何れか1項に記載のパターン検索方法。

請求項6

ネットワークを介して複数の端末装置に接続されたパターン検索装置において、検索対象データを格納する検索対象データ格納手段と、前記複数の端末装置の各々から送信された、前記検索対象データを検索するための検索パターンと検索式とを含む検索条件を、前記各端末装置を特定するための端末装置情報とともに受信する検索条件受信手段と、前記検索条件受信手段によって受信した検索条件と端末装置情報とを格納する検索条件バッファ手段と、先行する検索処理が実行中か否かを判断する検索処理判断手段と、前記検索処理判断手段によって先行する検索処理が実行中でないと判断された場合、前記検索条件バッファ手段に格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと前記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成する検索パターン変数テーブル作成手段と、前記検索条件バッファ手段に格納された検索式および端末装置情報と前記検索パターン変数テーブル作成手段によって作成された検索パターン変数テーブルとに基づいて、前記検索パターンを前記第1の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数との対応、および前記端末装置情報と前記検索式を前記第2の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成する検索要求式変数テーブル作成手段と、前記検索要求式変数テーブル作成手段によって作成された検索要求式変数テーブルに従って、前記検索対象データ格納手段を検索して前記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出する検索手段と、前記検索手段によって抽出された検索結果を前記複数の端末装置の各々に送信する送信手段とを備えたことを特徴とするパターン検索装置。

請求項7

ネットワークを介して複数の端末装置に接続されたパターン検索装置上で実行されるパターン検索プログラムプログラムコードを記録したコンピュータ読み取り可能な記録媒体において、前記複数の端末装置の各々から送信された、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、前記各端末装置を特定するための端末装置情報とともに受信し、前記受信した検索条件と端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、前記検索条件バッファに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと前記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成し、前記検索条件バッファに格納された検索式および端末装置情報と前記作成された検索パターン変数テーブルとに基づいて、前記検索パターンを前記第1の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数との対応、および前記端末装置情報と前記検索式を前記第2の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成し、前記作成された検索要求式変数テーブルに従って、前記検索対象データを格納した検索対象データデータベースを検索して前記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、前記抽出された検索結果を前記複数の端末装置の各々に送信することをコンピュータに実行させるためのパターン検索プログラムを記録したコンピュータ読み取り可能な記録媒体。

請求項8

ネットワークを介して複数の端末装置とパターン検索装置とが接続されたパターン検索システムにおいて、前記複数の端末装置の各々は、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、前記各端末装置を特定するための端末装置情報とともに送信する端末装置側送信手段を備え、前記パターン検索装置は、検索対象データを格納する検索対象データ格納手段と、前記複数の端末装置の各々の前記端末側送信手段から送信された、前記検索対象データを検索するための検索パターンと検索式とを含む検索条件を、前記各端末装置を特定するための端末装置情報とともに受信する検索条件受信手段と、前記検索条件受信手段によって受信した検索条件と端末装置情報とを格納する検索条件バッファ手段と、先行する検索処理が実行中か否かを判断する検索処理判断手段と、前記検索処理判断手段によって先行する検索処理が実行中でないと判断された場合、前記検索条件バッファ手段に格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと前記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成する検索パターン変数テーブル作成手段と、前記検索条件バッファ手段に格納された検索式および端末装置情報と前記検索パターン変数テーブル作成手段によって作成された検索パターン変数テーブルとに基づいて、前記検索パターンを前記第1の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数との対応、および前記端末装置情報と前記検索式を前記第2の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成する検索要求式変数テーブル作成手段と、前記検索要求式変数テーブル作成手段によって作成された検索要求式変数テーブルに従って、前記検索対象データ格納手段を検索して前記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出する検索手段と、前記検索手段によって抽出された検索結果を前記複数の端末装置の各々に送信する送信手段とを備え、前記複数の端末装置の各々は、さらに、前記送信手段によって送信された前記結果を受信する端末装置側受信手段とを備えたことを特徴とするパターン検索システム。

請求項9

ネットワークを介して複数の端末装置に接続されたパターン検索装置上で実行されるパターン検索プログラムにおいて、前記複数の端末装置の各々から送信された、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、前記各端末装置を特定するための端末装置情報とともに受信し、前記受信した検索条件と端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、前記検索条件バッファに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと前記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成し、前記検索条件バッファに格納された検索式および端末装置情報と前記作成された検索パターン変数テーブルとに基づいて、前記検索パターンを前記第1の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数との対応、および前記端末装置情報と前記検索式を前記第2の変数を用いて表した検索要求式と前記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成し、前記作成された検索要求式変数テーブルに従って、前記検索対象データを格納した検索対象データデータベースを検索して前記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、前記抽出された検索結果を前記複数の端末装置の各々に送信することをコンピュータに実行させるためのパターン検索プログラム。

技術分野

0001

本発明は、検索対象から検索パターン検索するパターン検索技術に関し、特に、複数の端末装置からの検索要求が同時に送られてくる場合に、これらの検索要求を纏めて一度に検索し、検索結果を各端末装置振り分け返信することにより、全体の処理時間を飛躍的に短縮するパターン検索技術に関する。

背景技術

0002

従来、文字列照合方式を用いた全文検索システムが存在している。文字列照合方式を用いた全文検索システムとは、指定した文字列と検索対象のテキストデータを、検索対象のテキストデータの先頭より後方に向かって逐次照合しながら、指定した文字列が検索対象のテキストデータ中に存在するか否かを調べるシステムである。

発明が解決しようとする課題

0003

しかしながら、この文字列照合方式を用いた全文検索システムにおいては、システムのCPUがテキストデータスキャンの間中文字の照合動作を行なっており、その間他の処理を行なうことができない。このことは、例えば、ネットワークを介して複数のユーザ端末検索装置とが接続されたシステムにおいて、複数のユーザ端末に検索サービス時分割に提供することが困難であるということを意味する。

0004

すなわち、フルテキスサーチ処理を行なう検索装置に複数個のユーザ端末が接続し、その各々のユーザ端末から頻繁に検索要求が与えられる場合、検索処理を開始した検索装置のCPUは、テキストスキャン中のため他の処理を行なうことができず、CPUの文字照合動作が一通り終了するまで他の要求が待たされるという問題があった。

0005

また、異なるユーザ端末から略同時期に同じ検索要求が来た場合であっても、検索装置は、それぞれの検索要求に対して同じ検索処理を反復して実行するという無駄な処理を行なっているという問題点があった。

0006

本発明は、上記問題点に鑑みてなされたもので、複数のユーザ端末と接続されたフルテキストサーチの検索装置において、各ユーザ端末からの検索要求が連続的に送られてきても、ユーザ端末と検索装置とが1対1である場合と略同じ応答時間で各ユーザ端末に検索結果を返すことのできる検索方法、検索装置、検索プログラムを記録したコンピュータ読み取り可能な記録媒体検索システムおよび検索プログラムを提供することを目的とする。

0007

また、本発明は、異なるユーザ端末から略同時期に同じ検索要求が来た場合に、無駄な検索処理を行なわずに検索処理を実行する検索方法、検索装置、検索プログラムを記録したコンピュータ読み取り可能な記録媒体、検索システムおよび検索プログラムを提供することを目的とする。

課題を解決するための手段

0008

本発明は、上記課題を解決するため、下記のような構成を採用した。すなわち、本発明の一態様によれば、本発明のパターン検索方法、パターン検索装置、パターン検索プログラムを記録したコンピュータ読み取り可能な記録媒体、パターン検索システムおよびパターン検索プログラムは、ネットワークを介して複数の端末装置とパターン検索装置とが接続されたパターン検索システムにおいて、上記複数の端末装置の各々から送信された、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置を特定するための端末装置情報とともに受信し、上記受信した検索条件と端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、上記検索条件バッファに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成し、上記検索条件バッファに格納された検索式および端末装置情報と上記作成された検索パターン変数テーブルとに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成し、上記作成された検索要求式変数テーブルに従って、上記検索対象データを格納した検索対象データデータベースを検索して上記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、上記抽出された検索結果を上記複数の端末装置の各々に送信することを特徴とする。

0009

これにより、短時間に多数の検索要求がある場合であっても、従来用いられていた技術に比べ、格段に高速で処理することができる。また、好適には、上記検索条件バッファが、実行中の検索処理が終了したことを判断するまで、上記検索条件を格納することが望ましい。

0010

また、好適には、上記検索条件バッファが、予め定めた時間または予め定めた容量に達するまで、上記検索条件を格納することが望ましい。また、好適には、上記検索が、複数個の検索パターンを同時に検索する手法であることが望ましい。

0011

また、好適には、上記検索が、Aho−Corasick(AC)法、Expanded−Boyer−Moore(EBM)法、またはShinohara−Arikawa(SA)法の何れかであることが望ましい。

発明を実施するための最良の形態

0012

以下、本発明の実施の形態を、図面を参照しながら詳細に説明する。図1は、本発明を適用したパターン検索システムの機能構成図である。

0013

図1において、パターン検索システム1は、ネットワーク2を介して複数の端末装置3とパターン検索装置4とが接続されている。上記複数の端末装置3の各々は、端末装置側送信手段31と、端末装置側受信手段32とを備える。

0014

上記パターン検索装置4は、検索対象データ格納手段(データベース)41と、検索条件受信手段42と、検索条件バッファ手段43と、検索処理判断手段44と、検索パターン変数テーブル作成手段45と、検索パターン変数テーブル46と、検索要求式変数テーブル作成手段47と、検索要求式変数テーブル48と、検索手段49と、送信手段50とを備える。

0015

端末装置側送信手段31は、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置3を特定するための端末装置情報とともに送信する。

0016

検索対象データ格納手段41は、検索対象データを格納する。検索条件受信手段42は、上記複数の端末装置3の各々の上記端末側送信手段31から送信された、上記検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置3を特定するための端末装置情報とともに受信する。

0017

検索条件バッファ手段43は、上記検索条件受信手段42によって受信した検索条件と端末装置情報とを格納する。例えば、下記検索処理判断手段44により先行する検索処理が終了したと判断するまで、あるいは、予め定めた時間または予め定めた容量に達するまで、上記検索パターンを格納する。

0018

検索処理判断手段44は、先行する検索処理が実行中か否かを判断する。検索パターン変数テーブル作成手段45は、上記検索処理判断手段44によって先行する検索処理が実行中でないと判断された場合、上記検索条件バッファ手段43に格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブル46を作成する。

0019

検索要求式変数テーブル作成手段47は、上記検索条件バッファ手段43に格納された検索式および端末装置情報と上記検索パターン変数テーブル作成手段45によって作成された検索パターン変数テーブル46とに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブル48を作成する。

0020

検索手段49は、上記検索要求式変数テーブル作成手段47によって作成された検索要求式変数テーブル48に従って、上記検索対象データ格納手段41を検索して上記複数の端末装置3の各々から送信された検索条件に合致する検索結果を抽出する。検索の手法としては、複数個の検索パターンを同時に検索する手法を用いることができる。例えば、Aho−Corasick(AC)法、Expanded−Boyer−Moore(EBM)法、またはShinohara−Arikawa(SA)法を用いることができる。これらAC法、EBM法SA法については概略を後述する。

0021

送信手段50は、上記検索手段49によって抽出された検索結果を上記複数の端末装置3の各々に送信する。端末装置側受信手段32は、上記送信手段50によって送信された結果を受信する。

0022

図2は、図1を用いて説明したパターン検索装置4上で実行されるパターン検索処理のフローチャートである。処理が開始されると、まずステップS1において、パターン検索装置4は、検索条件受信手段42によって、複数の端末装置3の各々の端末装置側送信手段31から送信された、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置3を特定するための端末装置情報とともに受信する。

0023

ステップS2において、パターン検索装置4は、検索条件バッファ手段43によって、上記受信した検索条件と端末装置情報とをバッファメモリ上に一時的に格納する。

0024

そして、ステップS3において、パターン検索装置4は、検索処理判断手段44によって、先行する検索処理が実行中か否かを判断する。検索実行中であれば(ステップS3:YES)、ステップS1に戻り、端末装置側送信手段31から送信された、他の検索条件等を受信し、上記バッファメモリ上に一時的に続けて格納(ステップS2)する。この受信(ステップS1)および格納(ステップS2)は、ステップS3で検索処理判断手段44により先行する検索処理が終了したと判断されるまで繰り返す。なお、先行する検索処理が終了したと判断されても、予め定めた時間または予め定めた容量に達するまで、上記検索条件等の受信/格納を繰り返すようにしても良い。

0025

一方、ステップS3で検索実行中でない(先行する検索処理が終了した)と判断される(ステップS3:NO)と、ステップS4において、パターン検索装置4は、検索パターン変数テーブル作成手段によって、上記バッファメモリに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブル46を作成する。

0026

続いて、ステップS5において、パターン検索装置4は、検索要求式変数テーブル作成手段47によって、上記バッファメモリに格納された検索式および端末装置情報と上記作成された検索パターン変数テーブル46とに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブル48を作成する。

0027

そして、ステップS6において、パターン検索装置4は、検索手段49によって、上記作成された検索要求式変数テーブル48に従って、上記検索対象データを格納した検索対象データ格納手段41を検索して上記複数の端末装置3の各々から送信された検索条件に合致する検索結果を、複数個の検索パターンを同時に検索する手法、AC法、EBM法、あるいは、SA法を用いて抽出(検索)する。

0028

最後に、ステップS7において、パターン検索装置4は、送信手段50によって、上記抽出された検索結果を上記複数の端末装置3の各々に送信する。端末装置3側では、各々の端末装置側受信手段32によって、上記検索結果を受信する。

0029

ここで、上述のAC法、EBM法、SA法について概略を説明する。まず、AC法について概略を説明する。なお、AC法に関しては、参考文献1(Aho.A.V. and Corasick.M.J., "Efficient String Matching:An Aid to Bibliographic Search", Comm.ACM, vol.18, no.6, pp.333-340, 1975)に詳述されている。

0030

AC法は、上記参考文献1の著者であるAlfred AhoとMargaret Corasick が考案したパターンマッチングエンジンアルゴリズムであり、検索対象文字列を先頭から後方に向かって1回操作するだけで、複数個の検索文字列の存在を見つけ出すことができる手法である。

0031

ここでは、ACアルゴリズムが採用している、検索対象文字列に存在する検索文字列を見つけ出す基本論理を説明する。一般に情報処理技術では、文字列を、実態上、0又は1の値しかとらないビットと呼ぶ2進数値の羅列により表現している。文字列は、それを1ビットまでに分解すれば2進数値の羅列であるが、4ビット単位に分解すれば16進数値の羅列であり、8ビット単位に分解すれば256進数値の羅列である。

0032

ここでは、文字列を16進数値の羅列として取り扱って、ACアルゴリズムの基本論理を説明する。まず、検索語を「富士(9578 8E6D)」、「瞬索(8F75 8DF5)」、「高速(8D82 91AC)」の3つとする。括弧内は同検索語の16進数表現の例である。

0033

そして、検索対象文字列を「富士の瞬索は超高速(9578 8E6D 82CC 8F75 8DF5 82CD 92B4 8D82 91AC)」とする。ただし、「の(82CC)」、「は(82CD)」、「超(92B4)」である。

0034

パターンマッチングエンジンは、まず、上記検索語に基づいて、図3に示すような状態遷移テーブルを作成する。図3は、「判定1」において、検索対象文字列の中の任意の4ビット(n番目の4ビット)が、「9」であるのか「8」であるのか、あるいは「9」と「8」のいずれでもないのかを判定する。そして、「9」であれば「判定2−1」を行ない、「8」であれば「判定2−2」を行なう。また、それ以外であればn+1番目の4ビットについて「判定1」を行なう。

0035

「判定2−1」においては、n+1番目の4ビットが「5」であるのか、あるいはそれ以外であるのかを判定する。「5」であればn+2番目の4ビットについて「判定3−1」を行ない、それ以外であればn+1番目の4ビットについて「判定1」を行なう。

0036

以下同様に逐次4ビット単位の判定を行なっていく。このような過程において、「判定8−1」が行なわれ、判定した4ビットが「D」であれば、検索語「富士」を検出したことになる。また、「判定8−2」が行なわれ、判定した4ビットが「C」であれば、検索語「高速」を検出したことになり、「判定8−3」が行なわれ、判定した4ビットが「5」であれば、「瞬索」を検出したことになる。

0037

なお、検索語は、「富士」、「高速」、「瞬索」の3つがあるが、「判定1 」では、3回の判定を行なわず、「9」か「8」かの2回の判定だけで済んでいる。しかし、「判定2−2」で、「D」か「F」かの判定を行なっているので、一見、「判定1」での判定回数の削減が意味をなさないように見えるが、「判定1」の結果が「8」でなければ「判定2−2」を実施しなくて済むわけであるから、実態上、判定回数が削減されることになる。各数値出現する確率が等確率であれば、「8」の出現する確率は16分の1となり、「判定2−2」の実施確率も16分の1となる。

0038

以上の説明の範囲では、判定回数の削減効果はあるものの、文字列照合時間が検索語の数に影響されないとは言えない。特に、検索語の数が少ない場合は、判定回数の削減効果は小さい。

0039

しかし、各判定処理を以下の方法により効率化することができる。各判定は、図4に示すような判定テーブルを使用して作成する。図4は、「判定1」の判定テーブルである。図4は、判定対象4ビットの値が、「9」であれば、次の4ビットを「判定2−1」の判定テーブルに従って判定を行ない、「8」であれば、次の4ビットを「判定2−1」の判定テーブルに従って判定を行ない、それ以外であれば、次の4ビットを「判定1」の判定テーブルに従って判定を行なうことを指示している。

0040

この判定テーブルでの判定は次のように行なう。前述した検索対象文字列を例にとれば、最初の数値は「9」であるので、まず、判定テーブル中の判定対象4ビットの値が「9」の欄を直接見に行き、「判定2−1」の判定テーブルに進む。つまり、判定テーブルの内容がどのようになっていても、常に、その一つの欄を見るだけで済む。従って、判定テーブルでの判定処理時間は検索語の数に影響されないことになる。

0041

以降、判定テーブルに従って検索対象文字列を走査すれば、一回の走査で、全検索対象文字列と全検索語の照合が完了することになる。なお、最後の判定テーブルでヒットした場合の行き先テーブルには、ヒットした文字列やその位置情報などの照合結果情報を格納しておき、そのテーブルに遷移した時点で、照合結果情報の取り出しを行なう。

0042

上述の説明では、文字を4ビット単位に区切って、判定テーブルを作成したが、文字を8ビット単位に区切れば、1回の判定処理で、次の判定テーブルに遷移する確率は256分の1となり、更に、処理時間は削減される。

0043

なお、状態遷移テーブルを作成する時間が、検索処理に加算されるが、この時間も一般的には検索処理時間に比較して十分に短いので、全体の処理時間には殆ど影響しない。

0044

次に、EBM法について概略を説明する。EBM法は、BM(Boyer−Moore)法を複数個のパターンが扱えるように拡張したアルゴリズムである。EBM法もAC法と同じく、テキストを1回走査するだけで複数個のパターンすべてを検出することができるが、AC法に比べ作業領域が少なくて済み、比較的効率が良い。

0045

まず、BM法について概略を説明する。BM法では、検索対象文字列とパターンをパターンの末尾から前方に向かって照合する。その照合過程においてアンマッチが発生した場合、検索対象文字列の照合を行う位置を後方にずらして、再度、パターンの末尾より照合を行う。この処理を、照合位置が検索対象文字列の末尾になるまで繰り返し行う。アンマッチが発生した場合に、照合を行う位置を何文字分後方にずらせば良いかは、アンマッチが発生した時点の検索対象文字列の文字により、一意に決まり、与えられたパターンを元に、文字と後方にずらす文字数の対応のテーブルを作成することができる。

0046

たとえば、「ABCD」というパターンが与えられた場合、そのテーブルは、図5(a)中のdel_abcdのようなdelta1テーブル(負でない整数値一次元配列)をとなる。上段は、照合過程でアンマッチとなった時点の検索対象文字列中の文字であり、下段は、その時、照合位置を何文字後方にずらすかを示す値である。パターンの末尾の文字の下段の数値は0とする。パターン中に存在しない文字の下段の値はパターンの文字数となる。照合時は、まず、パターンの末尾文字と照合すべき位置にある検索対象文字列中の文字を取り出し、delta1テーブルのその文字に対応する文字の下段の数値を調べ、その数値が0であれば、パターンの末尾の文字と一致していることになるので、前方に向かって照合を行い、下段の数値が1以上であれば、その数値分だけ検索対象文字列とパターンの照合位置を検索対象文字列の後方にずらして、引き続きパターンの末尾文字の照合を行う。この処理を、照合位置が検索対象文字列の末尾になるまで繰り返せば、照合が完了する。

0047

EBM法では、このテーブルを次のように利用する。いま、「ABCD」と「BCDE」という2つのパターンが与えられたとすると、まず、それぞれのパターンごとに図5(a)中のdel_abcdとdel_bcdeのようなdelta1テーブル(負でない整数値の1次元配列)を作成する。次にこれらのテーブルを合成して(同じ文字に対応する値の小さい方を値とする)図5(a)中のdel_comのようなdelta1テーブルを作成する。なお、最小値が0の場合は、0の代わりに大きな値L(large:検索対象文字列の文字数+パターンの文字数+1)を入れて置く。Lは照合処理終わりを判定するのに使用される。

0048

また、パターンの末尾の文字が見つかったとき(delta1の値がlargeのとき)、それがどのパターンの末尾の文字に対応するのかをわかるようにしておくために、図5(b)のようなテーブルを作成しておく。図5(b)中の数字(1、2、3)は、どのパターン化を示す番号である。そして、図5(a)のdel_comと図5(b)を用いて、BM方と同様な照合を行うことにより、パターンの数が複数あっても、検索対象文字列の前方から後方に向かった一回の照合処理で、検索処理を終えることができる。

0049

最後に、SA法について概略を説明する。SA法は、日本語テキストに対して文字列のパターンマッチングを行なう場合のアルゴリズムである。

0050

日本語テキストには、2バイト文字と1バイト文字とが混在することがある。2バイト文字と1バイト文字とが混在すると、注目している文字コードが1バイト文字であるのか2バイト文字であるのかを容易に認識することはできない。つまり、文字列の先頭から文字の切替わりを認識しながら処理をしていかないと、図6に示すような「ずれ読み」と呼ばれる現象が発生してしまう。

0051

先に説明したAC法およびEBM法は、複数のパターンのマッチングを効率的に行う方法は示しているが、この「ずれ読み」の問題を効率的に解決する手段を示していない。日本語テキストにおいては、この「ずれ読み」の問題を解決しないと、いずれの方法も効果的な適用ができない。SA法は、AC法をベースにしながら、この「ずれ読み」の問題を解決する手段を、以下のとおり示している。

0052

この「ずれ読み」の問題を解決するための方法の1つとして、1バイト文字と2バイト文字との境界を常に認識しながらパターンマッチングを行ない、「ずれ読み」が起こらないようにする方法がある。そのためには、日本語テキスト上でコード系シフトJIS)の特性を反映したオートマトンを作成し、これを用いてパターンマッチングを行なう。

0053

図7は、日本語テキスト上でコード系の特性を反映したオートマトンの例を示す図である。図7に示されたオートマトンは、{AB,苑,庭}のパターン集合を対象としている。図中の状態7は,中間状態を示しており,状態3と状態5の破線がこの中間状態7に向かっている。状態3または状態5から遷移ができなくなった場合、まず中間状態7へ遷移を行なう。中間状態7では、「ずれ読み」の調整を行った後、状態0に遷移する。この方法により、マッチングの過程において、効率的に「ずれ読み」の調整を行うことができる。

0054

例えば、テキストとして「外苑初霜」が与えられると、図8に示す状態遷移が発生し、パターンを正しく検出することができる。なお、AC法、EBM法については、参考文献2(「5種類のパターン・マッチング手法をC言語関数で実現する 第1回英文テキストの場合」, NIKKEI BYTE/AUGUST 1987)に、SA法については、参考文献3(「5種類のパターン・マッチング手法をC言語の関数で実現する 第2回日本語テキストの場合」, NIKKEI BYTE/SEPTEMBER1987)に詳述されている。

0055

図9は、本発明の文字列照合方式全文検索システム(以下、本システムという。)の概念モデルを示す図である。本システムは、複数の端末から非定期的に発生する検索要求に対して、検索対称テキストデータの中からそれぞれの検索要求を満足する情報を抽出して、その情報を検索結果としてそれぞれの端末に返信する装置である。検索対象テキストデータの内容の例を図10に示す。検索対象テキストデータの全体をここではファイルと言う。ファイルは複数のレコードから構成され、各レコードは複数の項目から構成される。項目の中身は文字列であり、レコードはレコード区切符号等により識別することができる。レコード内の項目は項目区切符号により区切られており、項目識別符号(以下、項目タグという。)により一意に特定することができる。

0056

検索要求は時系列で頻繁に本システムへ訪れる。各検索要求は、図11に示すように、項目タグと検索語を対とした情報の羅列と、検索条件式を持つ。これらの情報は、検索対象レコードの中の項目タグで指定する項目の中に指定検索語が存在し、かつ、検索条件式を満足するレコードを捜して欲しい、と言うことを意味する。

0057

そして、本システムは検索要求を満足するレコードをファイルの中から見つけ出し、そのレコードの一部または全体を検索要求元に返す。図9に示したような文字列照合方式全文検索システムは、従来は、端末から検索要求があった場合、その都度、検索処理を行なって、検索結果を端末に返していたが、本発明では、各端末からの検索要求を纏めて一度に検索処理を行ない、検索処理後に、検索結果をそれぞれの端末に振り分けて返信することにより、全体の処理時間を飛躍的に短縮している。

0058

検索要求は時系列で頻繁に本システムに訪れるが、各検索要求を個別に処理せず、複数の検索要求を纏めて一括して処理する。その一括処理する検索要求の集合を、ここでは検索要求群という。その概念図12に示す。

0059

検索要求群は以下のようにして構成される。本システムがある検索要求群の処理を行なっている最中に訪れた検索要求を全て待たせておき、処理中の検索要求群の処理が完了した時点で待っている検索要求全てを次の検索要求群とする。また、待っている検索要求が存在しない場合は、次に訪れる最初の検索要求1つだけで検索要求群を構成する。また、最初の検索要求群に含まれる検索要求の数は1つである。

0060

図13は、本発明の全体構成図の例を示す図である。本発明は、情報処理装置磁気ファイル装置とプログラム記憶装置とで構成される。プログラム記憶装置の構成要素は、制御プログラム受付プログラム依頼者スレッド、検索要求テーブル、検索結果テーブル及び検索プログラムである。

0061

図14は、制御プログラムの処理の流れを示すフローチャートである。制御プログラムは、諸テーブルの初期化等のシステムの初期化処理を行なった(ステップS141)後、検索プログラムの起動(ステップS142)と受付プログラムの起動を(ステップS143)順に行なう。

0062

図15は、受付プログラムの処理の流れを示すフローチャートである。受付プログラムは、常に端末からの検索要求待ちの状態(ステップS151)にあり、端末から検索要求が合った都度、依頼者スレッドを起動する(ステップS152)。依頼者スレッドは検索要求の数だけ作成される。

0063

図16は、依頼者スレッドの処理の流れを示すフローチャートである。依頼者スレッドは、起動された後、検索要求テーブルに検索要求の書込を行なう(ステップS161)。このステップS161の処理の概念図を図17に示す。

0064

その後、依頼者スレッドは、検索処理の完了待ちの状態となる(ステップS162)。検索処理終了後、検索結果が検索結果テーブルに書き込まれ、また、各依頼者スレッドへの回答が、検索結果テーブルの何処に書き込まれているかを示す最終式変数IDが、共通領域に書き込まれる。依頼者スレッドは、待ちの状態が溶けた後、共通領域内の自分の領域の最終式変数IDを見て(ステップS163)、検索結果テーブルより、ヒットレコードの内容を取り出して(ステップS164)、回答を編集して(ステップS165)端末に返信する(ステップS166)。このステップS162乃至ステップS165の処理の概念を図18に示す。

0065

図19は、検索プログラムの全体の構造を示す図である。検索プログラムは、前処理、検索処理及び後処理等から構成される。図20は、前処理の処理の流れを示すフローチャートである。

0066

前処理は、最初に新規の依頼者スレッドの検索要求テーブルへの書き込みを禁止する(ステップS201)。続いて、検索要求テーブルを元にキーワード変数テーブルと検索要求式変数テーブルを作成し(ステップS202、S203)、共通領域に各依頼者スレッドの最終式変数IDを書き込む(ステップS204)。

0067

その後、検索要求テーブルの全ての内容を削除(ステップS205)した後、新規の依頼者スレッドの検索要求テーブルへの書込禁止解除する(ステップS206)。

0068

図21は、キーワード変数テーブル作成処理の概念を示す図である。キーワード変数テーブルは、項目タグおよび検索語(両者を総称してキーワードという。)が複数並んだテーブル情報である。キーワードにはキーワード変数を付与し、更に、キーワードが検索対象レコード中に存在したかどうかを示すヒットフラグ欄を設ける。ヒットフラグの初期値は0であり、ヒットした場合は1にする。ヒットフラグは検索処理の過程において使用される。

0069

キーワード変数テーブルへ記録する項目タグ及び検索語は、検索要求テーブル中に存在する全ての項目タグ及び検索語である。但し、同じ内容の項目タグ及び検索語は重複して記録しない。

0070

図22は、検索要求式変数テーブル作成の概念を示す図である。検索要求式変数テーブルは、検索論理式が複数並んだテーブル情報である。各検索論理式には、一意に特定できる符号(以下、式変数という。)を付与する。検索論理式テーブルには、検索要求テーブル中の、項目タグと検索語の全ての対を、それぞれ、タグ変数と検索語変数(具体的には付与されたキーワード変数)を論理積(and)演算子で結んだ論理式として記録する。この論理式に付けた式変数をタグ式変数と呼ぶ。同一内容のタグ式変数は重複して登録しない。

0071

また、検索要求テーブル内の全ての検索条件式を、タグ式変数を論理演算子で結んだ論理式に置き換えて、検索要求式変数テーブルに記録する。この論理式に付けた式変数を検索要求式変数と呼ぶ。同一内容の検索論理式を持つ検索要求式変数は、重複して検索論理式テーブルに登録しない。

0072

検索要求式変数テーブルには、各式変数に対応して、最終式変数ID欄とヒットフラグ欄を設ける。検索要求式変数の最終式変数ID欄には、1から順を追って番号を付与する。タグ変数の最終式変数ID欄には、0を記録する。ヒットフラグ欄は検索処理の過程において使用する。ヒットフラグ欄の初期値は0である。

0073

この検索要求式変換テーブルの作成処理の後、共通領域内の各依頼者スレッドの対応領域に、その依頼者スレッドの検索条件に対応する検索要求式変数の最終式変数IDの書き込みを行なう。

0074

図23は、検索処理の処理の流れを示すフローチャートである。検索処理は、キーワード変数テーブル及び検索要求式変数テーブルを元にして、検索対象テキストデータから各依頼者スレッドからの検索要求を満足するレコードを見つけ出し、そのレコードの内容を、最終式変数ID別に、検索結果テーブルに書き込む処理である。

0075

この検索処理は、大きく分けて、ファイル中から指定文字列を検出するパターンマッチング処理(ステップS231)と、指定文字列を検出した後、検出された文字列に従って行なう処理(ステップS232乃至S238)に分けられる。

0076

パターンマッチング処理では、キーワード変数テーブル中の全キーワードにレコード区切り符号項目区切り符号を加えて、検索対象テキストデータの先頭より全文字照合を行なう。本発明で使用するパターンマッチング処理の技術としては、処理時間がキーワードの数に依存しないACアルゴリズム等(上述のAC法、EMB法、SA法等)の技術を用いる。

0077

まず、パターンマッチング処理で、キーワードがヒット( 検出) した場合は、キーワード変数テーブル中のヒットしたキーワードのヒットフラグを真(1)にする(ステップS232)。

0078

項目区切り符号がヒットした場合は、検索要求式変数評価を行なう(ステップS233)。検索要求式変数評価とは、検索要求式変数テーブルの全ての式変数について論理演算を行ない、その結果が真(1)となるものについて、ヒットフラグの値を真(1)にする処理である。

0079

図10の検索対象テキストデータを検索した場合、2番目の項目区切り符号を検出した時点では、キーワード変数テーブル及び検索要求式変数テーブルの状態は図24のとおりとなる。

0080

そして、検索要求式変数評価の後、キーワード変数テーブルの全ヒットフラグを(0)にする(ステップS234)。レコード区切り符号がヒットした場合は、最終式変数IDが真(1以上)で、かつヒットフラグが真(1)になっている(ステップS235:YES)検索要求式変数の最終式変数IDを取り出し、検索結果テーブルのその最終式変数IDの欄にヒットしたレコードの内容を書き込む(ステップS236)。その後、ファイルの終了まで(ステップS237:YES)、キーワード変数テーブルと検索要求式変数テーブルの全ヒットフラグを偽(0)にして(ステップS238)、ステップS231に戻り、パターンマッチング処理を続行する。

0081

図10の検索対象テキストデータを検索した場合、1件目のレコードの最後の項目区切り符号を検出した後の検索式変数評価後のキーワード変数テーブル及び検索要求式変数テーブルの状態は図25のとおりとなり、1件目レコードの最後にあるレコード区切り符号を検出した後の処理では、検索結果テーブルの内容は図26のとおりとなる。

0082

検索処理完了後、後処理を行なう。後処理は、各依頼者スレッドの待ちの状態を解除する。以上で本発明の第1の実施の形態の説明を終わる。

0083

次に、本発明の第2の実施の形態について説明する。第1の実施の形態では、レコードが複数の項目で構成されているデータの検索について説明したが、第2の実施の形態では、検索対象データのレコードが項目に分割されていない場合について説明する。

0084

図27は、第2の実施の形態の検索対象テキストデータの内容を示す図である。第2の実施の形態の制御プログラム、受付プログラム、依頼者スレッド及び検索プログラムの動きは、第1の実施の形態の場合と同じであるが、キーワード変数テーブル及び検索要求式変数テーブルの内容は、第1の実施の形態の場合と第2の実施の形態の場合とでは異なる。

0085

レコードが項目に分割されていない場合、検索要求では項目タグが使用されない。従って、第1の実施の形態の図21に対応する検索要求テーブル及びキーワード変数テーブルは、図28のとおりとなる。また、第1の実施の形態の図22に対応する検索要求式変数テーブルは、タグ変数が存在しなくなるため、図29のとおりとなる。

0086

検索処理も、図23と同じに動作するが、1件目のレコードの最後の項目区切り符号を検出した後の検索要求式変数評価の後の、キーワード変数テーブル及び検索要求式変数テーブルの内容は図30のとおりとなる。

0087

また、1件目のレコードの最後のレコード区切り符号を検出した後の処理が完了した後の検索結果テーブルは図31のとおりとなる。以上、本発明の実施の形態を、図面を参照しながら説明してきたが、本発明は、以下のような特徴を有している。
(1)端末から検索要求があった時点で、その端末に対応してその端末との会話権を持つ依頼者スレッドを起動し、それぞれの依頼者スレッドが、1つの検索要求テーブルに、自分が会話権を持つ端末からの検索要求を書き込む。
(2)検索プログラムの処理が終了した時点で、その時までに検索要求テーブルに書き込まれていた検索要求全体を1つの処理単位として検索処理を行なう。
(3)検索要求テーブルに存在する全ての項目タグ及び検索語を、検索要求単位に関係なく、まとめてキーワード変数テーブルに書き込む。その時、同じ項目タグ、同じ検索語が存在したら、キーワード変数テーブルに重複書込を行なわない。
(4)検索要求テーブルに存在する、全ての項目タグと検索語の対の論理積(and)条件と、全ての検索条件式を、検索論理式として、検索要求単位に関係なく、纏めて検索要求式変数テーブルに書き込む。その時、同じ内容の検索論理式は重複して書き込まない。
(5)検索要求式変数テーブル中の、検索要求テーブル中の検索条件式に対応する検索論理式の最終式変数ID欄に、順に番号を記入する。さらに、その付与した番号を、検索論理式の元となる検索条件式を持つ検索要求を検索要求テーブルに書き込んだ依頼者スレッドに対応付けされた共通領域に書き込む。
(6)キーワード変数テーブル中の全キーワードと検索対象テキストデータのパターンマッチング処理を行なっている過程において、検索要求式変数テーブル中の最終式変数ID欄に付番している検索論理式が真(1)となる全てのレコードの内容を最終式変数IDと対応させて検索結果テーブルに書き込む。
(7)依頼者スレッドが、共通領域に書き込まれた最終式変数IDを見て、その最終式変数IDに対応するレコードの内容を、検索結果テーブルから取り出して、自分が会話権を持っている端末に返信する。

0088

上述のように、本発明の実施の形態を、図面を参照しながら説明してきたが、本発明が適用されるパターン検索装置は、その機能が実行されるのであれば、上述の実施の形態に限定されることなく、単体の装置であっても、複数の装置からなるシステムあるいは統合装置であっても、LAN、WAN等のネットワークを介して処理が行なわれるシステムであってもよいことは言うまでもない。

0089

また、バスに接続されたCPU、ROMやRAMのメモリ入力装置出力装置外部記録装置媒体駆動装置可搬記録媒体ネットワーク接続装置で構成されるシステムでも実現できる。すなわち、前述してきた実施の形態のシステムを実現するソフトェアのプログラムコードを記録したROMやRAMのメモリ、外部記録装置、可搬記録媒体を、パターン検索装置に供給し、そのパターン検索装置のコンピュータがプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。

0090

この場合、記録媒体から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記録した可搬記録媒体等は本発明を構成することになる。

0091

プログラムコードを供給するための可搬記録媒体としては、例えば、フロッピー(登録商標ディスクハードディスク光ディスク光磁気ディスクCD−ROM、CD−R、DVD−ROM、DVD−RAM、磁気テープ不揮発性メモリーカード、ROMカード電子メールやパソコン通信等のネットワーク接続装置(言い換えれば、通信回線)を介して記録した種々の記録媒体などを用いることができる。

0092

また、図32に示すように、コンピュータ320がメモリ321上に読み出したプログラムコードを実行することによって、前述した実施の形態の機能が実現される他、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているOSなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現される。

0093

さらに、可搬型記録媒体322から読み出されたプログラムコードが、コンピュータ320に挿入された機能拡張ボードやコンピュータ320に接続された機能拡張ユニットに備わるメモリ321に書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるCPUなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現され得る。

0094

すなわち、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成または形状を取ることができる。ここで、上述した実施の形態の特徴を列挙すると、以下の通りである。

0095

(付記1)ネットワークを介して複数の端末装置に接続されたパターン検索装置上で実行されるパターン検索方法において、上記複数の端末装置の各々から送信された、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置を特定するための端末装置情報とともに受信し、上記受信した検索条件と端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、上記検索条件バッファに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成し、上記検索条件バッファに格納された検索式および端末装置情報と上記作成された検索パターン変数テーブルとに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成し、上記作成された検索要求式変数テーブルに従って、上記検索対象データを格納した検索対象データデータベースを検索して上記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、上記抽出された検索結果を上記複数の端末装置の各々に送信することを特徴とするパターン検索方法。
(付記2) 上記検索条件バッファは、実行中の検索処理が終了したことを判断するまで、上記検索条件を格納することを特徴とする付記1に記載のパターン検索方法。
(付記3) 上記検索条件バッファは、予め定めた時間または予め定めた容量に達するまで、上記検索条件を格納することを特徴とする付記1に記載のパターン検索方法。
(付記4) 上記検索は、複数個の検索パターンを同時に検索する手法であることを特徴とする付記1乃至3の何れか1項に記載のパターン検索方法。
(付記5) 上記検索は、Aho−Corasick(AC)法、Expanded−Boyer−Moore(EBM)法、またはShinohara−Arikawa(SA)法の何れかであることを特徴とする付記1乃至3の何れか1項に記載のパターン検索方法。
(付記6) ネットワークを介して複数の端末装置に接続されたパターン検索装置において、検索対象データを格納する検索対象データ格納手段と、上記複数の端末装置の各々から送信された、上記検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置を特定するための端末装置情報とともに受信する検索条件受信手段と、上記検索条件受信手段によって受信した検索条件と端末装置情報とを格納する検索条件バッファ手段と、先行する検索処理が実行中か否かを判断する検索処理判断手段と、上記検索処理判断手段によって先行する検索処理が実行中でないと判断された場合、上記検索条件バッファ手段に格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成する検索パターン変数テーブル作成手段と、上記検索条件バッファ手段に格納された検索式および端末装置情報と上記検索パターン変数テーブル作成手段によって作成された検索パターン変数テーブルとに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成する検索要求式変数テーブル作成手段と、上記検索要求式変数テーブル作成手段によって作成された検索要求式変数テーブルに従って、上記検索対象データ格納手段を検索して上記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出する検索手段と、上記検索手段によって抽出された検索結果を上記複数の端末装置の各々に送信する送信手段とを備えたことを特徴とするパターン検索装置。
(付記7) 上記検索条件バッファ手段は、上記検索処理判断手段により上記実行中の検索処理が終了したことを判断するまで、上記検索条件を格納することを特徴とする付記6に記載のパターン検索装置。
(付記8) 上記検索条件バッファ手段は、予め定めた時間または予め定めた容量に達するまで、上記検索条件を格納することを特徴とする付記6に記載のパターン検索装置。
(付記9) 上記検索手段は、複数個の検索パターンを同時に検索する手法であることを特徴とする付記6乃至8の何れか1項に記載のパターン検索装置。
(付記10) 上記検索手段は、Aho−Corasick(AC)法、Expanded−Boyer−Moore(EBM)法、またはShinohara−Arikawa(SA)法の何れかであることを特徴とする付記6乃至8の何れか1項に記載のパターン検索装置。
(付記11) ネットワークを介して複数の端末装置に接続されたパターン検索装置上で実行されるパターン検索プログラムのプログラムコードを記録したコンピュータ読み取り可能な記録媒体において、上記複数の端末装置の各々から送信された、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置を特定するための端末装置情報とともに受信し、上記受信した検索条件と端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、上記検索条件バッファに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成し、上記検索条件バッファに格納された検索式および端末装置情報と上記作成された検索パターン変数テーブルとに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成し、上記作成された検索要求式変数テーブルに従って、上記検索対象データを格納した検索対象データデータベースを検索して上記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、上記抽出された検索結果を上記複数の端末装置の各々に送信することをコンピュータに実行させるためのパターン検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
(付記12) 上記検索条件バッファは、実行中の検索処理が終了したことを判断するまで、上記検索条件を格納するためのパターン検索プログラムを記録した付記11に記載のコンピュータ読み取り可能な記録媒体。
(付記13) 上記検索条件バッファは、予め定めた時間または予め定めた容量に達するまで、上記検索条件を格納するためのパターン検索プログラムを記録した付記11に記載のコンピュータ読み取り可能な記録媒体。
(付記14) 上記検索は、複数個の検索パターンを同時に検索する手法であるパターン検索プログラムを記録した付記11乃至13の何れか1項に記載のコンピュータ読み取り可能な記録媒体。
(付記15) 上記検索は、Aho−Corasick(AC)法、Expanded−Boyer−Moore(EBM)法、またはShinohara−Arikawa(SA)法の何れかであるパターン検索プログラムを記録した付記11乃至13の何れか1項に記載のコンピュータ読み取り可能な記録媒体。
(付記16) ネットワークを介して複数の端末装置とパターン検索装置とが接続されたパターン検索システムにおいて、上記複数の端末装置の各々は、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置を特定するための端末装置情報とともに送信する端末装置側送信手段を備え、上記パターン検索装置は、検索対象データを格納する検索対象データ格納手段と、上記複数の端末装置の各々の上記端末側送信手段から送信された、上記検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置を特定するための端末装置情報とともに受信する検索条件受信手段と、上記検索条件受信手段によって受信した検索条件と端末装置情報とを格納する検索条件バッファ手段と、先行する検索処理が実行中か否かを判断する検索処理判断手段と、上記検索処理判断手段によって先行する検索処理が実行中でないと判断された場合、上記検索条件バッファ手段に格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成する検索パターン変数テーブル作成手段と、上記検索条件バッファ手段に格納された検索式および端末装置情報と上記検索パターン変数テーブル作成手段によって作成された検索パターン変数テーブルとに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成する検索要求式変数テーブル作成手段と、上記検索要求式変数テーブル作成手段によって作成された検索要求式変数テーブルに従って、上記検索対象データ格納手段を検索して上記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出する検索手段と、上記検索手段によって抽出された検索結果を上記複数の端末装置の各々に送信する送信手段とを備え、上記複数の端末装置の各々は、さらに、上記送信手段によって送信された上記結果を受信する端末装置側受信手段とを備えたことを特徴とするパターン検索システム。
(付記17) ネットワークを介して複数の端末装置に接続されたパターン検索装置上で実行されるパターン検索プログラムにおいて、上記複数の端末装置の各々から送信された、検索対象データを検索するための検索パターンと検索式とを含む検索条件を、上記各端末装置を特定するための端末装置情報とともに受信し、上記受信した検索条件と端末装置情報とを検索条件バッファに格納し、先行する検索処理が実行中か否かを判断し、先行する検索処理が実行中でないと判断された場合、上記検索条件バッファに格納された検索パターンのうち、2以上の同一の検索パターンがあれば1の検索パターン以外の検索パターンを省き、検索パターンと上記検索パターンを値とする第1の変数とを対応付けた検索パターン変数テーブルを作成し、上記検索条件バッファに格納された検索式および端末装置情報と上記作成された検索パターン変数テーブルとに基づいて、上記検索パターンを上記第1の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数との対応、および上記端末装置情報と上記検索式を上記第2の変数を用いて表した検索要求式と上記検索要求式を値とする第2の変数とを対応付けた検索要求式変数テーブルを作成し、上記作成された検索要求式変数テーブルに従って、上記検索対象データを格納した検索対象データデータベースを検索して上記複数の端末装置の各々から送信された検索条件に合致する検索結果を抽出し、上記抽出された検索結果を上記複数の端末装置の各々に送信することをコンピュータに実行させるためのパターン検索プログラム。
(付記18) 上記検索条件バッファは、実行中の検索処理が終了したことを判断するまで、上記検索条件を格納するためのパターン検索プログラムを記録した付記17に記載のパターン検索プログラム。
(付記19) 上記検索条件バッファは、予め定めた時間または予め定めた容量に達するまで、上記検索条件を格納するためのパターン検索プログラムを記録した付記17に記載のパターン検索プログラム。
(付記20) 上記検索は、複数個の検索パターンを同時に検索する手法であるパターン検索プログラムを記録した付記17乃至19の何れか1項に記載のパターン検索プログラム。
(付記21) 上記検索は、Aho−Corasick(AC)法、Expanded−Boyer−Moore(EBM)法、またはShinohara−Arikawa(SA)法の何れかであるパターン検索プログラムを記録した付記17乃至19の何れか1項に記載のパターン検索プログラム。

発明の効果

0096

以上説明してきたように、本発明によれば、文字列照合方式を用いた全文検索システムにおいて、短時間に多数の検索要求がある場合に、従来用いられていた技術に比べ、格段に高速で処理することができる。

0097

また、本発明によれば、索引ファイルを必要とする全文検索方式に比較し、ソフトウェアを格段に軽量化でき、また、索引ファイルの保守が不要であるため運用性に優れている。

0098

すなわち、本発明によれば、文字列照合方式を用いた全文検索システムで、かつ、短時間に多数の検索要求が時系列に発生する場合において、1件の検索要求を単独に処理した場合の時間に検索要求の数を掛けた時間以下の時間で、全ての検索要求を処理することができる。例えば、1件の検索要求を単独に処理するのに1秒かかる検索エンジンを使用して、100件の検索要求があってもそれを3秒以内に処理を終わらせることも可能である。

図面の簡単な説明

0099

図1本発明を適用したパターン検索システムの機能構成図である。
図2図1を用いて説明したパターン検索装置4上で実行されるパターン検索処理のフローチャートである。
図3AC法における状態遷移テーブルを説明するための図である。
図4図3の判定1の判定テーブルを示す図である。
図5EBM法に用いるdelta1テーブル(a)とパターンの右端を判定するためのテーブル(b)を示す図である。
図6日本語テキストの「ずれ読み」の例を示す図である。
図7日本語テキスト上でコード系の特性を反映したオートマトンの例を示す図である。
図8状態遷移によるパターンの検出を示す図である。
図9本発明の文字列照合方式全文検索システムの概念モデルを示す図である。
図10検索対象テキストデータの内容の例を示す図である。
図11検索要求の例を示す図である。
図12検索要求群の概念を示す図である。
図13本発明の全体構成図の例を示す図である。
図14制御プログラムの処理の流れを示すフローチャートである。
図15受付プログラムの処理の流れを示すフローチャートである。
図16依頼者スレッドの処理の流れを示すフローチャートである。
図17検索要求テーブルに検索要求の書き込みを行なう処理の概念を示す図である。
図18検索結果の端末への返信処理の概念を示す図である。
図19検索プログラムの全体の構造を示す図である。
図20前処理の処理の流れを示すフローチャートである。
図21第1の実施の形態におけるキーワード変数テーブル作成処理の概念を示す図である。
図22第1の実施の形態における検索要求式変数テーブル作成の概念を示す図である。
図23検索処理の処理の流れを示すフローチャートである。
図24第1の実施の形態におけるキーワード変数テーブル(a)及び検索要求式変数テーブル(b)の例(その1)を示す図である。
図25第1の実施の形態におけるキーワード変数テーブル(a)及び検索要求式変数テーブル(b)の例(その2)を示す図である。
図26第1の実施の形態における検索結果テーブルの例を示す図である。
図27第2の実施の形態の検索対象テキストデータの内容を示す図である。
図28第2の実施の形態におけるキーワード変数テーブル作成処理の概念を示す図である。
図29第2の実施の形態における検索要求式変数テーブル作成の概念を示す図である。
図30第2の実施の形態におけるキーワード変数テーブル(a)及び検索要求式変数テーブル(b)の例を示す図である。
図31第2の実施の形態における検索結果テーブルの例を示す図である。
図32本発明におけるプログラムのコンピュータへのローディングを説明する図である。

--

0100

1パターン検索システム
2ネットワーク
3端末装置
4 パターン検索装置
31 端末装置側送信手段
32 端末装置側受信装置
41検索対象データ格納手段(データベース)
42検索条件受信手段
43 検索条件バッファ手段
44検索処理判断手段
45検索パターン変数テーブル作成手段
46 検索パターン変数テーブル
47検索要求式変数テーブル作成手段
48 検索要求式変数テーブル
49検索手段
50 送信手段
320コンピュータ
321メモリ
322 可搬型記録媒体

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ