(57)【要約】【課題】  文書データのサイズに依存することなく、メモリサイズとメモリへの展開時間を削減することができる、文書データの検索方法及びそのプログラムを提供する。【解決手段】  要素名等に対応する符号を規定した変換シートを用いて、ＸＭＬ文書データを符号化した符号データから、取得要求となる要素名を含む構造型の検索鍵に対応する最終コンテンツを検索するためのものである。符号データは、要素ノード毎に占有ビット数を含み、符号データの先頭から順にパース位置を移行しつつ、変換シートを用いて、そのパース位置に、検索鍵に含まれる要素名があるか否かを判定し、検索鍵に含まれる要素名があれば、その要素名の占有ビット数内でパース処理し、属性及び子要素ノードインスタンスをメモリ上に生成し、符号データのパース位置を、要素名の占有ビット数を飛ばした位置に移行させることを繰り返すことにより、最終コンテンツを検索する。【選択図】  図７
2005215950.tif 000002
【特許請求の範囲】
【請求項１】
要素名及び該要素名に指定可能な属性名に対応する符号を規定した変換シートを用いて、テキスト形式の構造型記述言語で記載された文書データを符号化した符号データから、１つ以上の要素名を含む構造型の検索鍵に対応する最終コンテンツを検索するための文書データの検索方法であって、
前記符号データは、要素名毎に占有ビット数を含んでおり、
前記符号データの先頭から順にパース位置を移行しつつ、
前記変換シートを用いて、前記パース位置に前記検索鍵に含まれる要素名があるか否かを判定する第１のステップと、
前記検索鍵に含まれる要素名があれば、前記符号データの前記要素名の占有ビット数内でパース処理し、属性ノードインスタンス及び子要素ノードインスタンスをメモリ上に生成する第２のステップと、
前記符号データの前記パース位置を、前記要素名の占有ビット数を飛ばした位置に移行させる第３のステップと
を有し、前記第１から第３のステップを繰り返すことにより、前記最終コンテンツを検索することを特徴とする文書データの検索方法。
【請求項２】
要素名及び該要素名に指定可能な属性名に対応する符号を規定した変換シートを用いて、テキスト形式の構造型記述言語で記載された文書データを符号化した符号データから、１つ以上の要素名を含む構造型の検索鍵に対応する最終コンテンツを検索するための文書データの検索プログラムであって、
前記符号データは、要素名毎に占有ビット数を含んでおり、
前記符号データの先頭から順にパース位置を移行しつつ、
前記変換シートを用いて、前記パース位置に前記検索鍵に含まれる要素名があるか否かを判定する第１のステップと、
前記検索鍵に含まれる要素名があれば、前記符号データの前記要素名の占有ビット数内でパース処理し、属性ノードインスタンス及び子要素ノードインスタンスをメモリ上に生成する第２のステップと、
前記符号データの前記パース位置を、前記要素名の占有ビット数を飛ばした位置に移行させる第３のステップと
を有し、前記第１から第３のステップを繰り返すことにより、前記最終コンテンツを検索するようにコンピュータを実行させることを特徴とする文書データの検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化された文書データの検索方法及びそのプログラムに関する。
【背景技術】
【０００２】
従来、伝送すべきデータ量を削減するために、文書データを符号化及び復号化する方法がある。この方法を実現するには、送信装置及び受信装置はそれぞれ、変換シートを所持する必要がある。変換シートは、記述言語と符号とを１対１に対応付けたものである。送信装置は、変換シートに基づいて文書データを符号データに符号化する。一方、受信装置は、変換シートに基づいて符号データを文書データに復号化する。このような方法は、ネットワークにおけるセキュリティの観点からも有効である。変換シートを有さないクライアントは、符号データを復号することができないからである。
【０００３】
図１は、従来の符号化方法の説明図である。
【０００４】
具体的には、ＸＭＬ(eXtensible Markup Language)又はＳＧＭＬ(Standard Generalized Markup Language)準拠の符号化変換シートを用いて、ＸＭＬ／ＳＧＭＬ文書データをパーシングしながら符号化を行う（例えば特許文献１参照）。この変換シートは、ＸＭＬ／ＳＧＭＬ形式の記述言語で記載されており、要素名、要素値、属性名及び属性値の項目に符号長及び符号が定義されている。また、要素間の論理構造を示す符号長及び符号も定義されている。変換シートを用いて文書データを符号化された符号データは、データ量を削減することができ、データベースへの蓄積にも有効である。また、復号側でも同じ変換シートを用いることにより、符号データからの元の文書データをパースして復元させることなく、直接的に文書処理をすることができる。従って、復号側においてパース処理を必要としない。
【０００５】
図２は、従来の文書データ検索システムのシーケンス図である。
【０００６】
図２によれば、文書データ検索システムは、検索要求を解釈し且つ取得要求を通知する検索エンジン１０と、ＤＯＭツリーを展開するメモリシステム１１と、文書データの符号データを蓄積したデータベース１２と、要素等と符号との対応関係を定義した変換シート１３とを有する。取得要求となる検索鍵は、１つ以上の要素名を含む構造型ものであって、その検索鍵に対応する最終コンテンツが検索される。検索エンジン１０が検索要求を受け付けると、該当する文書データ全てのパース処理を行い、メモリシステム１１上に、その全てのＤＯＭ(Document Object Model)ツリーを展開する。ＤＯＭツリーは、Ｗ３Ｃで規定されている汎用的なＡＰＩ(Application Programming Interfase)である。そして、そのＤＯＭツリーから、該当するノード集合が獲得される。このように、ＸＭＬ文書データ全てのＤＯＭツリーをメモリ上に展開して、その特定部分を検索する技術として、ＸＰａｔｈ(XML Path Language)としてＷ３Ｃに勧告されている（例えば非特許文献１参照）。
【０００７】
【特許文献１】特開２００２−２５９１９４号公報
【非特許文献１】XML Path Language(XPath) Version 1.0 [online]、［平成１６年１月２９日検索］、インターネット＜URL:http://www.w3.org/TR/xpath/＞
【発明の開示】
【発明が解決しようとする課題】
【０００８】
前述した従来技術によれば、文書データ検索システムにおいて、ＸＭＬ文書データの一部を検索する場合であっても、その全てのＤＯＭツリーをメモリ上に展開しなければならない。このような処理は、展開するメモリサイズとその展開時間とが、文書データのサイズに大きく依存することとなる。
【０００９】
従って、本発明は、文書データのサイズに依存することなく、メモリサイズとメモリへの展開時間を削減することができる、文書データの検索方法及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明における符号化された文書データの検索方法によれば、
要素名及び該要素名に指定可能な属性名に対応する符号を規定した変換シートを用いて、テキスト形式の構造型記述言語で記載された文書データを符号化した符号データから、１つ以上の要素名を含む構造型の検索鍵に対応する最終コンテンツを検索するための方法であって、
符号データは、要素名毎に占有ビット数を含んでおり、
符号データの先頭から順にパース位置を移行しつつ、
変換シートを用いて、パース位置に検索鍵に含まれる要素名があるか否かを判定する第１のステップと、
検索鍵に含まれる要素名があれば、符号データの要素名の占有ビット数内でパース処理し、属性ノードインスタンス及び子要素ノードインスタンスをメモリ上に生成する第２のステップと、
符号データのパース位置を、要素名の占有ビット数を飛ばした位置に移行させる第３のステップと
を有し、第１から第３のステップを繰り返すことにより、最終コンテンツを検索することを特徴とする。
【００１１】
本発明における符号化された文書データの検索プログラムによれば、
要素名及び該要素名に指定可能な属性名に対応する符号を規定した変換シートを用いて、テキスト形式の構造型記述言語で記載された文書データを符号化した符号データから、１つ以上の要素名を含む構造型の検索鍵に対応する最終コンテンツを検索するためのプログラムであって、
符号データは、要素名毎に占有ビット数を含んでおり、
符号データの先頭から順にパース位置を移行しつつ、
変換シートを用いて、パース位置に検索鍵に含まれる要素名があるか否かを判定する第１のステップと、
検索鍵に含まれる要素名があれば、符号データの要素名の占有ビット数内でパース処理し、属性ノードインスタンス及び子要素ノードインスタンスをメモリ上に生成する第２のステップと、
符号データのパース位置を、要素名の占有ビット数を飛ばした位置に移行させる第３のステップと
を有し、第１から第３のステップを繰り返すことにより、最終コンテンツを検索するようにコンピュータを実行させることを特徴とする。
【発明の効果】
【００１２】
本発明における符号化された文書データの検索方法及びそのプログラムによれば、文書データのサイズに依存することなく、メモリサイズとメモリへの展開時間を削減することができる。本発明によれば、構造型の検索鍵に基づく必要なノードのみをパースすることができるために、従来技術のように全てのノードのインスタンスをメモリ上に展開する必要がない。これは、メモリサイズの削減だけでなく、不要なノードをパースしないことによるパース時間全体の短縮にもつながる。特に、大容量の文書データであって、常に全てのノードを必要としない文書に対する検索については、極めて有効といえる。
【００１３】
また、メモリからノードインスタンスが一旦消えると、再使用時には、再びパース処理を行う必要がある。本発明によれば、そのとき、パースするノードが極めて少なくなり、初期時処理負担が圧倒的に少なくなる。
【００１４】
本発明によれば、文書データの全てのノードを辿るような検索を行う場合は、特別な利点は無い。即ち、本発明は、Pull指向なＤＯＭツリーを構築し、XPath検索を行うことによって、利用時にパース処理をし、その文書データの解析を利用者が制御できる効率的な検索が可能となる。
【発明を実施するための最良の形態】
【００１５】
以下では、図面を用いて、本発明を実施するための最良の形態について詳述する。
【００１６】
図３は、サンプルとなる文書データと、その符号データである。以下では、この文書データを例にとって説明する。
【００１７】
サンプルとなる文書データの[T1]〜[T9]が、符号データの[T1]〜[T9]に対応している。ここで特徴的な点は、符号データの要素毎には、占有ビット数が含まれている点である。例えば、要素address[T2]は267bitを占有しており、この占有ビット数は、要素ノードインスタンスに含まれることとなる。即ち、符号データのこの位置にパース位置が存在する場合、要素addressをパースする必要がなければ、このパース位置から267bit飛び越えた位置から、次のパース処理の判断をすればよいこととなる。
【００１８】
図４Ａ及び図４Ｂは、変換シートである。
【００１９】
変換シートには、要素名、その要素名に指定可能な属性名、要素値、属性値等のそれぞれに対応する符号を規定している。図３の文書データ[T1]〜[T9]は、変換シート[T1]〜[T9]を参照して符号化できる。従って、図３の符号データ[T1]〜[T9]は、変換シート[T1]〜[T9]を参照して復号化できる。
【００２０】
図５Ａは、図４の符号データ（バイナリフォーマット）によって、本来、メモリ上に展開されるべき論理構造を示す。"e"は要素ノードインスタンス（以下「要素ノード」という）を示し、"a"は属性ノードインスタンス（以下「属性ノードという）を示し、"t"はテキストノードインスタンス（以下「テキストノード」という）を示している。破線で示されているのは、未だメモリ上に展開されていないことを表す。この段階においては、当然にメモリ消費量も０である。
【００２１】
ルート要素ノードの取得が要求されると、符号データの先頭から順にパース位置が移行する。最初に、変換シートを用いて、符号データのそのパース位置に、検索鍵に含まれる要素名があるか否かを判定する。符号データに出現する最初の要素ノードを発見すると、その要素ノードが作成されて保持される。
【００２２】
以下でメモリ上に展開される要素ノードのプロパティには、以下のものが含まれる。
（１）要素名
（２）占有ビット数
（３）属性の集合
（４）子要素ノード、子テキストノードの集合
【００２３】
図５Ｂは、図５Ａから、ルート要素ノードmemberがメモリ上に展開されたツリー構成図である。この要素ノードのプロパティには、要素名として"member"と、この要素の占有ビット数535bitとが保持される。
【００２４】
図５Ｃは、図５Ｂから、属性ノードidが更にメモリ上に展開されたツリー構成図である。要素ノードmemberがメモリ上に展開される際に、要素ノードmemberの占有ビット数における属性部分をパースして、属性ノードを作成する。このとき、要素ノードmemberのプロパティには、要素名及び占有バイト数に加えて、属性集合として属性idが保持される。そして、その文書データに対してルート取得要求が発行されると、パースしてメモリ上に展開された要素ノードmemberが応答される。
【００２５】
図５Ｄは、図５Ｃから、子要素ノードaddress,name,birthdayが更にメモリ上に展開されたツリー構成図である。要素ノードmemberに対して子要素集合の取得が要求されたとする。このとき、占有ビット中における子要素部分をパースして、その子要素ノードを作成し応答する。要素ノードmemberには、子要素address,name,birthdayがあるので、それぞれについて子要素ノードを作成する。
【００２６】
ここで、要素ノード"member"のプロパティには、更に子要素ノードaddress,name,birthdayの集合が保持される。その子要素ノードaddress,name,birthdayのプロパティにもそれぞれ、要素名と、占有ビット数とが保持される。例えば、要素ノード"address"の占有ビット数は267bitであるが、要素ノード"address"に対する取得要求でなければ、そのパース位置から、267bitだけ飛び越えた位置から、次のパース処理の判断が開始される。
【００２７】
図５Ｅは、図５Ｄから、子テキストノードtextが更にメモリ上に展開されたツリー構成図である。要素ノードnameに対して要素値の取得要求があったとする。このとき、占有ビット中における要素値部分をパースして、子テキストノードtextを作成して応答する。尚、要素ノードnameのプロパティには、更に子要素ノードtextが保持される。
【００２８】
図５Ｆは、図５Ｄから、属性ノードcountry,city及び子テキストノードtextが更にメモリ上に展開されたツリー構成図である。要素ノードaddressに対して要素集合の取得要求があったとする。このとき、占有ビット中における子要素部分をパースして、属性ノードcontry及びcityと、子テキストノードtextとのそれぞれの要素ノードを作成して応答する。尚、要素ノードaddrssのプロパティには、更に属性ノードcontry,city及び子テキストノードtextが保持される。
【００２９】
図６は、本発明におけるフローチャートである。
【００３０】
図６の処理フローは、要素及びテキストの取得要求をトリガとして開始される。
（Ｓ６１）取得要求のあった要素及びテキストが、パースされて、メモリ上に展開されているか否かを判定する。既にメモリ上にそのノードが展開されていれば、そのコンテンツで応答する（Ｓ６８）。
（Ｓ６２）取得要求のあったノードがメモリ上に展開されていなければ、属性が、パースされて、メモリ上に展開されているか否かを判定する。このとき、取得要求のあったノードについての占有ビット数を、符号データから取得する。
（Ｓ６３）その属性ノードがメモリ上に展開されていなければ、属性部分が、パースされて、メモリ上に展開される。
（Ｓ６４）取得要求のあったノードが要素ノードか又はテキストノードかを判定する。
（Ｓ６５）要素ノードであれば、要素ノードインスタンスを生成する。
（Ｓ６６）テキストノードであれば、テキストノードインスタンスを生成する。
（Ｓ６７）占有ビット数に残りがあるか否かを判定する。占有ビット数に残りがあれば、再度、要素ノード又はテキストノードの生成を行う。
（Ｓ６８）
【００３１】
図７は、本発明における文書データ検索システムのシーケンス図である。
【００３２】
（Ｓ７１）検索エンジン１０が、構造型/member/nameの検索鍵を受け付けると、メモリシステム１１に対して、最初に要素ノード/memberの取得を要求する。
（Ｓ７２）メモリシステム１１は、データベース１２から該当する符号データを取得し、変換シートを用いて、符号データの先頭から順に、そのパース位置に検索鍵に含まれる要素名があるか否かを判定する。ここでは、ルート要素ノード/memberが発見される。このとき、ルート要素ノード/memberをメモリ上に展開し、更に属性ノードidについてもメモリ上に展開する。そして、検索エンジン１０へ要素ノード/memberを応答する。
（Ｓ７３）次に、検索エンジン１０は、メモリシステム１１へ、要素ノード/memberの子要素及び子テキストの集合の取得を要求する。
（Ｓ７４）メモリシステム１１は、要素ノード/memberの子要素ノードをメモリ上に展開する。そして、検索エンジン１０へ要素ノード/memberの集合の取得を応答する。
（Ｓ７５）次に、検索エンジン１０は、メモリシステム１１へ、要素ノード/member/nameの取得を要求する。
（Ｓ７６）メモリシステム１１は、変換シートを用いて、そのパース位置に検索鍵に含まれる要素名nameがあるか否かを判定する。ここでは、要素ノード/member/nameが発見される。このとき、要素ノード/member/nameをメモリ上に展開し、更に子テキスト要素ノードtextについてもメモリ上に展開する。そして、検索エンジン１０へ要素ノード/member/nameを応答する。そのコンテンツは、検索結果として、要求元へ応答される。
【００３３】
以下の表１は、本発明における検索時間の評価結果である。
【表１】
2005215950.tif 000003
【００３４】
評価用ＸＭＬ文書データとして、ファイルサイズ1,339,240byte、要素数２０５４個、属性数４２３個、テキストノード数３７７０個のものを用意した。このＸＭＬ文書データを、本発明による変換シートによって符号化し、その符号化データからＤＯＭオブジェクトをメモリ上に展開し、XPathにより検索した。比較対象として、同じＸＭＬ文書データをＪＤＯＭ(http://jdom.org)によりＤＯＭツリーオブジェクトとしてメモリ上に展開し、XPathにて検索した場合も測定した。XPath式の値の評価を行うXPathエンジンには、共にＪａｘｅｎ(http://jaxen.org)を用いた。
【００３５】
計測した結果、本発明によるＤＯＭツリーオブジェクトによる検索の方が、ＪＤＯＭによりも、６４倍から１３８倍高速に検索できた。また、ＪＤＯＭの場合、検索時間のほとんどが、パース処理を行ってＤＯＭツリーオブジェクトをメモリ上に展開する時間となるために、検索時間が検索クエリに全く依存していない。一方、本発明によれば、検索に必要なノードのみパース処理を行ってＤＯＭツリーオブジェクトをメモリ上に展開するために、展開するノードが少ない検索クエリほど検索時間が速い。
【００３６】
前述した本発明における符号化された文書データの検索方法及びそのプログラムの種々の実施形態によれば、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略を、当業者は容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【００３７】
【図１】従来の符号化方法の説明図である。
【図２】従来の文書データ検索システムのシーケンス図である。
【図３】サンプルとなる文書データと、その符号データである。
【図４Ａ】変換シートの前半部分である。
【図４Ｂ】変換シートの後半部分である。
【図５Ａ】図３の符号データによってメモリ上に展開されるべき論理構造を示すツリー構成図である。
【図５Ｂ】図５Ａから、ルート要素ノードmemberがメモリ上に展開されたツリー構成図である。
【図５Ｃ】図５Ｂから、属性ノードidが更にメモリ上に展開されたツリー構成図である。
【図５Ｄ】図５Ｃから、子要素ノードaddress,name,birthdayが更にメモリ上に展開されたツリー構成図である。
【図５Ｅ】図５Ｄから、子テキストノードtextが更にメモリ上に展開されたツリー構成図である。
【図５Ｆ】図５Ｄから、属性ノードcountry,city及び子テキストノードtextが更にメモリ上に展開されたツリー構成図である。
【図６】本発明におけるフローチャートである。
【図７】本発明における文書データ検索システムのシーケンス図である。
【符号の説明】
【００３８】
１  文書データ検索システム
１０  検索エンジン
１１  メモリシステム
１２  データベース
１３  変換シート
【図１】
2005215950.tif 000004
【図２】
2005215950.tif 000005
【図３】
2005215950.tif 000006
【図４Ａ】
2005215950.tif 000007
【図４Ｂ】
2005215950.tif 000008
【図５Ａ】
2005215950.tif 000009
【図５Ｂ】
2005215950.tif 000010
【図５Ｃ】
2005215950.tif 000011
【図５Ｄ】
2005215950.tif 000012
【図５Ｅ】
2005215950.tif 000013
【図５Ｆ】
2005215950.tif 000014
【図６】
2005215950.tif 000015
【図７】
2005215950.tif 000016