JP5483166B2 - 文書検索装置、文書検索方法、及びプログラム - Google Patents

Description

本発明は、文書データの全文検索を行う文書検索装置、文書検索方法、及びプログラムに関する。

従来から、多量の文書中から特定のキーワード（検索キー）を検索する全文検索装置が知られている。
このような全文検索装置は、大別して２種類に分けられる。１つはサーチ（走査）方式であり、もう１つはインデックス方式である。サーチ方式は、蓄積されている文書データに対し、検索キーと文書中の文字列の比較を順次行う方法である。代表的なものとしてＵＮＩＸ（登録商標）のｇｒｅｐコマンドなどがある。インデックス方式は、文書データに対して事前にインデックスを作成し、このインデックスに対して検索キーを照合することにより検索を行う方式である。

サーチ方式では、インデックスを作成する必要がないため、インデックス部分のデータ増加がないという利点がある。また、文書データに対してインデックスを作成する時間が不要なため、検索を実行できる状態になるまでの待ち時間がないという特徴もある。一方、サーチ方式では検索速度が文書量に比例するため、データ量の大きい文書ではインデックス方式に比べると検索速度が遅くなるという問題がある。

インデックス方式では、元の文書データに対し、インデックス部分のデータが増加する。また、文書データに対してインデックスを作成する時間が必要なため、検索を実行できる状態になるまでの待ち時間が発生する。一方で、検索速度が文書量に依存しないため、大量の文書でも検索速度が非常に速いという利点がある。

インデックス方式を用いた文書検索については、例えば特許文献１〜４に開示されている。
例えば特許文献１には、インデックス方式において、元の文書データに対してインデックス部分のデータが増加する問題に対し、インデックス部のデータを圧縮することで、全体のデータ量を減少させることが記載されている。
また、特許文献２には、インデックスを作成する時間がかかる問題に対し、副インデックスを作成することにより、インデックス作成のために検索処理が阻害されないようにすることが記載されている。
特許文献３には、転置インデックスを用いて文書を高速に検索することが記載されている。
また、特許文献４には、文書を修正した際に、文字連鎖インデックスの修正を短縮することが記載されている。

特開平８−２８７１０５号公報 特開平７−１４６８８０号公報 特開２００８−２５０７２２号公報 特開平６−５２２２２号公報

しかし、一般にインデックスの作成により、元の文書データ量の２倍程度はデータが増加するため、インデックス部のデータを圧縮するだけでは十分にデータ量を削減することができなかった。このため、多量の文書データが蓄積されるドキュメントサーバなどでは、ストレージを増強する必要があった。

また、インデックス方式の全文検索では、文書データの改変時にインデックスデータも再作成する必要があるため、文書データの改変後、検索を実施できる状態になるまで遅延が発生する問題があった。

そこで本発明の目的は、文書データの全文検索を行う文書検索装置において、データ量を減少させると共に、文書修正時のインデックスの再作成時間を減少させることである。

本発明に係る文書検索装置は、検索の対象となる文書データを入力するためのデータ入力部と、データ入力部を介して入力された文書データから転置インデックスを作成するインデックス作成部と、インデックス作成部で作成された転置インデックスを記憶する転置データ蓄積部と、検索のためのキーワードを入力するための検索キーワード入力部と、検索キーワード入力部を介して入力されたキーワードを転置インデックスと照合し、キーワードと一致する文字列を検出する検索部と、文字列を含む文書データの情報、及び文字列を含む文書データの一部を出力する検索結果出力部と、文書データの修正要求を受付けるデータ修正入力部と、修正要求に基づいて、転置データ蓄積部に記憶された転置インデックスを修正するデータ修正反映部と、を備えたものである。

本発明によれば、文書データの全文検索を行う文書検索装置において、データ量を減少させると共に、文書修正時のインデックスの再作成時間を減少させることができる。

本発明による文書検索装置の機能構成を示すブロック図である。 本実施形態による転置インデックスの例を示す図である。 本実施形態の文書検索装置による、転置インデックスの作成・修正処理のフローチャートである。 文書データの編集（修正）前と編集後の転置インデックスの例を示す概念図である。

次に、本発明を実施するための最良の形態について、図面を参照して詳細に説明する。
図１は、本発明による文書検索装置の機能構成を示すブロック図である。図に示すように、文書検索装置は、データ入力部１、インデックス作成部２、転置データ蓄積部３、検索キーワード入力部４、検索部５、検索結果出力部６、データ修正入力部７、データ修正反映部８、を備えている。

文書検索装置は、例えば汎用的なパーソナルコンピュータに所定のプログラムを実行させたものである。インデックス作成部２、検索部５、データ修正反映部８は、プログラムに従ってコンピュータのプロセッサが行う動作のモジュールを表しており、これらは一体として文書検索装置のプロセッサを構成する。

転置データ蓄積部３は、文書検索装置のハードディスク等の記憶装置である。
データ入力部１、検索キーワード入力部４、データ修正入力部７は、例えばキーボード、マウス、タッチパネル等の入力手段であり、ユーザが文書検索装置に処理の指示を与えたり、データやパラメータを入力するために用いられる。また、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）インターフェイスを介して、メモリ媒体などからデータを読み込むことも可能である。
検索結果出力部６は、表示装置やプリンタ等である。

データ入力部１は、ユーザが検索対象となる文書データを文書検索装置に入力するための機能を有する。

インデックス作成部２は、データ入力部１を介して入力された文書データから転置インデックスを作成する機能を有する。図２は、本実施形態による転置インデックスの例を示す図である。図２には、図中の文書１及び文書２から作成された転置インデックスの一部が示されている。図に示すように、転置インデックスは、インデックスキーと各々のインデックスキーに対応する転置データ（マッピングデータ）を含んでいる。

インデックスキーには、文書データから抽出された単語が当てられている。また、転置データには（データ番号、文書番号、前のデータ番号、次のデータ番号）の４項目のデータが含まれている。例えば、インデックスキー「猫」については、３つの転置データが登録されている。１つ目の転置データ（００３、文書１、前００２、後００４）は、データ番号００３の「猫」は、文書１に含まれており、前のインデックスキーのデータ番号は００２（「は」）、後ろのインデックスキーのデータ番号は００４（「である」）であることを示している。さらに、データ番号００２「は」の転置データを参照すると、前のデータ番号は００１「我輩」であることが分かる。このようにして、転置データを参照することにより、元の文書１を再構成することができる。このように、本実施形態の転置データは、チェーン型のポインタリストになっている。このため、本実施形態による文書検索装置では、元の文書１や２を記憶しておく必要がなく、転置インデックスを作成したら、元の文書データ自体は削除してよい。

なお、図２の例では、インデックスキーが単語単位の単語インデックス方式を採用しているが、インデックスキーの作成方法はこれに限定されず、例えば文字単位の文字インデックス方式（ｎ−ｇｒａｍ）を採用してもよい。文字単位のインデックスキーを作成した場合も、転置データは図２に示す形式で作成することができる。

転置データ蓄積部３は、インデックス作成部２で作成した転置インデックスを記憶する機能を有する。

検索キーワード入力部４は、ユーザが検索のためのキーワードを文書検索装置に入力するための機能を有する。

検索部５は、検索キーワード入力部４を介して入力されたキーワードを転置データ蓄積部３に記憶された転置インデックスと照合し、キーワードと一致するインデックスキーを検出する機能を有する。

検索結果出力部６は、検索部５で検出されたインデックスキーを含む文書データの情報、及び文字列を含む文書データの一部を出力する。出力する情報は、例えば文書名、検索キーワードと周辺の文字列等である。

データ修正入力部７は、ユーザから、登録されている文書データの修正要求を受け付ける機能を有する。この機能は、一般にはエディット機能と呼ばれるものであり、本実施形態では、クライアントソフトとして実装してもよいし、ＷＥＢブラウザ上のテキスト入力領域として実装するようにしてもよい。データ修正入力部７は、修正要求が入力されると、修正要求に基づいた転置インデックスの修正処理手順を、データ修正反映部８に通知する。なお、データ修正反映部８への修正処理手順の通知は、ユーザから修正要求が入力された時点で即時に行ってもよいし、修正要求をある程度蓄積してから、まとめて通知するようにしてもよい。

データ修正反映部８は、データ修正入力部７から通知された修正処理手順に従って、転置データ蓄積部３に記憶された転置インデックスを修正する。

次に、図３のフローチャートを用いて本実施形態の文書検索装置による、転置インデックスの作成処理について説明する。
まず、ステップＳ１において、データ入力部１を介して入力された文書データ、またはデータ修正入力部７を介して入力された修正後の文書データを読み込む。

次に、ステップＳ２において、インデックス作成部２は、入力された文書データを先頭から参照し、インデックスキー候補を取得する。

次に、ステップＳ３において、インデックス作成部２は、ステップＳ２で取得したインデックスキー候補が、すでに転置データ蓄積部３の転置インデックスに登録されているか否か判断する。判断の結果、インデックスキー候補が登録されていなければ（ＮＯ）ステップＳ４へ、登録されていれば（ＹＥＳ）ステップＳ５へ移行する。

ステップＳ４では、インデックス作成部２はインデックスキー候補を転置インデックスに新規インデックスキーとして登録し、ステップＳ５に移行する。

ステップＳ５において、インデックス作成部２は、転置インデックスに登録されている当該インデックスキーに対応する転置データ領域を１つ確保し、データ番号を取得する。

次に、ステップＳ６において、インデックス作成部２は、転置データの「前のデータ番号」として、１つ前に取得されたインデックスキーのデータ番号を記憶する。同時に、１つ前に取得されたインデックスキーの転置データの「次のデータ番号」として、今回取得したインデックスキーのデータ番号を記憶する。

次に、ステップＳ７において、インデックス作成部２は、文書の終端まで読み取ったか否かを判断する。判断の結果、文書の終端まで読み取っていなければ、ステップＳ８において文字の読み取り位置を終端に向けて１つ移動してから、ステップＳ２へ戻る。文書の終端まで読み取っている場合には、処理を終了する。

図４は、文書データの編集（修正）前と編集後の転置インデックスの例を示す概念図である。図中の矢印は、各インデックスキーの前後関係を示している。図に示すように、文書が「我輩は猫である。」から「我輩の犬である。」へ変更されたことにより、新たにインデックスキー「の」と「犬」が追加され、キー同士の前後関係が修正されている。このように、本実施形態によれば、文書データを修正した場合でも、転置インデックスの再構成を行うだけで、文書の修正を反映することができる。

データ修正入力部７は、文書データの修正要求が入力されると、修正要求に基づいた転置インデックスの修正処理手順を、データ修正反映部８に通知する。修正処理手順は、何番目インデックスが消去、変更されたか、という情報を含んでいる。例えば、上述の「我輩は猫である。」から「我輩の犬である。」への変更を例にとると、２番目のインデックスキーの消去、及び２番目のインデックスキーに「の」を挿入、３番目のインデックス「猫」の消去、及び３番目のインデックスキーに「犬」を挿入、という情報が修正処理手順に含まれることになる。このように、本実施形態では、文書データが修正された場合に、修正後の文書データではなく、修正処理手順をデータ修正反映部８に通知する。

なお、作成または再構成した転置インデックスのデータを圧縮することにより、データ量をさらに削減するようにしてもよい。

以上のように、本実施形態によれば、元の文書データを容易に再構成できる転置インデックスを作成しているため、元の文書データを記憶しておく必要がないので、データ量を大幅に削減することができる。また、文書データを修正した場合でも、転置インデックスのみを再構成すればよいので、文書修正の反映を速やかに行うことができる。

本発明に係る文書検索装置の実装例について説明する。
インデックス作成部２、検索部５、データ修正反映部８は、電子回路やコンピュータのプロセッサにプログラムを実行させることにより実現することができる。

データ入力部１、検索キーワード入力部４、データ修正入力部７としては、キーボードや、マウスなどのポインティングデバイスを用いることができる。また、ＷＥＢブラウザなどのソフトウェアや通信装置を介して外部のコンピュータから入力を行えるようにしてもよい。

検索結果出力部６としては、ディスプレイやプリンタを用いることができる。また、通信装置を介して、外部のコンピュータ等に出力できるようにしてもよい。

データ入力部１、インデックス作成部２、転置データ蓄積部３、検索キーワード入力部４、検索部５、検索結果出力部６、データ修正入力部７、及びデータ修正反映部８は、パーソナルコンピュータなどの１つの装置に全てを実装しても良いし、一部の機能を別の装置に実装してもよい。

また、文書検索装置の各機能をサーバコンピュータに実装し、通信ネットワークを介して外部のコンピュータから文書登録、検索を行える構成としても良い。本実施形態によれば、データ量を大幅に削減し、文書修正の反映も速やかに行うことができるので、ネットワーク上で多量の文書書き込みや修正が発生するブログシステムや会議室システム、ＷＥＢメールシステムなどに利用すると、大変効果的である。

また、一部または全ての機能について、複数の装置に実装することにより性能を向上させるようにしてもよい。

また、本実施形態による文書検索装置を他の装置に組み込む場合には、他の装置に実装されているソフトウェアから呼び出して実行することができるように構成してもよい。

１ データ入力部、２ インデックス作成部、３ 転置データ蓄積部、４ 検索キーワード入力部、５ 検索部、６ 検索結果出力部、７ データ修正入力部、８ データ修正反映部

Claims (5)

1. 検索の対象となる文書データを入力するためのデータ入力部と、
   前記データ入力部を介して入力された前記文書データから転置インデックスを作成するインデックス作成部と、
   前記インデックス作成部で作成された前記転置インデックスを記憶する転置データ蓄積部と、
   前記検索のためのキーワードを入力するための検索キーワード入力部と、
   前記検索キーワード入力部を介して入力されたキーワードを前記転置インデックスと照合し、前記キーワードと一致する文字列を検出する検索部と、
   前記文字列を含む文書データの情報、及び前記文字列を含む文書データの一部を出力する検索結果出力部と、
   前記文書データの修正要求を受付けるデータ修正入力部と、
   前記修正要求に基づいて、前記転置データ蓄積部に記憶された前記転置インデックスを修正するデータ修正反映部と、を備え、
   前記転置インデックスは、前記文書データから抽出された単語をインデックスキーとして含むと共に、各々のインデックスキーに対応する転置データを含み、前記転置データは、当該単語のデータ番号、当該単語が抽出された文書の番号、当該単語の前の単語のデータ番号、および当該単語の次の単語のデータ番号を含み、
   前記データ修正反映部は、前記修正要求に基づいて、修正された単語の転置データを削除して修正後の単語の転置データを追加すると共に、前記修正された単語の前の単語の転置データに含まれる次の単語のデータ番号と、前記修正された単語の次の単語の転置データに含まれる前の単語のデータ番号を修正する、文書検索装置。
2. 請求項１に記載の文書検索装置の各部の機能が、マイクロチップによって実現される、文書検索装置。
3. 請求項１または２に記載の文書検索装置の各部の機能がネットワークを介して外部のコンピュータから利用可能である、文書検索装置。
4. 検索の対象となる文書データの入力を受け付ける工程と、
   前記文書データから転置インデックスを作成する工程と、
   前記転置インデックスを記憶装置に記憶する工程と、
   前記検索のためのキーワードの入力を受け付ける工程と、
   前記キーワードを前記転置インデックスと照合し、前記キーワードと一致する文字列を検出する工程と、
   前記文字列を含む文書データの情報、及び前記文字列を含む文書データの一部を出力する工程と、
   前記文書データの修正要求を受け付けた場合には、前記修正要求に基づいて、前記転置インデックスを修正する工程と、を備え、
   前記転置インデックスは、前記文書データから抽出された単語をインデックスキーとして含むと共に、各々のインデックスキーに対応する転置データを含み、前記転置データは、当該単語のデータ番号、当該単語が抽出された文書の番号、当該単語の前の単語のデータ番号、および当該単語の次の単語のデータ番号を含み、
   前記転置インデックスを修正する工程では、前記修正要求に基づいて、修正された単語の転置データを削除して修正後の単語の転置データを追加すると共に、前記修正された単語の前の単語の転置データに含まれる次の単語のデータ番号と、前記修正された単語の次の単語の転置データに含まれる前の単語のデータ番号を修正する、文書検索方法。
5. コンピュータを
   検索の対象となる文書データを入力するためのデータ入力部と、
   前記データ入力部を介して入力された前記文書データから転置インデックスを作成するインデックス作成部と、
   前記検索のためのキーワードを入力するための検索キーワード入力部と、
   前記検索キーワード入力部を介して入力されたキーワードを前記転置インデックスと照合し、前記キーワードと一致する文字列を検出する検索部と、
   前記文字列を含む文書データの情報、及び前記文字列を含む文書データの一部を出力する検索結果出力部と、
   前記文書データの修正要求を受付けるデータ修正入力部と、
   前記修正要求に基づいて、前記転置インデックスを修正するデータ修正反映部、として機能させ、
   前記転置インデックスは、前記文書データから抽出された単語をインデックスキーとして含むと共に、各々のインデックスキーに対応する転置データを含み、前記転置データは、当該単語のデータ番号、当該単語が抽出された文書の番号、当該単語の前の単語のデータ番号、および当該単語の次の単語のデータ番号を含み、
   前記データ修正反映部は、前記修正要求に基づいて、修正された単語の転置データを削除して修正後の単語の転置データを追加すると共に、前記修正された単語の前の単語の転置データに含まれる次の単語のデータ番号と、前記修正された単語の次の単語の転置データに含まれる前の単語のデータ番号を修正する、プログラム。