JPH08147320A

JPH08147320A - 情報検索方法及びシステム

Info

Publication number: JPH08147320A
Application number: JP6287642A
Authority: JP
Inventors: Rie Kubota; 理恵久保田
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1994-11-22
Filing date: 1994-11-22
Publication date: 1996-06-07
Anticipated expiration: 2012-10-29
Also published as: JP2669601B2; CN1151558A; KR960018993A

Abstract

(57)【要約】【目的】曖昧検索によって、人間の感覚に近いものを
検索し得る文字列検索技法を提供すること。【構成】本発明によれば、文字列パターンの文書内位
置情報を含む索引ファイルを使用して、指定された文字
列と文字の並びが似ている文字列を含む文書を高速に検
索する方式が提案される。この方式では、検索したい文
字列と検索精度（０より大きく１以下）とを指定し、検
索したい文字列との"似ている度合"が指定の検索精度以
上である"似ている文字列"を含む文書および"似ている
文字列"の文書内位置を特定することができる。これ
は、具体的には、文書中から、検索したい文字列と"似
ている文字列"を選びだして、何文字連続して一致して
いるか途中にどのくらい余分な文字がはさまっているか
の２つの観点から"似ている度合い"を数値化する処理で
ある。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、例えばテキスト・フ
ァイル形式でディスクに格納された大量の文書を、高速
且つ所望の曖昧度を許容しつつ検索するシステム及び方
法に関するものである。

【０００２】

【従来の技術】従来より、新聞記事、特許公報、科学技
術文献などの、自然言語で書かれ、ディスクに格納され
た大量の文書を高速で検索したいという要望があり、さ
まざまな検索方式が提案されている。そのような検索方
式を大別すると、次のとおりである。

【０００３】(a) キーワード検索方式この方式では、個々の文書とその文書の内容をあらわす
キーワードとの索引づけが予め行われる。このとき、キ
ーワードを決める方法としては、形態素解析などによる
自動キーワード抽出、人手によるキーワード付加、およ
びそれらを組み合わせた方法がある。しかし、この方式
は、キーワードとして索引付けされた文字列でしか検索
できず、また、形態素解析による自動キーワード抽出の
精度は、単語・文法辞書の精度に左右されるため、辞書
の保守に多くの人的作業を要するという欠点がある。

【０００４】(b) 索引なしの全文検索方式これは、索引を使用することなく、検索したい文字列が
指定されるたびに、検索対象となる文書をすべてスキャ
ンする方式である。特別なハードウェアを使用して検索
速度をあげている方式もある。しかし、特別なハードウ
ェアを使用したシステムは、コストが嵩み、また、クラ
イアント・サーバ環境では、使用できるマシンの種別に
制約が生じる場合がある。

【０００５】(c) 索引による全文検索方式本発明は、索引による全文検索方式に属するものであ
る。索引を使用することにより、全文検索を高速化する
ことを意図するものとしては、以下に示すような技法が
知られている。

【０００６】特開平４−２０５５６０号公報には、検索
対象となる文字列を検索を行う単位である検索単位に分
け、この検索単位毎に昇順の符号を付与し、この分けら
れた検索単位に対してその論理的な区分を示す属性符号
を付与し、検索対象となる文字列を各文字毎に検索単位
中での位置を示す文字位置順序符号を付与し、検索単位
識別符号と、文字位置順序符号と、属性符号とからなる
文字位置情報を作成して、この文字位置情報を文字種ご
との領域に格納して検索ファイルを作成することが開示
されている。

【０００７】特開平４−２１５１８１号公報には、検索
処理のための文字列照合回数を低減し，汎用の情報処理
装置で高速照合を可能にするために、検索対象となる文
字列を構成する各文字セツトが文字列中のどの位置にあ
るかを示す文字セツト位置情報を文字セツト種ごとにグ
ル−プ化した検索フアイルを作成することが開示されて
いる。

【０００８】ところで、検索文字列と完全に一致する文
字列を含むを検索するのみならず、部分的に一致する文
字列を含む文書も検索したいという必要性が生じること
も少なくない。例えば、ユーザーの、検索文字列に対す
る記憶が曖昧であったり、検索文字列がさまざまな変形
をともなって出現し得るものであって、そのような変形
すべてを列挙することが困難であったりする場合があ
る。

【０００９】従来技術における典型的な部分文字列指定
方法は、正規表現を使用するものである。これによれ
ば、任意の文字の０回以上の繰り返し、任意の文字の１
回以上の繰り返し、行末位置、行頭位置、特定の文字コ
ードの範囲内の任意の文字、などの指定が可能である。

【００１０】さらに、特開昭６３−９９８３０号公報
は、検索文字列データと、被検索文字列データとの部分
一致の機能を有するシステムにおいて、検索文字列デー
タの同類語関係に関するデータと、当該検索文字列デー
タが被検索文字列データのいずれかに出現するか否かを
表すデータとを蓄積するテーブルを設けることを開示す
る。

【００１１】また、特開昭６２−２２１０２７号公報
は、部分対象文字列の先頭から切出した文字列が辞書か
ら検索されなかった場合、その長さを１だけ増加した次
の切出し文字列については前方検索を行うことにより、
無効な検索回数を減らし、比較的高速で且つ効率的な単
語切出しを行えるようにすることを開示する。

【００１２】また、特開平４−３２６１６４号公報及び
特開平５−１７４０６７号公報は、デ−タベ−ス検索シ
ステムにおいて、検索対象の物件毎にその自己相関情報
を記憶し、検索キ−の自己相関情報と検索対象１０の上
記自己相関情報との合致度を物件毎に求め、物件番号を
合致度の降順に出力する検索手段を設けることを開示す
る。

【００１３】しかし、これら従来技術の文字列検索技法
では、検索すべき文字列の曖昧性の度合といったものを
指定することが困難であり、検索結果は、ユーザーにと
って所望でなく、あるいは不自然な多くの文字列を含む
ことになる。

【００１４】

【発明が解決しようとする課題】この発明の目的は、検
索すべき文字列の曖昧性の度合を任意に指定できるよう
な文字列検索技法を提供することにある。

【００１５】この発明の他の目的は、検索すべき文字列
の曖昧性の度合を任意に指定できるような文字列検索技
法を実現するための索引構造を提供することにある。

【００１６】この発明のさらに他の目的は、曖昧検索に
よって、人間の感覚に近いものを検索し得る文字列検索
技法を提供することにある。

【００１７】

【課題を解決するための手段】本発明によれば、複数の
文書からなるデータベースを全文検索するために、個々
の文書には、一意的な番号（または記号）が付与され、
検索ファイルには、各々の文書中の個々の連続するＮ個
の文字と、そのＮ個の文字があらわれる文書の番号及び
その文書中の位置情報が格納される。好適には、索引フ
ァイルは、文字パターン・ファイルと、位置情報ファイ
ルの２つのファイルで構成される。文字パターン・ファ
イルには、文字パターン・区切りパターンとそれに対応
する文書番号・文書内位置番号が位置情報ファイルのど
こに位置するかが格納される。位置情報ファイルには、
文書番号・文書内位置番号が格納される。

【００１８】本発明によれば、このような索引ファイル
を使用して、指定された文字列と文字の並びが似ている
文字列を含む文書を高速に検索する方式が提案される。
この方式では、検索したい文字列と検索精度（０より大
きく１以下）とを指定し、検索したい文字列との"似て
いる度合"が指定の検索精度以上である"似ている文字
列"を含む文書および"似ている文字列"の文書内位置を
特定することができる。

【００１９】これは、具体的には、文書中から、検索し
たい文字列と"似ている文字列"を選びだして、何文字連
続して一致しているか途中にどのくらい余分な文字がは
さまっているかの２つの観点から"似ている度合い"を数
値化する処理である。

【００２０】このとき、"似ている度合い"が最高値１に
なるとき、文字列は完全に一致しており、また、文字列
が完全に一致していれば必ず"似ている度合い"は１にな
る。似ている文字列に、検索したい文字列にない余分な
文字がはさまっていたり、検索したい文字列の一部しか
似ている文字列にあらわれない場合、"似ている度合い"
は、１よりも小さい値になるが、本発明に従えば、この
ような"似ている度合い"の数値が、人間の通常の感覚に
かなりよく合致する、妥当なものとなる。

【００２１】上記索引ファイルは、文書中の任意の連続
するＮ文字を高速で検索することを可能にするので、上
記索引ファイルを使用して検索すべき文字列とのＮ文字
の比較を順次行うことにより、何文字連続して一致して
いるか、及び途中にどのくらい余分な文字がはさまって
いるかを高速で検出することができる。

【００２２】

【実施例】以下、図面を参照して本発明の実施例を説明
する。

【００２３】Ａ．ハードウェア構成図１を参照すると、本発明を実施するためのシステム構
成の概観図が示されている。この構成は、バス１０１
に、演算及び入出力制御機能をもつ中央処理装置（ＣＰ
Ｕ）１０２、プログラムをロードし、また、ＣＰＵ１０
２のための作業領域を与える主記憶（ＲＡＭ）１０４、
コマンドや文字列などをキー入力するためのキーボード
１０６と、中央処理装置を制御するためのオペレーティ
ング・システム、データベース・ファイル、検索エンジ
ン、索引ファイルなどを格納したハードディスク１０８
と、データベースの検索結果を表示するためのディスプ
レイ装置１１０と、ディスプレイ装置１１０の画面上の
任意の位置をポイントしてその位置情報を中央処理装置
に伝えるためのマウス１１２を接続した通常の構成であ
る。

【００２４】オペレーティング・システムとしては、Ｗ
ｉｎｄｏｗｓ（マイクロソフトの商標）、ＯＳ／２（Ｉ
ＢＭの商標）、ＡＩＸ（ＩＢＭの商標）上のＸ−ＷＩＮ
ＤＯＷシステム（ＭＩＴの商標）などの、標準でＧＵＩ
マルチウインドウ環境をサポートするものが望ましい
が、本発明は、ＰＣ−ＤＯＳ（ＩＢＭの商標）、ＭＳ−
ＤＯＳ（マイクロソフトの登録商標）などのキャラクタ
・ベース環境でも実現可能であり、特定のオペレーティ
ング・システム環境に限定されるものではない。

【００２５】また、図１は、スタンド・アロン環境のシ
ステムを示しているが、一般的に、データベース・ファ
イルは大容量のディスク装置を要するものであるので、
クライアント／サーバ・システムとして本発明を実現
し、サーバ・マシンにデータベース・ファイルと検索エ
ンジンを配置し、クライアント・マシンは、サーバ・マ
シンに対して、イーサネット、トークン・リングなどで
ＬＡＮ接続し、クライアント・マシン側には、検索結果
を見るための表示制御部のみを配置するようにしてもよ
い。

【００２６】Ｂ．システム構成次に、図２のブロック図を参照して、本発明のシステム
構成について説明する。尚、図２で個別のブロックで示
されている要素は、図１のハードディスク１０８に、個
別にまたは集合的に、データ・ファイルまたはプログラ
ム・ファイルとして格納されているものであることに留
意されたい。

【００２７】データベース２０２として本発明が主に想
定するものは、新聞記事のデータベース、特許公報デー
タベースなどの、複数の文書が格納されたものである。
しかし、本発明の適用範囲は、複数の文書からなるデー
タベースの検索に限定されず、単一の文書内の検索にも
適用できることに留意されたい。このとき、個別の文書
のコンテンツは、例えばテキスト・ファイル形式で、検
索可能に格納されているものである。さらに、個々の文
書には、一意的な文書番号が付与されている。好適な文
書番号は、１から始まる昇順の順次番号であるが、特許
公報データベースの場合、出願番号あるいは公開番号を
一意的な文書番号として使用することもできる。また、
個々の文書を識別するために順次番号ではなく、"AB
C"、"&XYZ"などの記号を使用してもよい。但し、一般的
に、そのような識別記号を表現するためには、数字より
も多くのバイト数を要するので、実際上、順次番号で文
書を識別する方が好ましい。

【００２８】一般的に、データベース２０２に格納され
ている新聞記事あるいは特許公報のような膨大なコンテ
ンツを直接検索するのは長い処理時間を要するので、デ
ータベース２０２に格納されている全ての新聞記事のコ
ンテンツを対象として予め、索引ファイル２０４が、索
引作成・更新モジュール２０６によって作成される。本
発明の後述する実施例では、このようにして作成された
索引ファイル２０４は、文字パターン・ファイルと、位
置情報ファイルの２つのファイルで構成される。文字パ
ターン・ファイルには、文字パターン・区切りパターン
とそれに対応する文書番号・文書内位置番号が位置情報
ファイルのどこに位置するかが格納される。位置情報フ
ァイルには、文書番号・文書内位置番号が格納される。

【００２９】また、データベース２０２は、個々の文書
を、個別のファイルとして管理するものでもよく、ある
いは、連続する単一のファイルに、全ての文書を順次配
列したものでもよく、要するに、本質的なのは、個々の
文書に、一意的な番号が付与され、その一意的な番号で
もって、個々の文書の内容にアクセスできることであ
る。前者の場合、データベース２０２は、個々の文書の
一意的な番号と、文書を格納する実際のファイル名とを
対応付けるテーブルを管理し、後者の場合、データベー
ス２０２は、個々の文書の一意的な番号と、単一のデー
タベース・ファイル中のオフセット及び文書のサイズと
を対応付けるテーブルを管理することになる。

【００３０】検索エンジン２０８は、検索文字入力モジ
ュール２１０によって与えられた検索文字列を入力とし
て索引ファイル２０４を検索し、入力された検索文字列
を含む文書の文書番号（複数あり得る）と、その入力さ
れた検索文字列が文書中にあらわれる位置（やはり複数
あり得る）とを返す機能をもつ。検索文字入力モジュー
ル２１０は、好適には、マルチウインドウ環境における
ダイアログ・ボックスで構成され、その入力ボックス
に、キーボード１０６で所望の検索すべき文字を入力す
るようにした形式のものである。

【００３１】さらに本発明の特徴によれば、検索文字入
力モジュール２１０は、曖昧検索の類似度を、０〜１の
数値（百分率を基準として、０〜１００の数字でもよ
い）で入力することを可能とする。このため、検索文字
入力モジュール２１０は、０〜１間の任意の位置を指し
示すハンドルをもつスライダまたはスクロール・バーを
表示する。そのスライダのハンドルは、例えばデフォー
ルトでは１を指し示し、さらに、ハンドルをマウス１１
２でドラッグして移動することにより、別の値を指し示
すように操作可能である。

【００３２】結果表示モジュール２１２は、検索エンジ
ン２０８から与えられた検索結果である文書番号と、検
索文字が当該文書中にあらわれる位置の値に基づき、デ
ータベース２０２にアクセスし、その文書のその位置に
対応する行を、好ましくは個別の検索結果表示ウインド
ウに表示する。検索結果がそのウインドウの１画面に収
まらない場合、スクロール・バーがあらわれ、ユーザー
が、それをクリックすることによって、順次検索結果を
眺めることができるようにする。

【００３３】Ｃ．索引ファイルの構造及び作成方法本発明においては、すべての連続するＮ文字とその文書
内位置、及び文書内分割情報を文書と索引づけしたファ
イルが作成される。ここで、文書内分割情報とは、典型
的には、「。」、「、」などの文章の区切りや、「第１
章」、「要約」などの、広い意味で文書の区切りであ
る。

【００３４】Ｃ１．文字列の正規化索引ファイルを作成するために必要な最初の処理は、文
字列の正規化であって、それは次のような処理である。
すなわち、検索すべき文書が特に日本語テキスト・ファ
イルである場合、半角と全角が混在することがあり得
る。そこで、例えば、半角文字を対応する全角文字に置
換する、という処理を行う。

【００３５】Ｃ２．文字パターン情報の取り出し索引ファイルを作成するための次のステップは、正規化
された文字列のすべての文字について、その文字から始
まる連続するＮ個の文字（以下，文字パターンと呼ぶ）
を取り出して、文書番号、文書内位置番号とともに索引
ファイルに格納する。ただし、Ｎ≧１であって、日本語
の場合、Ｎ＝２が適当である。

【００３６】文書内位置番号は、文書内の検索対象とな
るすべての文字に文書内で一意的な番号を順につけたも
のである。そして、文字パターンの最初の文字の文書内
位置番号を、その文字パターンの文書内位置番号とす
る。文書の終わりで後続の文字とあわせてＮ個に満たな
い場合には、Ｘ'００'など定められた詰め文字を詰めて
あわせてＮ個になるようにする。

【００３７】また、この実施例では、個々の単独の文書
を、検索時に意味を持つような分け方でブロックに分割
し、分割情報を索引ファイルに格納する。分割情報の格
納は前述の文字パターンと同等の形式で行う。すなわ
ち、正規化された文字列からとりだした文字パターンの
かわりに、特別に定めた区切りパターンを、文書の文書
番号とブロックの境界の文字の文書内位置情報とともに
格納する。

【００３８】区切りパターンを数種類定めることによ
り、数種類の異なる分割方法を持つことができるように
なる。ただし、区切りパターンは、正規化された文字列
から取り出される文字パターンと重複しないように定め
なくてはならない。この実施例では、正規化処理によっ
て、１バイトのコードも、２バイト・コードに変換され
るので、２バイトを１ワードと見たときに、その１ワー
ドの値が２５５以下である場合は、通常の文字コードに
は該当しない。そこで、０〜２５５の任意のワード値
を、複数種類の区切りパターンに個別に割り当てること
ができる。

【００３９】分割情報を文字パターンと同様なこのよう
な形式で格納することの利点は、以下のとおりである。 - 索引の作成・更新が簡単。分割情報のために特別な処
理をする必要がない。 - 索引の容量をいちじるしく増加させることがない。例えば、文書内位置番号ごとにそれが属するブロック番
号を付加するような形式に比べて容量の増加ははるかに
小さい。

【００４０】Ｃ３．文書内位置番号の具体例例えば、「本日は晴天なり。ただいま、マイクのテスト
中。」という文章を先頭に含む文書がデータベース２０
２（図２）に含まれていたとする。この文章の各文字に
文書内位置番号を付与すると、次のとおりである。

【表１】文字の文書内位置番号 1 2 3 4 5 6 7 8 9 10111213141516171819202122 正規化された文字列本日は晴天なり。ただいま、マイクのテスト中。区切り方その１ | | 区切り方その２ | | |

【００４１】そして、その文書の文書番号が１番である
とし、上記文字パターンの文字数Ｎを２であるとする。
すると、個々の文字パターン（長さ２）に関連付けられ
る文書番号、及び文書内位置番号は、次のとおりであ
る。

【表２】文字パターン文書番号文書内位置番号 ------------------------------------------ 本日 1 1 日は 1 2 は晴 1 3 晴天 1 4 天な 1 5 なり 1 6 り。 1 7 。た 1 8 区切りパターン１ 1 8 区切りパターン２ 1 8 ただ 1 9 だい 1 10 いま 1 11 ま、 1 12 、マ 1 13 区切りパターン２ 1 13 マイ 1 14 イク 1 15 クの 1 16 のテ 1 17 テス 1 18 スト 1 19 ト中 1 20 中。 1 21 。 1 22 区切りパターン１ 1 22 区切りパターン２ 1 22

【００４２】Ｃ４．文書内分割情報の役割次に、検索における、文書内の分割情報（区切り）の利
用価値について説明する。

【００４３】・特定ブロックだけを対象にした検索例えば、文書がタイトル・要約・本文という構成にな
っている場合に、タイトルだけ、要約だけなど特定部分
だけを対象にして検索することは一般的な要望である
といえる。タイトルの終わり、要約の終わりについて、
区切りパターンとその位置情報を格納することにより、
そのような検索が実現できる。

【００４４】・複数の文字列どうしの関連が強い文書の
検索複数の文字列どうしの文脈中での関連の強さを意識した
検索をすることは一般的な要望であるといえる。たとえ
ば、文字列どうしが単に同一文書内にあるだけよりは、
同一段落中にあったほうが関係が強い可能性が高く、同
一文中にあればさらに関係が強いことが予測される。段
落や文の終わりについて、区切りパターンとその位置情
報を格納しておくことにより、複数の文字列どうしが同
一ブロック内にある文書を検索することが可能になり、
関係の強さを意識した検索ができるようになる。

【００４５】Ｃ５．索引ファイルの構造文字パターン・区切りパターンとその文書番号・文書内
位置番号は、検索時に効率よくとりだせる形で格納する
必要がある。そのために、この実施例では、索引ファイ
ルを文字パターン・ファイル（主に文字パターン・区切
りパターンを格納するファイル）、位置情報ファイル
（主に文書番号・文書内位置番号を格納するファイル）
の２つのファイルで構成する。文字パターン・ファイル
には、文字パターン・区切りパターンとそれに対応する
文書番号・文書内位置番号が位置情報ファイルのどこに
位置するかを格納する。位置情報ファイルには、文書番
号・文書内位置番号を格納する。

【００４６】このような文字パターン・ファイルと、そ
れに対応する位置情報ファイルの例を図３に示す。

【００４７】図３において、文字パターン・ファイル３
０２のエントリは、データベース２０２の全ての文書に
おける連続するＮ文字（ここでは、Ｎ＝２である）の文
字パターンである。文字パターン・ファイル３０２のエ
ントリは、好適には、２分探索を可能ならしめるよう
に、正規化された文字パターンの先頭の文字のコード値
で昇順にソートされている。「区切りパターン１」、
「区切りパターン２」、「なり」、「は晴」などが、文
字パターン・ファイル３０２の個別のエントリである。
尚、例えば、「区切りパターン１」は、「，」、「、」
または「。」などの文・句の区切りを包括的に示すもの
であって、特殊な２バイト値が割り当てられる。

【００４８】図３の位置情報ファイル３０４は、文字パ
ターン・ファイル３０２の個々のエントリに対応する少
なくとも１つの文書番号及び、その個々の文書番号毎に
関連付けられた少なくとも１つの文書内位置番号を格納
している。

【００４９】文字パターン・ファイル３０２のエントリ
と、位置情報ファイル３０４のエントリとを対応付ける
ために、図示しないが、文字パターン・ファイル３０２
の個々のエントリは、対応する位置情報ファイル３０４
のエントリの、位置情報ファイル３０４の先頭からのオ
フセット、及び、対応する位置情報ファイル３０４のエ
ントリのサイズの情報をもつ。すなわち、図３で例え
ば、文字パターン・ファイル３０２は、「区切りパター
ン２」に関連してそこに格納されているオフセットの情
報から、位置情報ファイル３０４を先頭からシークし、
サイズの情報に指定されたバイト数だけシークした位置
から読取り、これによって、「区切りパターン２」に関
連して、文書番号１における８，１３，２２・・・とい
う文書内位置番号値と、文書番号２に関連する文書内位
置番号値、・・・（もしあるなら）文書番号ｎに関連す
る文書内位置番号値を一括して読み取ることが可能とな
る。

【００５０】一般に、文書番号ｉに関連する文書内位置
番号値は、例えば、（文書番号ｉ：４バイト）（文書内
位置番号の数ｋ：４バイト）（１番目の文書内位置番
号：４バイト）・・・（ｋ番目の文書内位置番号：４バ
イト）のような形式で格納されている。この例では、文
書内位置番号を格納するフィールドとして、文書の絶対
位置を格納するために４バイトをとるようにしている
が、実際上、１つ前の文書内位置番号からのオフセット
を格納するようにして、これを１〜３バイトに節約する
ようにした方がよい。文書番号及び文書内位置番号の数
を格納するフィールドについても同様である。

【００５１】Ｃ６．索引ファイルの作成処理次に、図４を参照して、索引ファイルの作成処理につい
て説明する。この処理は、最初のデータベース２０２の
構築時または、データベース２０２に文書を追加あるい
はデータベース２０２から文書を削除したときに、図２
の索引作成・更新モジュール２０６によって行われる処
理である。

【００５２】図４で、先ずステップ４０２では、メモリ
領域を確保する処理が行われる。これは、例えば、オペ
レーティング・システムの機能を呼び出すことによっ
て、ＲＡＭ１０４上で、所定のサイズの作業領域を獲得
する処理である。

【００５３】ステップ４０４では、データベース２０２
から１つの文書が、好適には上記ステップ４０２で獲得
されたメモリ領域に読み込まれる。

【００５４】ステップ４０６では、ステップ４０４で読
み込まれた文書につき、前述の正規化処理が行われる。

【００５５】ステップ４０８では、正規化された文書を
走査することによって、文字パターン・区切りパターン
が作成され、文字パターン・区切りパターンと、当該文
書の文書番号と、文字パターン・区切りパターンの文書
内位置番号が、上記ステップ４０２で獲得されたメモリ
領域に格納される。

【００５６】ステップ４０８の処理において、文字パタ
ーン、文書番号及び文書内位置番号をステップ４０２で
予め獲得されたメモリ領域に格納していくにつれて、そ
の獲得されたメモリ領域の空き領域が不足してくること
があり得る。そこで、ステップ４１０では、獲得された
メモリ領域が満杯かどうかを調べる処理が行われ、もし
そうなら、ステップ４１２で、メモリ領域に格納されて
いる文字パターン・区切りパターンと、文書の文書番号
と、文字パターン・区切りパターンの文書内位置情報と
が、例えば、文字パターン・区切りパターンの文字コー
ド値・文書番号・文書内位置番号に基づきソートされ
て、中間ファイルとしてディスク１０８（図１）に書き
出され、これによって、中間ファイルに書き出されたデ
ータが格納されていたメモリ領域は、以下の処理で使用
可能に開放される。そして、この後処理は、ステップ４
１４に進む。

【００５７】ステップ４１０で、メモリ領域にまだ余裕
があると判断されたなら、処理は直ちにステップ４１４
に進む。

【００５８】ステップ４１４では、ステップ４０４でま
だ読み込んでいない文書がデータベース２０２に残って
いるかどうかが判断される。もしそうなら、処理は、ス
テップ４０４に戻る。

【００５９】ステップ４１４で、データベース２０２の
全ての文書の読み込み処理が完了したと判断されると、
ステップ４０２で獲得されたメモリ領域に書き出されな
いで残っている文字パターン・区切りパターンと、文書
の文書番号と、文字パターン・区切りパターンの文書内
位置番号とが、やはり文字パターン・区切りパターンの
文字コード値・文書番号・文書内位置番号に基づきソー
トされて、中間ファイルとしてディスク１０８（図１）
に書き出される。

【００６０】ステップ４１２とステップ４１６での中間
ファイルの書き出しによって、ディスク１０８には、複
数の中間ファイルが存在し、また、その各々の中間ファ
イルは予めソートされているので、ステップ４１８で
は、周知のマージ・ソートの技法で、それらの複数の中
間ファイルから、図３に示す文字パターン・ファイル３
０２と、位置情報ファイル３０４とを作成しディスク１
０８に格納する処理が行われる。尚、もとの複数の中間
ファイルには、文字パターンは重複して何度もあらわれ
得るので、ここでは、重複する同一の文字パターンのエ
ントリを１つにまとめて、それに関連する文書番号及び
文書内位置番号を関連付ける処理が行われる。その後、
中間ファイルは最早不要なので削除される。

【００６１】Ｄ．索引ファイルを使用した検索処理次に、上述のようにして作成された索引ファイルを使用
して、文字列検索を行う処理の例について、図５のフロ
ーチャートを参照して説明する。ステップ５０２では、
先ず、例えば、入力ボックスをもつダイアログ・ボック
スを表示し、ユーザーに、その入力ボックスに検索文字
列を入力するようにプロンプトする処理が行われる。

【００６２】ユーザーが入力ボックスに検索文字列を入
力し、ＯＫボタンをクリックすると、必要に応じて検索
文字列の正規化処理が行われた後で、その検索文字列の
最初のＮ文字パターンで以って上記索引ファイルを使用
した検索処理が行われる。尚、ここでいうＮ文字パター
ンの長さは、上記索引ファイルの文字列パターンの長さ
Ｎと同一であり、従って、検索文字列の部分文字列であ
るこのＮ文字パターンをキーとして、上記索引ファイル
を高速に２分探索することができる。日本語の文書に適
切なＮの値の１つの例は、２である。

【００６３】ステップ５０６で、検索文字列の最初のＮ
文字パターンが見つからなかったと判断されると、好適
には、検索文字列が見つからなかったことを示すメッセ
ージ・ボックスがステップ５０８で表示され、処理は終
了する。

【００６４】ステップ５０６で、検索文字列の最初のＮ
文字パターンが見つかったと判断されると、索引ファイ
ルからは、１つ以上の文書番号とその文書番号における
少なくとも１つの文書内位置番号が返されるので、この
情報は、ステップ５１０で後の処理のため主記憶または
ディスク上の所定のバッファ領域に一旦格納される。

【００６５】ステップ５１２では、検索文字列全てをＮ
文字パターンの部分文字列として検索してしまったかど
うかが判断され、もしそうなら、処理はステップ５２０
に進む。もしそうでないなら、ステップ５１８で、検索
文字列の次のＮ文字パターンで以って上記索引ファイル
を使用した検索処理が行われる。尚、検索文字列の長さ
は、一般的にＮの倍数とは限らず、従って、Ｎ文字パタ
ーンずつ検索していって検索文字列の末端付近まで部分
文字列をとる処理が進んだ時、索引ファイルのキーとな
る文字列がＮ文字よりも短いという場合もある。この場
合は、検索文字列の最後のＮ文字を部分文字列としてと
る。すると、直前にとったＮ文字と重複する文字がある
ことになる。検索文字列がＮ文字未満である場合には、
２分探索の結果は複数の候補を有し、その後の処理は、
順次探索によって複数の候補を見出すことになる。

【００６６】ステップ５１６では、ステップ５０６と同
様に、検索文字列の当該Ｎ文字パターンが索引ファイル
で見つかったかどうかが判断される。但し、ステップ５
１６がステップ５０６と本質的に異なるのは、ステップ
５１６では、検索文字列の直前のＮ文字パターンに関す
るどれかの文書番号における、どれかの文書内位置番号
をＮだけ増分した文書内位置番号をもつ文字パターンに
ヒットしなければ、見つかったと見なされない、という
ことである。

【００６７】ステップ５１６で、検索文字列の当該Ｎ文
字パターンが見つからなかったと判断されると、好適に
は、検索文字列が見つからなかったことを示すメッセー
ジ・ボックスがステップ５０８で表示され、処理は終了
する。

【００６８】ステップ５１６で、検索文字列の当該Ｎ文
字パターンが見つかったと判断されると、索引ファイル
の検索の結果返される文書番号とその文書番号における
少なくとも１つの文書内位置番号のうち１つ前のＮ文字
パターンの情報と同一文書内で位置番号が順次的にリン
クされるもののみ、ステップ５１８で、後の処理のため
主記憶またはディスク上の所定のバッファ領域に一旦格
納される。

【００６９】ステップ５１２で、検索文字列が全て検索
されたと判断されると、ステップ５２０に進んで、バッ
ファに格納されている文書番号及び文書内位置番号か
ら、検索文字列が存在する文書番号とその位置が決定さ
れ、ステップ５２２では、その文書番号と文書内位置番
号から、データベース２０２の文書のコンテンツがアク
セスされ、文書検索文字列が存在する文書の該当行が、
好適には個別のウインドウ内に表示される。

【００７０】尚、検索文字列が文書内の特定ブロック
（例：３番目のブロック）にあらわれることを調べるた
めには、上記検索文字列が文書中にあらわれる位置まで
にあらわれる上記文書内の区切り位置を数えて、上記検
索文字列が上記文書内でどのブロック（何番目のブロッ
ク）に位置するかを調べて、指定のブロック番号と比較
すればよい。

【００７１】Ｅ．曖昧検索処理図５で示す処理は、索引ファイルを使用して、いわば厳
密検索を行う処理であったが、本発明に従えば、索引フ
ァイルを使用して、指定された文字列と文字の並びが似
ている文字列を含む、いわゆる曖昧検索処理をも、デー
タベースの個々の文書に関して高速に実行することが可
能である。特に、この方式では、検索したい文字列と、
検索精度（０より大きく１以下）とを指定し、検索した
い文字列との"似ている度合"が指定の検索精度以上であ
る"似ている文字列"を含む文書および"似ている文字列"
の文書内位置を特定するものである。

【００７２】Ｅ１．文字列を似ていると感じる人間の感
覚日本語のわかる人間が見て、文字の並びが似ていてしか
も意味が近いと感じる日本語の文字列には，次のような
ものがある。

【表３】（１）カタカナ語の異表記小さい字と大きい字「ソフトウェア」「ソフトウエ
ア」長音「ー」の有無「コンパイラー」「コンパイラ」中黒「・」の有無「アイビーエム」「アイ・ビー・
エム」その他「ビルディング」「ビルヂング」（２）漢字熟語と漢字熟語の間に助詞等が入ったもの「在宅起訴」「在宅のまま起訴」「政界再編」「政界の再編」（３）漢字熟語の複合語と一部が欠けた組み合わせの複
合語「国立民族博物館」「国立博物館」「民族博物館」（４）省略語などにより一部がかけたもの「ソフトウェア開発」「ソフト開発」（５）入力まちがい「カリフォルニア」「カリフォリニア」

【００７３】これらに共通しているのは、ほとんどの文
字は連続して一致しているが不足文字や余分な文字があ
る、ということである。

【００７４】次に、どちらが似ているかという観点から
いくつかの言葉を考えてみると、「ソフトメーカー」に
似ているのは、「ソフトのメーカー」、「ソフト開発メ
ーカー」、「ソフトの開発メーカー」の順であるし、
「政治資金規正法案」と比べるならば、「政治資金規正
法」、「政治資金規正」、「政治資金」の順に似ている
と感じる。

【００７５】また、文字が一致するとはいっても、「ソ
フトクリーム製造機械の製造を主業務とする機械メーカ
ー」を「ソフトメーカー」を似ている文字列と言うには
無理があると感じられる。

【００７６】これらのことから、文字列を似ていると感
じるかどうかの人間の感覚をまとめると、

【００７７】(A) 連続して一致する文字が多いほど似て
いると感じ、(B) 途中にはさまる不一致文字が多いほど
似ていないと感じ、(C) 途中にはさまる不一致文字が多
すぎると一つの文字列とは感じられないということがい
える。

【００７８】このとき、入力文字列のある部分が文書中
の近い位置で重複して出現する特殊な場合を考慮しなく
てはならない。例をあげると、入力文字列が「理学部長
に就任」、文書中に「理学部部長に就任」とあった場合
である。重複して出現している「部」という文字の一方
は余分な文字であるが、「理学部の長に就任」の「の」
のようにまったく無関係な文字よりは、一致文字に近い
文字と考えるのが妥当である。

【００７９】Ｅ２．索引ファイルの構造との整合性図３で示す索引ファイルの構造は、Ｎ文字の文字パター
ンを文書番号・文書内位置番号と索引づけしたものであ
り、検索処理の最小単位は、ひとつの文字パターンを探
して、その文書番号・文書内位置番号を得る処理であ
る。Ｎ文字未満の文字列を検索する場合には、検索した
い文字列で始まる文字パターンのすべてについて、その
個数分、最小単位の検索処理を繰り返す必要があり、そ
の個数はかなり多い場合がある。入力文字列がＮ文字以
上の検索は高々入力文字列の文字数の回数の最小単位検
索を実行すればよいのに比べて、Ｎ文字未満の入力文字
列の検索は負荷が大きいといえる。

【００８０】したがって、Ｎ文字未満の部分一致は切り
捨てて、Ｎ文字以上連続して一致する部分を元に似てい
る文字列を決めることが、高速性を保つために適当と言
える。

【００８１】Ｅ３．似ている文字列と似ている度合いの
決定ルール入力文字列とＭ文字以上連続で一致する文字列の中か
ら、互いに入力文字列中と同じ順序関係である程度近く
にあるものを集めて似ている文字列とし、一致する文字
数、一致しない文字数から、似ている度合いを決めるの
がルールの概要である。

【００８２】まず、説明で使う言葉を定義する。

【００８３】一致文字列：検索したい文字列と文書テキ
ストとがＭ文字以上連続して一致する部分。同じ文字か
ら始めた中では長さが最大になるものを選ぶ。

【００８４】（例）検索したい文字列 : 政治資金規正法案文書テキスト : ...資金規正のために法の力で...

【００８５】Ｍ＝２とする。すると、「資金規正」が
一致文字列。このとき、最長選択のため「資金」や「資
金規」は一致文字列とは呼ばない。また、「法」は２文
字未満なので一致文字列にはならない。

【００８６】有効一致文字列：似ている文字列を構成す
る一致文字列。

【００８７】最大不一致文字列長Ｌ：似ている文字列中
に含める不一致文字は連続Ｌ文字までとする。Ｌは１以
上の定数とする。

【００８８】"似ている文字列"の選びだし方と、"似て
いる度合い"の数値化の方法について説明する。

【００８９】(1) １番目の有効一致文字列の決定文書中での順序で、１番目の一致文字列を、１番目の有
効一致文字列とする。ここで、

【００９０】ｉ番目の有効一致文字列の文書中での開始
位置を s(D, i) ｉ番目の有効一致文字列の文書中での終了位置を e(D,
i) ｉ番目の有効一致文字列の検索したい文字列中での開始
位置を s(C, i) ｉ番目の有効一致文字列の検索したい文字列中での終了
位置を e(C, i) と表記することにする。

【００９１】(2) 次の有効一致文字列の決定ｉ番目の有効一致文字列が決定しているとき、ｉ＋１番
目の有効一致文字列を次のようにして決定する。

【００９２】次の２つの条件a),b)を満たす最初の一致
文字列を、ｉ＋１番目の有効一致文字列とする。

【００９３】

【数１】 a) e(D, i) + 1 ≦ s(D, i+1) ≦ e(D, i) + L + 1

【００９４】これはｉ番目の有効一致文字列とｉ＋１番
目の有効一致文字列の間に入る余分な文字はＬ文字まで
許すことを意味する。（後述する例３参照）

【数２】b) s(C, i+1) ＞ e(C, i) - (M-1)

【００９５】そのような有効一致文字列が選べなくなる
まで繰り返す。

【００９６】(3) "似ている文字列"とその"似ている度
合い"（類似度）の決定それ以上有効一致文字列が選べなくなったら１番目の有
効一致文字列の最初の文字から最後の有効一致文字列の
最後の文字までを"似ている文字列"とし、次の式で"似
ている度合い"を計算する。

【数３】類似度 =minimum ( 検索したい文字列中で有効
一致文字列に属している文字数/ 検索したい文字列の文
字数,"似ている文字列"中で有効一致文字列に属してい
る文字数/ "似ている文字列"の文字数)

【００９７】Ｅ４．．"似ている文字列"中で有効一致文字列に属している文
字数の数え方２つの文字が、検索したい文字列の同一文字と対応して
いる場合には１つ目は１と数え、２つ目は０．５と数え
る。その他の場合には１文字を１と数える。（後述する
例４を参照）

【００９８】Ｅ５．"似ている文字列"の決定順序１番目の"似ている文字列"は文書の先頭から比較を始め
て決定する。ｉ番目の"似ている文字列"が決定している
時、ｉ＋１番目の"似ている文字列"は、ｉ番目の"似て
いる文字列"の先頭の文字より後ろで、ｉ番目の"似てい
る文字列"を構成する有効一致文字列に属さない最初の
文字から比較を始めて決定する。

【００９９】定数Ｌ,Ｍを適当な値に設定することによ
り、文字の並びが似ているかどうかについて、人間の一
般的な判断とかなり一致した"似ている度合い"を算出す
ることができる。

【０１００】なお、"似ている度合い"が最高値１になる
とき、文字列は完全に一致しており、また、文字列が完
全に一致していれば必ず"似ている度合い"は１になる。Ｅ６．曖昧検索の処理フローチャート以上の処理をフローチャートであらわすと、図６のよう
になる。図６では先ず、ステップ６０２で、検索文字列
の入力がプロンプトされる。また、ステップ６０４で
は、０〜１の類似度の入力がプロンプトされる。通常、
ステップ６０２とステップ６０４における文字列及び値
の入力は、単一のダイアログ・ボックスで、入力ボック
スとスクロール・バーを使用して行われる。

【０１０１】ステップ６０６では、有効一致文字列の番
号ｉが１にセットされ、ステップ６０８では、有効一致
文字列の検索が行われる。今、有効一致文字列の長さが
Ｍ以上であるという条件があったとすると、図４の処理
で、Ｍ文字パターンの索引ファイルを作成しておけば有
利である。というのは、そのような索引ファイルが予め
存在すると、任意のＭ文字パターンの検索が、索引ファ
イルの２分探索によって高速に実行されるからである。
続いて、検索文字列での、Ｍ文字パターンをとる開始位
置を１つずらしＭ文字パターンの検索を索引ファイルで
行い、その結果得られた文書番号が一回前のＭ文字パタ
ーンの検索と同一であり、且つ、文書内位置番号が順次
的であれば、Ｍ＋１の長さの有効一致文字列が得られた
ことになる。そのようにして、文書番号が一回前のＭ文
字パターンの検索と同一であり、且つ、文書内位置番号
が順次的である、という条件が満たされる毎に、有効一
致文字列の長さも１つ増分される。しかし、索引ファイ
ルを使用したＭ文字パターンの探索で何も見つからない
か、返される文書番号が不一致か、文書内位置番号が順
次的でなくなれば、有効一致文字列の終了位置が見出さ
れたことになる。

【０１０２】場合によっては、全く有効一致文字列が見
出されないこともあり、そのような場合、ステップ６１
０での判断で、ステップ６２６に進み、そこで、見つか
らなかったことを表示して処理を終了する。

【０１０３】ステップ６１０で、有効一致文字列が見つ
かったと判断されると処理は、ステップ６１２に進み、
文書中ではs(D,i)からe(D,i)、検索文字列中ではs(C,i)
からe(C,i)までが、有効文字列であるとしてマークされ
る。

【０１０４】ステップ６１４では、

【数４】 a) e(D, i) + 1 ≦ s(D, i+1) ≦ e(D, i) + L + 1 且つ、 b) s(C, i) ＞ e(C, i) - (M-1)

【０１０５】という条件をみたす、i+1番目の有効一致
文字列がやはり索引ファイルを使用して検索され、もし
見つかると、ステップ６１２に戻って、そのi+1番目の
有効一致文字列に関して、文書中ではs(D,i+1)からe(D,
i+1)、検索文字列中ではs(C,i+1)からe(C,i+1)までが、
有効文字列であるとしてマークされる（ステップ６１８
でのiの増分は、次の有効一致文字列に注目することを
示す）。

【０１０６】一方、ステップ６１６で、最早有効一致文
字列が見つからなくなると、ステップ６２０で、類似度
の計算が行われる。これは、上述のように例えば、

【０１０７】

【数５】類似度 =minimum ( 検索したい文字列中で有効
一致文字列に属している文字数/ 検索したい文字列の文
字数,"似ている文字列"中で有効一致文字列に属してい
る文字数/ "似ている文字列"の文字数)

【０１０８】で与えられる。このとき、"似ている文字
列"とは、文書中の、最初の有効一致文字列の開始位置
から、最後の有効一致文字列の最後の位置までの間の文
字列である。

【０１０９】ステップ６２２では、ステップ６２０で計
算された類似度と、ステップ６０４で入力された類似度
とから、結果の選別が行われ、結果がステップ６０４で
入力された類似度以上であるもののみ、ステップ６２４
で結果表示を行う。

【０１１０】ステップ６２４では、ステップ６０８、ス
テップ６１４での索引ファイルの検索の結果返された文
書番号と、文書内位置番号に基づいて、データベースに
格納されている文書コンテンツにアクセスし、該当箇所
を含む行を表示する処理が行われる。

【０１１１】尚、１つの検索文字列に対する"似ている
文字列"は、複数の文書で同時に見つかることがあり得
るが、単一の文書内でも、複数の箇所で見つかることが
ある。従って、ステップ６０６〜６２２は、そのような
複数の"似ている文字列"の個々に対して適用され、ステ
ップ６２４では、複数の"似ている文字列"のうち、類似
度の条件を満たすもののみが選別して表示される、とい
うことに留意されたい。

【０１１２】Ｅ７．"似ている文字列"と類似度の決定例Ｍ = ２, Ｌ = ３として例を示す。

【０１１３】(例１) （*アイビーエムは、ＩＢＭ社の商標である）

【０１１４】

【０１１５】最初に一致する最長文字列は"アイ" だか
ら

【０１１６】１番目の有効一致文字列は"アイ" s(C,1) = 1 e(C,1) = 2 s(D,1) = 1 e(D,1) = 2

【０１１７】e(C,1)-(M-1) = 1 なので、検索したい文
字列の２文字目以降から始まる文字列を、文書の３，
４，５または６文字目から始まる文字列と比較して２番
目の有効一致文字列を探す( e(D,1)+1 = 3, e(D,1)+L+1
= 6 なので )。

【０１１８】２番目の有効一致文字列 "ビー" s(C,2) = 3 e(C,2) = 4 s(D,2) = 4 e(D,2) = 5

【０１１９】e(C,1)-(M-1) = 3 なので、検索したい文
字列の４文字目以降から始まる文字列を文書の５，６，
７または８文字目から始まる文字列と比較して３番目の
有効一致文字列を探す( e(D,2)+1 = 5, e(D,2)+L+1 = 8
なので )。３番目の有効一致文字列 "エム" s(C,3) = 5 e(C,3) = 6 s(D,3) = 7 e(D,3) = 8

【０１２０】検索したい文字列の最後に到達したので有
効一致文字列は３番目が最後となる。

【０１２１】

【表４】

【０１２２】番号は有効一致文字列の番号。

【０１２３】したがって"似ている文字列"は s(D, 1)
から e(D, 3) までの"アイ・ビー・エム"。 "類似度" = minimum( 6 / 6 , 6 / 8 ) = 6 / 8 = 0.75

【０１２４】(例２)

【表５】

【０１２５】

【表６】

【０１２６】似ている文字列 = "ソフト開発メーカー" 類似度 = minimum( 7 / 10 , 7 / 9 ) = 0.7

【０１２７】(例３)

【表７】

【表８】 1 2 3 4 5 6 7 8 9 101112131415 文書 D : 在宅のままで起訴にふみきった。

【０１２８】最初に一致する最長文字列は"在宅" だか
ら

【数６】１番目の有効一致文字列は在宅 s(C, 1) = 1 e(C, 1) = 2 s(D, 1) = 1 e(D, 1) = 2

【０１２９】文書の３，４，５または６文字目から始ま
る文字列と( e(D,1)+1 = 3, e(D,1)+L+1 = 6 なので )
検索したい文字列の２文字目以降から始まる文字列を(
e(C,1)-(M-1) = 1なので )比較して２番目の有効一致文
字列を探す。

【０１３０】２番目の有効一致文字列は見つからないの
で、検索したい文字列の最後に到達したので有効一致文
字列は１番目のみとなる。

【表９】在宅起訴 1 在宅のままで起訴にふみきった。 1

【０１３１】したがって１番目の"似ている文字列"は s
(D, 1) から e(D, 1) までの"在宅"。 "類似度" = minimum( 2 / 4 , 2 / 2 ) = 2 / 4 = 0.5

【０１３２】"在"より後ろで最初の非有効一致文字は"
の"。"の"から後ろで２番目の"似ている文字列"を探す
と、

【表１０】在宅起訴 1 在宅のままで起訴にふみきった。 1

【０１３３】但し、文書で、「在宅」と「起訴」と
は、４文字離れており、この例では、Ｌ＝３なので、上
記の「起訴」は、有効一致文字列とは見なさない。

【０１３４】(例４)

【表１１】

【０１３５】最初に一致する最長文字列は"銀行" だか
ら

【０１３６】

【数７】１番目の有効一致文字列は"銀行" s(C,1) = 1 e(C,1) = 2 s(D,1) = 2 e(D,1) = 3

【０１３７】検索したい文字列の２文字目以降から始ま
る文字列を( e(C,1)-(M-1)=1なので)文書の４，５，６
または７文字目から始まる文字列と( e(D,1)+1 = 4, e
(D,1)+L+1 = 7 なので )比較して２番目の有効一致文字
列を探す。

【０１３８】２番目の有効一致文字列は"行員" s(C,2) = 2 e(C,2) = 3 s(D,2) = 4 e(D,2) = 5

【０１３９】検索したい文字列の最後に到達したので有
効一致文字列は２つ。

【表１２】 1, 1, 0.5, 1 -> 3.5

【０１４０】"似ている文字列"は s(D, 1) から e(D,
2) までの"銀行行員"。"類似度" = minimum( 3 / 3 ,
3.5 / 4 ) = 3.5 / 4 = 0.875

【０１４１】Ｅ８．人間の感覚に近い曖昧の例

【表１３】ソフトウェアメーカーソフトウェアのメーカー 0.909 ソフトウェア開発メーカー 0.833 ソフトウェアの開発メーカー 0.769

【０１４２】この例は、余分な文字が入るにつれて"類
似度"が低下することを示す。

【表１４】ニットウェアメーカー 0.800 ソフトメーカー 0.700 ソフトウェア 0.600

【０１４３】この例は、一致する文字が減るにつれて"
類似度"が低下することを示す。

【表１５】理学部長選挙理学部長選挙 1.000 理学部部長選挙 0.929 理学の部長選挙 0.857

【０１４４】Ｅ９．索引の構造と"似ている文字列"の検
索の関係Ｍの値を適当に定めることにより、"似ている文字列"を
探すあいまい検索は、本発明の索引の構造でかなり高速
に実現できる。

【０１４５】定数Ｎ,Ｍの定め方

【表１６】Ｎ: 索引に格納する文字パターンの文字数Ｍ: あいまい検索における有効一致文字列の最低長Ｌ: あいまい検索において、"似ている文字列"中の非有
効一致文字列の最大長

【０１４６】Ｎを大きくすると、文字パターンの種類数
が増加し、文字パターン１つあたりのデータ量は減少す
るので、検索はより速くなるが、索引ファイルの容量は
増加する。平均的な日本語の文書では、Ｎ = ２で充分
な検索速度が得られる。

【０１４７】また、Ｍ≧ＮとなるようにMを定めれば、
あいまい検索において充分な検索速度が得られる。Ｍは
小さいほど、きめ細かなあいまい検索ができることから
考えると、Ｍ=Ｎとなるように決めることがよいと思わ
れる。

【０１４８】Ｅ１０．類似度決定の第２の実施例

【０１４９】第２の実施例の曖昧検索処理では特に、
「途中にはさまる不一致文字が多いほど似ていないと感
じる」ということと、「途中にはさまる不一致文字が多
すぎると一つの文字列とは感じられない」ということの
かねあいについて考慮される。文書中に入力文字列と一
致する文字列、不一致な文字列、一致する文字列の順に
並んでいた場合に、後者の一致文字列までを似ている文
字列として取りこむことによって、似ている度合いが下
がるのは不自然である。たとえば、入力文字列が「在宅
起訴」、文書１には「在宅のまま起訴」、文書２には
「在宅」とあった場合、 ”文書１は「在宅のまま起
訴」、文書２は「在宅」が似ている文字列であり、似て
いる度合いは「在宅」の方が高い”とするようなルール
は人間の感覚に反している。文書１が「起訴」というさ
らなる一致文字列があるがために、逆に低い評価を受け
るのは不自然である。「在宅のまま起訴」の似ている度
合いが「在宅」より高くなるか、あるいは、文書１の似
ている文字列は「在宅」と「起訴」の２つであると判断
されるかのどちらかが、自然である。

【０１５０】次に、第２の実施例の処理について説明す
る。図６のフローチャートを参照すると、この実施例で
は、ステップ６０２〜６１２までは同一であり、i+1番
目の有効一致文字列を検索するための条件を示すステッ
プ６１４の処理が次のように変更される。

【０１５１】

【数８】s(C, i+1) > e(C, i) - (M - 1) ... (式１) s(D, i+1) > e(D, i) ... (式２) 且つ s(D, i+1) - e(D, i) - 1 + max(e(C, i) - s(C, i+1) + 1, 0) ≦ L ・・・ (式３)

【０１５２】尚、s(C, i)、e(C, i)、s(D, i)、s(D, i)
などの定義は、前述のとおりである。

【０１５３】式１は、前述の「理学部部長」の「部」の
ような重複出現文字をＭ−１文字（まで許容し、それ以
外は入力文字列中での文字の順序と同じ順序で出現する
文字列を有効とすることを意味する。

【０１５４】式２は、文書中で有効一致文字列どうしが
重ならないことを意味する。

【０１５５】式３は、間にはさまる不一致文字と「理学
部部長」の「部」のような重複出現文字を、あわせてＬ
文字まで許容することを意味する。

【０１５６】この実施例では、前の実施例のように、検
索文字列と、文書中の似ている文字列の各々で、有効一
致文字列が占める割合を計算し、そのうちの小さい方を
類似度として選ぶのではなく、似ている文字列に点数を
つけて、満点（完全に一致している場合の点数）で割っ
て割合を出すことによって算出する。似ている文字列の
点数は、各文字に次の規則で点数をつけてそれを加算す
ることで算出する。従って、図６のステップ６２０での
処理は次のようになる。

【０１５７】１番目の有効一致文字列に属する文字・・・ 1 点ｉ番目（i > 1）の有効一致文字列に属していて検索文字列における位置≧e(C,i-1)+1 (式４) ・・・ 1 点検索文字列における位置≦e(C,i-1) (式５) ・・・ -1/(2*L) 点有効一致文字列に属していない文字・・・ -1 / L 点

【０１５８】この実施例でも、ｉ番目の似ている文字列
が決定している時、ｉ＋１番目の似ている文字列は、ｉ
番目の似ている文字列の先頭の文字より後ろで、ｉ番目
の似ている文字列を構成する有効一致文字列に属さない
最初の文字から比較を始めて決定する。

【０１５９】有効一致文字列に属していない文字のマイ
ナス点は、「途中にはさまる不一致文字が多いほど似て
いないと感じる」ということと、「途中にはさまる不一
致文字が多すぎると一つの文字列とは感じられない」と
いうことのかねあいを考慮して設定している。一つの非
一致文字列のマイナス点の合計の最大は1 / L * L =1,
次の一致文字列を取り入れることによるプラス点の最小
はＮ ≧ 1 （特に日本語の場合は２が推奨されている）
でマイナス点がプラス点を上回ることがない。また、式
５は前述の「理学部部長」の「部」のような重複出現文
字を示し、式４は重複出現文字でない単純な一致文字を
示している。式５で表される文字には単純な非一致文字
より小さなマイナス点をつけることで、重複して文字が
あらわれる場合に対処している。

【０１６０】Ｅ１１．第２の実施例での似ている文字列
と似ている度合いの決定例やはり、Ｎ = ２, Ｌ = ３として例を示す。

【表１７】

【０１６１】最初の一致文字列は「アイ」だから１番目
の有効一致文字列は「アイ」

【数９】s(C,1) = 1 e(C,1) = 2 s(D,1) = 1 e(D,1) = 2

【０１６２】式１、式２、式３により２番目の有効一致
文字列は「ビー」

【数１０】s(C,2) = 3 e(C,2) = 4 s(D,2) = 4 e(D,2) = 5

【０１６３】式１、式２、式３により３番目の有効一致
文字列「エム」

【数１１】s(C,3) = 5 e(C,3) = 6 s(D,3) = 7 e(D,3) = 8

【０１６４】入力文字列の最後に到達したので有効一致
文字列は３つとなる。

【表１８】

【０１６５】似ている文字列は s(D, 1) から e(D, 3)
までの「アイ・ビー・エム」。似ている度合い = (( 1
* 6 + (-1/3) * 2 ) / 6 ) = 0.88

【０１６６】

【表１９】（例６） 1 2 3 4 5 6 7 8 9 10 入力文字列 C : ソフトウェアメーカー 1 2 3 4 5 6 7 8 9 文書の一部 D : ・・・ソフト開発メーカー・・・

【０１６７】似ている文字列 = "ソフト開発メーカー" 似ている度合い = ( ( 1 * 7 + (-1/3) * 2 ) / 10 ) =
0.63

【０１６８】

【表２０】 (例７) 1 2 3 4 入力文字列 C : 在宅起訴 1 2 3 4 5 6 7 8 91011121314 文書の一部 D : ・・・在宅のままで起訴にふみきった。・・・

【０１６９】最初の一致文字列は「在宅」だから１番目
の有効一致文字列は「在宅」次の一致文字列「起訴」は式３を満たさないので、有効
一致文字列は１番目のみとなる。

【表２１】 C: 在宅起訴 1 D: 在宅のままで起訴にふみきった。 1

【０１７０】似ている文字列は「在宅」。似ている度合
い = 2 / 4 = 0.5

【０１７１】「在」より後ろで最初の非有効一致文字は
「の」。２番目の似ている文字列は、「の」から後ろで
探す。

【０１７２】 C: 在宅起訴 1 D: 在宅のままで起訴にふみきった。 1

【０１７３】従って、２番目の似ている文字列は、「起
訴」。

【０１７４】

【表２２】

【０１７５】有効一致文字列は「理学部」、「部長に就
任」の２つ。

【０１７６】

【表２３】

【０１７７】似ている文字列は「理学部部長に就任」。
２つ目の「部」は式５を満たしている。そこで、似てい
る度合い = (( 1 * 7 + (-1/6) * 1 ) / 7 ) = 0.97
となる。

【０１７８】Ｅ１２．第２の実施例の結果のまとめ

【表２４】入力文字列文書中類似度 ===================================================== ソフトメーカーソフトのメーカー 0.95 ソフトの開発メーカー 0.85 政治資金規正法案政治資金規正法 0.87 政治資金 0.50 理学部長に就任理学部部長に就任 0.97 理学部の長に就任 0.95

【０１７９】

【発明の効果】以上説明したように、この発明によれ
ば、文書ファイルまたはデータベースにおいて、人間の
感覚に自然な曖昧検索を、固有のインデックス構造を用
いて高速に実現できるという効果が得られる。

【図面の簡単な説明】

【図１】ハードウェア構成を示すブロック図である。

【図２】処理要素のブロック図である。

【図３】索引ファイルの構造を示す図である。

【図４】索引ファイル作成処理を示すフローチャート
である。

【図５】索引ファイルを使用した文字列検索処理のフ
ローチャートである。

【図６】索引ファイルを使用した曖昧検索処理のフロ
ーチャートである。

Claims

【特許請求の範囲】

【請求項１】コンピュータ処理によって検索可能に記憶
された文書中で、検索文字列と、文書中の文字列の類似
度を見出すための方法であって、(a) 検索文字列を入力
する段階と、(b) 上記検索文字列の先頭から、長さＭ文
字以上の（Ｍは、２以上の予定の整数）の部分文字列に
つき、上記文書中で一致する開始位置及び終了位置を見
出す（以下、その開始位置及び終了位置によって決定さ
れるＭ文字以上の長さの部分文字列を有効一致文字列と
称する）段階と、(c) 上記段階(b)で有効一致文字列が
見出されなかったことに応答して、上記検索文字列の部
分文字列の開始位置を１つずらした長さＭ文字以上の
（Ｍは、２以上の予定の整数）の部分文字列につき、上
記有効一致文字列を見出す段階と、(d) 上記有効一致文
字列が見出されたことに応答して、上記検索文字列にお
ける部分文字列の開始位置と、上記文書中での検索の開
始位置とをそれぞれ直前の有効一致文字列の長さだけず
らして、その開始位置の、該直前の有効一致文字列の終
了位置からの距離がＬ文字以内（Ｌは、１以上の予定の
整数）である有効一致文字列を見出す段階と、(e) 上記
有効一致文字列が見つかる限り、上記段階(d)を継続す
る段階と、(f) 少なくとも、上記文書における最初の有
効一致文字列の開始位置から、上記文書における最後の
有効一致文字列の終了位置までの間の文字列における、
有効一致文字列の存在情報に基づき、上記検索文字列
と、上記文書における最初の有効一致文字列の開始位置
から、上記文書における最後の有効一致文字列の終了位
置までの間の文字列との間の類似度を計算する段階を有
する、情報検索方法。
【請求項２】上記Ｍが２であり、上記Ｌが３以上であ
る、請求項１に記載の情報検索方法。
【請求項３】上記類似度の計算は、検索文字列における
有効一致文字列が占める割合と、上記文書における最初
の有効一致文字列の開始位置から、上記文書における最
後の有効一致文字列の終了位置までの間の文字列におけ
る有効一致文字列が占める割合のうちの小さい方の値を
利用して行われる、請求項１に記載の情報検索方法。
【請求項４】上記類似度の計算は、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列の個
々の文字において、それが有効一致文字列に属するとき
は加点し、そうでないときは減点し、結果の得点値を、
完全一致の得点値で割った値を利用して行われる、請求
項１に記載の情報検索方法。
【請求項５】コンピュータ処理によって検索可能に記憶
された文書中で、検索文字列があらわれる位置を見出す
ための情報検索方法であって、(a) 検索文字列を入力す
る段階と、(b) 類似度を入力する段階と、(c) 上記検索
文字列の先頭から、長さＭ文字以上の（Ｍは、２以上の
予定の整数）の部分文字列につき、上記文書中で一致す
る開始位置及び終了位置を見出す（以下、その開始位置
及び終了位置によって決定されるＭ文字以上の長さの部
分文字列を有効一致文字列と称する）段階と、(d) 上記
段階(c)で有効一致文字列が見出されなかったことに応
答して、上記検索文字列の部分文字列の開始位置を１つ
ずらした長さＭ文字以上の（Ｍは、２以上の予定の整
数）の部分文字列につき、上記有効一致文字列を見出す
段階と、(e) 上記有効一致文字列が見出されたことに応
答して、上記検索文字列における部分文字列の開始位置
と、上記文書中での検索の開始位置とをそれぞれ直前の
有効一致文字列だけずらして、その開始位置の、該直前
の有効一致文字列の終了位置からの距離がＬ文字以内
（Ｌは、１以上の予定の整数）である有効一致文字列を
見出す段階と、(f) 上記有効一致文字列が見つかる限
り、上記段階(e)を継続する段階と、(g) 少なくとも、
上記文書における最初の有効一致文字列の開始位置か
ら、上記文書における最後の有効一致文字列の終了位置
までの間の文字列における、有効一致文字列の存在情報
に基づき、上記検索文字列と、上記文書における最初の
有効一致文字列の開始位置から、上記文書における最後
の有効一致文字列の終了位置までの間の文字列との間の
類似度を計算する段階と、(h) 上記計算された類似度
が、上記段階(b)で入力された類似度以上であることに
応答して、上記文書の上記有効一致文字列を含む内容を
表示する段階を有する、情報検索方法。
【請求項６】上記Ｍが２であり、上記Ｌが３以上であ
る、請求項５に記載の情報検索方法。
【請求項７】上記類似度の計算は、検索文字列における
有効一致文字列が占める割合と、上記文書における最初
の有効一致文字列の開始位置から、上記文書における最
後の有効一致文字列の終了位置までの間の文字列におけ
る有効一致文字列が占める割合のうちの小さい方の値を
利用して行われる、請求項５に記載の情報検索方法。
【請求項８】上記類似度の計算は、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列の個
々の文字において、それが有効一致文字列に属するとき
は加点し、そうでないときは減点し、結果の得点値を、
完全一致の得点値で割った値を利用して行われる、請求
項５に記載の情報検索方法。
【請求項９】上記加点が、１つの文字について１であ
り、上記減点が、１つの文字について１／Ｌである、請
求項８に記載の情報検索方法。
【請求項１０】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースで、検索文字列
と、文書中の文字列の類似度を見出すための方法であっ
て、(a) 検索文字列を入力する段階と、(b) 上記検索文
字列の先頭から、長さＭ文字以上の（Ｍは、２以上の予
定の整数）の部分文字列につき、上記データベースの同
一文書中で一致する開始位置及び終了位置を見出す（以
下、その開始位置及び終了位置によって決定されるＭ文
字以上の長さの部分文字列を有効一致文字列と称する）
段階と、(c) 上記段階(b)で有効一致文字列が見出され
なかったことに応答して、上記検索文字列の部分文字列
の開始位置を１つずらした長さＭ文字以上の（Ｍは、２
以上の予定の整数）の部分文字列につき、上記有効一致
文字列を見出す段階と、(d) 上記有効一致文字列が見出
されたことに応答して、上記検索文字列における部分文
字列の開始位置と、上記同一文書中での検索の開始位置
とをそれぞれ直前の有効一致文字列の長さだけずらし
て、その開始位置の、該直前の有効一致文字列の終了位
置からの距離がＬ文字以内（Ｌは、１以上の予定の整
数）である有効一致文字列を見出す段階と、(e) 上記有
効一致文字列が見つかる限り、上記段階(d)を継続する
段階と、(f) 少なくとも、上記文書における最初の有効
一致文字列の開始位置から、上記同一文書における最後
の有効一致文字列の終了位置までの間の文字列におけ
る、有効一致文字列の存在情報に基づき、上記検索文字
列と、上記同一文書における最初の有効一致文字列の開
始位置から、上記文書における最後の有効一致文字列の
終了位置までの間の文字列との間の類似度を計算する段
階を有する、情報検索方法。
【請求項１１】上記Ｍが２であり、上記Ｌが３である、
請求項１０に記載の情報検索方法。
【請求項１２】上記類似度の計算は、検索文字列におけ
る有効一致文字列が占める割合と、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列にお
ける有効一致文字列が占める割合のうちの小さい方の値
を利用して行われる、請求項１０に記載の情報検索方
法。
【請求項１３】上記類似度の計算は、上記文書における
最初の有効一致文字列の開始位置から、上記文書におけ
る最後の有効一致文字列の終了位置までの間の文字列の
個々の文字において、それが有効一致文字列に属すると
きは加点し、そうでないときは減点し、結果の得点値
を、完全一致の得点値で割った値を利用して行われる、
請求項１０に記載の情報検索方法。
【請求項１４】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースにおいて、検索
文字列があらわれる箇所を見出すための情報検索方法で
あって、(a) 検索文字列を入力する段階と、(b) 類似度
を入力する段階と、(c) 上記検索文字列の先頭から、長
さＭ文字以上の（Ｍは、２以上の予定の整数）の部分文
字列につき、上記データベースの同一文書中で一致する
開始位置及び終了位置を見出す（以下、その開始位置及
び終了位置によって決定されるＭ文字以上の長さの部分
文字列を有効一致文字列と称する）段階と、(d) 上記段
階(c)で有効一致文字列が見出されなかったことに応答
して、上記検索文字列の部分文字列の開始位置を１つず
らした長さＭ文字以上の（Ｍは、２以上の予定の整数）
の部分文字列につき、上記有効一致文字列を見出す段階
と、(e) 上記有効一致文字列が見出されたことに応答し
て、上記検索文字列における部分文字列の開始位置と、
上記同一文書中での検索の開始位置とをそれぞれ直前の
有効一致文字列だけずらして、その開始位置の、該直前
の有効一致文字列の終了位置からの距離がＬ文字以内
（Ｌは、１以上の予定の整数）である有効一致文字列を
見出す段階と、(f) 上記有効一致文字列が見つかる限
り、上記段階(e)を継続する段階と、(g) 少なくとも、
上記同一文書における最初の有効一致文字列の開始位置
から、上記同一文書における最後の有効一致文字列の終
了位置までの間の文字列における、有効一致文字列の存
在情報に基づき、上記検索文字列と、上記同一文書にお
ける最初の有効一致文字列の開始位置から、上記同一文
書における最後の有効一致文字列の終了位置までの間の
文字列との間の類似度を計算する段階と、(h) 上記計算
された類似度が、上記段階(b)で入力された類似度以上
であることに応答して、上記文書の上記有効一致文字列
を含む内容を表示する段階を有する、情報検索方法。
【請求項１５】上記複数の文書に、固有の番号または記
号を予め付与する段階を有する、請求項１４に記載の情
報検索方法。
【請求項１６】上記固有の番号または記号は、順次的な
番号である、請求項１５に記載の情報検索方法。
【請求項１７】上記Ｍが２であり、上記Ｌが３である、
請求項１４に記載の情報検索方法。
【請求項１８】上記類似度の計算は、検索文字列におけ
る有効一致文字列が占める割合と、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列にお
ける有効一致文字列が占める割合のうちの小さい方の値
を利用して行われる、請求項１４に記載の情報検索方
法。
【請求項１９】上記類似度の計算は、上記文書における
最初の有効一致文字列の開始位置から、上記文書におけ
る最後の有効一致文字列の終了位置までの間の文字列の
個々の文字において、それが有効一致文字列に属すると
きは加点し、そうでないときは減点し、結果の得点値
を、完全一致の得点値で割った値を利用して行われる、
請求項１４に記載の情報検索方法。
【請求項２０】上記加点が、１つの文字について１であ
り、上記減点が、１つの文字について１／Ｌである、請
求項１９に記載の情報検索方法。
【請求項２１】コンピュータ処理によって検索可能に記
憶された文書中で、検索文字列があらわれる位置を見出
すための情報検索システムであって、(a) 検索文字列を
入力する手段と、(b) 上記検索文字列の、長さＭ文字以
上の（Ｍは、２以上の予定の整数）の部分文字列につ
き、上記文書中で一致する開始位置及び終了位置を見出
す（以下、その開始位置及び終了位置によって決定され
るＭ文字以上の部分文字列を有効一致文字列と称する）
手段と、(c) 上記検索文字列の先頭から、上記手段(b)
を適用し、有効一致文字列が見出されたことに応答し
て、上記検索文字列における部分文字列の開始位置と、
上記文書中での検索の開始位置とをそれぞれ直前の有効
一致文字列だけずらして、その開始位置の、該直前の有
効一致文字列の終了位置からの距離がＬ文字以内（Ｌ
は、１以上の予定の整数）である有効一致文字列を見出
し、有効一致文字列が見出されなかったことに応答し
て、上記検索文字列の部分文字列の開始位置を１つずら
した長さＭ文字以上の（Ｍは、２以上の予定の整数）の
部分文字列につき、上記有効一致文字列を見出す手段
と、(d) 上記有効一致文字列が見つかる限り、上記手段
(c)を順次適用する手段と、(e) 少なくとも、上記文書
における最初の有効一致文字列の開始位置から、上記文
書における最後の有効一致文字列の終了位置までの間の
文字列における、有効一致文字列の存在情報に基づき、
上記検索文字列と、上記文書における最初の有効一致文
字列の開始位置から、上記文書における最後の有効一致
文字列の終了位置までの間の文字列との間の類似度を計
算する手段を有する、情報検索システム。
【請求項２２】コンピュータ処理によって検索可能に記
憶された文書中で、検索文字列があらわれる位置を見出
すための情報検索システムであって、(a) 検索文字列を
入力する手段と、(b) 類似度を入力する手段と、(c) 上
記検索文字列の、長さＭ文字以上の（Ｍは、２以上の予
定の整数）の部分文字列につき、上記文書中で一致する
開始位置及び終了位置を見出す（以下、その開始位置及
び終了位置によって決定されるＭ文字以上の部分文字列
を有効一致文字列と称する）手段と、(d) 上記検索文字
列の先頭から、上記手段(c)を適用し、有効一致文字列
が見出されたことに応答して、上記検索文字列における
部分文字列の開始位置と、上記文書中での検索の開始位
置とをそれぞれ直前の有効一致文字列だけずらして、そ
の開始位置の、該直前の有効一致文字列の終了位置から
の距離がＬ文字以内（Ｌは、１以上の予定の整数）であ
る有効一致文字列を見出し、有効一致文字列が見出され
なかったことに応答して、上記検索文字列の部分文字列
の開始位置を１つずらした長さＭ文字以上の（Ｍは、２
以上の予定の整数）の部分文字列につき、上記有効一致
文字列を見出す手段と、(e) 上記有効一致文字列が見つ
かる限り、上記手段(d)を順次適用する手段と、(f) 少
なくとも、上記文書における最初の有効一致文字列の開
始位置から、上記文書における最後の有効一致文字列の
終了位置までの間の文字列における、有効一致文字列の
存在情報に基づき、上記検索文字列と、上記文書におけ
る最初の有効一致文字列の開始位置から、上記文書にお
ける最後の有効一致文字列の終了位置までの間の文字列
との間の類似度を計算する手段と、(g) 上記計算された
類似度が、上記段階(b)で入力された類似度以上である
ことに応答して、上記文書の上記有効一致文字列を含む
内容を表示する手段を具備する、情報検索システム。
【請求項２３】上記Ｍが２であり、上記Ｌが３である、
請求項２２に記載の情報検索システム。
【請求項２４】上記類似度の計算は、検索文字列におけ
る有効一致文字列が占める割合と、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列にお
ける有効一致文字列が占める割合のうちの小さい方の値
を利用して行われる、請求項２２に記載の情報検索シス
テム。
【請求項２５】上記類似度の計算は、上記文書における
最初の有効一致文字列の開始位置から、上記文書におけ
る最後の有効一致文字列の終了位置までの間の文字列の
個々の文字において、それが有効一致文字列に属すると
きは加点し、そうでないときは減点し、結果の得点値
を、完全一致の得点値で割った値を利用して行われる、
請求項２２に記載の情報検索システム。
【請求項２６】上記加点が、１つの文字について１であ
り、上記減点が、１つの文字について１／Ｌである、請
求項２５に記載の情報検索システム。
【請求項２７】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースで、検索文字列
があらわれる位置を見出すための情報検索システムであ
って、(a) 検索文字列を入力する手段と、(b) 類似度を
入力する手段と、(c) 上記検索文字列の、長さＭ文字以
上の（Ｍは、２以上の予定の整数）の部分文字列につ
き、上記文書中で一致する開始位置及び終了位置を見出
す（以下、その開始位置及び終了位置によって決定され
るＭ文字以上の部分文字列を有効一致文字列と称する）
手段と、(d) 上記検索文字列の先頭から、上記手段(c)
を適用し、有効一致文字列が見出されたことに応答し
て、上記検索文字列における部分文字列の開始位置と、
上記同一の文書中での検索の開始位置とをそれぞれ直前
の有効一致文字列だけずらして、その開始位置の、該直
前の有効一致文字列の終了位置からの距離がＬ文字以内
（Ｌは、１以上の予定の整数）である有効一致文字列を
見出し、有効一致文字列が見出されなかったことに応答
して、上記検索文字列の部分文字列の開始位置を１つず
らした長さＭ文字以上の（Ｍは、２以上の予定の整数）
の部分文字列につき、上記有効一致文字列を見出す手段
と、(e) 上記有効一致文字列が見つかる限り、上記手段
(d)を順次適用する手段と、(f) 少なくとも、上記同一
の文書における最初の有効一致文字列の開始位置から、
上記同一の文書における最後の有効一致文字列の終了位
置までの間の文字列における、有効一致文字列の存在情
報に基づき、上記検索文字列と、上記同一の文書におけ
る最初の有効一致文字列の開始位置から、上記同一の文
書における最後の有効一致文字列の終了位置までの間の
文字列との間の類似度を計算する手段と、(g) 上記計算
された類似度が、上記段階(b)で入力された類似度以上
であることに応答して、上記文書の上記有効一致文字列
を含む内容を表示する手段を具備する、情報検索システム。
【請求項２８】上記Ｍが２であり、上記Ｌが３である、
請求項２７に記載の情報検索システム。
【請求項２９】上記類似度の計算は、検索文字列におけ
る有効一致文字列が占める割合と、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列にお
ける有効一致文字列が占める割合のうちの小さい方の値
を利用して行われる、請求項２７に記載の情報検索シス
テム。
【請求項３０】上記類似度の計算は、上記文書における
最初の有効一致文字列の開始位置から、上記文書におけ
る最後の有効一致文字列の終了位置までの間の文字列の
個々の文字において、それが有効一致文字列に属すると
きは加点し、そうでないときは減点し、結果の得点値
を、完全一致の得点値で割った値を利用して行われる、
請求項２７に記載の情報検索システム。
【請求項３１】上記加点が、１つの文字について１であ
り、上記減点が、１つの文字について１／Ｌである、請
求項３０に記載の情報検索システム。
【請求項３２】コンピュータ処理によって検索可能に記
憶された文書において、長さＮ文字のパターンを高速に
検索することを可能ならしめる索引ファイルの作成方法
であって、(a) 上記文書を順次走査し、上記文書中に連
続してあらわれる任意のＮ文字パターン、及びそのＮ文
字パターンが上記文書中にあらわれる位置の情報を、記
憶領域に書き出す段階と、(b) 上記段階(a)が、上記文
書全体の走査を完了したことに応答して、上記記憶領域
に書き出された情報を上記文字パターンにつきソート
し、互いに異なる上記文字パターン毎に、上記位置の情
報をまとめて関連付ける段階と、(c) 文字パターンをキ
ーとして、該文字パターンに関連付けられた上記位置の
情報を探索できるように、ファイルを作成し出力する段
階を有する、索引ファイルの作成方法。
【請求項３３】上記段階(c)での探索が２分探索であ
る、請求項３２に記載の索引ファイルの作成方法。
【請求項３４】上記文書におけるＭ文字以上の文字パタ
ーンの検索は、請求項３３の方法で作成された索引ファ
イルを使用し、それによって得られる位置情報を利用す
ることにより行う、請求項１または請求項５に記載の情
報検索方法。
【請求項３５】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースにおいて、長さ
Ｎ文字のパターンを高速に検索することを可能ならしめ
る索引ファイルの作成方法であって、(a) 上記複数の文
書の各々に、それぞれを個別に識別するための符号また
は番号を付与する段階と、(b) 上記データベースを順次
走査し、上記データベースの個々の文書中に連続してあ
らわれる任意のＮ文字パターン、及びそのＮ文字パター
ンが該文書中にあらわれる位置の情報を、該文書の識別
符号または番号に関連付けて記憶領域に書き出す段階
と、(c) 上記段階(b)が、上記データベースの文書全体
の走査を完了したことに応答して、上記記憶領域に書き
出された情報を上記文字パターンにつきソートし、互い
に異なる上記文字パターン毎に、上記文書の識別符号ま
たは番号と、該文書内の位置の情報をまとめて関連付け
る段階と、(d) 文字パターンをキーとして、該文字パタ
ーンに関連付けられた文書の識別符号または番号と、上
記位置の情報を探索できるように、ファイルを作成し出
力する段階を有する、索引ファイルの作成方法。
【請求項３６】上記段階(d)での探索が２分探索であ
る、請求項３５に記載の索引ファイルの作成方法。
【請求項３７】上記文書におけるＭ文字以上の文字パタ
ーンの検索は、請求項３６の方法で作成された索引ファ
イルを使用し、それによって得られる位置情報を利用す
ることにより行う、請求項１０または請求項１４に記載
の情報検索方法。
【請求項３８】上記Ｍ及びＮはともに２であり、上記Ｌ
は３以上である、請求項３７に記載の索引ファイルの作
成方法。
【請求項３９】コンピュータ処理によって検索可能に記
憶された文書において、長さＮ文字のパターンを高速に
検索することを可能ならしめる索引ファイルの作成方法
であって、(a) 上記文書を順次走査し、上記文書中にあ
らわれる、予め指定された文書区切り文字パターン、及
びその区切り文字パターンが上記文書中にあらわれる位
置の情報を、記憶領域に書き出すとともに、上記文書中
に連続してあらわれる任意のＮ文字パターン、及びその
Ｎ文字パターンが上記文書中にあらわれる位置の情報
を、記憶領域に書き出す段階と、(b) 上記段階(a)が、
上記文書全体の走査を完了したことに応答して、上記記
憶領域に書き出された情報を上記文字パターンにつきソ
ートし、互いに異なる上記文字パターン毎に、上記位置
の情報をまとめて関連付ける段階と、(c) 文字パターン
をキーとして、該文字パターンに関連付けられた上記位
置の情報を探索できるように、ファイルを作成し出力す
る段階を有する、索引ファイルの作成方法。
【請求項４０】上記文書におけるＭ文字以上の文字パタ
ーンの検索は、請求項３９の方法で作成された索引ファ
イルを使用し、それによって得られる位置情報を利用す
ることにより行う、請求項１または請求項５に記載の情
報検索方法。
【請求項４１】上記文書中の区切り文字パターンを検索
してそれによって得られる位置情報を、上記文書におけ
るＭ文字以上の文字パターンの検索によって得られる位
置情報とを関連付ける段階をさらに有する、請求項４０
に記載の情報検索方法。
【請求項４２】コンピュータ処理によって検索可能に記
憶された文書において、長さＮ文字のパターンを高速に
検索することを可能ならしめる索引ファイルの作成シス
テムであって、(a) 上記文書を順次走査し、上記文書中
に連続してあらわれる任意のＮ文字パターン、及びその
Ｎ文字パターンが上記文書中にあらわれる位置の情報
を、記憶領域に書き出す手段と、(b) 上記手段(a)が、
上記文書全体の走査を完了したことに応答して、上記記
憶領域に書き出された情報を上記文字パターンにつきソ
ートし、互いに異なる上記文字パターン毎に、上記位置
の情報をまとめて関連付ける手段と、(c) 文字パターン
をキーとして、該文字パターンに関連付けられた上記位
置の情報を探索できるように、ファイルを作成し出力す
る手段を有する、索引ファイルの作成システム。
【請求項４３】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースにおいて、長さ
Ｎ文字のパターンを高速に検索することを可能ならしめ
る索引ファイルの作成システムであって、(a) 上記複数
の文書の各々に、それぞれを個別に識別するための符号
または番号を付与する手段と、(b) 上記データベースを
順次走査し、上記データベースの個々の文書中に連続し
てあらわれる任意のＮ文字パターン、及びそのＮ文字パ
ターンが該文書中にあらわれる位置の情報を、該文書の
識別符号または番号に関連付けて記憶領域に書き出す手
段と、(c) 上記手段(b)が、上記データベースの文書全
体の走査を完了したことに応答して、上記記憶領域に書
き出された情報を上記文字パターンにつきソートし、互
いに異なる上記文字パターン毎に、上記文書の識別符号
または番号と、該文書内の位置の情報をまとめて関連付
ける手段と、(d) 文字パターンをキーとして、該文字パ
ターンに関連付けられた文書の識別符号または番号と、
上記位置の情報を探索できるように、ファイルを作成し
出力する手段を有する、索引ファイルの作成システム。
【請求項４４】上記Ｎは２である、請求項４３に記載の
索引ファイルの作成システム。
【請求項４５】コンピュータ処理によって検索可能に記
憶された文書において、長さＮ文字のパターンを高速に
検索することを可能ならしめる索引ファイルの作成シス
テムであって、(a) 上記文書を順次走査し、上記文書中
にあらわれる、予め指定された文書区切り文字パター
ン、及びその区切り文字パターンが上記文書中にあらわ
れる位置の情報を、記憶領域に書き出すとともに、上記
文書中に連続してあらわれる任意のＮ文字パターン、及
びそのＮ文字パターンが上記文書中にあらわれる位置の
情報を、記憶領域に書き出す手段と、(b) 上記手段(a)
が、上記文書全体の走査を完了したことに応答して、上
記記憶領域に書き出された情報を上記文字パターンにつ
きソートし、互いに異なる上記文字パターン毎に、上記
位置の情報をまとめて関連付ける手段と、(c) 文字パタ
ーンをキーとして、該文字パターンに関連付けられた上
記位置の情報を探索できるように、ファイルを作成し出
力する手段を有する、索引ファイルの作成システム。
【請求項４６】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースにおいて、長さ
Ｎ文字のパターンを高速に検索することを可能ならしめ
る索引ファイルの作成システムであって、(a) 上記複数
の文書の各々に、それぞれを個別に識別するための符号
または番号を付与する手段と、(b) 上記データベースを
順次走査し、上記データベースの個々の文書中にあらわ
れる、予め指定された文書区切り文字パターン、及びそ
の区切り文字パターンが上記文書中にあらわれる位置の
情報を、該文書の識別符号または番号に関連付けて記憶
領域に書き出すとともに、上記データベースの個々の文
書中に連続してあらわれる任意のＮ文字パターン、及び
そのＮ文字パターンが該文書中にあらわれる位置の情報
を、該文書の識別符号または番号に関連付けて記憶領域
に書き出す手段と、(c) 上記手段(b)が、上記データベ
ースの文書全体の走査を完了したことに応答して、上記
記憶領域に書き出された情報を上記文字パターンにつき
ソートし、互いに異なる上記文字パターン毎に、上記文
書の識別符号または番号と、該文書内の位置の情報をま
とめて関連付ける手段と、(d) 文字パターンをキーとし
て、該文字パターンに関連付けられた文書の識別符号ま
たは番号と、上記位置の情報を探索できるように、ファ
イルを作成し出力する手段を有する、索引ファイルの作成システム。
【請求項４７】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースにおいて、検索
文字列があらわれる箇所を見出すための情報検索方法で
あって、(a) 検索文字列を入力する段階と、(b) 類似度
を入力する段階と、(c) 上記検索文字列の先頭から、長
さＭ文字以上の（Ｍは、２以上の予定の整数）の部分文
字列につき、上記データベースの同一文書中で一致する
開始位置及び終了位置を見出す（以下、その開始位置及
び終了位置によって決定されるＭ文字以上の長さの部分
文字列を有効一致文字列と称する）段階と、(d)ｉ番目
の有効一致文字列の文書中での開始位置を s(D, i) ｉ番目の有効一致文字列の文書中での終了位置を e(D,
i) ｉ番目の有効一致文字列の検索したい文字列中での開始
位置を s(C, i) ｉ番目の有効一致文字列の検索したい文字列中での終了
位置を e(C, i) として、 e(D, i) + 1 ≦ s(D, i+1) ≦ e(D, i) + L + 1 且つ s(C, i+1) > e(C,i) - (M-1) （この式で、Ｌは、１以上の予定の整数）という条件を満たすi+i番目の有効一致文字列を見出す
段階と、(e) 上記有効一致文字列が見つかる限り、上記
段階(d)を継続する段階と、(f) 少なくとも、上記同一
文書における最初の有効一致文字列の開始位置から、上
記同一文書における最後の有効一致文字列の終了位置ま
での間の文字列における、有効一致文字列の存在情報に
基づき、上記検索文字列と、上記同一文書における最初
の有効一致文字列の開始位置から、上記同一文書におけ
る最後の有効一致文字列の終了位置までの間の文字列と
の間の類似度を計算する段階と、(g) 上記計算された類
似度が、上記段階(b)で入力された類似度以上であるこ
とに応答して、上記文書の上記有効一致文字列を含む内
容を表示する段階を有する、情報検索方法。
【請求項４８】上記Ｍが２であり、上記Ｌが３以上であ
る、請求項４７に記載の情報検索方法。
【請求項４９】上記類似度の計算は、検索文字列におけ
る有効一致文字列が占める割合と、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列にお
ける有効一致文字列が占める割合のうちの小さい方の値
を利用して行われる、請求項４７に記載の情報検索方
法。
【請求項５０】上記文書における最初の有効一致文字列
の開始位置から上記文書における最後の有効一致文字列
の終了位置までの間における有効一致文字列が占める割
合を算出するために、上記検索文字列中で複数の有効一
致文字列に属する文字をそれ以外の文字より低い重み付
けをする、請求項４７に記載の情報検索方法。
【請求項５１】コンピュータ処理によって検索可能に記
憶された複数の文書を含むデータベースにおいて、検索
文字列があらわれる箇所を見出すための情報検索方法で
あって、(a) 検索文字列を入力する段階と、(b) 類似度
を入力する段階と、(c) 上記検索文字列の先頭から、長
さＭ文字以上の（Ｍは、２以上の予定の整数）の部分文
字列につき、上記データベースの同一文書中で一致する
開始位置及び終了位置を見出す（以下、その開始位置及
び終了位置によって決定されるＭ文字以上の長さの部分
文字列を有効一致文字列と称する）段階と、(d)ｉ番目
の有効一致文字列の文書中での開始位置を s(D, i) ｉ番目の有効一致文字列の文書中での終了位置を e(D,
i) ｉ番目の有効一致文字列の検索したい文字列中での開始
位置を s(C, i) ｉ番目の有効一致文字列の検索したい文字列中での終了
位置を e(C, i) として、 s(C, i+1) > e(C, i) - (M - 1)、 s(D, i+1) > e(D, i) 且つ s(D, i+1) - e(D, i) - 1 + max(e(C, i) - s(C, i+1)
+ 1, 0) ≦ L （この式で、Ｌは、１以上の予定の整数）という条件を
満たすi+i番目の有効一致文字列を見出す段階と、(e)
上記有効一致文字列が見つかる限り、上記段階(d)を継
続する段階と、(f) 少なくとも、上記同一文書における
最初の有効一致文字列の開始位置から、上記同一文書に
おける最後の有効一致文字列の終了位置までの間の文字
列における、有効一致文字列の存在情報に基づき、上記
検索文字列と、上記同一文書における最初の有効一致文
字列の開始位置から、上記同一文書における最後の有効
一致文字列の終了位置までの間の文字列との間の類似度
を計算する段階と、(g) 上記計算された類似度が、上記
段階(b)で入力された類似度以上であることに応答し
て、上記文書の上記有効一致文字列を含む内容を表示す
る段階を有する、情報検索方法。
【請求項５２】上記Ｍが２であり、上記Ｌが３以上であ
る、請求項５１に記載の情報検索方法。
【請求項５３】上記類似度の計算は、検索文字列におけ
る有効一致文字列が占める割合と、上記文書における最
初の有効一致文字列の開始位置から、上記文書における
最後の有効一致文字列の終了位置までの間の文字列にお
ける有効一致文字列が占める割合のうちの小さい方の値
を利用して行われる、請求項５１に記載の情報検索方
法。
【請求項５４】上記類似度の計算は、上記文書における
最初の有効一致文字列の開始位置から、上記文書におけ
る最後の有効一致文字列の終了位置までの間の文字列の
個々の文字において、それが有効一致文字列に属すると
きは加点し、そうでないときは減点し、結果の得点値
を、完全一致の得点値で割った値を利用して行われる、
請求項５１に記載の情報検索方法。
【請求項５５】上記加点が、１つの文字について１であ
り、上記減点が、１つの文字について１／Ｌである、請
求項５４に記載の情報検索方法。
【請求項５６】ｉ番目の有効一致文字列に属していて、
且つ対応する検索文字列中の文字がｉ−１番目の有効一
致列に属している文字について１／（２Ｌ）の減点をす
る、請求項５５に記載の情報検索方法。