米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 索引作成方法およびその装置と文書検索装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−105237
公開日 平成7年(1995)4月21日
出願番号 特願平5−253032
出願日 平成5年(1993)10月8日
代理人 【弁理士】
【氏名又は名称】蔵合 正博
発明者 菅 野 祐 司
要約 目的
複雑な検索条件での高速な全文検索を可能にする。

構成
索引作成装置として、高頻度の文字または文字列の出現の度合を詳細に分析する文字出現頻度算定手段104と2文字連続出現頻度算定手段105と3文字連続出現頻度算定手段106を有し、それぞれの出現の度合いに応じて低頻度文字、2文字連続、3文字連続をそれぞれグループ化する手段107〜109を有して小型で精密な索引データを作成するための索引型式を定め、この型式に従って高速に索引データを作成する。文書検索装置は、このようにして作成された索引データと索引照合条件作成手段と索引照合手段と全文走査文字列照合手段とを有し、正規表現などの複雑な検索条件の場合でも、索引データを活用した高速な検索動作を実現する。
特許請求の範囲
【請求項1】 検索対象文書データに関する索引データを作成する際に、まずサンプル文書データの文字および文字列の出現を統計的に調べて前記索引データを作成する際の共通情報となる索引型式データを作成し、この索引型式データの型式に従って前記索引データを作成することを特徴とする索引作成方法。
【請求項2】 サンプル文書データ中のある1文字の出現の度合を統計的に調べる文字出現頻度算定手段と、前回調べた文字の出現の度合が予め定められた値よりも高い場合に、前回調べた文字の全てを含むN文字(Nは2、3、4、・・・の自然数)の文字列についての出現の度合を統計的に調べる複数のN文字連続出現頻度算定手段と、サンプル文書データ中の文字または文字列の出現の度合に応じて前記文字出現頻度算定手段および前記複数のN文字連続出現頻度算定手段の出力から検索対象文書データに関する索引データを作成する際の共通情報となる索引型式データを作成する索引型式出力手段とを備えた索引作成装置。
【請求項3】 サンプル文書データ中の文字または文字列をその出現の度合に応じてグループ化する複数のグループ化手段を備え、索引型式出力手段が、前記各グループ化手段から出力されたグループ化情報を基に各グループの通し番号と所属する文字または文字列との対応表を出力することを特徴とする請求項2記載の索引作成装置。
【請求項4】 検索対象文書データに関する索引データを作成する際に用いる検索文字数を請求項3記載の索引作成装置から出力された索引型式データに従って決定する文字連続数算定手段と、前記文字連続数算定手段により決定された文字数と請求項3記載の索引作成装置から出力された索引型式データとから対応するグループ番号を算定するグループ番号算定手段と、前記グループ番号算定手段から出力されたグループ番号からそれぞれの文書レコードの索引データを作成する索引情報蓄積出力手段とを備えた索引作成装置。
【請求項5】 文字列パターンを含む検索条件を入力する検索入力手段と、前記検索条件から請求項4記載の索引作成装置から出力された索引データを照合するための文字または文字列のAND/OR木を作成する索引照合条件作成手段と、前記索引データと前記索引照合条件作成手段が作成したAND/OR木との照合を行なう索引照合手段と、照合が成功した場合に、検索対象文書データの対応する部分を前記検索条件入力手段から入力された文字列パターンを含む検索条件と照合し、照合の成功した部分を最終的な検索結果として出力する全文走査文字列照合手段とを備えた文書検索装置。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、電子計算機を応用した文書検索システムや文書編集システムにおける文書中から文字列等を検索するための索引の作成方法およびその装置と文書検索装置に関するものである。
【0002】
【従来の技術】近年、ワードプロセッサやパーソナルコンピューターの普及、コンピュータの記憶装置の容量の増大、コンピュータによる文字認識の実用化等に伴い、文書中の全ての文字情報を蓄積した全文データベースが多くなってきた。このため、大量の文字情報を蓄積し、必要に応じて文書情報を検索する全文データベース検索システムに対する関心が高まってきている。
【0003】従来の文書データベースシステムでは、文書を検索する際の鍵として、文書毎に人手により付与されたキーワードを利用するキーワード検索方式が一般的であった。しかし、キーワード付け作業が蓄積文書の増加に間に合わない、時間が経過するとキーワードが陳腐化する、キーワード付けを行った者と検索する者とのキーワードの解釈の相違により検索もれが生じる、などの問題点があった。このような背景から、近年、全文検索(フルテキストサーチ)と呼ばれる文書検索方式が注目されている。
【0004】全文検索は、文書データのほかには補助的な情報を持たずに、検索毎に文書データを全文走査する「フルテキストスキャン」方式と、検索に先だって、文書データ中に出現する文字あるいは文字列の情報を高速に取り出せるような索引情報を自動的に作成しておいて、検索時にこの索引を検索する方式の2種類に大別される。
【0005】このうち、フルテキストスキャン方式は、原文書以外の情報を用いないので、記憶容量が少なくて済むとともに文書データの更新直後でも即座に検索できる点、および正規表現等の文字列パターンや論理条件を含む複雑な検索条件の場合や検索結果が多い場合でも、検索時間がほぼ一定である点が長所であるが、文書データの全てを走査するため、索引方式に比べて検索速度が遅いという問題が指摘されている。
【0006】一方、索引方式は、一般にフルテキストスキャン方式よりも検索速度が速く、索引の作成方法によっては、検索速度が文書量にほとんど依存しないという利点があるが、索引情報の容量が大きいこと、索引を作成する時間が長いこと、検索条件が複雑な場合や検索結果が多い場合に検索速度が低下すること等の問題が指摘されている。
【0007】このような従来の全文検索ための文書検索方法と索引作成方法とその特徴は、「Access Methods for Text](Ohristos Faloutsos,Computing Surveys,Vol.17,No.1,March 1985)等の論文や、「テキスト検索プロセッサ」(高橋恒介著、電子情報通信学会刊)等の成書に詳細な説明がなされている。
【0008】
【発明が解決しようとする課題】しかしながら、上記の論文、成書で紹介されている従来の方法では、索引を用いないと検索速度が上がらず、一方索引を用いると、索引の作成・更新時間がかかる上に、索引データの容量が大きくなり、正規表現などの複雑な文字列パターンでの検索にも時間がかかるという課題があった。
【0009】本発明は、上記の従来技術の課題を解決するもので、作成・更新時間が短く、容量が小さく、正規表現などの複雑な文字列パターンでの近似検索も高速で行なうことのできる索引作成方法とその装置および作成された索引データとフルテキストスキャンとを組み合わせた検索速度の速い文書検索装置を提供することを目的とする。
【0010】
【課題を解決するための手段】上記目的を達成するために、本発明による索引作成方法は、検索対象文書データに関する索引データを作成する際に、まずサンプル文書データの文字および文字列の出現を統計的に調べて索引データを作成する際の共通情報となる索引型式データを作成し、この索引型式データの型式に従って索引データを作成するようにしたものである。
【0011】また、本発明によると索引作成装置は、サンプル文書データ中のある1文字の出現の度合を統計的に調べる文字出現頻度算定手段と、前回調べた文字の出現の度合が予め定められた値よりも高い場合に、前回調べた文字の全てを含むN文字(Nは2、3、4、・・・の自然数)の文字列についての出現の度合を統計的に調べる複数のN文字連続出現頻度算定手段と、サンプル文書データ中の文字または文字列の出現の度合に応じて文字出現頻度算定手段および複数のN文字連続出現頻度算定手段の出力から検索対象文書データに関する索引データを作成する際の共通情報となる索引型式データを作成する索引型式出力手段とを備えたものである。
【0012】さらに、本発明による索引作成装置は、サンプル文書データ中の文字または文字列をその出現の度合に応じてグループ化する複数のグループ化手段を備え、索引型式出力手段が、各グループ化手段から出力されたグループ化情報を基に各グループの通し番号と所属する文字または文字列との対応表を出力するようにしたものである。
【0013】さらに、本発明による索引作成装置は、検索対象文書データに関する索引データを作成する際に用いる検索文字数を上記構成の索引作成装置から出力された索引型式データに従って決定する文字連続数算定手段と、文字連続数算定手段により決定された文字数と上記構成の索引作成装置から出力された索引型式データとから対応するグループ番号を算定するグループ番号算定手段と、グループ番号算定手段から出力されたグループ番号からそれぞれの文書レコードの索引データを作成する索引情報蓄積出力手段とを備えたものである。
【0014】また、本発明による文書検索装置は、文字列パターンを含む検索条件を入力する検索入力手段と、検索条件から上記構成の索引作成装置から出力された索引データを照合するための文字または文字列のAND/OR木を作成する索引照合条件作成手段と、索引データと索引照合条件作成手段が作成したAND/OR木との照合を行なう索引照合手段と、照合が成功した場合に、検索対象文書データの対応する部分を検索条件入力手段から入力された文字列パターンを含む検索条件と照合し、照合の成功した部分を最終的な検索結果として出力する全文走査文字列照合手段とを備えたものである。
【0015】
【作用】本発明は、上記構成によって、検索対象文書データに関する索引の型式が統計的に検索対象文書データに適合した、容量の小さい索引データを、検索対象文書データの統計的性質を調べることなしに高速に作成し、また、サンプル文書中における出現の度合が、予め定められた値以下すなわち絞り込み率以下である低頻度文字については、索引型式出力手段が検索対象文書データにおける1文字の出現を記録するための索引データの型式を指示し、サンプル文書中における出現の度合が絞り込み率よりも高い高頻度文字については、高頻度文字に属するN文字、すなわちまず初めに2つの文字からなる2文字連続のサンプル文書データ中における出現の度合を2文字連続出現頻度算定手段が統計的に調べ、サンプル文書データ中における出現の度合が絞り込み率以下である低頻度2文字連続については、索引型式出力手段が検索対象文書データにおける2文字連続の出現を記録するための索引データの型式を指示し、サンプル文書データ中における出現の度合が絞り込み率よりも高い高頻度2文字連続については、高頻度2文字連続に属する2つの2文字連続をそれぞれ初めの2文字、および最後の2文字に持つ3文字連続のサンプル文書データ中における出現の度合を3文字連続出現頻度算定手段が統計的に調べ、索引型式出力手段が、検索対象文書データにおける3文字連続の出現を記録するための索引データの型式を指示することによって、文字および文字列の出現の度合が異なっていても、検索条件によらずに絞り込み率以下に検索対象文書データを絞り込むことを可能にする索引データを作成することができる。
【0016】また、サンプル文書データ中の文字または文字列の出現の度合を文字列出現頻度算定手段が統計的に調べ、その後で、グループ化手段が、1つ以上の文字または文字列からなるグループであって、当該グループに属する文字または文字列の少なくとも1種が出現する度合が予め定めた絞り込み率以下であるグループに、サンプル文書データ中の文字または文字列を振り分け、検索対象文書データにおいて当該グループに所属するいずれかの文字あるいは文字列が出現した場合には、「当該グループに属する文字あるいは文字列のいずれかが出現した」という情報を記録するための索引データの型式を索引型式決定手段が決定して索引型式データを作成することによって、多くの種類の低頻度文字がある場合でも、容量の小さな索引を作成することができる。
【0017】さらに、文書検索装置においては、利用者が検索条件入力手段から入力した文字列パターンを含む検索条件から、索引照合条件作成手段が、索引データを照合するための文字または文字列のAND/OR木を作成し、索引照合手段が、索引データと、索引照合条件作成手段の作成したAND/OR木との照合を行い、照合が成功したデータの場合には、全文走査文字列照合手段が、検索対象文書データの対応する部分を検索条件入力手段から入力された文字列パターンを含む検索条件と完全に照合し、照合の成功した部分を最終的な検索結果とすることにより、従来はフルテキストスキャン方式でしか扱えなかった複雑な検索条件の場合でも、索引による検索速度の高速化を実現することができる。
【0018】
【実施例】
(実施例1)以下、本発明の索引作成方法を実施するための装置について、図面を参照しながら説明する。図1は本発明の第1の実施例における索引作成装置の構成を示すブロック図である。図1において、101は文書データを構成する複数の文書レコードを格納したサンプル文書データである。サンプル文書データは、検索対象文書データの全部または一部でもよく、検索対象文書データに対し、文字および文字列の出現に関する統計的性質が類似している他の文書データであってもよい。102はサンプル文書データ101中の各文書レコードの位置を記録したサンプル文書句切りデータ、103はサンプル文書句切りデータ102の位置情報に従ってサンプル文書データ101から指定された文書レコードを切り出して、レコード先頭を表す特別な文字<START>を文書レコード先頭に付与し、レコード終了を表す特別な文字<END>を文書レコード末尾に付与した文字列を出力する文書区切り手段、104は文書区切り手段103の出力である文書レコード文字列を受け取ってサンプル文書データ101中に出現する各文字の出現の度合を、「当該文字の出現する文書レコードの文字数の総和を全文書レコードの文字数の総和で除した値」として算定する文字出現頻度算定手段、105は文書区切り手段103の出力である文書レコード文字列と、文字出現頻度算定手段104の算定結果とを受け取って、サンプル文書データ101中に高頻度で出現する2文字連続の出現の度合を、「当該2文字連続の出現する文書レコードの文字数の総和を全文書レコードの文字数の総和で除した値」として算定する2文字連続出現頻度算定手段、106は文書区切り手段103の出力である文書レコード文字列と、2文字連続出現頻度算定手段105の算定結果とを受け取って、サンプル文書データ101中に高頻度で出現する3文字連続の出現の度合を、「当該3文字連続の出現する文書レコードの文字数の総和を全文書レコードの文字数の総和で除した値」として算定する3文字連続出現頻度算定手段、107は文字出現頻度算定手段104の算定結果を受け取って、出現の度合が予め定められた「絞り込み率」以下である複数の文字をグループ化し、グループに属するいずれかの文字が出現する度合が絞り込み率を越えない範囲で絞り込み率に最も近くなるように調整する文字グループ化手段、108は2文字連続出現頻度算定手段105の算定結果を受け取って、出現の度合が絞り込み率以下である複数の2文字連続をグループ化し、グループに属するいずれかの2文字連続が出現する度合が絞り込み率を越えない範囲で絞り込み率に最も近くなるように調整する2文字連続グループ化手段、109は3文字連続出現頻度算定手段106の算定結果を受け取って、出現の度合が絞り込み率以下である複数の3文字連続がある場合には、これをグループ化し、グループに属するいずれかの3文字連続が出現する度合が絞り込み率を越えない範囲で絞り込み率に最も近くなるように調整し、出現の度合が絞り込み率よりも高い3文字連続はそれ1つだけで1グループにする3文字連続グループ化手段、110は文字グループ化手段107と2文字連続グループ化手段108と3文字連続グループ化手段109の出力であるグループ化情報を受け取って、各グループに通し番号を付与し、各グループの通し番号と、所属文字あるいは2文字連続あるいは3文字連続との対応表を出力する索引型式出力手段、111は索引型式出力手段110の出力する索引型式データである。
【0019】サンプル文書データ101には、図4に示すような、書籍のISBN番号が1番号1文書レコードとして、553966レコード分記録されており、サンプル文書区切りデータ102には、図4に示した文書データの各文書レコードの先頭の文字の、サンプル文書データ101先頭からの文字単位での隔たりが記録されているものとし、絞り込み率として、0.05を指定するものとする。
【0020】以上のように構成された索引作成装置について、その動作を説明する。まず、サンプル文書データ101中の各文書レコードが、文書区切り手段103で切り出されて、文字出現頻度算定手段104に送られ、各文字の出現の度合が、当該文字の出現する文書レコードの文字数の総和/全文書レコードの文字数の総和によって算定される。図5〜図23は、この索引作成装置のレポート出力であり、図5の「文字頻度表(Character histgram & Monogram−index)」、図6〜図7の「高頻度2文字連連続表」(Frequent Digram)、図8の「2文字連続のグループ化結果」(Digram partitions)、図9〜図18の「高頻度3文字連続表」(Trigram Table)、図19〜図22の「3文字連続のグループ化結果」(Trigram Partitioning Table)、図23の「索引の大きさ」(Index size)の各情報が、順に記録されている。
【0021】文字出現頻度算定手段104の算定結果である図5において、「Occurence」項目は、着目文字の出現する文書レコードの文字数の総和を表し、「(Percent)」項目は、着目文字の出現する文書レコードの文字数の総和を全文書レコードの文字数の総和で除した値に100を乗じた値を表し、「Rank」項目は、着目文字の出現度合による順序を表し、「Char」項目は、着目文字を表し、「Monogram−index」項目は、出現度合によってグループ化された文字グループ番号を表す。例えば、「Char」項目の文字「−」は、第4番目に高頻度の文字であり、出現文書レコードの文字数の総和は、3699241文字であり、87.29%の出現頻度を持つ。なお、このサンプル文書データの場合には、文字種が16種と少ないため、2文字以上からなる文字グループは存在しない。
【0022】こうして、サンプル文書データ101の1回目の走査が終了したら、文書区切り手段103は、サンプル文書データ101の2回目の走査を開始し、切り出した文書レコードを2文字連続出現頻度算定手段105に送る。2文字連続出現頻度算定手段105は、文書レコード中の2文字連続のうちで、高頻度文字(この例の場合には、全ての文字種が高頻度文字に当たる)同士の連続のみを抽出し、各2文字連続の出現の度合が、「当該2文字連続の出現する文書レコードの文字数の総和/全文書レコードの文字数の総和」によって算定される。そのうちで、出現の度合が絞り込み率よりも高い、高頻度の2文字連続を表示したのが、図6〜図7の「高頻度2文字連続表」である。
【0023】図6において、「No.」項目は、高頻度2文字連続の通し番号を表し、「Digram−Code」項目は、2文字連続を構成する第1文字、第2文字を文字グループ番号で表現した組を表し、「Digram−Character」項目は、2文字連続を構成する文字列を表し、「Occ」項目は着目2文字連続の出現する文書レコードの文字数の総和を表し、「(Percent)」項目は、着目2文字連続の出現する文書レコードの文字数の総和を全文書レコードの文字数の総和で除した値に100を乗じた値を表す。例えば、通し番号が6である「−4」という2文字連続は、出現の度合が17.57%であることがわかる。高頻度文字同士からなる2文字連続のうち、高頻度2文字連続以外のすべてを、文字グループ番号で第1文字、第2文字を表現した際の文字列の昇順に並べ、その後で、並び順が近接する2文字連続を、2文字連続グループ化手段108がグループにまとめる。グループ化の際の、グループのいずれかの2文字連続が表れる度合の算定法は、グループ内の各2文字連続の出現が統計的に独立であると仮定し、以下の式から求める。
【0024】
【数1】

ただし、Pはグループ内のn個の2文字連続のいずれかが現れる度合であり、Pj (j=1,2,・・・n)はグループ内のj番目の2文字連続が現れる度合である。
【0025】その結果が、図8の「2文字連続のグループ化結果」である。図8において、「No.」項目は、2文字連続のグループ番号を表し、「Digram−Code」項目はグループとグループの境界に位置する当該グループ中で最も文字列順の大きい2文字連続の第1文字、第2文字の文字グループ番号を表し、「Digram−Character」項目は当該2文字連続を構成する文字列を表す。例えば、2文字連続のグループ番号7には、2文字連続「22」および「23」が含まれ、2文字連続のグループ番号8には、2文字連続「25」、「26」、「27」、「29」が含まれる。
【0026】こうして、サンプル文書データ101の2回目の走査が終了したら、文書区切り手段103は、サンプル文書データ101の3回目の走査を開始し、切り出した文書レコードを3文字連続出現頻度算定手段106に送る。3文字連続出現頻度算定手段106は、文書レコード中の3文字連続のうちで、(第1文字、第2文字)および(第2文字、第3文字)がいずれも高頻度2文字連続である3文字連続のみを抽出し、各3文字連続の出現の度合が、「当該3文字連続の出現する文書レコードの文字数の総和/全文書レコードの文字数の総和」によって算定され、その結果が3文字連続グループ化手段109に送られ、式(1)と同様の基準によって、絞り込み率をもとにグループ化される。その結果を表示したのが図9〜図18の「高頻度3文字連続表」および図19〜図22の「3文字連続のグループ化結果」である。
【0027】図9において、「No.」項目は、3文字連続の通し番号を表し、「Group」項目は、3文字連続のグループ番号を表し、「Trigram−Code」項目は、3文字連続の第1文字、第2文字、第3文字の文字グループ番号を表し、「Trigram−Character」項目は、当該3文字連続を構成する文字列を表し、「Occ」項目は、着目3文字連続の出現する文書レコードの文字数の総和を表し、「(Percent)」項目は、着目3文字連続の出現する文書レコードの文字数の総和を全文書レコードの文字数の総和で除した値に100を乗じた値を表す。
【0028】また、図19において、「No.」項目は、3文字連続のグループ番号を表し、「Trigram−Code」項目は、グループとグループの境界に位置する当該グループ中で文字グループ番号で計った文字列順の大きい2文字連続の第1文字、第2文字の文字グループ番号を表し、「Trigram−Character」項目は、当該3文字連続を構成する文字列を表す。例えば、3文字連続のグループ番号138には、3文字連続「202」、「203」、「205」、「206」、「207」、「209」、「204」が所属する。
【0029】こうして、得られたグループ化情報が、索引型式出力手段110に送られ、低頻度文字グループ、2文字連続グループ、3文字連続グループの1つ1つに対して、1bitの索引情報を割り当てるような索引型式を、索引型式データ111に出力する。作成される索引の文書レコード当りの大きさを表示したものが、図23の「索引の大きさ」である。
【0030】図23において、「1)Monogram−index:」項目は、低頻度文字索引の大きさを表し、「2)Digram−index:」項目は、2文字連続の索引の大きさを表し、「3)Trigram−index:」項目は、3文字連続の索引の大きさを表し、「Total Index size:」項目は、1)2)3)を合計した1文書レコード当りの索引のサイズを表す。この例では、1文書レコードあたり、合計32バイトの索引が作成される。
【0031】以上のように、本実施例によれば、サンプル文書データの文字および文字列の出現の度合から、多く出現する文字については、2文字連続情報を用いて、より詳細な索引情報をつくり、その中でより多く出現する2文字連続には、3文字連続情報を用いてさらに詳細な索引情報をつくることで、高頻度で出現する文字および文字列に対して高精度な索引型式データを作成でき、逆に、あまり出現しない文字および文字列については、グループ化によって、索引情報の容量を縮小した索引型式データを作成することができる。
【0032】(実施例2)次に、本発明の第2の実施例について、図面を参照しながら説明する。図2は本発明の第2の実施例における索引作成装置の構成を示すブロック図である。図2において、201は複数の文書レコードを格納した検索対象文書データ、202は検索対象文書データ201中の各文書レコードの位置を記録した検索対象文書句切りデータ、203は検索対象文書句切りデータ202の位置情報に従って検索対象文書データ201から指定された文書レコードを切り出して、レコード先頭を表す特別な文字<START>を文書レコード先頭に付与し、レコード終了を表す特別な文字<END>を文書レコード末尾に付与した文字列を出力する文書区切り手段、204は図1に示した索引作成装置により作成された索引型式データ、205は文書区切り手段203の出力である文書レコード文字列を受け取って、検索対象文書データ201中に出現する各文字から始まる文字列の、索引作成時に用いる検索文字数が1であるか2であるか3であるかを、索引型式データ204に従って決定する文字連続数算定手段、206は文字連続数算定手段205の算定結果である文字数と、文字列および索引型式データのグループの定義とを受け取って、対応するグループ番号を算定するグループ番号算定手段、207はグループ番号算定手段206の出力であるグループ番号を受け取って、1文書レコードの索引情報を作成して出力する索引情報蓄積出力手段、208は索引情報蓄積出力手段207が出力する検索対象データ201に関する索引データである。
【0033】以上のように構成された索引作成装置について、その動作を、図24に示すこの索引作成装置が動作する際に出力したレポート出力を例にして説明する。図24において、Record No,2の「<START>4−587−51151−X<END>」は、検索対象データの第2レコードの切り出し結果である。この文字列が文字連続数算定手段205に送られると、まず、各文字を文字グループ番号に直し、次に索引型式データ204にしたがって、文字連続数を算定する。この例の文字列は、文字グループ番号で表現すると、「0、2、3、9、6、11、3、7、7、10、5、4、3、10、1」となる。そして、先頭の「<START>,4」なる2文字が2文字連続として、文字グループ番号の組[0−2]で切り出され、グループ番号算定手段206が、これからグループ番号0を算定し、索引情報蓄積出力手段207が、これを受け取って、内部のビット列の0番目のものを、16進「0000」から16進「0001」に変える。先頭から2文字目の「4,−,5」なる3文字の場合は、3文字連続として、文字グループ番号の組[2−3−9]で切り出され、グループ番号算定手段206が、これからグループ番号72を算定し、索引情報蓄積出力手段207が、これを受け取って、内部のビット列の4番目のものを、16進「0000」から16進「0100」に変える。このようにして、着目文字を次々と移動させながら、索引情報蓄積出力手段207の内部のビット列に、第2レコードの索引情報をビット列の形で蓄積する。最後の文字の処理が終了した場合には、蓄積したビット列を、索引データ208に出力する。以上の処理を各文書レコードに対して次々に行うことにより、最終的に、検索対象データ101内の全文書レコードに関する索引情報を、索引データ208に格納し、索引作成処理を終了する。
【0034】このように、本実施例の索引作成装置によれば、索引型式データ204が、検索対象文書データと文字および文字列の出現の度合が類似している場合には、索引型式データ204内の統計情報を用いて、検索対象文書データを調べることなしに、多く出現する文字については、2文字連続情報を用いてより詳細な索引情報を作り、その中でより多く出現する2文字連続には、3文字連続情報を用いてさらに詳細な索引情報をつくることで、高頻度で出現する文字および文字列に対して、高精度な索引データを作成でき、逆に、あまり出現しない文字および文字列については、グループ化によって、索引情報の容量を縮小した索引データを作成することができる。
【0035】(実施例3)次に、本発明の第3の実施例について、図面を参照しながら説明する。図3は本発明の文書検索方法を用いた文書検索装置の一実施例を示すブロック図である。図3において、301は複数の文書レコードを格納した検索対象文書データ、302は利用者が検索条件を入力する検索条件入力手段、303は検索対象文書データ301に関する索引情報を記録した図2の索引作成装置を用いて作成した索引データ、304は検索対象文書データ301を走査して、検索条件入力手段302から入力された検索条件と照合する文書レコードを出力する全文走査文字列照合手段、305は検索条件入力手段302から入力された検索条件を、索引データ303が取り扱える検索条件に変形する索引照合条件作成手段、306は索引データ303と、索引照合条件作成手段305の作成した索引照合条件との照合を行って、照合した文書レコードの情報を、全文走査文字列照合手段304に通知する索引照合手段、307は全文走査文字列照合手段304が出力する検索結果である。
【0036】以上のように構成された文書検索装置について、その動作を、図25の検索例により説明する。図25において、「キーワード?」の次の文字列が、利用者が検索条件入力手段302を用いて入力した検索条件で、この例では、正規表現「115[1−3]−X」が入力されている。この検索条件の解釈は、「1151−X」か、「1152−X」か、あるいは「1153−X」のいずれかがレコード中に含まれる文書データを全て求めよ、ということである。この検索条件が索引照合条件作成手段305に送られると、図25の「Matching Vector」以下で示されているように、検索照合条件がベクトルに埋め込まれたAND/OR木の型式で求まる。このベクトルの各要素は(位置−オフセット−ビット列)の情報を持つ。その解釈は、図26および図27のようになる。この例では、例えば「115」の3文字連続に対応する要素が(5−10−1000)で、このうち、「10」と16進「1000」で、文書レコードに対応する索引情報のビット列中のビットを特定する。このベクトル型式の検索照合条件が、索引照合手段306に送られ、索引データ303と照合され、図25の「Index match」以下のように、「Record No.3(4−587−51151−X)」や「Record No.10347(4−09−151801−X)」などの文書レコードが照合し、このレコードの位置情報が全文走査文字列照合手段304に送られる。全文走査文字列照合手段304は,この索引照合手段306が照合に成功した文書レコードの位置情報と、検索対象文書データ301の文書情報をもとに、必要な文書レコードを読み込み、検索条件入力手段302から入力された検索条件、この例では正規表現「115[1−3]−X」との文字列照合を行い、図25の「Result」のような、最終的な結果を得て、検索結果307に格納し、文書検索処理を終了する。
【0037】このように、本実施例の文書検索装置によれば、索引容量が小さく、正規表現などの複雑な検索条件にも対応可能な本発明の索引作成装置を援用して作成した索引データを用いて、従来はフルテキストスキャン方式でしか扱えなかった複雑な検索条件の場合でも、高速に文書検索を実行することができる。
【0038】
【発明の効果】本発明は、上記各実施例から明らかなように、検索対象文書データに関する索引データを作成する際に、まずサンプル文書データの文字および文字列の出現を統計的に調べて索引データを作成する際の共通情報となる索引型式データを作成し、この索引型式データの型式に従って索引データを作成するようにしたので、作成・更新時間が短く、容量が小さく、正規表現などの複雑な文字列パターンでの近似検索も高速で行なうことのできる索引作成方法とその装置および作成された索引データとフルテキストスキャンとを組み合わせた検索速度の速い文書検索装置を実現することができる。
【0039】特に、文字および文字列の出現の度合があまり変わらない多数の検索対象文書がある場合や、検索対象文書の更新がひんぱんに行われる場合などは、一旦索引型式データを作成しておけば、きわめて高速に、小容量の索引データが作成でき、検索条件の制約なしに、フルテキストスキャンの高速化を図ることができ、その効果は大きい。ちなみに本発明による索引データを用いれば、全国紙の新聞1年分をキーワード1個で検索した場合、検索速度を従来の20倍程度も向上させることができる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013