図面 (/)

技術 圧縮プログラムおよび検索プログラム

出願人 富士通株式会社
発明者 片岡正弘大田貴文出内将夫
出願日 2014年12月10日 (5年2ヶ月経過) 出願番号 2014-250289
公開日 2016年6月20日 (3年8ヶ月経過) 公開番号 2016-110587
状態 特許登録済
技術分野 検索装置 計算機におけるファイル管理
主要キーワード ビットフィルタ 単語コード 割り当て順序 上位所定 的番号 ランキング形式 英文テキスト 監視メッセージ
関連する未来課題
重要な関連分野

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

図面 (20)

課題

インデックスのデータサイズを抑えつつ、検索ノイズの発生を抑制すること。

解決手段

ファイルリード部112は、処理対象のファイルから単語を抽出する。格納部114は、抽出された単語が出現頻度の高い高頻度単語である場合、高頻度単語に対応する静的情報が予め登録されたインデックスに、抽出された単語に対応する静的情報に対応付けて単語の出現の有無または単語の出現回数を格納し、抽出された単語が高頻度単語以外の単語である場合、動的に動的情報を割り当て、当該動的情報に対応付けて単語の出現の有無または単語の出現回数を前記インデックスに追加で格納する。

概要

背景

検索対象文字列との関連度が高いファイル検索する技術が存在する。かかる技術では、インデックスを用いて検索対象の文字列中の単語を含むファイルを特定し、特定したファイル毎に検索対象の文字列との関連度を求める。インデックスとは、各単語が含まれるファイルを表す情報ビット列である。そして、検索対象の文字列との関連度が高い順にファイルを列挙することで候補一覧ランキング形式で表示される。

概要

インデックスのデータサイズを抑えつつ、検索ノイズの発生を抑制すること。ファイルリード部112は、処理対象のファイルから単語を抽出する。格納部114は、抽出された単語が出現頻度の高い高頻度単語である場合、高頻度単語に対応する静的情報が予め登録されたインデックスに、抽出された単語に対応する静的情報に対応付けて単語の出現の有無または単語の出現回数を格納し、抽出された単語が高頻度単語以外の単語である場合、動的に動的情報を割り当て、当該動的情報に対応付けて単語の出現の有無または単語の出現回数を前記インデックスに追加で格納する。

目的

一つの側面では、インデックスのデータサイズを抑えつつ、検索ノイズの発生を抑制できる圧縮プログラムおよび検索プログラムを提供する

効果

実績

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

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

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

請求項1

コンピュータに、処理対象ファイルから単語を抽出し、抽出された単語が出現頻度の高い高頻度単語である場合、高頻度単語に対応する静的情報が予め登録されたインデックスに、抽出された単語に対応する静的情報に対応付けて単語の出現の有無または単語の出現回数を格納し、抽出された単語が高頻度単語以外の単語である場合、動的に動的情報を割り当て、当該動的情報に対応付けて単語の出現の有無または単語の出現回数を前記インデックスに追加で格納する処理を実行させることを特徴とする圧縮プログラム

請求項2

前記格納する処理は、前記インデックスに、ファイル単位またはファイルの区分けした所定単位に、単語の出現の有無または単語の出現回数を格納することを特徴とする請求項1に記載の圧縮プログラム。

請求項3

コンピュータに、前記処理対象のファイルから抽出された単語が属する類語情報毎に、当該類語情報に対応する単語が抽出された回数を、前記インデックスに格納する処理をさらに実行させることを特徴とする請求項1または2に記載の圧縮プログラム。

請求項4

コンピュータに、前記他の情報に対応付けて記憶部に格納する処理は、単語と類語情報とをそれぞれ対応付ける類語データベースを用いて、単語が属する類語情報を特定する処理をさらに実行させ、前記前記インデックスに格納する処理は、特定された類語情報毎に、当該類語情報に対応する単語が抽出された回数を、前記インデックスに格納することを特徴とする請求項3に記載の圧縮プログラム。

請求項5

ファイル単位またはファイルの区分けした所定単位に、単語の出現回数を記憶したインデックスから、検索対象文字列に含まれる単語が抽出された回数をファイル毎に取得し、ファイル毎に取得された単語が抽出された回数に基づいて、前記検索対象の文字列との類似度が高いファイルを検索する処理を実行させることを特徴とする検索プログラム

請求項6

前記インデックスは、単語が属する類語情報毎に、当該類語情報に対応する単語が抽出された回数をさらに記憶し、前記取得する処理は、前記インデックスから、前記検索対象の文字列に含まれる単語が属する類語情報が抽出された回数をさらに取得し、前記検索する処理は、ファイル毎に、前記単語が抽出された回数および前記類語情報が抽出された回数に基づいて、検索対象の文字列との類似度が高いファイルを検索することを特徴とする請求項5に記載の検索プログラム。

技術分野

0001

本発明は、圧縮プログラムおよび検索プログラムに関する。

背景技術

0002

検索対象文字列との関連度が高いファイル検索する技術が存在する。かかる技術では、インデックスを用いて検索対象の文字列中の単語を含むファイルを特定し、特定したファイル毎に検索対象の文字列との関連度を求める。インデックスとは、各単語が含まれるファイルを表す情報ビット列である。そして、検索対象の文字列との関連度が高い順にファイルを列挙することで候補一覧ランキング形式で表示される。

先行技術

0003

特開2004−110271号公報
特開平08−147311号公報
特開平09−214352号公報
特開平05−241776号公報

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

0004

このような検索に用いられるインデックスには、例えば、Nグラム(N-Gram)形式のものがある。Nグラム形式のインデックスは、ファイルに、N個の文字が連続したNグラム文字ごとに、それぞれのNグラム文字が含まれるか否かを記録したものである。Nの値を1とした1グラムは、ユニグラム(uni-gram)とも呼ばれる。Nの値を2とした2グラムは、バイグラム(bi-gram)とも呼ばれる。Nの値を3とした3グラムは、トライグラム(tri-gram)とも呼ばれる。

0005

例えば、日本語テキストについて、インデックスを1グラム形式とした場合、インデックスのデータサイズを小さく抑えられるものの、検索ノイズが大きい。例えば、1グラム形式のインデックスが、使用頻度の高い8000個の文字について、各文字がファイルに含まれるかを記録するものとする。このような1グラム形式のインデックスは、8000個の各文字がファイルに含まれるかを記録すればよいため、インデックスのデータサイズを小さく抑えることができる。しかし、1グラム形式のインデックスは、文字ごとに、ファイルに含まれているかを記録するため、検索ノイズが大きい。例えば、「京都の東部」が記録されたファイルについて1グラム形式のインデックスを生成した場合、インデックスには、「京」、「都」、「の」、「東」、「部」の各文字を含んだことが記憶される。このインデックスを用いて、例えば、「東京」が含まれるか否かを検索した場合、インデックスには、「東」、「京」の各文字を含むことが記録されているため、「東京」が含まれると誤って検索されてしまう。

0006

一方、Nグラム形式のインデックスは、Nの値が大きいほど検索ノイズが減少するが、インデックスのデータサイズが大幅に大きくなる。例えば、2グラム形式のインデックスは、使用頻度の高い8000個の文字をそれぞれの組み合わせた2グラム文字ごとに、それぞれの2グラム文字がそれぞれファイルに含まれるかを記録する。例えば、「京都の東部」が記憶されたファイルについて2グラム形式のインデックスを生成した場合、インデックスには、「京都」、「都の」、「の東」、「東部」の各2文字を含むことが記録される。このインデックスを用いて、例えば、「東京」が含まれるか否かを検索した場合、インデックスには、「東京」の2文字を含んだことが記録されていないため、「東京」を含んだファイルとは検索されない。しかし、このような2グラム形式のインデックスは、8000×8000個の2グラム文字の組み合わせについて、ぞれぞれの2グラム文字についてファイルに含まれるかを記録するため、1グラム形式の場合と比較して、インデックスのデータサイズが大幅に大きくなる。このように、Nグラム形式のインデックスは、検索ノイズの減少と、データサイズの減少にトレードオフの関係がある。

0007

さらに、英文テキストにおいても、例えば、「This is a ball」では、1グラムの「a」は、単語「a」や「ball」に含まれ、2グラムの「is」は、単語「This」や「is」に含まれる。そのため、検索ノイズが大きく、数グラムのインデックスが必要となり、日本語テキストと同じようなトレードオフの関係がある。

0008

そこで、高頻度な単語に着目し、例えば、インデックスが、出現頻度の高い高頻度単語については、それぞれの単語がそれぞれファイルに含まれるかを記録し、高頻度単語以外の単語については単語を構成するNグラム文字それぞれがファイルに含まれるかを記録する手法も考えられる。しかしながら、高頻度単語以外の単語については、当該単語を構成するNグラム文字それぞれの有無を記録するため、それぞれの単語がファイルに含まれているかが記録された高頻度単語の場合と異なり、検索ノイズが発生する場合がある。

0009

一つの側面では、インデックスのデータサイズを抑えつつ、検索ノイズの発生を抑制できる圧縮プログラムおよび検索プログラムを提供することを目的とする。

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

0010

第1の案では、圧縮プログラムは、コンピュータに、処理対象のファイルから単語を抽出する処理を実行させる。圧縮プログラムは、コンピュータに、抽出された単語が出現頻度の高い高頻度単語である場合、高頻度単語に対応する静的情報が予め登録されたインデックスに、抽出された単語に対応する静的情報に対応付けて単語の出現の有無または単語の出現回数を格納する処理を実行させる。圧縮プログラムは、コンピュータに、抽出された単語が高頻度単語以外の単語である場合、動的に動的情報を割り当て、当該動的情報に対応付けて単語の出現の有無または単語の出現回数を前記インデックスに追加で格納する処理を実行させる。

発明の効果

0011

本発明の1実施態様によれば、インデックスのデータサイズを抑えつつ、検索ノイズの発生を抑制できるという効果を奏する。

図面の簡単な説明

0012

図1は、実施例1のインデックスを生成する処理の流れを示す図である。
図2Aは、単語の出現頻度を説明する図である。
図2Bは、単語に割り当てる圧縮符号の長さを説明する図である。
図3Aは、Nグラム形式のインデックスの一例を示す図である。
図3Bは、単語ビットマップインデックスの一例を示す図である。
図4は、実施例1のインデックス生成処理にかかるシステム構成の例を示す図である。
図5Aは、実施例1のビットフィルタの一例を示す図である。
図5Bは、実施例1のビットフィルタの一例を示す図である。
図6は、実施例1の動的辞書部のデータ構造の一例を示す図である。
図7は、実施例1の単語ビットマップインデックスの一例を示す図である。
図8は、実施例1のインデックス生成処理の流れの例を示すフロー図である。
図9は、実施例1の検索処理の流れの例を示すフロー図である。
図10は、実施例2のインデックスを生成する処理の流れを示す図である。
図11は、実施例2のインデックス生成処理にかかるシステム構成の例を示す図である。
図12は、実施例2の類語データベースのデータ構造の一例を示す図である。
図13Aは、実施例2のビットフィルタの一例を示す図である。
図13Bは、実施例2のビットフィルタの一例を示す図である。
図14は、カウントマップインデックスの一例を示す図である。
図15は、実施例2のインデックス生成処理の流れの例を示すフロー図である。
図16は、実施例2の検索処理の流れの例を示すフロー図である。
図17は、情報処理装置ハードウェア構成を示す図である。

0013

以下に、本願の開示する圧縮プログラムおよび検索プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの権利範囲が限定されるものではない。各実施例は、処理内容矛盾させない範囲で適宜組み合わせることが可能である。

0014

最初に、図1を用いて、実施例1の情報処理装置100がインデックスを生成する処理について説明する。情報処理装置100は、ファイルを圧縮する際に、インデックスを生成する処理を行う。図1は、実施例1のインデックスを生成する処理の流れを示す図である。図1には、圧縮を行う対象ファイル10に含まれる文章「first cavy was・・・」についてのインデックスを生成する例が示されている。情報処理装置100は、対象ファイル10に含まれる文書から単語単位に、それぞれの単語を取得する。図1の例では、「first」、「cavy」、「was」を取得する。そして、情報処理装置100は、取得した単語をビットフィルタ121と照合する。

0015

ビットフィルタ121は、単語毎の圧縮符号を記憶した圧縮用辞書である。ビットフィルタ121の詳細な構成は、後述する。ビットフィルタ121は、出現頻度の高い高頻度単語については圧縮符号およびインデックスの登録番号が登録され、出現頻度の低い低頻度単語については圧縮符号およびインデックスの登録番号が初期状態では未登録とされている。図1の例では、「cavy」を低頻度単語とし、「first」および「was」を高頻度単語とする。ビットフィルタ121は、高頻度単語である「first」および「was」の圧縮符号が登録され、低頻度単語である「cavy」の圧縮符号が未登録とする。

0016

情報処理装置100は、照合の結果、照合した単語に対応する圧縮符号がビットフィルタ121に登録されている場合、照合した単語の圧縮符号をビットフィルタ121から取得して圧縮ファイルに出力する。一方、情報処理装置100は、照合の結果、照合した単語に対応する圧縮符号がビットフィルタ121に登録されていない場合、新たな圧縮符号を割り当て、動的辞書部122に登録する。また、情報処理装置100は、新たな圧縮符号を照合した単語に対応する圧縮符号として、ビットフィルタ121に登録する。そして、情報処理装置100は、割り当てた新たな圧縮符号を圧縮ファイルに出力する。また、情報処理装置100は、照合した単語が対象ファイル10に含まれていたことを単語ビットマップインデックス123に記録する。

0017

単語ビットマップインデックス123は、ファイル毎に、単語が出現するか否かを記憶したインデックスである。単語ビットマップインデックス123には、高頻度単語がファイルに出現したか否かを記憶する第1記憶領域123aと、低頻度単語がファイルに出現したか否かを記憶する第2記憶領域123bとが設けられている。第1記憶領域123aは、各高頻度単語が対象ファイル10に出現したか否かを記憶するため、予め設けられる。すなわち、第1記憶領域123aは、高頻度単語の分だけ記憶領域が予め確保される。例えば、図1の例では、第1記憶領域123aに、n個のファイルに、それぞれの高頻度単語が出現したか否かを記憶する記憶領域が予め設けられている。第2記憶領域123bは、対象ファイル10に低頻度単語が出現した際に、出現した低頻度単語がファイルに出現したか否かを記憶する記憶領域が追加で設けられる。すなわち、第2記憶領域123bは、対象ファイル10に新たな低頻度単語が出現する毎に、記憶領域が確保される。

0018

ビットフィルタ121には、高頻度単語である「first」の登録番号が予め登録されている。単語ビットマップインデックス123の第1記憶領域123aには、「first」に対応する登録番号「0123h」が予め登録されている。情報処理装置100は、「first」を取得した場合、ビットフィルタ121から「first」の圧縮符号を取得して圧縮ファイルに出力する。また、情報処理装置100は、単語ビットマップインデックス123の第1記憶領域123aに、「first」が対象ファイル10に出現したことを記録する。図1の例では、第1記憶領域123aの登録済みの「first」に対応する登録番号「0123h」のレコードの対象ファイル10に対応するファイル番号「3」に単語がファイルに出現したことを示す「1」が記録されている。なお、本実施例では、登録番号などを16進数で表している。16進数で表した番号には、最後に「h」を付す。

0019

一方、ビットフィルタ121および動的辞書部122は、当初、低頻度単語である「cavy」の圧縮符号が未登録となっている。情報処理装置100は、「cavy」を取得した場合、「cavy」の圧縮符号が登録されていないので、新たに圧縮符号および登録番号を割り当ててビットフィルタ121および動的辞書部122に登録する。また、情報処理装置100は、単語ビットマップインデックス123の第2記憶領域123bに「cavy」の登録番号に対応するレコードを追加し、対象ファイル10に対応するファイル番号3に単語がファイルに出現したことを示す「1」を記録する。図1の例では、第2記憶領域123bに「cavy」に対応する登録番号「2004h」のレコードが追加され、追加されたレコードの対象ファイル10に対応するファイル番号「3」に単語がファイルに出現したことを示す「1」が記録されている。なお、追加されたレコードは、対象ファイル10以前のファイル番号のファイルについては単語がファイルに出現しなかたことが記録されている。図1の例では、登録番号「2004h」のレコードのファイル番号「1」、「2」について出現しなかたことを示す「0」が記録されている。

0020

次に、実施例1の情報処理装置100がビットフィルタ121および単語ビットマップインデックス123を生成する処理について説明する。情報処理装置100は、母集団からビットフィルタ121に登録する各単語の出現頻度を求める。例えば、情報処理装置100は、複数のファイルを母集団として用いて、辞典に登録された各単語の出現頻度を求める。図2Aは、単語の出現頻度を説明する図である。図2Aには、ファイルA、ファイルB、ファイルC等を含む母集団22に含まれる単語の分布表20aが示されている。分布表20aの縦軸は、単語数を示す。図2Aの例では、母集団22は、一般的な辞典に登録された約19万語の単語を有するものとする。分布表20aでは、母集団22の単語数において出現頻度の高い順に単語を並べている。すなわち、単語数は、母集団における単語の出現順位を表す。例えば、母集団22において比較的出現頻度が高い「the」は、単語数「1語」に位置し、比較的出現頻度が低い「zymosis」は、単語数「189,000語」に位置する。なお、母集団22において最も出現頻度の低い単語は、「190,000語」に位置する。

0021

分布表20aの横軸は、符号長を示す。例えば、各単語に、母集団22における出現頻度に応じた符号長を割り当てる。この場合、母集団22において出現頻度の高い単語に対して短い符号長が割り当てられ、出現頻度の低い単語に対して長い符号長が割り当てられる。例えば、分布表20aのように、出現頻度が高い「the」よりも出現頻度が低い「zymosis」に対して長い符号長が割り当てられる。以下、本実施例では、母集団において出現頻度の順位が1〜8000位までの単語を高頻度単語とし、出現頻度の順位が8001位以下の単語を低頻度単語とする。なお、高頻度単語と低頻度単語を分ける境界となっている出現順位8000位は、あくまで一例であり、他の出現順位を境界としてもよい。単語「first」、「was」や、分布表20aに示すように単語「the」、「mouse」、「rat」は、8000位以内の高頻度単語である。一方、単語「cavy」は、8001位以下の低頻度単語である。

0022

分布表20aの横縞は、出現した単語に対応する単語数の位置を表す。分布表20aには、母集団22から収集した19万語の単語が全て登録される。このため、分布表20aでは、単語数1〜190000語の高頻度単語から低頻度単語までの領域にわたって横縞が一様に示されている。

0023

分布表20aに示されるように、各単語に、母集団22における単語の出現頻度に応じた符号長を割り当てた場合、低頻度単語に割り当てられる符号長が長くなる。例えば、低頻度単語である「zymosis」は、出現順位が189000位であり、低頻度単語の中でも出現順位が低いので、割り当てられる符号長が長い。

0024

また、図2Aには、割り当てられた符号長の圧縮符号により対象ファイル10を圧縮した圧縮ファイル23に含まれる単語の分布表20bが示されている。分布表20bは、分布表20aと同様に、縦軸が単語数で、横軸が符号長を示す。圧縮ファイル23は、辞典に登録されている19万語の単語のうちの32000語程度の単語を有する。分布表20bの横縞は、分布表20aに含まれる単語のうち、圧縮ファイル23にも共通して出現した単語に対応する単語数の位置を表す。単語数1〜8000語の高頻度単語は、圧縮ファイル23に大部分出現する。このため、分布表20bでは、単語数1〜8000語の高頻度単語の領域において横縞が一様に示されている。一方、単語数8001〜190000語の低頻度単語は、圧縮ファイル23に一部しか出現しない。このため、分布表20bでは、単語数8001〜190000語の低頻度単語の領域において横縞がまばらに示されている。

0025

ここで、例えば、圧縮ファイル23の各単語に、母集団22における出現頻度に応じた符号長を割り当てた場合、圧縮ファイル23では、低頻度単語の符号長の変化が大きく、単語数の少ない低頻度単語に対して長い符号長が割り当てられる。例えば、「zymosis」のように分布表20bの底辺付近に位置する低頻度単語は、長い符号長が割り当てられる。このため、各単語の圧縮に割り当てられた符号長の圧縮符号を用いて圧縮した場合、圧縮ファイル23は、出現順位が低い低頻度単語に割り当てる可変長符号冗長になるため、圧縮率が低下する。

0026

そこで、本実施例の情報処理装置100は、高頻度単語については出現頻度に応じた可変長の圧縮符号を予め割り当て、低頻度単語については出現した際に固定長の圧縮符号を割り当て、圧縮を行う。図2Bは、単語に割り当てる圧縮符号の長さを説明する図である。図2Bには、図2Aと同様に、母集団22に含まれる単語の分布表上での対象ファイル10に含まれる単語の分布を示す分布表21aが示されている。図2Bの例に示される分布表21aは、図2Aと同様に、縦軸が単語数で、横軸が符号長を示す。分布表21aの横縞は、母集団22に含まれる単語のうち、圧縮対象の対象ファイル10から収集した約32000語の単語に対応する単語数の位置を表す。

0027

例えば、出現順位が1〜8000位までの「the」「a」「of」等の高頻度単語は、母集団22と、対象ファイル10とで概ね共に出現する。このため、分布表21aは、単語数が1〜8000語までの単語で横縞が一様に示されている。一方、出現順位が8001位以下の「zymosis」等の低頻度単語は、母集団22に含まれる単語のうちの一部のみが対象ファイル10に出現する。このため、分布表21aは、単語数が8001〜190000語までは単語で横縞がまばらに示されている。このように単語に対して出現頻度に応じた符号長を割り当てた場合、分布表21bの底辺付近に位置する低頻度単語は、長い符号長が割り当てられる。

0028

そこで、本実施例の情報処理装置100は、高頻度単語に対して出現頻度の高い順に可変長の符号を割り当てる。分布表21bには、単語に割り当てる圧縮符号の長さが示されている。例えば、情報処理装置100は、高頻度単語に対して、出現頻度の高い順に1〜16ビットまでの可変長符号を割り当てる。例えば、情報処理装置100は、分布表21bにおいて、単語数が1〜8000語までの高頻度単語に対して「0000h」〜「9FFFh」までの領域の圧縮符号を割り当てる。また、情報処理装置100は、高頻度単語に対して、登録番号を割り当てる。例えば、情報処理装置100は、8000語の高頻度単語に対応して、順に登録番号を割り当てる。例えば、情報処理装置100は、8000語に対応して「0001h」〜「2000h」を高頻度単語用の登録番号として、静的コードの順に高頻度単語に登録番号を割り当てる。なお、高頻度単語への登録番号の割り当て順序は、これに限定されず、例えば、出現頻度の順としてもよい。高頻度単語の登録番号は、高頻度単語に対して静的に定めるため、以下、「静的番号」とも言う。

0029

また、情報処理装置100は、対象ファイル10に出現した順に、低頻度単語に対して、固定長の符号を割り当てる。例えば、情報処理装置100は、対象ファイル10に出現した順に、低頻度単語に対して16ビットの固定長符号を割り当てる。例えば、情報処理装置100は、低頻度単語に対して、「A000h」〜「FFFFh」までの領域の圧縮符号が割り当てられる。これにより、分布表21bに示されるように、対象ファイル10に出現した順に、8001〜32000語の低頻度単語に固定長の符号が割り当てられる。分布表21aに示す単語数が8001〜190000語の低頻度単語は、出現する頻度が低い。このため、情報処理装置100は、低頻度単語が出現した場合に動的に固定長の符号が割り当てることにより、割り当てる符号の符号長を短くすることができる。例えば、図2Bの例に示されるように、分布表21aの「zymosis」の符号長よりも、分布表21bの「zymosis」の符号長の方が短い。また、情報処理装置100は、低頻度単語に対して、出現した順に登録番号を割り当てる。例えば、情報処理装置100は、「2001h」以降を低頻度単語用の登録番号として、低頻度単語の出現順に低頻度単語に登録番号を割り当てる。低頻度単語の登録番号は、低頻度単語に対して動的に定めるため、以下、「動的番号」とも言う。

0030

情報処理装置100は、出現頻度の高い高頻度単語については割り当てた符号長の圧縮符号および静的番号を登録し、低頻度単語については圧縮符号および動的番号を未登録としてビットフィルタ121を生成する。また、情報処理装置100は、全ての高頻度単語の分の第1記憶領域123aを固定で確保し、低頻度単語については、所定個分、追加可能な第2記憶領域123bを確保した単語ビットマップインデックス123を生成する。図2Bの例では、第2記憶領域123bとして、単語がファイルに出現したか否かを後から動的に記録するための24000語分の記憶領域が確保されている。

0031

ここで、インデックスについて説明する。例えば、インデックスを従来のようなNグラム形式として、Nグラムの文字毎にファイルに含まれるかを記録するものとすると、インデックスのデータサイズが大幅に大きくなる。図3Aは、Nグラム形式のインデックスの一例を示す図である。図3Aに示すNグラム形式のインデックスには、1〜3グラムの文字毎に、各ファイルに文字が出現するか否かが記憶される。例えば、ファイル番号「1」のファイルには、「This is a ball」の英文テキストが含まれる。この場合、Nグラム形式のインデックスには、1グラムの「a」や「b」、2グラムの「is」などのレコードのファイル番号「1」に出現したことを示す「1」が記録される。また、ファイル番号「n」のファイルには、「first cavy was」の英文テキストが含まれる。この場合、Nグラム形式のインデックスには、1グラムの「a」やなどのレコードのファイル番号「n」に出現したことを示す「1」が記録される。ここで、英文テキストの場合、検索ノイズを減らすため、インデックスは、少なくとも3グラム以上の形式とされる。しかし、インデックスをNグラム形式とした場合、データサイズが大きくなる。また、Nグラム形式では、検索ノイズが発生する場合がある。

0032

一方、本実施例では、ファイル毎に、単語が出現するか否かを単語ビットマップインデックス123に記録する。図3Bは、単語ビットマップインデックスの一例を示す図である。図3Bに示す単語ビットマップインデックス123には、高頻度単語については、登録番号に、各高頻度単語の静的番号が予め登録されて高頻度単語の分だけ記憶領域が予め確保され、ファイルに高頻度単語が出現するか否か記憶される。また、単語ビットマップインデックス123には、低頻度単語については、ファイルに出現した順に、登録番号に、低頻度単語の動的番号が登録されて、ファイルに低頻度が出現するか否か記憶される。例えば、ファイル番号「1」のファイルには「This is a ball」の英文テキストが含まれる。この場合、単語ビットマップインデックス123には、高頻度単語「a」のレコードのファイル番号「1」に出現したことを示す「1」が記録される。また、ファイル番号「n」のファイルには、低頻度単語「cavy」を含む「first cavy was」の英文テキストが含まれる。この場合、単語ビットマップインデックス123には、低頻度単語「cavy」のレコードのファイル番号「1」に出現したことを示す「1」が記録される。

0033

情報処理装置100は、単語ビットマップインデックス123に単語毎にファイルに出現したか否かを記録することにより、検索ノイズの発生を抑制できる。また、情報処理装置100は、単語ビットマップインデックス123に高頻度単語については予めレコードを作成し、高頻度単語については出現した際にレコードを作成することでデータサイズを抑えることができる。

0034

次に、図4を用いて、実施例1のインデックス生成処理にかかるシステム構成について説明する。図4は、実施例1のインデックス生成処理にかかるシステム構成の例を示す図である。図4の例のように、情報処理装置100は、圧縮部110と、記憶部120と、検索部130とを有する。記憶部120は例えば、RAM(Random Access Memory)、ROM(Read Only Memory)、フラッシュメモリ(Flash Memory)などの半導体メモリ素子ハードディスク光ディスクなどの記憶装置に対応する。

0035

また、圧縮部110および検索部130の機能は、例えば、CPU(Central Processing Unit)が所定のプログラムを実行することで実現することができる。また、圧縮部110および検索部130の機能は、例えば、ASIC(Application Specific IntegratedCircuit)やFPGA(Field Programmable Gate Array)などの集積回路により実現することができる。

0036

圧縮部110は、圧縮対象のファイルから単語を抽出し、当該単語に符号を付与し、圧縮対象のファイルから抽出された単語毎に、当該単語が抽出された回数を、圧縮対象のファイルを特定する情報に対応付けて記憶部120に格納する。圧縮部110は、辞書作成部111と、ファイルリード部112と、登録部113と、格納部114と、ファイルライト部115とを有する。以下、圧縮部110の各構成について詳細に説明する。

0037

辞書作成部111は、ビットフィルタ121および単語ビットマップインデックス123を作成する処理部である。辞書作成部111は、所定の母集団から辞典に登録された各単語を収集する。例えば、辞書作成部111は、母集団とする複数のテキストファイルから約19万語の単語を収集する。辞書作成部111は、収集した各単語の母集団での出現頻度を求め、高頻度単語と低頻度単語を識別する。辞書作成部111は、収集した単語のそれぞれを基礎単語として、ビットフィルタ121に登録する。辞書作成部111は、例えば、登録した基礎単語のそれぞれに3バイトの静的コードを割り当て、ビットフィルタ121に登録する。また、辞書作成部111は、高頻度単語について、出現頻度の高い順に、短い符号長で圧縮符号を割り当て、ビットフィルタ121に符号長、圧縮符号を登録する。また、辞書作成部111は、単語ビットマップインデックス123を作成する。この単語ビットマップインデックス123では、全ての高頻度単語の分の第1記憶領域123aを固定で確保し、低頻度単語については、所定個分、追加可能な第2記憶領域123bを確保する。

0038

図5Aおよび5Bを用いて、辞書作成部111が作成するビットフィルタ121について説明する。図5Aおよび5Bは、実施例1のビットフィルタの一例を示す図である。図5Aおよび5Bの例のようにビットフィルタ121は、2グラム、ビットマップ、基礎単語へのポインタ、基礎単語、静的コード、動的コード、符号長、圧縮符号、登録番号を有する。登録番号は、静的番号と動的番号に領域が分けられている。

0039

「2グラム」は、各単語に含まれる2グラム文字である。例えば、「able」は、「ab」「bl」「le」に対応する2グラム文字を含む。「ビットマップ」は、2グラム文字が含まれる基礎単語の位置を表す。例えば、2グラム「ab」のビットマップが「1_0_0_0_0」の場合、ビットマップは基礎単語の先頭2文字が「ab」であることを表す。各ビットマップは、基礎単語へのポインタによってそれぞれ基礎単語に対応付けられる。例えば、2グラム「ab」のビットマップ「1_0_0_0_0」は、「able」および「about」に対応付けられる。

0040

「基礎単語」は、ビットフィルタ121に登録された単語である。例えば、辞書作成部111は、母集団から抽出した約19万語の各単語を、それぞれ基礎単語としてビットフィルタ121に登録する。「静的コード」は、各基礎単語に一意に割り当てられる3バイトの単語コードである。「動的コード」は、対象ファイル10に出現する各低頻度単語に割り当てられる16ビット(2バイト)の圧縮符号である。「動的コード」には、初期状態は空白とされ、低頻度単語に対して圧縮符号が割り当てられた際に、圧縮符号が格納される。「符号長」は、各基礎単語に割り当てる圧縮符号の長さである。「圧縮符号」は、高頻度単語に割り当てられた圧縮符号である。例えば、「圧縮符号」には、符号長が「6」の高頻度単語の場合、6ビットの圧縮符号が格納される。登録番号は、単語に付される識別情報である。高頻度単語には、静的番号が順に予め割り当てられる。登録番号の静的番号の領域には、割り当てられた静的番号が登録される。低頻度単語には、出現順に動的番号が割り当てられる。登録番号の動的番号の領域には、低頻度単語が出現した際に、割り当てられた動的番号が格納される。例えば、図5Aに示すビットフィルタ121は、低頻度単語「cavy」について動的番号が未登録とされている。ファイルに低頻度単語「cavy」が出現すると、例えば、動的番号「2004h」が割り当てられ、図5Bに示すように低頻度単語「cavy」について動的番号「2004h」が格納とされる。なお、図5の例では、各項目のデータがレコードとして関連づけられて記憶されている例を示したが、上記説明において互いに関連づけられた項目どうしの関係が保たれれば、データは他の記憶のされ方をしても構わない。

0041

ファイルリード部112は、圧縮を行う対象ファイル10を読み出し、対象ファイル10から単語を抽出する処理部である。例えば、英語ように、文章の単語がスペースなどの所定の区切り文字で区切られる場合、ファイルリード部112は、対象ファイル10の文字列を読み出し、文字列中の区切り文字によって文字列を単語毎に区切ることで、文字列から各単語を抽出する。一方、例えば、日本語ように、文章の単語が特定の区切り文字で区切られていない場合、ファイルリード部112は、対象ファイル10の文字列を読み出を行う。そして、ファイルリード部112は、読み出した文字列に形態素解析構文解析など、文章の言語に応じた自然言語処理を行うことで、文字列から各単語を抽出する。ファイルリード部112は、抽出した単語を登録部113に出力する。

0042

登録部113は、対象ファイル10から抽出された単語の圧縮符号を動的辞書部122に登録する処理部である。登録部113は、ビットフィルタ121において、ファイルリード部112が抽出した単語に対応する基礎単語のレコードを参照する。登録部113は、ビットフィルタ121の「動的コード」に圧縮符号が登録されているか否かに基づいて、ファイルリード部112によって抽出された単語の圧縮符号が、動的辞書部122に登録されているか否かを判定する。

0043

登録部113は、ファイルリード部112によって抽出された単語の圧縮符号が、ビットフィルタ121に登録されていると判定した場合、格納部114に処理を移行させる。

0044

一方、登録部113は、ファイルリード部112によって抽出された単語の圧縮符号が、ビットフィルタ121に登録されていないと判定した場合、抽出された単語に圧縮符号を割り当てる。次いで、登録部113は、抽出された単語の登録番号として、新たな動的番号を採番し、動的番号に対応付けて圧縮符号を動的辞書部122に登録する。

0045

図6を用いて、動的辞書部122への圧縮符号の登録について説明する。図6は、実施例1の動的辞書部のデータ構造の一例を示す図である。図6の例のように、動的辞書部122には、符号列1に「aadvark」、符号列2に「aargh」、符号列3に「ancient」が格納されている。登録部113は、ファイルリード部112によって「cavy」が抽出された場合、符号列4に「cavy」を登録する。登録部113は、例えば、符号列4のデータ領域A(4)に、「cavy」の圧縮符号と、動的辞書部122の動的番号「2004h」とを対応付けて登録する。なお、動的辞書部122には、その他のデータを記憶させてもよい。例えば、動的辞書部122には、登録する単語の静的コードを対応させて記憶してもよい。

0046

次いで、登録部113は、ビットフィルタ121に登録番号を登録する。このように、
単語の登録番号を設定することによって、登録番号により、ビットフィルタ121と動的辞書部122に登録された符号列とが対応付けられる。また、登録部113は、動的辞書部122に登録した圧縮符号をビットフィルタ121の動的コードに登録する。

0047

格納部114は、単語ビットマップインデックス123に情報を格納する処理部である。単語ビットマップインデックス123は、単語毎に、当該単語が出現したか否かを記憶するインデックスである。単語ビットマップインデックス123は、単語毎に各ファイルにおける単語の出現の有無を保持する。格納部114は、ファイルリード部112によって抽出された単語の静的番号または動的番号の登録番号が単語ビットマップインデックス123に登録されているか否かを判定する。

0048

格納部114は、登録番号が登録されていると判定した場合、単語ビットマップインデックス123に記憶された、抽出された単語の登録番号のレコードの対象ファイル10に対応するファイル番号に単語が出現したことを記録する。

0049

一方、格納部114は、登録番号が登録されていないと判定した場合、単語ビットマップインデックス123の第2記憶領域123bに、抽出された単語の動的番号のレコードを追加し、対象ファイル10に対応するファイル番号に単語が出現したことを記録する。

0050

図7を用いて、単語ビットマップインデックス123の更新について説明する。図7は、実施例1の単語ビットマップインデックスの一例を示す図である。格納部114は、単語ビットマップインデックス123に「cavy」の動的番号「2004h」が登録されていない場合、「cavy」の動的番号に対応づけてレコードを単語ビットマップインデックス123に追加する。そして、格納部114は、追加したレコードの「cavy」が抽出されたファイルに対応するファイル番号「3」に単語が出現したことを示す「1」を記録する。

0051

一方、格納部114は、単語ビットマップインデックス123に「cavy」の動的番号が登録されている場合、「cavy」の動的番号に対応するレコードのファイル番号「3」に単語が出現したことを示す「1」を記録する。

0052

ファイルライト部115は、ファイルリード部112によって抽出された単語に圧縮符号を割り当て、圧縮符号を圧縮ファイルに書き込む処理部である。ファイルライト部115は、ビットフィルタ121からファイルリード部112によって抽出された単語に対応する圧縮符号を取得する。ファイルライト部115は、取得した圧縮符号を圧縮ファイルに出力する。また、ファイルライト部115は、各高頻度単語と、当該高頻度単語の母集団での出現頻度を対応付けて圧縮ファイルに出力する。例えば、ファイルライト部115は、各高頻度単語と、当該高頻度単語の母集団での出現頻度とを出現頻度の順に圧縮ファイルのヘッダに記録する。また、ファイルライト部115は、動的辞書部122を圧縮ファイルに出力する。例えば、ファイルライト部115は、動的辞書部122を圧縮ファイルのフッターに記録する。この圧縮ファイルを復元する場合、低頻度単語については、動的辞書部122に基づいて復元される。高頻度単語については、圧縮ファイルに記録された高頻度単語の出現頻度から高頻度単語の圧縮符号を求めて復元される。

0053

検索部130は、検索対象の文字列との類似度が高い圧縮対象のファイルを検索する。検索部130は、受付部131と、取得部132と、特定部133とを有する。以下、検索部130の各構成について詳細に説明する。

0054

受付部131は、検索対象の文字列を受け付ける処理部である。受付部131は、検索対象の文字列を受け付ける入力インタフェースを提供しており、検索対象の文字列を受け付ける。

0055

取得部132は、検索対象の文字列に含まれる単語を含む圧縮ファイルを特定する処理部である。取得部132は、ビットフィルタ121の静的番号の領域および動的番号の領域を参照して、受付部131により受け付けた検索対象の文字列に含まれる単語の登録番号を特定する。取得部132は、登録番号が対応するレコードが単語ビットマップインデックス123に登録されているか判定する。取得部132は、登録番号が対応するレコードが単語ビットマップインデックス123に登録されている場合、登録番号が対応するレコードから検索対象の文字列に含まれる単語を含む各圧縮ファイルを取得する。

0056

特定部133は、検索対象の文字列を含んだファイルを特定する処理部である。特定部133は、取得部132の取得結果に基づき、検索対象の文字列との類似度が高い圧縮対象のファイルを特定する。例えば、特定部133は、検索対象の文字列に含まれる単語を全て、あるいは、所定個以上、あるいは、所定割合以上含んだファイルを、検索対象の文字列を含んだファイルと特定する。なお、検索対象の文字列を含んだファイルを特定する特定方法は、一例であり、これに限定されるものではない。例えば、検索対象の文字列に含まれる単語と一致する単語数が多いファイルほど類似度の高いファイルとしてランキングしてもよい。

0057

このように、情報処理装置100は、インデックスを、単語毎に、当該単語がファイルに含まれるかを記録した単語ビットマップインデックス123としたことにより、検索ノイズの発生を抑制できる。また、情報処理装置100は、圧縮対象のファイルから抽出された単語毎に、単語の出現の有無を単語ビットマップインデックス123に記録することにより、単語ビットマップインデックス123のデータサイズを抑えることができる。また、情報処理装置100は、単語ビットマップインデックス123を用いることで、圧縮されたファイル内を復元して検索することなく、類似度の高いファイルを速やかに検索できる。

0058

次に、図8を用いて実施例1のインデックス生成処理の流れについて説明する。図8は、実施例1のインデックス生成処理の流れの例を示すフロー図である。図8の例のように、圧縮部110は、前処理をおこなう(ステップS10)。例えば、圧縮部110は、前処理として、動的辞書部122に圧縮符号を登録するための記憶領域を確保する。また、辞書作成部111は、前処理として、所定の母集団から各単語の出現頻度を求めて高頻度単語と低頻度単語を識別し、単語ビットマップインデックス123を生成す。また、辞書作成部111は、前処理として、ビットフィルタ121を生成する。

0059

ファイルリード部112は、対象ファイル10を読み出し(ステップS11)、対象ファイル10から単語を抽出する(ステップS12)。登録部113は、抽出した単語をビットフィルタ121の静的辞書部と照合する(ステップS13)。

0060

格納部114は、ビットフィルタ121の静的辞書部において、抽出した単語に対応する基礎単語のレコードの動的コードおよび圧縮符号を参照し、圧縮符号が登録済みであるか否かを判定する(ステップS14)。格納部114は、基礎単語のレコードに圧縮符号が登録済みの場合(ステップS14Yes)、抽出した単語の静的番号または動的番号の登録番号に対応する単語ビットマップインデックス123のレコードに単語が出現したことを記録する(ステップS18)。次いで、格納部114は、ステップS19の処理に移行する。

0061

一方、登録部113は、基礎単語のレコードに圧縮符号が登録されていない場合(ステップS14No)、単語に圧縮符号および動的番号を割り当て、動的番号に対応付けて圧縮符号を動的辞書部122に登録する(ステップS15)。次いで、登録部113は、単語の圧縮符号および動的番号をビットフィルタ121の静的辞書部に登録する(ステップS16)。格納部114は、単語ビットマップインデックス123の第2記憶領域123bに、抽出された単語の動的番号のレコードを追加し、対象ファイル10に対応するファイル番号に単語がファイルに出現したことを記録する(ステップS17)。

0062

ファイルライト部115は、ファイルリード部112によって抽出された単語に対応する圧縮符号を圧縮ファイルに書き込む(ステップS19)。

0063

ファイルリード部112は、ファイルの終端までファイルを読み込んだか否かを判定する(ステップS20)。ファイルリード部112は、ファイルの終端までファイルを読み込んだ場合(ステップS20Yes)、処理を終了させる。一方、ファイルリード部112は、ファイルを読み込んだ位置がファイルの終端に至らない場合(ステップS20No)、ステップS12の処理に戻る。

0064

次に、図9を用いて実施例1の検索処理の流れについて説明する。図9は、実施例1の検索処理の流れの例を示すフロー図である。図9の例のように、受付部131は、検索対象の文字列を受け付ける(ステップS50)。

0065

取得部132は、ビットフィルタ121を参照して、検索対象の文字列に含まれる各単語の静的番号または動的番号から登録番号を特定する(ステップS51)。取得部132は、登録番号に基づいて、単語ビットマップインデックス123から、検索対象の文字列に含まれる単語毎の各圧縮ファイルでの出現の有無を取得する(ステップS52)。特定部133は、取得結果に基づき、検索対象の文字列との類似度が高い圧縮対象のファイルを特定し(ステップS53)、処理を終了する。

0066

以上説明したように、情報処理装置100は、圧縮対象のファイルから単語を抽出し、当該単語に符号を付与する。情報処理装置100は、圧縮対象のファイルから抽出された単語毎に、単語の出現の有無を圧縮対象のファイルを特定する情報に対応付けて記憶部120に格納する。このように、ファイルに含まれる各単語に対応するインデックスを生成することで、情報処理装置100は、インデックスのデータサイズを抑えつつ、検索ノイズの発生を抑制できる。

0067

次に、実施例2について説明する。実施例2では、インデックスを各ファイルにおける単語の出現回数の情報を保持するカウントマップ型インデックスとし、単語および類似語毎に出現回数を記録する場合について説明する。

0068

図10は、実施例2のインデックスを生成する処理の流れを示す図である。図10に示す処理の流れは、図1と一部同様であるため、主に異なる部分について説明する。図10には、圧縮を行う対象ファイル10に含まれる文章「first cavy was・・・」についてのインデックスを生成する例が示されている。情報処理装置100は、対象ファイル10に含まれる文書から単語単位に、それぞれの単語を取得する。図10の例では、「first」、「cavy」、「was」を取得する。情報処理装置100は、取得した単語をビットフィルタ121と照合する。そして、情報処理装置100は、照合した単語が対象ファイル10に含まれていた回数をカウントマップインデックス125に記録する。

0069

カウントマップインデックス125は、ファイル毎に、単語が出現した回数を記憶したインデックスである。カウントマップインデックス125には、高頻度単語がファイルに出現した回数を記憶する第1記憶領域125aと、低頻度単語がファイルに出現した回数を記憶する第2記憶領域125bとが設けられている。また、カウントマップインデックス125には、出現した単語に関する類似語がファイルに出現した回数を記憶する第3記憶領域125cが設けられている。第1記憶領域125aは、各高頻度単語が対象ファイル10に出現した回数か否かを記憶するため、予め設けられる。すなわち、第1記憶領域125aは、高頻度単語の分だけ記憶領域が予め確保される。例えば、図10の例では、第1記憶領域125aに、n個のファイルに、それぞれの高頻度単語が出現した回数を記憶するカウンタが予め設けられている。第2記憶領域125bは、対象ファイル10に低頻度単語が出現した際に、出現した低頻度単語がファイルに出現した回数を記憶するカウンタが追加で設けられる。すなわち、第2記憶領域125bは、対象ファイル10に新たな低頻度単語が出現する毎に、記憶領域が確保される。第3記憶領域125cは、類似語の種類毎に、対象ファイル10に出現した回数を記憶するため、予め設けられる。すなわち、第3記憶領域125cは、類似語の種類の数だけ記憶領域が予め確保される。

0070

情報処理装置100は、照合した単語が高頻度単語である場合、照合した単語の出現回数を第1記憶領域125aに記録し、照合した単語が低頻度単語である場合、照合した単語の出現回数を第2記憶領域125bに記録する。また、情報処理装置100は、照合した単語が含まれる類似語の種類がある場合、照合した単語を含んだ類似語の種類での出現回数を第3記憶領域125cに記録する。

0071

次に、図11を用いて、実施例2のインデックス生成処理にかかるシステム構成について説明する。図11は、実施例2のインデックス生成処理にかかるシステム構成の例を示す図である。図11に示す情報処理装置100は、図4と一部同様であるため、主に異なる部分について説明する。

0072

記憶部120は、類語データベース124をさらに記憶する。類語データベース124は、類似する単語に関する情報を記憶したデータである。例えば、類語データベース124には、類似する単語の群毎に、類似する単語が登録されている。

0073

図12を用いて、類語データベース124について説明する。図12は、実施例2の類語データベースのデータ構造の一例を示す図である。図12の例のように類語データベース124は、類語番号、類似単語を有する。「類語番号」は、類似語の種類を識別するために定められた識別情報である。類語番号には、静的番号および動的番号と重複しないように付与されたコードが格納される。「類似単語」は、互いに類似する単語である。類似単語には、例えば、シソーラスを基に、類似する複数の単語が格納される。例えば、シソーラスには、類似語として約1600種類がある。図12の例では、類語データベース124には、類語番号「F00011h」に対応付けて、「mouse」、「rat」、「cavy」、・・・が登録されている。

0074

辞書作成部111は、ビットフィルタ121およびカウントマップインデックス125を作成する処理部である。辞書作成部111は、所定の母集団から辞書に登録された各単語を収集する。辞書作成部111は、収集した各単語の母集団での出現頻度を求め、高頻度単語と低頻度単語を識別する。辞書作成部111は、収集した単語のそれぞれを基礎単語として、ビットフィルタ121に登録する。辞書作成部111は、例えば、登録した基礎単語のそれぞれに3バイトの静的コードを割り当て、ビットフィルタ121に登録する。また、辞書作成部111は、高頻度単語について、出現頻度の高い順に、短い符号長で圧縮符号を割り当て、ビットフィルタ121に符号長、圧縮符号を登録する。また、辞書作成部111は、高頻度単語が類語データベース124に登録されている場合、高頻度単語を含んだ類似語の種類の類語番号をビットフィルタ121に登録する。また、辞書作成部111は、カウントマップインデックス125を作成する。このカウントマップインデックス125では、全ての高頻度単語の分の第1記憶領域125aを固定で確保し、低頻度単語については、所定個分、追加可能な第2記憶領域125bを確保し、類似語の種類の数分の第3記憶領域125cを固定で確保する。

0075

図13Aおよび図13Bは、実施例2のビットフィルタの一例を示す図である。図13Aおよび図13Bに示すビットフィルタ121は、図5と一部同様であるため、主に異なる部分について説明する。ビットフィルタ121は、類似種別をさらに有する。「類似種別」は、類似語の種類である。類似種別には、単語に類似語がある場合、単語が属する類似語の種類を示す類似情報が格納される。例えば、図13Aに示すビットフィルタ121は、類似語を有する低頻度単語「cavy」について、登録番号に動的番号が未登録とされ、類似種別も未登録とされている。ファイルに低頻度単語「cavy」が出現すると、例えば、動的番号「2004h」が割り当てられ、図13Bに示すように低頻度単語「cavy」について登録番号に動的番号「2004h」が格納とされ、類似種別に類語番号「F00011h」が格納されている。

0076

格納部114は、カウントマップインデックス125に情報を格納する処理部である。カウントマップインデックス125は、単語毎に、当該単語の出現回数を記憶するインデックスである。カウントマップインデックス125は、単語毎に各ファイルにおける単語の出現回数を保持する。格納部114は、ファイルリード部112によって抽出された単語の静的番号または動的番号の登録番号がカウントマップインデックス125の第1記憶領域125aまたは第2記憶領域125bに登録されているか否かを判定する。

0077

格納部114は、登録番号が登録されていると判定した場合、カウントマップインデックス125に記憶された、抽出された単語の登録番号のレコードの対象ファイル10に対応するファイル番号に単語の出現回数を記録する。

0078

一方、格納部114は、登録番号が登録されていないと判定した場合、カウントマップインデックス125の第2記憶領域125bに、抽出された単語の動的番号のレコードを追加する。そして、格納部114は、追加したレコードの対象ファイル10に対応するファイル番号に単語の出現回数を記録する。

0079

また、格納部114は、ファイルリード部112によって抽出された単語の類語番号がカウントマップインデックス125の第3記憶領域125cに登録されているか否かを判定する。

0080

格納部114は、類語番号が登録されていると判定した場合、カウントマップインデックス125に記憶された、抽出された単語の類語番号のレコードの対象ファイル10に対応するファイル番号に類似語の出現回数を記録する。

0081

一方、格納部114は、類語番号が登録されていないと判定した場合、カウントマップインデックス125の第3記憶領域125cに、抽出された単語の類語番号のレコードを追加する。そして、格納部114は、追加したレコードの対象ファイル10に対応するファイル番号に類似語の出現回数を記録する。

0082

図14を用いて、カウントマップインデックス125の更新について説明する。例えば、ファイル番号「3」に対応するファイルで単語「cavy」が抽出された場合、格納部114は、第2記憶領域125bに「cavy」の動的番号に対応するレコードが存在するため、当該レコードのファイル番号「3」に単語の出現回数を記録する。

0083

格納部114は、カウントマップインデックス125の第3記憶領域125cに「cavy」の類語番号が登録されてない場合、カウントマップインデックス125の第3記憶領域125cに、「cavy」の類語番号「F00011h」に対応づけてレコードを追加する。そして、格納部114は、ファイル番号「3」に単語の出現回数を記録する。

0084

一方、格納部114は、カウントマップインデックス125の第3記憶領域125cに「cavy」の類語番号が登録されている場合、「cavy」の類語番号に対応するレコードのファイル番号「3」に類似語の出現回数を記録する。

0085

なお、図14に示すカウントマップインデックス125では、出現回数を記録するカウンタを4ビットとしているが、カウンタのビット数はこれに限定されるものではない。また、カウンタには、離散的に出現回数を対応させてもよい。例えば、格納部114は、カウンタの値「1」に対して、出現回数「1」、カウンタの値「2」に対して、出現回数「3」、カウンタの値「3」に対して、出現回数「7」などと、カウンタの値に対して指数的に出現回数を対応させて記録してもよい。

0086

取得部132は、ビットフィルタ121の静的番号の領域および動的番号の領域を参照して、受付部131により受け付けた検索対象の文字列に含まれる単語の登録番号を特定する。また、取得部132は、ビットフィルタ121の類似種別の領域を参照して、受付部131により受け付けた検索対象の文字列に含まれる単語の類語番号を特定する。そして、取得部132は、カウントマップインデックス125の登録番号が対応するレコードから各圧縮ファイルでの単語の出現回数を、単語が抽出された回数として取得する。また、取得部132は、カウントマップインデックス125の類語番号が対応するレコードから各圧縮ファイルでの類似語の出現回数を、単語が属する類語情報が抽出された回数として取得する。

0087

特定部133は、検索対象の文字列と類似度の高い文字列を含んだファイルを特定する処理部である。特定部133は、取得部132により取得された単語が抽出された回数および類語情報が抽出された回数に基づいて、検索対象の文字列との類似度が高い圧縮対象のファイルを特定する。例えば、特定部133は、ファイル毎に、単語が抽出された回数および類似語の出現回数を重み付け演算してスコアを算出する。例えば、特定部133は、単語が抽出された回数に対して大きい重み値乗算し、類似語の出現回数に対して小さい重み値を乗算し、乗算結果を全て加算してスコアを算出する。このスコアは、単語が抽出された回数、類似語が抽出された回数が多いほど値が大きくなる。特定部133は、スコアに基づいて、検索対象の文字列と類似度の高い文字列を含んだファイルを特定する。例えば、特定部133は、スコアが上位所定位以上、あるいは、スコアが所定のしきい値以上のファイルを、類似度の高いファイルと特定する。特定部133は、特定したファイルを検索結果として出力する。なお、上記のスコアの算出方法は、一例であり、これに限定されるものではない。単語が抽出された回数、類似語が抽出された回数が多いファイルほどスコアを高く算出できれば、何れの算出方法を用いてもよい。

0088

このように、情報処理装置100は、インデックスを、単語毎に、当該単語がファイルに含まれるかを記録したカウントマップインデックス125としたことにより、検索ノイズの発生を抑制できる。また、情報処理装置100は、圧縮対象のファイルから抽出された単語毎に、単語が抽出された回数、類似語が抽出された回数をカウントマップインデックス125に記録することにより、カウントマップインデックス125のデータサイズを抑えることができる。また、情報処理装置100は、単語ビットマップインデックス123を用いることで、圧縮されたファイル内を復元して検索することなく、類似度の高いファイルを速やかに検索できる。

0089

次に、図15を用いて実施例2のインデックス生成処理の流れについて説明する。図15は、実施例2のインデックス生成処理の流れの例を示すフロー図である。図15に示すインデックス生成処理は、図8と一部同様であるため、主に異なる部分について説明する。

0090

図15の例のように、格納部114は、基礎単語のレコードに圧縮符号が登録済みの場合(ステップS14Yes)、抽出した単語の静的番号または動的番号の登録番号に対応するレコードに単語の出現回数を記録する(ステップS30)。次いで、格納部114は、ステップS32の処理に移行する。

0091

一方、ステップS16の後、格納部114は、単語ビットマップインデックス123の第2記憶領域125bに抽出された単語の動的番号のレコードを追加し、対象ファイル10に対応するファイル番号に単語の出現回数を記録する(ステップS31)。次いで、格納部114は、ステップS32の処理に移行する。

0092

格納部114は、ファイルリード部112によって抽出された単語の類語番号がカウントマップインデックス125の第3記憶領域125cに登録されているか否かを判定する(ステップS32)。

0093

格納部114は、抽出された単語の類語番号が登録されている場合(ステップS32Yes)、抽出された単語の類語番号のレコードの対象ファイル10に対応するファイル番号に類似語の出現回数を記録する(ステップS33)。次いで、格納部114は、ステップS19の処理に移行する。

0094

一方、格納部114は、抽出された単語の類語番号が登録されていないと判定した場合(ステップS32No)、第3記憶領域125cに抽出された単語の類語番号のレコードを追加する。そして、格納部114は、対象ファイル10に対応するファイル番号に類似語の出現回数を記録する(ステップS34)。次いで、格納部114は、ステップS19の処理に移行する。

0095

次に、図16を用いて実施例2の検索処理の流れについて説明する。図16は、実施例2の検索処理の流れの例を示すフロー図である。図16に示す検索処理は、図9と一部同様であるため、主に異なる部分について説明する。

0096

取得部132は、ビットフィルタ121を参照して、検索対象の文字列に含まれる単語の登録番号および類語番号を特定する(ステップS55)。取得部132は、登録番号および類語番号に基づいて、カウントマップインデックス125から、各圧縮ファイルでの単語の出現回数、類似語の出現回数を取得する(ステップS56)。特定部133は、ファイル毎に、単語の出現回数、類似語の出現回数を重み付け演算してスコアを算出する(ステップS57)。特定部133は、スコアに基づいて、検索対象の文字列と類似度の高い文字列を含んだファイルを特定し(ステップS58)、処理を終了する。

0097

以上説明したように、情報処理装置100は、圧縮対象のファイルから単語を抽出し、当該単語に符号を付与する。情報処理装置100は、圧縮対象のファイルから抽出された単語毎に、単語の出現回数を圧縮対象のファイルを特定する情報に対応付けて記憶部120に格納する。このように、ファイルに含まれる各単語に対応するインデックスを生成することで、辞典に登録されている全ての単語に対応するインデックスを生成する場合に比べ、インデックスの容量を小さくすることができる。また、検索対象の文字列との関連度が高いファイルを検索するときに、インデックスから各単語の出現回数を取得することで、検索時間を短縮することができる。

0098

また、情報処理装置100は、圧縮対象のファイルから抽出された単語が属する類語情報毎に、当該類語情報に対応する単語が抽出された回数を、圧縮対象のファイルを特定する他の情報に対応付けて記憶部120に格納する。これにより、情報処理装置100は、検索対象の文字列と類似語を含んで関連度が高いファイルを検索するときに、インデックスから各単語の類似語の出現回数を取得することで、検索時間を短縮することができる。

0099

また、情報処理装置100は、単語と類語情報とをそれぞれ対応付ける類語データベース124を用いて、単語が属する類語情報を特定する。これにより、情報処理装置100は、類語データベース124から単語が属する類語情報を速やかに特定できる。

0100

また、情報処理装置100は、圧縮対象のファイルから抽出された単語毎に、当該単語が抽出された回数を対応付けた圧縮対象のファイルを特定する情報から、検索対象の文字列に含まれる単語が抽出された回数を圧縮対象のファイル毎に取得する。情報処理装置100は、圧縮対象のファイル毎に取得された単語が抽出された回数に基づいて、検索対象の文字列との類似度が高い圧縮対象のファイルを検索する。これにより、情報処理装置100は、検索対象の文字列との類似度が高い圧縮対象のファイルを速やかに検索できる。

0101

また、情報処理装置100は、圧縮対象のファイルから抽出された単語が属する類語情報毎に、当該類語情報に対応する単語が抽出された回数を対応付けた圧縮対象のファイルを特定する他の情報から、検索対象の文字列に含まれる単語が属する類語情報が抽出された回数を取得する。情報処理装置100は、圧縮対象のファイル毎に取得した単語が抽出された回数および類語情報が抽出された回数に基づいて、検索対象の文字列との類似度が高い圧縮対象のファイルを検索する。これにより、情報処理装置100は、類似語を考慮して、検索対象の文字列との類似度が高い圧縮対象のファイルを速やかに検索できる。

0102

さて、これまで開示の装置に関する実施例について説明したが、開示の技術は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。

0103

例えば、上記の実施例では、複数のテキストファイルを含む母集団から基礎単語を収集したが、これに限定されない。一つのテキストファイルから基礎単語を収集してもよい。

0104

また、上記の実施例では、低頻度単語に対して16ビットの固定長の圧縮符号を割り当てる旨を説明したが、これに限定されない。低頻度単語に対して16ビット以外のビット数を割り当ててもよい。

0105

また、上記の実施例では、8000位以上の単語に可変長符号を割り当て、8000位以下の単語に固定長符号を割り当てたが、これに限定されない。8000位以外の順位を境界にして可変長符号または固定長符号を単語に割り当ててもよい。

0106

また、圧縮処理の対象は、ファイル内のデータ以外にも、システムから出力される監視メッセージなどでもよい。例えば、バッファに順次格納される監視メッセージを上述の圧縮処理により圧縮し、ログファイルとして格納するなどの処理が行なわれる。また、例えば、データベース内のページ単位に圧縮が行なわれてもよいし、複数のページをまとめた単位で圧縮が行なわれてもよい。

0107

また、上記の実施例では、インデックスに、ファイル単位に、単語の出現の有無または単語の出現回数を格納したが、これに限定されない。例えば、インデックスは、ファイルの文章の章単位や、段落単位、所定のデータサイズに分けたブロック単位など、所定単位に単語の出現の有無または単語の出現回数を記憶してもよい。格納部114は、インデックスに、ファイルの区分けした所定単位に、単語の出現の有無または単語の出現回数を格納してもよい。また、取得部132は、このように所定単位に単語の出現回数を格納したインデックスからから、検索対象の文字列に含まれる単語が抽出された回数をファイル毎に取得してもよい。

0108

また、上記の実施例に示した処理手順制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。

0109

また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、辞書作成部111、ファイルリード部112、登録部113、格納部114、ファイルライト部115、受付部131、取得部132および特定部133の各処理部が適宜統合されてもよい。また、各処理部の処理が適宜複数の処理部の処理に分離されてもよい。さらに、各処理部にて行なわれる各処理機能は、その全部または任意の一部が、CPUおよび該CPUにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。

0110

図17は、情報処理装置のハードウェア構成を示す図である。図17に示すように、コンピュータ200は、各種演算処理を実行するCPU201と、ユーザからのデータ入力を受け付ける入力装置202と、モニタ203とを有する。また、コンピュータ200は、記憶媒体からプログラム等を読み取る媒体読取装置204と、他の装置と接続するためのインターフェース装置205と、他の装置と無線により接続するための無線通信装置206とを有する。また、コンピュータ200は、各種情報一時記憶するRAM(Random Access Memory)207と、ハードディスク装置208とを有する。また、各装置201〜208は、バス209に接続される。

0111

ハードディスク装置208には、例えば、圧縮部110の辞書作成部111、ファイルリード部112、登録部113、格納部114およびファイルライト部115の各処理部と同様の機能を有する情報処理プログラムが記憶される。また、ハードディスク装置208には、例えば図4および図11に示した検索部130の受付部131、取得部132および特定部133の各処理部と同様の機能を有する情報処理プログラムが記憶される。また、ハードディスク装置208には、情報処理プログラムを実現するための各種データが記憶される。

0112

CPU201は、ハードディスク装置208に記憶された各プログラムを読み出して、RAM207に展開して実行することで各種の処理を行う。これらのプログラムは、コンピュータ200を、例えば、辞書作成部111、ファイルリード部112、登録部113、格納部114およびファイルライト部115として機能させることができる。さらに、これらのプログラムは、コンピュータ200を、受付部131、取得部132および特定部133として機能させることができる。

実施例

0113

なお、上記の情報処理プログラムは、必ずしもハードディスク装置208に記憶されている必要はない。例えば、コンピュータ200が読み取り可能な記憶媒体に記憶されたプログラムを、コンピュータ200が読み出して実行するようにしてもよい。コンピュータ200が読み取り可能な記憶媒体は、例えば、CD−ROMDVDディスク、USB(Universal Serial Bus)メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリハードディスクドライブ等が対応する。また、公衆回線インターネット、LAN(Local Area Network)等に接続された装置にこのプログラムを記憶させておき、コンピュータ200がこれらからプログラムを読み出して実行するようにしてもよい。

0114

10対象ファイル
100情報処理装置
110圧縮部
111辞書作成部
112ファイルリード部
113登録部
114 格納部
115 ファイルライト部
120 記憶部
121ビットフィルタ
122 動的辞書部
123 単語ビットマップインデックス
123a 第1記憶領域
123b 第2記憶領域
124類語データベース
125カウントマップインデックス
125a 第1記憶領域
125b 第2記憶領域
125c 第3記憶領域
130検索部
131 受付部
132 取得部
133 特定部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

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

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

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

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い 技術一覧

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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