図面 (/)

技術 全文検索装置、プログラム及び記録媒体

出願人 株式会社リコー
発明者 平岡卓也
出願日 2012年2月29日 (7年6ヶ月経過) 出願番号 2012-043121
公開日 2013年9月9日 (6年0ヶ月経過) 公開番号 2013-178711
状態 特許登録済
技術分野 検索装置
主要キーワード バキューム処理 削除回数 論理差 検索処理用 活動報告 ファイル方式 電子図書館 入出力単位
関連する未来課題
重要な関連分野

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

図面 (13)

課題

転置ファイルのサイズの増加を防ぐことができる全文検索装置プログラム及び記録媒体を提供することを課題とする。

解決手段

全文検索装置100において、検索用全文索引記憶部8と、登録用全文索引記憶部9と、削除用全文索引記憶部10と、登録用全文索引記憶部9及び削除用全文索引記憶部10から検索用全文索引記憶部8へデータをマージするマージ手段11と、削除領域情報に基づき、検索用全文索引記憶部8から削除領域解放する領域解放手段12とを有し、マージ手段11は削除用全文索引記憶部10からデータを検索用全文索引記憶部8へマージするとき、削除領域情報を検索用全文索引記憶部8へ付加し、領域解放手段12は削除用全文索引記憶部10から検索用全文索引記憶部8へのデータのマージの結果が所定条件を満たすとき、検索用全文索引記憶部8の削除領域を解放することで上記課題を解決する。

概要

背景

近年、情報通信技術発達により電子化された文書電子化文書)及びその電子化文書に関する情報がインターネットなどを介して大量に流通している。この電子化文書及びその電子化文書に関する情報の流通に際し、所望の電子化文書を精度よく、さらには高速検索する文書検索装置が提案されている。

文書検索装置ではキーワード検索手法や全文検索手法が用いられている。全文検索手法を用いた全文検索装置は、任意の検索文字列検索対象の電子化文書の全てとの間で照合を行なって、検索文字列を含む電子化文書を漏れなく抽出する装置である。全文検索手法を用いた全文検索装置は、キーワード検索手法のように、検索対象となる全ての電子化文書に対してキーワードを予め付与するといった多大な人力が必要ない。

全文検索装置としては、様々な種類のものが提案されている。全文検索装置の1種としては、転置索引ファイル方式を採用した装置がある。転置ファイル方式を採用した全文検索装置は、検索のための補助ファイルとして文字/単語/n-gram(n文字連接)などが出現する電子化文書、或いはそれらの電子化文書中の出現位置を記録する転置ファイルを予め構築しておく。そして、転置ファイル方式を採用した全文検索装置は、全文検索時に、転置ファイルを用いて検索することで非常に高速な検索を行なうことができ、大量の電子化文書の高速検索が要求されるシステムに対して有効である。

なお、全文検索方式一般、転置ファイル方式の詳細については、文献「情報検索アルゴリズム」(研二、津田和彦、獅々堀正著、共立出版株式会社、pp.160-179)、特開平11−073429号公報の従来技術、及び全文検索システム協議会平成10年度活動報告(http://www.ftsanet.com/dbtokyo99/Db99.htm)などで述べられており、公知であるのでその説明を省略する。

転置ファイル方式を採用した全文検索装置では、通常、原データ(電子化文書)の数倍にも及ぶ転置ファイルを構築する必要がり、登録されている電子化文書のデータ量が多くなるに従って登録・削除処理に時間を要するようになる。そこで、従来は、利用者側からみた登録・削除処理のレスポンスタイムを短くすることができる全文検索装置が知られていた(例えば特許文献1参照)。

概要

転置ファイルのサイズの増加を防ぐことができる全文検索装置、プログラム及び記録媒体を提供することを課題とする。全文検索装置100において、検索用全文索引記憶部8と、登録用全文索引記憶部9と、削除用全文索引記憶部10と、登録用全文索引記憶部9及び削除用全文索引記憶部10から検索用全文索引記憶部8へデータをマージするマージ手段11と、削除領域情報に基づき、検索用全文索引記憶部8から削除領域解放する領域解放手段12とを有し、マージ手段11は削除用全文索引記憶部10からデータを検索用全文索引記憶部8へマージするとき、削除領域情報を検索用全文索引記憶部8へ付加し、領域解放手段12は削除用全文索引記憶部10から検索用全文索引記憶部8へのデータのマージの結果が所定条件を満たすとき、検索用全文索引記憶部8の削除領域を解放することで上記課題を解決する。

目的

本発明は、上記の点に鑑みなされたもので、転置ファイルのサイズの増加を防ぐことができる全文検索装置、プログラム及び記録媒体を提供する

効果

実績

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

この技術が所属する分野

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

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

請求項1

指定された文字列を含む文書を複数の文書データから検索する全文検索装置において、検索用全文索引記憶部と、登録用の全文索引記憶部と、削除用の全文索引記憶部と、前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段と、削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段とを有し、前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、前記領域解放手段は、前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へのデータのマージの結果が所定の条件を満たすとき、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放することを特徴とする全文検索装置。

請求項2

前記領域解放手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージした回数、又は、前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へマージしたデータのサイズが、閾値に達すると、前記削除するデータが記憶されている領域を解放することを特徴とする請求項1記載の全文検索装置。

請求項3

前記検索用の全文索引記憶部、前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部は、入出力単位である固定長ページに前記データを格納していることを特徴とする請求項1又は2記載の全文検索装置。

請求項4

前記領域解放手段は、前記マージ手段が前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージしたあとで、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放することを特徴とする請求項1乃至3何れか一項記載の全文検索装置。

請求項5

前記マージ手段は、前記領域解放手段が前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放したあとで、前記登録用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージすることを特徴とする請求項4記載の全文検索装置。

請求項6

指定された文字列を含む文書を複数の文書データから検索するコンピュータを、検索用の全文索引記憶部、登録用の全文索引記憶部、削除用の全文索引記憶部、前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段、削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段として機能させ、前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、前記領域解放手段は、前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へのデータのマージの結果が所定の条件を満たすとき、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放することを特徴とするプログラム

請求項7

請求項6に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体

技術分野

0001

本発明は、全文検索装置プログラム及び記録媒体に関する。

背景技術

0002

近年、情報通信技術発達により電子化された文書電子化文書)及びその電子化文書に関する情報がインターネットなどを介して大量に流通している。この電子化文書及びその電子化文書に関する情報の流通に際し、所望の電子化文書を精度よく、さらには高速検索する文書検索装置が提案されている。

0003

文書検索装置ではキーワード検索手法や全文検索手法が用いられている。全文検索手法を用いた全文検索装置は、任意の検索文字列検索対象の電子化文書の全てとの間で照合を行なって、検索文字列を含む電子化文書を漏れなく抽出する装置である。全文検索手法を用いた全文検索装置は、キーワード検索手法のように、検索対象となる全ての電子化文書に対してキーワードを予め付与するといった多大な人力が必要ない。

0004

全文検索装置としては、様々な種類のものが提案されている。全文検索装置の1種としては、転置索引ファイル方式を採用した装置がある。転置ファイル方式を採用した全文検索装置は、検索のための補助ファイルとして文字/単語/n-gram(n文字連接)などが出現する電子化文書、或いはそれらの電子化文書中の出現位置を記録する転置ファイルを予め構築しておく。そして、転置ファイル方式を採用した全文検索装置は、全文検索時に、転置ファイルを用いて検索することで非常に高速な検索を行なうことができ、大量の電子化文書の高速検索が要求されるシステムに対して有効である。

0005

なお、全文検索方式一般、転置ファイル方式の詳細については、文献「情報検索アルゴリズム」(研二、津田和彦、獅々堀正著、共立出版株式会社、pp.160-179)、特開平11−073429号公報の従来技術、及び全文検索システム協議会平成10年度活動報告(http://www.ftsanet.com/dbtokyo99/Db99.htm)などで述べられており、公知であるのでその説明を省略する。

0006

転置ファイル方式を採用した全文検索装置では、通常、原データ(電子化文書)の数倍にも及ぶ転置ファイルを構築する必要がり、登録されている電子化文書のデータ量が多くなるに従って登録・削除処理に時間を要するようになる。そこで、従来は、利用者側からみた登録・削除処理のレスポンスタイムを短くすることができる全文検索装置が知られていた(例えば特許文献1参照)。

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

0007

転置ファイル方式を採用した全文検索装置では全文索引の構成要素を転置ファイルに実装するとき、転置ファイルを、データ長固定長ページブロック)に実装するのが一般的である。なお、全文索引の構成要素は、電子化文書の登録や削除によりデータ長が変動する。

0008

したがって、従来の転置ファイル方式を採用した全文検索装置では、全文索引の構成要素を固定長のページに分割して格納しているため、電子化文書の登録や削除によりページ内に空き領域が発生してしまう。一般に、電子化文書の登録であれば、ページ内に発生する空き領域は小さい。一方、電子化文書の削除の場合、ページ内に発生する空き領域は大きくなる。このように、電子化文書の削除の場合、従来の転置ファイル方式を採用した全文検索装置では、転置ファイルが格納されたページの利用率が低下し、転置ファイルのサイズ(データ量)が大きくなってしまうという問題があった。

0009

本発明は、上記の点に鑑みなされたもので、転置ファイルのサイズの増加を防ぐことができる全文検索装置、プログラム及び記録媒体を提供することを目的とする。

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

0010

上記課題を解決するため、請求項1に記載した全文検索装置は、指定された文字列を含む文書を複数の文書データから検索する全文検索装置において、検索用の全文索引記憶部と、登録用の全文索引記憶部と、削除用の全文索引記憶部と、前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段と、削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段とを有し、前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、前記領域解放手段は、前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へのデータのマージの結果が所定の条件を満たすとき、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放することを特徴とする。

0011

なお、本発明の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、データ構造などに適用したものも本発明の態様として有効である。

発明の効果

0012

本発明によれば、転置ファイルのサイズの増加を防ぐことができる。

図面の簡単な説明

0013

本実施形態に係る全文検索装置の一例のハードウェア構成図である。
本実施形態に係る全文検索装置をサーバクライアントで構成した場合の一例のシステム構成図である。
本実施形態に係る全文検索装置の一例の処理ブロック図である。
本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャート(1/3)である。
本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャート(2/3)である。
本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャート(3/3)である。
本実施形態に係る全文検索装置の処理の一例を説明する為の説明図である。
マージ処理及びバキューム処理概要を説明する為の説明図である。
転置リスト論理的な構造について説明する為の説明図である。
入出力単位であるページに合わせて格納された転置リストの構造について説明する為の説明図である。
削除回数記憶部に記録されているバキューム処理を実施するか否かを判断するための情報の一例の構成図である。
テップS28の処理の詳細を表したフローチャートである。

実施例

0014

次に、本発明の実施の形態について、詳細に説明する。
[第1の実施形態]
<ハードウェア構成>
図1は本実施形態に係る全文検索装置の一例のハードウェア構成図である。図1の全文検索装置100は、スタンドアローンで構成した場合のハードウェア構成の一例を示している。

0015

図1に示した全文検索装置100は、入力装置101、表示装置102、外部I/F103、RAM(Random Access Memory)104、ROM(Read Only Memory)105、CPU(Central Processing Unit)106、通信I/F107、及びHDD(Hard Disk Drive)108などを備え、それぞれがバスBで相互に接続されている。

0016

入力装置101はキーボードマウスなどを含み、全文検索装置100に各操作信号を入力するのに用いられる。表示装置102はディスプレイなどを含み、全文検索装置100による処理結果を表示する。通信I/F107は全文検索装置100をネットワークに接続するインタフェースである。

0017

HDD108は、プログラムやデータを格納している不揮発性記憶装置である。格納されるプログラムやデータには、全文検索装置100全体を制御する基本ソフトウェアであるOS(Operating System)、及びOS上において各種機能を提供するアプリケーションソフトウェアなどがある。また、HDD108は格納しているプログラムやデータを、所定のファイルシステム及び/又はDB(Data Base)により管理している。

0018

外部I/F103は、外部装置とのインタフェースである。外部装置には、記録媒体103aなどがある。これにより、全文検索装置100は外部I/F103を介して、記録媒体103aの読み取り及び/又は書き込みを行うことができる。記録媒体103aにはフレキシブルディスク、CD(Compact Disk)、DVD(Digital Versatile Disk)、SDメモリカード(SD Memory card)、USBメモリ(Universal Serial Bus memory)等がある。

0019

ROM105は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリ(記憶装置)である。ROM105には、全文検索装置100の起動時に実行されるBIOS(Basic Input/Output System)、OS設定、及びネットワーク設定などのプログラムやデータが格納されている。RAM104は、プログラムやデータを一時保持する揮発性の半導体メモリ(記憶装置)である。

0020

CPU106は、ROM105やHDD108などの記憶装置からプログラムやデータをRAM104上に読み出し、処理を実行することで、全文検索装置100全体の制御や機能を実現する演算装置である。

0021

本実施形態に係る全文検索装置100は、上記ハードウェア構成により、後述するような各種処理を実現できる。

0022

図2は本実施形態に係る全文検索装置をサーバ/クライアントで構成した場合の一例のシステム構成図である。なお、全文検索装置100及び端末装置110のハードウェア構成は図1と同様である。

0023

図2の全文検索システム200はサーバとしての全文検索装置100及びクライアントとしての端末装置110が、インターネットやLANなどのネットワークN1を介して接続可能である。ネットワークN1は有線通信無線通信の何れかであっても、両方を含むものであってもよい。

0024

端末装置110は全文検索装置100にアクセス可能である。全文検索装置100は端末装置110からの要求(リクエスト)に対して応答レスポンス)できる。全文検索装置100は、複数の文書データ(複数の電子化文書)から、指定された文字列を含む文書データを検索する装置である。

0025

なお、本実施形態において、全文検索装置100における「全文検索」とは、検索すべき全ての文字列を対象とした検索であることを意味している。したがって、例えばSGML等のタグ付の文書であれば、全文検索装置100は、適宜、所定のタグ間にある文字列を検索の対象としてもよい。

0026

また、図2の全文検索システム200は、1台の全文検索装置100を含む構成を一例として表しているが、全文検索装置100で行う一部の処理を行う他のサーバ装置などが含まれていてもよい。

0027

ソフトウェア構成
全文検索装置100は、例えば図3に示すような処理ブロックで実現される。図3は本実施形態に係る全文検索装置の一例の処理ブロック図である。全文検索装置100はプログラムを実行することで、入力部1、出力部2、登録処理部3、削除処理部4、検索処理部5、テキスト分割部6、文書データ記憶部7、検索用大規模全文索引記憶部8、登録用小規模全文索引記憶部9、削除用小規模全文索引記憶部10、マージ部11、バキューム部12、削除回数記憶部13を実現している。

0028

入力部1は、登録処理用の文書データ,削除処理用の文書識別子検索処理用検索条件などが入力される。入力部1は、入力された登録処理用の文書データを登録処理部3に渡す。入力部1は入力された削除処理用の文書識別子を削除処理部4に渡す。入力部1は入力された検索処理用の検索条件を検索処理部5に渡す。

0029

登録処理部3は文書データに関する登録処理を行う。登録処理部3は文書データ記憶部7及び登録用小規模全文索引記憶部9に対し、文書データに関する登録処理を行う。削除処理部4は文書データに関する削除処理を行う。削除処理部4は、入力部1に入力された削除処理用の文書識別子に基づいて、文書データ記憶部7に記憶された文書データを読み出す。削除処理部4は文書データ記憶部7から読み出した文書データを、テキスト分割部6を用いて部分文字列に分割する。

0030

削除処理部4は分割した部分文字列が登録用小規模全文索引記憶部9に登録された索引である場合に、その索引を削除し、分割した部分文字列が登録用小規模全文索引記憶部9に登録された索引でない場合に、分割した部分文字列を索引として削除用小規模全文索引記憶部10に記録する。

0031

テキスト分割部6は、登録処理部3,削除処理部4,検索処理部5の各々で必要な、登録処理における文書データから部分文字列への分割処理、削除処理における文書データから部分文字列への分割処理、検索処理における検索条件(検索文字列)から部分文字列への分割処理を行う。

0032

検索処理部5は検索用大規模全文索引記憶部8,登録用小規模全文索引記憶部9,削除用小規模全文索引記憶部10に対して検索処理を行う。検索処理部5は検索用大規模全文索引記憶部8及び登録用小規模全文索引記憶部9の検索結果から、削除用小規模全文索引記憶部10の検索結果を差し引いた結果を求め、検索結果として出力部2に出力する。

0033

マージ部11は、検索用大規模全文索引記憶部8,登録用小規模全文索引記憶部9及び削除用小規模全文索引記憶部10の間でのマージ処理(広義データ転送ともいえる)を行う。マージ部11に含まれるバキューム部12は検索用大規模全文索引記憶部8に対してバキューム処理を行う。削除回数記憶部13はバキューム処理を実施するか否かを判断するための情報の一例として削除回数を記録している。なお、バキューム処理を実施するか否かを判断するための情報は削除回数に限るものでなく、検索用大規模全文索引記憶部8における後述の未使用領域のサイズであってもよい。検索用大規模全文索引記憶部8に記録されている検索用大規模全文索引は転置ファイルの一例である。

0034

<全文検索装置100の動作>
以下に、上述のごとく構成された本実施形態に係る全文検索装置100の動作の一例を詳細に説明する。図4図6は本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャートである。

0035

ステップS1において、全文検索装置100は利用者からの処理要求を受け取る。全文検索装置100は、ステップS2において、利用者から受け取った処理要求が登録処理に関するものか判定する。また、ステップS3において、全文検索装置100は利用者から受け取った処理要求が削除処理に関するものか検索処理に関するものか判定する。全文検索装置100は、ステップS2及びS3の判定結果に基づいて以下の登録処理、削除処理及び検索処理の何れかの処理を実行する。

0036

《登録処理》
登録処理を実行する場合、利用者は文書データを作成し、入力部1から文書データを登録する。ステップS11において、登録処理部3は文書データを文書データ記憶部7に保存し、その文書データを示す識別子(文書識別子)を定める。例えばSGML等のタグ付の文書であれば、登録処理部3は所定のタグ間にある文字列を対象としてもよい。

0037

ステップS12において、登録処理部3はテキスト分割部6を用いて、文書データから部分文字列(トークン)と、そのトークンの出現位置情報とを得る。そして、登録処理部3はステップS13において、文書識別子と各トークンの出現位置情報とを登録用小規模全文索引記憶部9に記録する。ここでの「記録」は、登録用小規模全文索引記憶部9の登録用小規模全文索引(全文索引)への記録であり(以下同様)、ステップ13のごとき処理を索引記憶ステップとも呼ぶ。

0038

なお、テキスト分割部6で使用される分割手法については、N文字組をトークンとする手法でもよいし、形態素解析を行い、単語をトークンとする手法でもよい。以下ではN文字組みをトークンとする手法を用いたテキスト分割部について説明するが、形態素解析を行った単語をトークンとする手法も同様に適用可能である。また、ステップS13における記録のあと、登録処理部3はステップS14〜S16において、適時、後述のマージ処理を行う。

0039

図7は本実施形態に係る全文検索装置の処理の一例を説明する為の説明図である。図7は全文索引の一例を示している。ここでは図7の例を用いて転置ファイル方式の全文索引について詳細に説明する。また、「文書1」及び「文書2」は、入力部1から登録される文書データであるとする。

0040

図7では「文書1」の内容(ここではテキスト分割部6で「文書1」を分割することにより得た内容)61と「文書2」の内容(ここではテキスト分割部6で「文書2」を分割することにより得た内容)62とを表している。

0041

「文書1」及び「文書2」の内容61及び62は、左側の数字が文字列の先頭からの文字数を表している。例えば「文書1」の内容61の「全文検索」は先頭から11文字目に出現していることを意味する。また「文書1」の内容61の「方法」は先頭から20文字目及び60文字目に出現していることを意味する。また「文書1」の内容61の「全文検索方法」は先頭から31文字目に出現していることを意味する。

0042

例えば「文書2」の内容62の「探索方法」は先頭から1文字目に出現していることを意味する。また「文書2」の内容62の「方法」は先頭から24文字目に出現していることを意味する。また「文書2」の内容62の「全文」は先頭から30文字目及び42文字目に出現していることを意味する。

0043

なお、2文字組を部分文字列とする場合、登録処理部3は登録された文書データ中の全ての部分文字列を抽出し、それらの文書データ内での出現位置(先頭からの文字数)を部分文字列ごとにまとめて全文索引63に記録する。

0044

例えば「文書1」は「全文」が先頭から11,31文字目の位置、「文検」が先頭から12,32文字目の位置に出現しているので、全文索引63に記録する。全文索引63では、文書データ内での出現位置だけでなく、どの文書データに出現したかを識別するための文書識別子と部分文字列の出現回数とを加えて記録するので、図7に示したような形式になる。

0045

例えばトークン「全文」に対する転置リスト{1,2,(11,31)}は「文書1」において2回出現して、その文書データ内での出現位置が先頭から11,31文字目であることを意味している。

0046

トークン「全文」に対する転置リスト{2,2,(30,42)}は「文書2」において2回出現して、その文書データ内での出現位置が先頭から30,42文字目であることを意味している。

0047

《削除処理》
削除処理を実行する場合、利用者は入力部1から削除する文書データの文書識別子を入力する。ステップS21において、削除処理部4は文書データ記憶部7から、利用者により入力された文書識別子に対応する文書データを読み出す。

0048

ステップS22において、削除処理部4はテキスト分割部6を用いて、文書データから部分文字列(トークン)と、そのトークンの出現位置情報を得る。例えばSGML等のタグ付の文書であれば、削除処理部4は所定のタグ間にある文字列を対象としてもよい。

0049

ステップS23において、削除処理部4は利用者により入力された文書識別子が登録用小規模全文索引記憶部9に登録されている文書識別子か判定する。登録用小規模全文索引記憶部9に登録されている文書識別子であれば、削除処理部4はステップS25において各トークンの出現位置情報を登録用小規模全文索引記憶部9から削除する。ステップS30において、削除処理部4は文書データ記憶部7から、利用者により入力された文書識別子に対応する文書データを削除する。

0050

なお、登録用小規模全文索引記憶部9に登録されている文書識別子でなければ(検索用大規模全文索引記憶部8に登録されている文書識別子であれば)削除処理部4はステップS24において、文書識別子と、各トークンの出現位置情報とを削除用小規模全文索引記憶部10に記録する。ステップS24における記録のあと、削除処理部4はステップS26〜S29において、適時、後述のマージ処理及びバキューム処理を行う。

0051

《検索処理》
検索処理を実行する場合、利用者は入力部1から検索文字列を入力する。ステップS4において、検索処理部5はテキスト分割部6を用いて、利用者から入力された検索文字列から部分文字列(トークン)を得る。

0052

ステップS5において、検索処理部5は検索用大規模全文索引記憶部8の検索用大規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合(Rs)を得る。ステップS6において、検索処理部5は登録用小規模全文索引記憶部9の登録用小規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合(Ri)を得る。

0053

また、ステップS7において、検索処理部5は削除用小規模全文索引記憶部10の削除用小規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合(Rd)を得る。

0054

ステップS8において、検索処理部5はステップS5〜S7で得られた文書データの文書識別子の集合(Rs,Ri,Rd)に対して下記の集合演算を行い、その結果を検索結果(R)とする。ステップS9において、検索処理部5は出力部2を利用して利用者に検索文字列を含む文書データの文書識別子の集合を出力する。

0055

R=Rs+Ri−Rd
ただし、+を論理和演算子、−を論理差演算子とする。

0056

ここでは、図7の全文索引63を例として検索処理について詳細に説明する。検索文字列を「全文検索」とすると、テキスト分割部6は「全文」「文検」「検索」の3個のトークンを抽出する。次に、検索処理部5は全文索引63の対応するトークンの3つの転置リストを調べる。検索処理部5は、それぞれのトークンの出現位置の差が1であるものを探すことで、文書識別子1の文書データの先頭から11文字目と31文字目に「全文検索」が存在すると判定できる。

0057

《マージ処理》
マージ部11によるマージ処理は、元の文書データを用いて登録・削除処理を行う場合に比べて、マージ処理開始時に既に作成されている登録用小規模全文索引及び削除用小規模全文索引の転置リストを直接利用するので、テキスト分割処理によるトークンの切り出し及びその転置リスト作成に要する時間が不要となり、データ転送時間を短くできる。

0058

本実施形態においては転置リスト同士の処理であることからデータ転送処理(データ転送ステップ)のことをマージ処理(マージステップ)と呼ぶ。

0059

全文検索装置100における文書データの登録・削除処理を転置リスト同士の処理とすることにより、検索用大規模全文索引への文書データの登録・削除処理の際に、既に作成されている登録用小規模全文索引及び削除用小規模全文索引の転置リストを直接利用するので、検索用大規模全文索引へのマージ処理の時間を短縮でき、検索処理の待ち時間を短くすることができる。

0060

登録用小規模全文索引のマージ処理を実行する場合、マージ部11はステップS14において、登録用小規模全文索引の全てのトークンに対し、そのトークンの転置リストを取り出す。ステップS15において、マージ部11は登録用小規模全文索引の全てのトークンに対して、検索用大規模全文索引の対応するトークンの転置リストの末尾にステップS14で取り出した転置リストを加える。マージ部11はステップS16において、登録用小規模全文索引記憶部9に記録されている登録用小規模全文索引を空にする。

0061

削除用小規模全文索引のマージ処理を実行する場合、マージ部11はステップS26において、削除用小規模全文索引の全てのトークンに対し、そのトークンの転置リストを取り出す。

0062

ステップS27において、マージ部11は検索用大規模全文索引の対応するトークンの転置リストから、ステップS26で取り出した対応するトークンの転置リスト中の出現位置情報を削除する。ステップS28において、マージ部11のバキューム部12はバキューム処理を実施する必要があれば、検索用大規模全文索引記憶部8の検索用大規模全文索引に対してバキューム処理を実施する。ステップS29において、マージ部11は削除用小規模全文索引を空にする。

0063

バキューム処理とは、例えばデータを固定長のページに分割して格納するデータベース管理システム等において、データの登録や削除によりページ内に発生した空き領域が大きくなってページの利用率が低下したとき、ページ内に発生している空き領域が少なくなるように、順次、データを詰めてページに格納する処理である。つまり、バキューム処理はデータの登録や削除によりページ内に発生した空き領域を集めて、データを格納できるようにする(空き領域を解放する)処理である。

0064

図8はマージ処理及びバキューム処理の概要を説明する為の説明図である。図8図7における全文索引63のトークン「全文」の転置リストを例にマージ処理及びバキューム処理の概要を説明するための図である。

0065

検索用大規模全文索引の転置リスト71の一例として、図8では「全文」に対する転置リスト{1,2,(11,31)}{2,2,(30,42)}が記録されている。削除用小規模全文索引の転置リスト72の一例として、図8では{1,2,(11,31)}が記録されている。

0066

また、マージ処理73は図6のステップS26〜S28に示した削除用小規模全文索引のマージ処理(削除のマージ処理)である。検索用大規模全文索引の転置リスト71と削除用小規模全文索引の転置リスト72とにマージ処理73を実行することで「全文」に対する転置リスト{<空き領域>}{2,2,(30,42)}74が得られる。

0067

バキューム処理75は例えば削除回数記憶部13に記録されている削除回数「1」と閾値との比較により実施するか否かを判断される。ここではバキューム処理を実施すると判断されたものとして説明する。検索用大規模全文索引の転置リスト74にバキューム処理75を実行することで「全文」に対する転置リスト{{2,2,(30,42)}76が得られる。検索用大規模全文索引の転置リスト76は転置リスト74の空き領域を解放したものである。

0068

また、マージ処理77は図5のステップS14〜S16に示した登録用小規模全文索引のマージ処理(登録のマージ処理)である。図8は登録用小規模全文索引の転置リスト78の一例として「全文」に対する転置リスト{5,2,(4,16)},{8,1,(3)}が記録されている。

0069

検索用大規模全文索引の転置リスト76と登録用小規模全文索引の転置リスト78とにマージ処理77を実行することで、検索用大規模全文索引の転置リスト79の一例として「全文」に対する転置リスト{1,2,(11,31)},{2,2,(30,42)},{5,2,(4,16)},{8,1,(3)}が得られる。

0070

図8に示すように、バキューム処理75は削除のマージ処理73と登録のマージ処理77との間で必要に応じて実施されることで、利用者が明示的に起動しなくても、自動的に実施される。バキューム処理75が実施されることにより、検索用大規模全文索引の転置リスト79は空き領域が解放される。したがって、本実施形態に係る全文検索装置100は転置リストが格納されたページの利用率を上昇させることで、転置ファイルのサイズの増加を抑制できる。

0071

ここでは、マージ処理及びバキューム処理の詳細について説明する。図9は転置リストの論理的な構造について説明する為の説明図である。図9に示すように、転置リスト82はトークン81と対応付けられている。図9の転置リスト82は論理的な構造として文書識別子の一例としての文書ID、出現回数の一例として出現頻度、1つ以上の出現位置を持つ。

0072

転置ファイル方式を採用した全文検索装置100では、転置ファイルの入出力を固定長のページに分割して格納する必要がある。したがって、転置ファイル方式を採用した全文検索装置100は図10(A)に示すように、入出力単位であるページに合わせて転置リストを複数のページに分割して格納する。

0073

図10は入出力単位であるページに合わせて格納された転置リストの構造について説明する為の説明図である。転置ファイルへのアクセスは非常に時間が掛かる処理である。したがって、一般的にはページの参照回数を最小限にする実装が行われている。例えば転置リストから文書ID「2」のものを削除する場合、削除によりページ内に発生した空き領域を削除の度に詰めようとすると、削除する度にNページを参照しなければならず、非常に時間が掛かってしまう。

0074

そこで、本実施形態に係る全文検索装置100は文書ID「2」のものが格納されている領域を図10(B)のように、未使用領域としてマークすることで、削除処理を行っている。なお、マークの仕方は様々考えられるが、例えば未使用領域とする領域の先頭に未使用領域であることを示すデータと、未使用領域のサイズとを格納しておくことが考えられる。

0075

しかし、未使用領域は徐々に蓄積されていく。したがって、転置ファイル方式を採用した全文検索装置100では、転置ファイルが格納されたページの利用率が低下し、転置ファイルのサイズが大きくなってしまう。そこで、本実施形態に係る全文検索装置100は図10(B)に示す未使用領域を図10(C)に示すように詰めて、空き領域を開放するバキューム処理を行っている。

0076

バキューム処理は、例えば転置リストが格納されているページを参照し、未使用領域を詰める方法、又は、新しいページを用意し、転置リストの未使用領域以外の部分を新しいページにコピーする方法などが一般的である。

0077

図11は削除回数記憶部に記録されているバキューム処理を実施するか否かを判断するための情報の一例の構成図である。削除回数記憶部13はバキューム処理を実施するか否かを判断するための情報として、概念的に図11(A)又は図11(B)のような構造の情報を持っている。なお、実際の構造としては、例えばハッシュ表や、木構造一種であるB+木などが考えられる。

0078

図11(A)はバキューム処理を実施するか否かを判断するための情報として削除回数を記録する例である。図11(B)はバキューム処理を実施するか否かを判断するための情報として未使用領域のサイズを記録する例である。図11(A)のようにバキューム処理を実施するか否かを判断するための情報として削除回数を記録した場合、バキューム部12は削除回数が閾値に達しているとバキューム処理75を行う。

0079

また、図11(B)のようにバキューム処理を実施するか否かを判断するための情報として未使用領域のサイズを記録した場合、バキューム部12は未使用領域のサイズが閾値に達しているとバキューム処理75を行う。

0080

図12はステップS28の処理の詳細を表したフローチャートである。なお、図12は一例としてバキューム処理を実施するか否かを判断するための情報として削除回数を利用する例を示している。

0081

ステップS51において、バキューム部12は削除回数記憶部13が記録している削除回数が、予め指定された回数(閾値)に達しているか判定する。削除回数記憶部13が記録している削除回数が、予め指定された回数(閾値)に達していれば、バキューム部12はステップS52において、検索用大規模全文索引記憶部8に記録されている検索用大規模全文索引に対してバキューム処理75を実施する。なお、削除回数記憶部13が記録している削除回数が、予め指定された回数(閾値)に達していなければ、バキューム部12はバキューム処理75を実施しない。

0082

<まとめ>
本実施形態によれば、マージ処理73及びバキューム処理75を実施する条件を満たしたときに、マージ処理73を自動的に行うことで、転置リストが格納されたページの利用率を上昇させることができ、転置ファイルのサイズの増加を抑制できる。

0083

本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。例えば文書管理システム電子図書館システム、特許公報検索システム、データベース管理システム、エンタープライズインフォメーションポータルなど、多量の文書データを管理するシステムに適用可能である。

0084

なお、特許請求の範囲に記載したマージ手段はマージ部11に相当し、領域解放手段はバキューム部12に相当する。

0085

1 入力部
2 出力部
3登録処理部
4削除処理部
5検索処理部
6テキスト分割部
7文書データ記憶部
8検索用大規模全文索引記憶部
9登録用小規模全文索引記憶部
10 削除用小規模全文索引記憶部
11マージ部
12バキューム部
13削除回数記憶部
100全文検索装置
101入力装置
102表示装置
103 外部I/F
103a記録媒体
104 RAM(Random Access Memory)
105 ROM(Read Only Memory)
106 CPU(Central Processing Unit)
107通信I/F
108 HDD(Hard Disk Drive)
110端末装置
200全文検索システム
B バス

先行技術

0086

特開2003−122794号公報

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

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

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

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

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

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

  • 三菱電機株式会社の「 情報処理装置および情報処理方法」が 公開されました。( 2019/08/08)

    【課題・解決手段】情報処理装置(10)は、時系列データである入力データを取得するデータ取得部(101)と、時系列データである学習データから抽出した部分列である複数の学習部分列の中で類似する学習部分列を... 詳細

  • オムロン株式会社の「 センシングデバイス管理装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】センサ側メタデータに相当するデータカタログの生成が簡単且つ適正に行えるセンシングデバイス管理装置を提供する。デバイス情報取得機能部11dが、測定対象をセンシングするセンシングデバイス... 詳細

  • オムロン株式会社の「 マッチング処理装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】利活用対象のセンシングデータによる容易なセンサマッチングを行うマッチング処理部50が提供される。マッチング処理部50は、提供側端末11により入力された提供側センシングデータを取得する... 詳細

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

関連性が強い 技術一覧

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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