JPH09190448A - 文字列検索装置およびその検索方法 - Google Patents

Abstract

(57)【要約】 【課題】 辞書や構文解析を要せずにインデックスを自
動作成でき、任意の文字列を簡便に検索することができ
る文字列検索装置およびその方法を提供する。 【解決手段】 検索対象となるテキストを一定長さの文
字列に分割し、分割された文字列に前記検索対象テキス
トにおけるその文字列の位置情報を付加してインデック
スを作成し、これらのインデックスをソートしてインデ
ックスファイルを作成するインデックス生成部２と、検
索文字列を入力し、検索文字列がインデックス文字列と
等しい長さの場合は、インデックスの中から同一文字列
を検索し、検索文字列がインデックス文字列より短い場
合は、検索文字列にワイルドカード文字を付加し、イン
デックスの中から該当する文字列を検索し、検索文字列
がインデックスの文字列より長い場合は、フレーズ式を
作成し、インデックスの中から該当文字列を検索する検
索処理部３と、を備えた。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、テキストファイル
中から任意の文字列を検索する装置とその方法に係り、
特に検索対象のテキストファイルについて機械的な文字
列分割によってインデックスファイルを作成し、このイ
ンデックスファイルを用いて任意の文字列を効率よく検
索することができる文字列検索装置およびその方法に関
する。

【０００２】

【従来の技術】一般に、コンピュータやワードプロセッ
サの分野では、テキストファイル（文書ファイル）か
ら、任意の文字列を検索する技術は不可欠である。特
に、最近ではコンピュータ等が取り扱うテキスト（文
書）の量が膨大化しているので、確実かつ効率よく所定
の文字列を検索する要求が高まっていた。

【０００３】また、電子通信分野でも、通信ネットワー
ク上に多数のユーザーがメッセージを掲載するようにな
ったので、掲載されている大量な情報の中から自分が求
める情報を検索するために、大量なテキストから任意の
文字列を効率よく検索する技術の開発が求められてい
た。

【０００４】ところで、欧米の言語は、単語と単語の間
にスペースが挿入されているので、このスペースを標識
として一連のテキストから単語を抽出することが容易で
ある。技術的に言えば、欧米の言語は一文字が一バイト
になっており、スペースなどをそれを表すバイトによっ
て検出することが簡単である。したがって、検索対象と
なるテキストについて、スペースを区切りとして単語
と、テキストにおけるその単語の位置とを予め抽出して
インデックスファイルを作成しておけば、そのインデッ
クスファイルを参照することにより、検索しようとする
単語や文字列の有無と、存在する場合の位置とを素早く
検索することができる。

【０００５】しかし、日本語や韓国語や中国語は、句読
点があるものの、単語と単語が連続して文章を構成して
おり、かつ、一文字が複数バイトによって表される言語
は（このことからこれらの言語をマルチバイト言語とい
う）、インデックスファイルを作成するのが容易ではな
い。

【０００６】すなわち、日本語等の場合は、文字列をい
ずれの位置で区切って単語として抽出するかは、単純な
バイトの照合から判断することが困難である。このた
め、これらのマルチバイト言語は、辞書を用意してお
き、文章の構文解析を行った後なければ、単語を単語と
して文字列から抽出することができない。

【０００７】そこで、従来のマルチバイト言語の文字列
検索は、主に以下の３つの方法のいずれかの方法によっ
て行っていた。

【０００８】(1) 単純検索による方法 ワードプロセッサの分野で一般に行われているように、
インデックスファイルを作成することなく、文字列を検
索するときは、テキスト全体について一致する文字列を
検索する方法である。

【０００９】(2) キーワード検索による方法 ある種のデータベースのように、所定のテキストに対し
てユーザが予めキーワードを指定することにより、イン
デックスファイルを作成しておき、そのインデックスフ
ァイルを利用して文字列を検索する方法である。

【００１０】(3) インデックスファイルによる全文検索
の方法 辞書を用意し、テキストを形態索解析等の手法を用いて
テキスト全部を自動的に単語に分割してインデックスフ
ァイルを作成し、そのインデックスファイルを用いてテ
キストの全文から文字列を検索する方法である。

【００１１】

【発明が解決しようとする課題】しかしながら、上記従
来の文字列検索方法では、最近の、あるいは近い将来さ
らに顕著になる大テキストからの文字列検索を効率よく
行うことはできなかった。

【００１２】すなわち、上記単純検索の方法では、テキ
ストの最初から逐一的に同一文字列を検索するので、大
きなテキストを検索するには時間がかかり過ぎて実用に
適していない。

【００１３】次に、上記キーワード検索の方法では、ユ
ーザーがテキストについてキーワードを入力しなければ
ならないので、入力の時間と手間がかかる上に、入力し
たキーワード以外の文字列を検索するできないという問
題があった。

【００１４】最後に、上記インデックスファイルによる
全文検索の方法では、テキストを構文解析するための時
間がかかる上に、その構文解析によっても完全に単語を
正確に分割することができなかった。たとえば、現在の
構文解析の技術では「新党さきがけ」のような漢字とひ
らがなとからなる単語は、単語として抽出するのが困難
であった。さらに、次々に生み出される新語を辞書に登
録しなければ、新語を単語として抽出することができな
いので、継続的に辞書をメンテナンスしなければならな
かった。

【００１５】このため、検索するための準備を含めて、
大量の文字を含むテキストから任意の文字列を簡単に検
索する簡便な技術の開発が求められていた。

【００１６】そこで、本願発明が解決しようとする課題
は、辞書のメンテナンスや構文解析を行うことなく文字
列検索のためのインデックスファイルを自動作成でき、
このインデックスファイルを用いて任意の文字列を検索
する文字列検索装置およびその検索方法を提供すること
にある。

【００１７】

【課題を解決するための手段】上記課題を解決するため
に、本願請求項１に係る文字列検索装置は、検索対象と
なるテキストを入力し、これを一定の長さの文字列に分
割し、それぞれの分割された文字列にその文字列が前記
検索対象テキストにおいて出現する位置に関する情報を
付加してインデックスを作成し、これらのインデックス
をソートしてインデックスファイルを作成するインデッ
クス生成部と、検索文字列を入力し、前記検索文字列が
前記インデックスの文字列と等しい長さの場合には、前
記インデックスの中から同一文字列を検索し、前記検索
文字列が前記インデックスの文字列より短い場合には、
検索文字列の末尾にインデックスの文字列と同一長さに
なるまでワイルドカード文字を付加し、前記インデック
スの中から該当する文字列を検索し、前記検索文字列が
前記インデックスの文字列より長い場合には、フレーズ
式を作成し、インデックスの中から該当する文字列を検
索する検索処理部と、を有していることを特徴とするも
のである。

【００１８】本願請求項２に係る文字列検索方法は、検
索対象となるテキストを入力し、これを一定の長さの文
字列に分割し、それぞれの分割された文字列にその文字
列が前記検索対象テキストにおいて出現する位置に関す
る情報を付加してインデックスを作成し、これらのイン
デックスをソートしておき、検索文字列を入力し、前記
検索文字列が前記インデックスの文字列と等しい長さの
場合には、前記インデックスの中から同一文字列を検索
し、前記検索文字列が前記インデックスの文字列より短
い場合には、検索文字列の末尾にインデックスの文字列
と同一長さになるまでワイルドカード文字を付加し、前
記インデックスの中から該当する文字列を検索し、前記
検索文字列が前記インデックスの文字列より長い場合に
は、フレーズ式を作成し、インデックスの中から該当す
る文字列を検索することを特徴とするものである。

【００１９】

【発明の実施の形態】次に、本願発明の文字列検索装置
およびその検索方法の実施形態について、添付の図面を
用いて以下に説明する。

【００２０】図１は、本発明による文字列検索装置の構
成とその処理の流れを示したものである。図１に示すよ
うに、本発明による文字列検索装置１は、インデックス
生成部２と検索処理部３とからなる。インデックス生成
部２は、検索対象となるテキスト４を入力し、これを後
述の方法で処理してインデックスファイル５を自動的に
作成する。

【００２１】一方、検索処理部３は、検索対象である検
索文字列６を入力し、後述する検索のための処理を行っ
て検索文字列を生成し、インデックスファイル５を参照
することにより、検索文字列とその位置７を出力する。

【００２２】次に上記インデックス生成部２と検索処理
部３における処理をさらに説明する。

【００２３】図２は、インデックス生成部２におけるイ
ンデックス生成のための処理の流れを示している。図２
に示すように、インデックス生成部２は、最初に検索対
象となるテキストを入力し（ステップ１００）、これを
固定長の文字列に分割する（ステップ１１０）。

【００２４】つまり、インデックス生成部２は、検索対
象となるテキストを入力すると、その構文（単語や助詞
や接続詞等の別）に拘わらず、一定の長さの文字列（こ
の文字列の長さを固定長という）に分割する。

【００２５】たとえば、検索対象となるテキストを「辞
書や単語分割機能を有する」とし、固定長をｎ＝３とす
ると、ステップ１１０では上記テキストを、 「辞書や」 「書や単」 「や単語」 「単語分」 「語分割」 「分割機」 「割機能」 「機能を」 「能を有」 「を有す」 「有する」 「する 」 「る 」 の１３個の固定長文字列に分割する。

【００２６】次に上記固定長文字列にその出現する位置
の情報、すなわち、検索対象テキストの最初の文字から
その固定長文字列の先頭文字までの文字数を示す数値を
付す（ステップ１２０）。

【００２７】上記検索対象テキスト「辞書や単語分割機
能を有する」の例で言えば、 「辞書や，０」 「書や単，１」 「や単語，２」 「単語分，３」 「語分割，４」 「分割機，５」 「割機能，６」 「機能を，７」 「能を有，８」 「を有す，９」 「有する，１０」 「する ，１１」 「る ，１２」 というように、各固定長文字列とその位置情報とをペア
として、１３個のインデックスを生成する。

【００２８】なお、上記位置情報は検索対象テキストの
最初の文字から固定長文字列の先頭文字までの文字数に
限られず、検索対象テキストの末尾の文字からの文字数
でもよく、また、一定の関数として与えてもよい。

【００２９】次に、これらのインデックスをその先頭文
字によって一定の順序に並べ替える（この操作をソート
という）（ステップ１３０）。

【００３０】上記インデックス「辞書や，０」，…，
「る ，１２」の例で言えば、 「する ，１１」 「や単語，２」 「る ，１２」 「を有す，９」 「割機能，６」 「機能を，７」 「語分割，４」 「辞書や，０」 「書や単，１」 「単語分，３」 「能を有，８」 「分割機，５」 「有する，１０」 というように、ソートする。ソートしたインデックスは
インデックスファイルとして出力する（ステップ１４
０）。

【００３１】上記インデックス生成の処理で注目すべき
ことは、この処理方法によれば、インデックスを作成す
るのに、辞書を用意することもなく、また、困難な構文
解析も行うことなく、機械的にテキストからインデック
スを生成することができる点にある。このインデックス
はソートによって後述するように検索が容易となる。

【００３２】次に、上記インデックスの使用方法、すな
わち、検索処理部３による処理を図３を用いて説明す
る。図３に示すように、検索処理部３は、検索文字列を
入力し（ステップ２００）、その長さを判断して、固定
長と比較することによってその後の処理を振り分ける
（ステップ２１０）。

【００３３】最初に、検索文字列の長さｍと固定長ｎが
等しい場合について説明する。検索文字列の長さｍと固
定長ｎが等しいときは、検索文字列と同一の文字列をイ
ンデックスファイルから検索する（ステップ２２０）。

【００３４】たとえば、前記インデックスファイルを作
成した「辞書や単語分割機能を有する」から、「語分
割」という検索文字列を検索する場合がこれに該当す
る。

【００３５】すなわち、検索文字列「語分割」の長さは
３文字ゆえ、ｍ＝３となり、前述した固定長ｎ＝３と等
しい（ｍ＝ｎ）。この場合は、前述したソートしたイン
デックスから同一の文字列を検索すればよい。インデッ
クスの文字列には位置情報が付加されているので、その
文字列の位置も知ることができる。

【００３６】ここで注目すべきことは、前述したように
インデックスファイルはインデックスをソートしている
ので、全部を検索する必要がなく、「語」を先頭文字と
する「語分割，４」なるインデックスを直ちに検索する
ことができることである。これにより、従来の単純検索
の方法に比べてはるかに効率的に検索することができ
る。

【００３７】上記例ではインデックス「語分割，４」を
得ることにより、テキストの最初の文字から４番目に
「語分割」なる文字列が存在することを知ることができ
る。

【００３８】次に、検索文字列の長さｍが固定長ｎより
小さい場合について説明する。検索文字列の長さｍが固
定長ｎより小さいときは、検索文字列にワイルドカード
を補充してワイルドカード文字列を作成し（ステップ２
３０）、インデックスファイルから該当する文字列を検
索する（ステップ２４０）。

【００３９】たとえば、前記例の「辞書や単語分割機能
を有する」から、「分割」という検索文字列を検索する
場合がこれに該当する。この場合、検索文字列「分割」
の長さは２文字ゆえ、ｍ＝２となり、前述した固定長ｎ
＝３より小さい（ｍ＜ｎ）。

【００４０】このときは、「分割＊」なるワイルドカー
ド文字列をインデックスファイルから検索する。ここで
「＊」がワイドカード文字であり、このワイルドカード
文字に該当する部分は任意の文字であってよい。

【００４１】上記インデックスファイル「辞書や，
０」，…，「る ，１２」の例で言えば、「分割＊」
に該当する文字列として「分割機，５」なるインデック
スを得ることができる。これによって、検索文字列「分
割」はテキストの最初の文字から５番目に存在すること
を知ることができる。

【００４２】ここで、注目すべきことは、ｍ＜ｎの場
合、ワイルドカード文字＊は検索文字の後尾に付し、先
頭文字によってソートされたインデックスの該当部分に
直ちにアクセスことができることである。インデックス
は、テキストの各文字を先頭として作成されているの
で、上述方法でも検索漏れを生じることがない。

【００４３】最後に、検索文字列の長さｍが固定長ｎよ
り大きい場合について説明する。検索文字列の長さｍが
固定長ｎより大きいときは、検索文字列を固定長文字列
に分割し（ステップ２５０）、後述するフレーズ式を作
成し（ステップ２６０）、インデックスファイルから該
当するフレーズ式を検索する（ステップ２７０）。

【００４４】たとえば、前記例の「辞書や単語分割機能
を有する」から「単語分割機能を」という検索文字列を
検索する場合がｍ＞ｎの場合に該当する。最初に「単語
分割機能を」からフレーズ式を作成する。ここで、フレ
ーズ式とは、文字列「○○○」と文字列「△△△」を含
む検索文字列（これをフレーズという）において、文字
列「○○○」と文字列「△△△」の先頭文字どうしがｐ
文字離れて出現する場合に、これを「○○○」＜ｐ＞
「△△△」と表し、この「○○○」＜ｐ＞「△△△」を
フレーズ式という。なお、ｐがｎ（＝３）より小さい場
合は、文字列「○○○」と文字列「△△△」の一部また
は全部が重複して場合であるが、これらも全く同一の方
法によって上記フレーズ式に表すことができる。

【００４５】上記文字列「○○○」と文字列「△△△」
を含む検索文字列を検索するには、ｐ文字離れた「○○
○」というインデックスと「△△△」というインデック
スとを検索すればよい。

【００４６】上記「辞書や単語分割機能を有する」から
「単語分割機能を」という検索文字列を検索する例で
は、「単語分割機能を」から、「単語分」＜３＞「割機
能」＜１＞「機能を」あるいは、「単語分」＜２＞「分
割機」＜２＞「機能を」のようなフレーズ式を作成す
る。ここで、上記２つのフレーズ式は互いに等価であ
り、フレーズ式は検索文字列の全体をカバーしていれば
よい。

【００４７】次にインデックス「辞書や，０」，…，
「る ，１２」から、上記フレーズ式に該当するイン
デックスを検索する。

【００４８】これにより、インデックス「単語分，３」
〜「機能を，７」が検索され、検索文字列は検索対象の
テキストの最初の文字から３文字目に出現することを知
ることができる。

【００４９】上記フレーズ検索機能によれば、インデッ
クス固定長より長い文字列も予め用意したインデックス
ファイルを用いて検索でき、インデックスファイルがソ
ートされていることから、目的とする文字列を素早く検
索することができる。

【００５０】以上で上記実施形態の説明を終了するが、
上記実施形態は、検索対象テキストについて予め固定長
を定めてインデックスファイルを作成し、このインデッ
クスファイルを用いて検索文字列を検索するものであ
る。しかし、本発明の方法を用いれば、異なる検索方法
も可能となる。以下にその検索方法について説明する。

【００５１】上記異なる検索方法とは、予めインデック
スファイルを作成することなく、検索する際に、検索文
字列の長さに合わせて検索対象のテキストを分割する方
法である。

【００５２】この方法は、比較的少量、かつ、保存すべ
き期間が短いテキストに対しては有効なものである。

【００５３】この方法によれば、所定の検索対象テキス
トに対して検索文字列を入力すると、その文字列の長さ
を固定長として検索対象テキストを分割してインデック
スを作成する。

【００５４】この場合、検索文字列の長さに満たないテ
キスト末端部のインデックスは作成を省略する。このよ
うなインデックスは検索文字列と一致しないことが明ら
かだからである。

【００５５】たとえば、「辞書や単語分割機能を有す
る」というテキストから「単語分割機能を有する」とい
う文字列を検索しようとする場合、固定長ｎ＝１０（＝
ｍ）として、「辞書や単語分割機能を有する」から、下
記のインデックスを作成する。

【００５６】「辞書や単語分割機能を，０」 「書や単語分割機能を有，１」 「や単語分割機能を有す，２」 「単語分割機能を有する，３」 このとき、９文字以下のインデックス、すなわち、「語
分割機能を有する ，４」〜「る ，
１２」を作成する必要がない。これらには検索文字列は
含まれていないことが明らかだからである。

【００５７】次にインデックスをソートする。上記例で
は、下記のように並べ変える。

【００５８】「や単語分割機能を有す，２」 「辞書や単語分割機能を，０」 「書や単語分割機能を有，１」 「単語分割機能を有する，３」 この状態で検索文字列「単語分割機能を有する」と同一
の文字列をインデックスから検索すれば、求める文字列
の位置を知ることができる。上記例では文字列「単語分
割機能を有する」がテキストの最初の文字から３文字目
に存在することを知ることができる。

【００５９】ここで注目すべき点は、この方法によれ
ば、すべてのテキストについてインデックスを作成して
おく必要がなく、記憶装置の利用効率を高くすることが
できるという点と、長い検索文字列を検索する場合、テ
キストの後尾のｎより短い文字列についてインデックス
を作成する必要がなく、インデックスの作成が簡単であ
り、かつ、文字列の検索方法が同一文字列の発見である
のできわめて簡単である点にある。

【００６０】したがって、比較的少量、かつ、保存すべ
き期間が短いテキストに対しては有効な検索方法であ
り、特に、長い文字列を検索する場合にきわめて効率よ
く検索することができる。

【００６１】

【発明の効果】以上の説明から明らかなように、本発明
による文字列検索装置およびその検索方法は、検索対象
となるテキストの構文解析することなく、したがって構
文解析のための辞書を用意することなく、機械的に一定
長の文字列からなるインデックスを作成して、これらの
インデックスをソートしておくことができる。

【００６２】このインデックスを利用し、文字列を検索
するときは、同一文字列検索、ワイルドカード文字列検
索、フレーズ式検索のいずれかによって、検索文字列の
長さに拘わらず、任意の長さの検索文字列を検索するこ
とができる。

【００６３】これにより、大容量のテキストを多数検索
する場合も、機械的な処理によってインデックスを作成
しておき、任意の文字列を素早く、かつ、確実に検索す
ることが可能となる。

【図面の簡単な説明】

【図１】本願発明による文字列検索装置の構成とその処
理の流れを示したブロック図。

【図２】本願発明による文字列検索装置のインデックス
生成部における処理を示したフローチャート。

【図３】本願発明による文字列検察装置の検索処理部に
おける処理を示したフローチャート。

【符号の説明】

１ 文字列検察装置 ２ インデックス生成部 ３ 検索処理部 ４ 検索対象となるテキスト ５ インデックスファイル ６ 検索文字列 ７ 検索しようとする文字列とその位置

───────────────────────────────────────────────────── フロントページの続き (72)発明者 鈴 木 奏 神奈川県横浜市保土ケ谷区神戸町134番地 株式会社野村総合研究所内 (72)発明者 佐 藤 理 史 石川県能美郡辰口町旭台15 北陸先端科学 技術大学院大学内

Claims (2)

【特許請求の範囲】
1. 【請求項１】検索対象となるテキストを入力し、これを
   一定の長さの文字列に分割し、それぞれの分割された文
   字列にその文字列が前記検索対象テキストにおいて出現
   する位置に関する情報を付加してインデックスを作成
   し、これらのインデックスをソートしてインデックスフ
   ァイルを作成するインデックス生成部と、 検索文字列を入力し、前記検索文字列が前記インデック
   スの文字列と等しい長さの場合には、前記インデックス
   の中から同一文字列を検索し、前記検索文字列が前記イ
   ンデックスの文字列より短い場合には、検索文字列の末
   尾にインデックスの文字列と同一長さになるまでワイル
   ドカード文字を付加し、前記インデックスの中から該当
   する文字列を検索し、前記検索文字列が前記インデック
   スの文字列より長い場合には、フレーズ式を作成し、イ
   ンデックスの中から該当する文字列を検索する検索処理
   部と、を有していることを特徴とする文字列検索装置。
2. 【請求項２】検索対象となるテキストを入力し、これを
   一定の長さの文字列に分割し、それぞれの分割された文
   字列にその文字列が前記検索対象テキストにおいて出現
   する位置に関する情報を付加してインデックスを作成
   し、これらのインデックスをソートしておき、 検索文字列を入力し、前記検索文字列が前記インデック
   スの文字列と等しい長さの場合には、前記インデックス
   の中から同一文字列を検索し、前記検索文字列が前記イ
   ンデックスの文字列より短い場合には、検索文字列の末
   尾にインデックスの文字列と同一長さになるまでワイル
   ドカード文字を付加し、前記インデックスの中から該当
   する文字列を検索し、前記検索文字列が前記インデック
   スの文字列より長い場合には、フレーズ式を作成し、イ
   ンデックスの中から該当する文字列を検索することを特
   徴とする文字列検索方法。