(57)【要約】【課題】構造化文書からの検索式評価による情報抽出処理において、差分情報が与えられた時に、これを用いて高速に検索式の評価処理を行う。【解決手段】事前に登録された検索式111を単純構造式、述語付式、複雑式などに分類して検索式テーブル108に登録するとともに、事前に登録された元文書112に対して検索式を適用し、その適用結果と計算過程情報を計算し、元文書テーブル109に登録しておく。差分情報113が入力されると、差分解析部104によりそれを解析し、値差分と構造差分の何れかに分類し、差分情報113の種類と検索式の種類の組合せによって、各検索式毎に、差分計算が可能な場合には差分検索式評価部105により差分情報113と計算過程情報を用いて検索式の評価を行い、それ以外は全文検索式評価部106により構造化文書に戻して検索式の評価を行う。【選択図】図１
2007310617.tif 000002
【特許請求の範囲】
【請求項１】
検索式をその性質に基づいて分類して保持する検索式管理部と、元文書を前記保持された検索式に適用した結果および適用時の処理過程情報とともに格納する元文書管理部と、構造化文書の差分情報をその性質に基づいて分類し、差分の種類と検索式の種類とに基づいて検索式評価方法を決定する差分解析部と、差分情報による検索式評価が可能な場合に、差分情報と、検索式及びその分類結果と、元文書と、元文書に対する検索式の評価結果とを用いて検索式の評価を行う差分検索式評価部と、差分情報による検索式評価が不可能な場合に、元文書に差分情報を適用した新文書を生成してこれに検索式を適用する全文検索式評価部と、差分検索式評価部と全文検索式評価部の結果をあわせて元文書に差分情報を適用した文書に対する検索式の評価結果として出力する出力部とを備えたことを特徴とする構造化文書処理システム。
【請求項２】
前記検索式管理部は、検索式を、検索式が構造化文書のノードの親子関係のみを含む場合に単純構造式と分類し、検索式が単純構造式に単純構造式を含む述語を付加したものである場合に述語付式と分類し、それ以外の式を複雑式と分類するものであり、前記差分解析部は、差分情報を変更箇所が値か文書構造かで分類し、変更箇所が値のみの場合に値差分と分類するものであり、且つ、差分情報が値差分の場合でかつ検索式が単純構造式あるいは述語付式である場合に差分情報による検索式評価が可能と判断するものであることを特徴とする請求項１記載の構造化文書処理システム。
【請求項３】
前記元文書管理部は、前記処理過程情報を、検索式の適用結果に含まれるノードのリストである結果ノードセットと、検索式の適用結果を導出するために検索式が直接評価したノードのリストである条件ノードセットとして保存することを特徴とする請求項２記載の構造化文書処理システム。
【請求項４】
前記元文書管理部は、前記処理過程情報としてさらに、検索式に述語が含まれ、かつ述語以外の式は該当し、かつ述語の評価結果によって該当しないと判断されたノードのリストである候補ノードセットを保存することを特徴とする請求項３記載の構造化文書処理システム。
【請求項５】
前記元文書管理部は、元文書を各ノードに一意なIDをつけて保存するとともに処理過程情報のノードセットを前記IDによって指定し、前記差分解析部は、差分情報を前記IDによって変更箇所を指定することを特徴とする請求項４記載の構造化文書処理システム。
【請求項６】
前記差分検索式評価部は、差分が前記値差分であり、かつ検索式が前記単純構造式である場合に、前記結果ノードセットによって前記元文書に対する処理結果の出力に対する変更があるか否かを調べ、無い場合には前記処理結果をそのまま検索式の評価結果とし、変更がある場合はそれを適用しこの元文書の処理結果に差分を適用したものを評価結果とすることを特徴とする請求項４または５記載の構造化文書処理システム。
【請求項７】
前記差分検索式評価部は、さらに、差分が前記値差分であり、かつ検索式が前記述語付式である場合に、前記条件ノードセットによって差分による変更が前記元文書に対する検索式評価の出力結果が無効になる可能性があるか否かを調べ、可能性がある場合には前記条件ノードセットに関連する差分のみを適用してその部分に対して検索式を再評価し、前記条件ノードセットの調査で可能性が無いか、あるいは前記検索式の再評価の結果検索式と該当すると判断された場合に、前記結果ノードセットによって前記元文書に対する処理結果の出力に対する変更があるか否かを調べ、無い場合には前記処理結果をそのまま検索式の評価結果とし、変更がある場合はそれを適用しこの元文書の処理結果に差分を適用したものを評価結果とすると同時に、前記候補ノードセットによって差分による変更が前記元文書に対する検索式評価で該当しないと判断されたノードが該当するようになる可能性があるか否かを調べ、可能性がある場合には候補ノードセットに関連する差分のみを適用してその部分に対して検索式を再評価し、その結果検索式と該当すると判断された場合に、該当箇所の出力結果に対する変更があるか否かを調べ、無い場合には前記出力結果をそのまま検索式の評価結果とし、変更がある場合はそれを適用したものを評価結果とすることを特徴とする請求項６記載の構造化文書処理システム。
【請求項８】
入力された構造化文書を元文書と比較して差分を計算する差分計算部と、入力された構造化文書を保存する入力文書保存部とをさらに備え、前記差分検索式評価部と前記全文検索式評価部は、元文書に差分を適用する代わりに前記入力文書保存部に保存された入力文書を参照することを特徴とする請求項１乃至７の何れか１項に記載の構造化文書処理システム。
【請求項９】
元文書に対して一部あるいは全部の差分を適用した新文書を管理する新文書管理部をさらに備え、前記差分検索式評価部と前記全文検索式評価部は、元文書への差分の適用時に新文書管理部に適用と結果の取得を依頼し、新文書管理部が、既に差分適用済みの箇所は再度差分適用を行わず保存している新文書から適用結果を返すことを特徴とする請求項１乃至７の何れか１項に記載の構造化文書処理システム。
【請求項１０】
１以上の検索式とその種類、および、元文書と該元文書に前記検索式を適用した結果と処理過程情報を記憶する記憶部と、
与えられた構造化文書の差分情報をその性質に基づいて分類し、該差分情報の種類と前記記憶部に記憶されている検索式の種類とに従って、それぞれの前記検索式毎に、差分情報を用いて評価を行うか否かを決定する差分解析部と、
差分情報を用いて評価を行うと決定された検索式について、前記記憶部に記憶された元文書に前記検索式を適用した結果と処理過程情報とを用いて評価を行う差分検索式評価部と、
差分情報を用いずに評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記差分情報を適用した文書を用いて評価を行う全文検索式評価部とを備えることを特徴とする構造化文書処理システム。
【請求項１１】
前記記憶部には、構造化文書のノードの親子関係のみを含む単純構造式の検索式と、該検索式を元文書に適用した結果と処理過程情報とが記憶されており、
前記差分解析部は、与えられた構造化文書の差分情報が、変更箇所が値のみである値差分である場合、前記単純構造式の検索式については差分情報を用いて評価を行うと決定し、
前記差分検索式評価部は、前記単純構造式の検索式について、前記記憶部に記憶された元文書に前記単純構造式の検索式を適用した結果と処理過程情報とを用いて評価を行うことを特徴とする請求項１０記載の構造化文書処理システム。
【請求項１２】
前記記憶部には、構造化文書のノードの親子関係のみを含む単純構造式に単純構造式を含む述語を付加した述語付式の検索式と、該検索式を元文書に適用した結果と処理過程情報とが記憶されており、
前記差分解析部は、与えられた構造化文書の差分情報が、変更箇所が値のみである値差分である場合、前記述語付式の検索式については差分情報を用いて評価を行うと決定し、
前記差分検索式評価部は、前記述語付式の検索式について、前記記憶部に記憶された元文書に前記述語付式の検索式を適用した結果と処理過程情報とを用いて評価を行うことを特徴とする請求項１０記載の構造化文書処理システム。
【請求項１３】
コンピュータを用いて構造化文書に対する検索式の評価を行う方法において、
前記コンピュータが、1以上の検索式をその種類を付加して記憶部に記憶すると共に、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１のステップと、
前記コンピュータが、与えられた構造化文書の差分情報をその性質に基づいて分類し、該差分情報の種類と前記記憶部に記憶されている検索式の種類とに従って、それぞれの前記検索式毎に、差分情報を用いて評価を行うか否かを決定する第２のステップと、
前記コンピュータが、差分情報を用いて評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記検索式を適用した結果と処理過程情報とを用いて評価を行い、差分情報を用いずに評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記差分情報を適用した文書を用いて評価を行う第３のステップとを含むことを特徴とする構造化文書処理方法。
【請求項１４】
コンピュータを用いて構造化文書に対する検索式の評価を行う方法において、
前記コンピュータが、構造化文書のノードの親子関係のみを含む単純構造式の検索式と、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１のステップと、
前記コンピュータが、与えられた構造化文書の差分情報をその性質に基づいて分類し、変更箇所が値のみである値差分である場合、前記単純構造式の検索式については差分情報を用いて評価を行うと決定する第２のステップと、
前記コンピュータが、前記単純構造式の検索式について、前記記憶部に記憶された元文書に前記単純構造式の検索式を適用した結果と処理過程情報とを用いて評価を行う第３のステップとを含むことを特徴とする構造化文書処理方法。
【請求項１５】
コンピュータを用いて構造化文書に対する検索式の評価を行う方法において、
前記コンピュータが、構造化文書のノードの親子関係のみを含む単純構造式に単純構造式を含む述語を付加した述語付式の検索式と、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１のステップと、
前記コンピュータが、与えられた構造化文書の差分情報をその性質に基づいて分類し、変更箇所が値のみである値差分である場合、前記述語付式の検索式については差分情報を用いて評価を行うと決定する第２のステップと、
前記コンピュータが、前記述語付式の検索式について、前記記憶部に記憶された元文書に前記述語付式の検索式を適用した結果と処理過程情報とを用いて評価を行う第３のステップとを含むことを特徴とする構造化文書処理方法。
【請求項１６】
コンピュータに、
１以上の検索式をその種類を付加して記憶部に記憶すると共に、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１の処理と、
与えられた構造化文書の差分情報をその性質に基づいて分類し、該差分情報の種類と前記記憶部に記憶されている検索式の種類とに従って、それぞれの前記検索式毎に、差分情報を用いて評価を行うか否かを決定する第２の処理と、
差分情報を用いて評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記検索式を適用した結果と処理過程情報とを用いて評価を行い、差分情報を用いずに評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記差分情報を適用した文書を用いて評価を行う第３の処理とを行わせるためのプログラム。
【請求項１７】
コンピュータに、
構造化文書のノードの親子関係のみを含む単純構造式の検索式と、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１の処理と、
与えられた構造化文書の差分情報をその性質に基づいて分類し、変更箇所が値のみである値差分である場合、前記単純構造式の検索式については差分情報を用いて評価を行うと決定する第２の処理と、
前記単純構造式の検索式について、前記記憶部に記憶された元文書に前記単純構造式の検索式を適用した結果と処理過程情報とを用いて評価を行う第３の処理とを行わせるためのプログラム。
【請求項１８】
コンピュータに、
構造化文書のノードの親子関係のみを含む単純構造式に単純構造式を含む述語を付加した述語付式の検索式と、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１の処理と、
与えられた構造化文書の差分情報をその性質に基づいて分類し、変更箇所が値のみである値差分である場合、前記述語付式の検索式については差分情報を用いて評価を行うと決定する第２の処理と、
前記述語付式の検索式について、前記記憶部に記憶された元文書に前記述語付式の検索式を適用した結果と処理過程情報とを用いて評価を行う第３の処理とを行わせるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は主に構造化文書に対する検索処理に関し、特に他の構造化文書との差分情報によって表現された構造化文書に対する検索式の評価を、他の構造化文書に対する検索式の評価結果と差分情報とに基づいて行う構造化文書処理システム、構造化文書処理方法および構造化文書処理用プログラムに関する。
【背景技術】
【０００２】
(XMLとXPath)
XMLやSGMLを始めとする構造化文書は、柔軟性や拡張性などの利点から通信の標準規格など様々な用途で利用されている。構造化文書を標準規格に採用した通信規格としては、SOAP(Simple Object Access Protocol)などが著名である。
【０００３】
構造化文書は、一つの要素を根とした木構造を構成する。木の幹や葉の部分をノードと呼び、一般に各ノードは要素名、要素値、属性名、属性値、子要素などから構成される。繋がりのあるノード同士の関係は、より根に近い側を"親"や"先祖"、より葉に近い側を"子"や"子孫"、同一の親を持つ子ノードを"兄弟"などと表現される。ノードの中で、特に要素値や属性値など値を示し子孫を持たないノードを、本明細書では「値ノード」と表現する。
【０００４】
このような構造化文書、特にXML内の特定の要素を抽出するための検索式としてXPath(XML Path Language)が利用されている。XPathは標準化団体W3C（WWWコンソーシアム）によって規格化され非特許文献１に仕様が記載されている。
【０００５】
XPathでは検索式を、XMLの要素を“/”で区切って列記し要素間の構造関係を示すことで表現し、それによりXML文書内でその関係を満たす箇所を指定する。よく利用される式は、"/A/B/C"のように文書の根から子の方向に辿るパスを記述するものであり、構造化文書中で該当する"C"の要素とその子孫が検索式の結果となる。一つの検索式で一つの文書内での該当箇所は複数になり得る。
【０００６】
また述語と呼ばれる表現で、構造関係にさらに付加的な条件を課す事も出来る。これは要素の後ろに"[]"で囲む形で表現し、"[]"内にさらに検索式やその結果に対する条件を記述することで表現する。よくある述語の用途は、"/A/B[C=1]"のようにある要素に対してその近傍の値ノードの内容に対する条件の記述や、"/A/B[2]"など兄弟ノード群の中での順番の指定などである。
【０００７】
さらにXPathでは、親子以外の関係やある検索式での指定箇所に対する関数処理、またそれらの様々な組合せで、非常に複雑な検索条件を記述する事が可能となっている。
【０００８】
(XPath検索の既存技術)
しかしながら、このXPathの検索は負荷の重い処理であり、これを方式の工夫により高速に処理する技術が提案されてきた。例えば特許文献１では、検索すべきXPathを事前に登録してオートマトンに変換しておき、XML文書をSAXパーサを用いて逐次解析しながらこのオートマトンを駆動することで高速にXPath検索を行う技術を開示している。
【０００９】
一方XPathの検索ではないが、類似の構造化文書を多数扱うようなシステム、例えば同一システム間の通信メッセージの処理システムなどにおいては、ある一つの文書を処理したらその結果を保持しておき、類似した他の文書を処理する時には、以前の文書との差分を求め、この差分を以前の文書の処理結果に適応することで処理を高速化する技術が幾つか提案されている。
【００１０】
例えば特許文献２や特許文献３では、構造化文書の処理としてHTML文書のレンダリングを高速化するためにこのような方式を使用している。図23は差分情報を用いた構造化文書処理装置の従来技術の例である。差分情報を用いた従来の構造化文書処理装置は、入力部2301と、差分計算部2302と、差分反映部2303と、出力部2304と、元文書格納部2305と、元文書処理結果格納部2306から構成されている。
【００１１】
このような構成を有する従来の差分情報を用いた構造化文書処理装置はつぎのように動作する。
【００１２】
すなわち、事前に元文書格納部2305に元文書が登録され、その処理結果であるレンダリング結果が元文書処理結果格納部2306に登録される。ここで入力部2301に実際に処理すべき新文書が与えられると、まず差分計算部2302で元文書と新文書の差分を計算し、差分反映部2303で元文書処理結果格納部2306に保存されている処理結果をとりだし、その差分情報と元文書の処理結果から元文書の処理結果の修正すべき点を決定し、該当部分のみを修正してそれ以外の部分は元文書の処理結果を再利用した新文書の処理結果を作成し、出力部2304で出力する。
【００１３】
また特許文献４では、XML文書の解析処理に同様な手法を用いている。
【００１４】
これらの技術では、差分情報によって元文書の変更が指示された場合、その処理結果への反映を行うべく、必ず差分情報と処理結果の対応関係を取得する。すなわち、差分情報と処理結果の対応関係が取得できない場合は想定されていない。
【００１５】
例えば特許文献２や特許文献３では、処理結果であるレンダリング結果が画面部品の入れ子関係に基づく木構造を構成し、これが元の構造化文書の木構造にほぼそのまま対応するため、元文書の木構造のある箇所が変更されていた場合、該当するレンダリング結果のどの画面部品を修正するのかを特定している。
【００１６】
一方特許文献４では、入力としてバイナリ列としての構造化文書が与えられ、差分情報もこのバイナリ列の差分となるが、これを処理結果である解析済み文書データへ反映するために、状態遷移機械を用いてその対応関係を得ている。
【００１７】
【特許文献１】特開2003-323429号公報
【特許文献２】特開2005-108101号公報
【特許文献３】特開2002-091730号公報
【特許文献４】特開2006-024179号公報
【非特許文献１】「エックスエムエル  パス  ランゲージ（エックスパス）“XML Path Language(XPath)”」、［online］、［２００４年１２月２２日検索］、インターネット＜URL:http://www.w3.org/TR/xpath＞
【発明の開示】
【発明が解決しようとする課題】
【００１８】
特許文献１のような高速化手法では、方式自体は比較的高速であるものの、差分情報を有効に利用できないため、処理のためには毎回文書全体を処理する必要がある。その結果、類似の文書を多数扱わねばならない時でも常に毎回文書全体を検索処理せねばならず、高速化の効果には限界がある。
【００１９】
一方、特許文献２，３，４などの従来技術では差分情報と以前の処理結果を用いてレンダリングや文書解析処理を高速化する手法は開示されているが、XPathなどの検索式評価による情報抽出処理に対して差分情報を有効活用した事例は見当たらない。その理由は、XPathなどの検索式評価による情報抽出処理では、元の文書構造と処理結果の関係がきわめて多様であり、特許文献２，３，４などの従来技術のように差分情報と処理結果の対応関係を常に正確に求めることができないためである。
【００２０】
このため、類似の構造化文書を多数扱うようなシステムにおける構造化文書からの検索式評価による情報抽出処理において、既知の構造化文書である元文書との差分情報が与えられた時に、その差分情報を用いて元文書とそれに対する情報抽出処理結果から高速に情報抽出を行える新規な手法の開発が切望されている。
【００２１】
［発明の目的］
本発明はこのような事情に鑑みて提案されたものであり、その目的は、XPathなどの検索式評価による情報抽出処理に対して差分情報を有効活用した新規な構造化文書処理システム及びその方法を提供することにある。
【課題を解決するための手段】
【００２２】
本発明者は、XPathなどの検索式評価による情報抽出処理において元の文書構造と処理結果の関係がきわめて多様になる原因は検索式および差分情報の双方にあること、検索式および差分情報をその性質により分類すれば、差分情報による検索式の評価が行えるケースを検索式と差分情報の種類の組合せで特定できることを見出して本発明を完成させたものであり、本発明の第１の構造化文書処理システムは、検索式をその性質に基づいて分類して保持する検索式管理部と、元文書を前記保持された検索式に適用した結果および適用時の処理過程情報とともに格納する元文書管理部と、構造化文書の差分情報をその性質に基づいて分類し、差分の種類と検索式の種類とに基づいて検索式評価方法を決定する差分解析部と、差分情報による検索式評価が可能な場合に、差分情報と、検索式及びその分類結果と、元文書と、元文書に対する検索式の評価結果とを用いて検索式の評価を行う差分検索式評価部と、差分情報による検索式評価が不可能な場合に、元文書に差分情報を適用した新文書を生成してこれに検索式を適用する全文検索式評価部と、差分検索式評価部と全文検索式評価部の結果をあわせて元文書に差分情報を適用した文書に対する検索式の評価結果として出力する出力部とを備えたことを特徴とする。
【００２３】
本発明の第２の構造化文書処理システムは、第１の構造化文書処理システムにおいて、前記検索式管理部は、検索式を、検索式が構造化文書のノードの親子関係のみを含む場合に単純構造式と分類し、検索式が単純構造式に単純構造式を含む述語を付加したものである場合に述語付式と分類し、それ以外の式を複雑式と分類するものであり、前記差分解析部は、差分情報を変更箇所が値か文書構造かで分類し、変更箇所が値のみの場合に値差分と分類するものであり、且つ、差分情報が値差分の場合でかつ検索式が単純構造式あるいは述語付式である場合に差分情報による検索式評価が可能と判断するものであることを特徴とする。
【００２４】
本発明の第３の構造化文書処理システムは、第２の構造化文書処理システムにおいて、前記元文書管理部は、前記処理過程情報を、検索式の適用結果に含まれるノードのリストである結果ノードセットと、検索式の適用結果を導出するために検索式が直接評価したノードのリストである条件ノードセットとして保存することを特徴とする。
【００２５】
本発明の第４の構造化文書処理システムは、第３の構造化文書処理システムにおいて、前記元文書管理部は、前記処理過程情報としてさらに、検索式に述語が含まれ、かつ述語以外の式は該当し、かつ述語の評価結果によって該当しないと判断されたノードのリストである候補ノードセットを保存することを特徴とする。
【００２６】
本発明の第５の構造化文書処理システムは、第４の構造化文書処理システムにおいて、前記元文書管理部は、元文書を各ノードに一意なIDをつけて保存するとともに処理過程情報のノードセットを前記IDによって指定し、前記差分解析部は、差分情報を前記IDによって変更箇所を指定することを特徴とする。
【００２７】
本発明の第６の構造化文書処理システムは、第４または第５の構造化文書処理システムにおいて、前記差分検索式評価部は、差分が前記値差分であり、かつ検索式が前記単純構造式である場合に、前記結果ノードセットによって前記元文書に対する処理結果の出力に対する変更があるか否かを調べ、無い場合には前記処理結果をそのまま検索式の評価結果とし、変更がある場合はそれを適用しこの元文書の処理結果に差分を適用したものを評価結果とすることを特徴とする。
【００２８】
本発明の第７の構造化文書処理システムは、第６の構造化文書処理システムにおいて、前記差分検索式評価部は、さらに、差分が前記値差分であり、かつ検索式が前記述語付式である場合に、前記条件ノードセットによって差分による変更が前記元文書に対する検索式評価の出力結果が無効になる可能性があるか否かを調べ、可能性がある場合には前記条件ノードセットに関連する差分のみを適用してその部分に対して検索式を再評価し、前記条件ノードセットの調査で可能性が無いか、あるいは前記検索式の再評価の結果検索式と該当すると判断された場合に、前記結果ノードセットによって前記元文書に対する処理結果の出力に対する変更があるか否かを調べ、無い場合には前記処理結果をそのまま検索式の評価結果とし、変更がある場合はそれを適用しこの元文書の処理結果に差分を適用したものを評価結果とすると同時に、前記候補ノードセットによって差分による変更が前記元文書に対する検索式評価で該当しないと判断されたノードが該当するようになる可能性があるか否かを調べ、可能性がある場合には候補ノードセットに関連する差分のみを適用してその部分に対して検索式を再評価し、その結果検索式と該当すると判断された場合に、該当箇所の出力結果に対する変更があるか否かを調べ、無い場合には前記出力結果をそのまま検索式の評価結果とし、変更がある場合はそれを適用したものを評価結果とすることを特徴とする。
【００２９】
本発明の第８の構造化文書処理システムは、第１乃至第７の何れかの構造化文書処理システムにおいて、入力された構造化文書を元文書と比較して差分を計算する差分計算部と、入力された構造化文書を保存する入力文書保存部とをさらに備え、前記差分検索式評価部と前記全文検索式評価部は、元文書に差分を適用する代わりに前記入力文書保存部に保存された入力文書を参照することを特徴とする。
【００３０】
本発明の第９の構造化文書処理システムは、第１乃至第７の何れかの構造化文書処理システムにおいて、元文書に対して一部あるいは全部の差分を適用した新文書を管理する新文書管理部をさらに備え、前記差分検索式評価部と前記全文検索式評価部は、元文書への差分の適用時に新文書管理部に適用と結果の取得を依頼し、新文書管理部が、既に差分適用済みの箇所は再度差分適用を行わず保存している新文書から適用結果を返すことを特徴とする。
【００３１】
本発明の第１０の構造化文書処理システムは、１以上の検索式とその種類、および、元文書と該元文書に前記検索式を適用した結果と処理過程情報を記憶する記憶部と、与えられた構造化文書の差分情報をその性質に基づいて分類し、該差分情報の種類と前記記憶部に記憶されている検索式の種類とに従って、それぞれの前記検索式毎に、差分情報を用いて評価を行うか否かを決定する差分解析部と、差分情報を用いて評価を行うと決定された検索式について、前記記憶部に記憶された元文書に前記検索式を適用した結果と処理過程情報とを用いて評価を行う差分検索式評価部と、差分情報を用いずに評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記差分情報を適用した文書を用いて評価を行う全文検索式評価部とを備えることを特徴とする。
【００３２】
本発明の第１１の構造化文書処理システムは、第１０の構造化文書処理システムにおいて、前記記憶部には、構造化文書のノードの親子関係のみを含む単純構造式の検索式と、該検索式を元文書に適用した結果と処理過程情報とが記憶されており、前記差分解析部は、与えられた構造化文書の差分情報が、変更箇所が値のみである値差分である場合、前記単純構造式の検索式については差分情報を用いて評価を行うと決定し、前記差分検索式評価部は、前記単純構造式の検索式について、前記記憶部に記憶された元文書に前記単純構造式の検索式を適用した結果と処理過程情報とを用いて評価を行うことを特徴とする。
【００３３】
本発明の第１２の構造化文書処理システムは、第１０の構造化文書処理システムにおいて、前記記憶部には、構造化文書のノードの親子関係のみを含む単純構造式に単純構造式を含む述語を付加した述語付式の検索式と、該検索式を元文書に適用した結果と処理過程情報とが記憶されており、前記差分解析部は、与えられた構造化文書の差分情報が、変更箇所が値のみである値差分である場合、前記述語付式の検索式については差分情報を用いて評価を行うと決定し、前記差分検索式評価部は、前記述語付式の検索式について、前記記憶部に記憶された元文書に前記述語付式の検索式を適用した結果と処理過程情報とを用いて評価を行うことを特徴とする。
【００３４】
本発明の第１の構造化文書処理方法は、コンピュータを用いて構造化文書に対する検索式の評価を行う方法において、前記コンピュータが、１以上の検索式をその種類を付加して記憶部に記憶すると共に、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１のステップと、前記コンピュータが、与えられた構造化文書の差分情報をその性質に基づいて分類し、該差分情報の種類と前記記憶部に記憶されている検索式の種類とに従って、それぞれの前記検索式毎に、差分情報を用いて評価を行うか否かを決定する第２のステップと、前記コンピュータが、差分情報を用いて評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記検索式を適用した結果と処理過程情報とを用いて評価を行い、差分情報を用いずに評価を行うと決定した検索式について、前記記憶部に記憶された元文書に前記差分情報を適用した文書を用いて評価を行う第３のステップとを含むことを特徴とする。
【００３５】
本発明の第２の構造化文書処理方法は、コンピュータを用いて構造化文書に対する検索式の評価を行う方法において、前記コンピュータが、構造化文書のノードの親子関係のみを含む単純構造式の検索式と、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１のステップと、前記コンピュータが、与えられた構造化文書の差分情報をその性質に基づいて分類し、変更箇所が値のみである値差分である場合、前記単純構造式の検索式については差分情報を用いて評価を行うと決定する第２のステップと、前記コンピュータが、前記単純構造式の検索式について、前記記憶部に記憶された元文書に前記単純構造式の検索式を適用した結果と処理過程情報とを用いて評価を行う第３のステップとを含むことを特徴とする。
【００３６】
本発明の第３の構造化文書処理方法は、コンピュータを用いて構造化文書に対する検索式の評価を行う方法において、前記コンピュータが、構造化文書のノードの親子関係のみを含む単純構造式に単純構造式を含む述語を付加した述語付式の検索式と、元文書を該元文書に前記検索式を適用した結果と処理過程情報とを付加して前記記憶部に記憶する第１のステップと、前記コンピュータが、与えられた構造化文書の差分情報をその性質に基づいて分類し、変更箇所が値のみである値差分である場合、前記述語付式の検索式については差分情報を用いて評価を行うと決定する第２のステップと、前記コンピュータが、前記述語付式の検索式について、前記記憶部に記憶された元文書に前記述語付式の検索式を適用した結果と処理過程情報とを用いて評価を行う第３のステップとを含むことを特徴とする。
【００３７】
『作用』
本発明の構造化文書処理システムにあっては、評価すべき検索式と差分の対象となる元文書とを事前に登録しておく。ここで、検索式管理部は、登録された検索式を保持すると同時に、検索式をその性質に基づいて分類しておき、元文書管理部は、登録された元文書と、元文書に登録された検索式を適用した結果とその処理過程情報とを共に保持する。
【００３８】
次に、ある新文書と元文書との差分情報が与えられると、差分解析部は与えられた構造化文書の差分情報を解析し、差分の種類と検索式の種類とに基づいて、各検索式毎に検索式評価方法を決定する。そして、差分情報による検索式評価が可能な場合に、差分検索式評価部が、差分情報と、検索式及びその分類結果と、元文書と、元文書に対する検索式の評価結果とを用いて検索式の評価を行い、差分情報による検索式評価が不可能な場合に、全文検索式評価部が、元文書に差分情報を適用した新文書を生成してこれに検索式を適用し、出力部が、差分検索式評価部と全文検索式評価部の結果をあわせて元文書に差分情報を適用した文書に対する検索式の評価結果として出力する。
【００３９】
このように検索式と差分情報をその性質によって分類し、検索式と差分情報の種類の組合せから適切な検索式評価方法を決定し、特に差分情報を元文書の検索式評価結果に適用可能な組合せの場合に差分情報と元文書の検索式評価結果を用いた検索式評価を行うことで、元文書への全ての差分情報の適用と、全ての検索式の文書全体に対する評価を省略でき、本発明の目的を達成することができる。
【発明の効果】
【００４０】
本発明によれば、検索式と、構造化文書の差分情報が与えられたときに、検索式と差分情報の性質によっては、差分の対象となる元文書とそれに対する情報抽出処理結果を利用して、高速に情報抽出処理を行える効果がある。
【００４１】
その理由は、検索式と差分情報の性質を解析し、両者の性質毎に適切な検索式評価方法を用い、特に差分情報を元文書の検索式評価結果に適用可能な場合には適用することで、検索式の文書全体に対する評価を省略できるためである。
【発明を実施するための最良の形態】
【００４２】
次に、本発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００４３】
図1を参照すると、本発明の構造化文書処理装置101の第１の実施の形態は、検索式管理部102と、元文書管理部103と、差分解析部104と、差分検索式評価部105と、全文検索式評価106と、出力部107とから構成されている。
【００４４】
検索式管理部102は、内部に分類部102aと保存部102bとを持ち、保存部102bは検索式テーブル108を持つ。図2は検索式テーブル108の構成図である。検索式テーブル108は、個々の検索式毎に、検索式と、検索式の種類とを持つ。
【００４５】
また元文書管理部103は、内部に検索式評価部103aと保存部103bとを持ち、保存部103bは元文書テーブル109を持つ。図3は元文書テーブル109の構成図である。元文書テーブル109は、元文書と、検索式と、処理結果と、処理結果ノードセットと、条件ノードセットと、候補ノードセットとを持つ。各元文書は検索式を複数持てる。各検索式は処理結果を複数持てる。各処理結果は一つずつの結果ノードセットと条件ノードセットを持てる。また各検索式は一つの候補ノードセットを持てる。ここで、本実施の形態では、元文書テーブル109中の或る元文書および検索式に対応して、その元文書にその検索式を適用した結果とは別に、その適用結果に現れるノード群のIDのセットを結果ノードセットとして格納しているのは、ID比較により差分の影響の有無を容易にチェックできるようにするためである。別の実施の形態として、結果ノードセットを省略し、適用結果から毎回、結果ノードセットを動的に生成する実施の形態も考えられる。
【００４６】
差分解析部104は、内部に分類部104aと評価部決定部104bとを持つ。
【００４７】
これらの手段はそれぞれ概略つぎのように動作する。
【００４８】
検索式管理部102は、外部から登録された検索式111を分類部102aで解析、分類し、その結果を検索式111とともに保存部102bを通して検索式テーブル108に保持する。ここで、検索式111の分類は差分計算の容易性に基づいて行う。
【００４９】
元文書管理部103は、外部から登録された元文書112に対して検索式管理部102で検索式テーブル108に保持された検索式を適用し、元文書112と、検索式の適用結果と、適用過程の情報とを保存部103bを通して元文書テーブル109に保持する。
【００５０】
差分解析部104は入力された差分情報113を分類部104aで解析、分類し、評価部決定部104bで検索式管理部102に登録された各検索式毎に、差分情報の分類結果と検索式の分類結果とから差分情報を用いた検索が可能か否かを判定し、可能な検索式は差分検索式評価部105に、不可能な検索式は全文検索式評価部106に、それぞれ評価させる。
【００５１】
差分検索式評価部105は、差分情報113および検索式の種類と、差分情報113の変更対象と元文書管理部103に保存してある処理結果と処理過程の情報とから差分情報の利用方法を決定し、差分情報を用いた検索式評価を行う。
【００５２】
全文検索式評価部106は、差分情報113を元文書に適用した新文書を作成し、新文書に対して検索式の評価を行う。
【００５３】
出力部107は、差分検索式評価部105の結果と全文検索式評価部106の結果とをあわせて出力する。
【００５４】
図4は検索式管理部102の動作を示すフローチャートである。検索式管理部102は、S401で外部からの検索式111の登録要求を受けて、S402でその検索式111に含まれる記述内容を調べて検索式111を分類し、S403で検索式111と分類結果とを検索式テーブル108に追加し、S404で加えて式が追加された事を元文書管理部103に通知する。ここで分類は、検索式111が構造化文書の構造情報である要素の単純な親から子への参照関係のみを含む場合は単純構造式、単純構造式に加え同じく単純な参照関係のみで記述される値に対する条件である述語を持つ場合は述語付式、それ以外の式は複雑式として分類する。
【００５５】
図5は元文書管理部103の動作を示すフローチャートである。元文書管理部103は、S501で外部からの要求を受け、S502で元文書112の登録要求の場合、S503で登録要求から対象となる元文書112を取り出し、S504で元文書112を元文書テーブル109に保存するとともに、S505で検索式管理部102から検索式の一覧を獲得し、S506で各検索式について検索式の処理結果と処理過程とを計算し、S507で処理結果と処理過程情報とを保存する。
【００５６】
ここで、元文書保存時には、元文書112の各ノードに文書内で一意なIDを振り、このIDとともに保存する。また検索式の処理結果と処理過程の計算は、具体的には、元文書112に適用した結果を元文書テーブル109に処理結果として保存し、適用結果に現われるノード群のIDのセットを処理過程の結果ノードセットとして保存し、適用結果を導出するために検索式が直接評価したノード群のIDのセットを処理過程の条件ノードセットとして保存し、もし検索式が述語付式の場合には、述語を除いた単純構造式部分のみであれば該当したが述語部によって該当しなくなったノードを仮の適用結果と見なした時の条件ノードセット相当のノード群のIDのセットを、候補ノードセットとして保存する。
【００５７】
また、S502で要求が検索式管理部102からの新たな検索式の追加要求だった場合には、S511で検索式追加要求から対象となる検索式を取り出し、S512で既に登録されている全ての元文書を取り出し、S513でこれに対してその検索式の適用結果と処理過程とを計算し、S514でこれを元文書テーブル109に追加する。
【００５８】
図6Aは差分解析部104の動作を示すフローチャートである。差分解析部104は、S601で元文書管理部103に保存された元文書への参照と元文書の各ノードを元文書管理部103がつけたIDによって指定しそのノードの変更を指示することで表現される差分情報113を受けると、S602で差分情報113に記述された変更先ノードの一覧を取り出し、S603で変更先ノードに要素値や属性値などの値ノード以外のノードが含まれているか否かを調べることで差分を分類する。差分の分類は、変更先ノードに値ノード以外のノードが含まれていない差分を値差分、値ノード以外のノードが一つでも含まれている差分を構造差分とする。
【００５９】
次に、S604で検索式管理部102から登録されている検索式とその種類の一覧を取得し、S605とS606で各検索式について、差分の種類と検索式の種類とから、差分情報を用いて検索式の評価が可能か否かを調べ、S607で差分情報が値差分であり、かつS608で検索式が単純構造式かあるいは述語付式である場合には差分情報で処理可能と判断してS610でその検索式を差分検索式評価部105に割り当て、S607やS608で差分情報が構造差分あるいは検索式が複雑式の場合には不可能と判断してS609でその検索式を全文検索式評価部106に割り当て、S611で各検索式について割り当てられた検索式評価部105，106に検索式と差分情報と差分情報の種類を渡して検索式の評価を行う。
【００６０】
すなわち、本実施の形態においては、図6Bに示されるように、差分情報をその性質により値差分と構造差分との２種類に分類し、検索式をその性質により単純構造式と述語付式とそれら以外の複雑式との３種類に分類し、差分情報の種類が値差分で且つ検索式の種類が単純構造式および述語付式となる○印を付けた組合せの場合に差分情報による検索を行い、それ以外の×印を付けた組合せの場合には全文検索を行う。
【００６１】
図7は差分検索式評価部105の動作を示すフローチャートである。差分検索式評価部105は、検索式のセットと差分情報と差分情報の種類とを受け取ると、各検索式について、元文書管理部103から該当検索式の処理過程情報と処理結果とを取得し、差分情報を用いて以下のように検索式の評価を行い、結果を出力部107に送る。
【００６２】
(1)検索式が単純構造式の場合、元文書の処理結果への差分適用を行い、これを結果とする。具体的には、S710で変更対象ノードIDが一つでも結果ノードセットに含まれるか否かを調べ、含まれていなければS712で元文書の処理結果をそのまま結果とし、含まれればS711で元文書の処理結果に該当する部分を差分情報によって書換えたものを結果とする。
【００６３】
(2)検索式が述語付式の場合、以下の両方の処理を行う。
【００６４】
(2.1)S720で変更対象ノードIDが一つでも条件ノードセットに含まれるか否かを調べ、変更対象ノードIDが一つでも条件ノードセットに含まれる場合、S721で条件ノードセットが示す元文書の一部分を差分情報によって書換え、S722でこの一部分に対してのみ検索式を再度評価する。S720で条件ノードセットに含まれないか、あるいはS722で再度検索式を満たす場合、S723,S724,S725で前記の元文書の処理結果への差分適用を行い、これを結果とする。
【００６５】
(2.2)S731で変更対象ノードIDが一つでも候補ノードセットに含まれるか否かを調べ、含まれている場合、S732で候補ノードセットが示す元文書の一部分を差分情報によって書換え、S733でこの一部分に対してのみ検索式を再度評価し、その結果検索式が新たに該当した場合、S734でその結果に対しての差分があるか否かを調べ、無ければS736でその結果をそのまま、あればS735で結果に対して再度差分適用を行い、これを結果とする。
【００６６】
図8Aは全文検索式評価部106の動作を示すフローチャートである。全文検索式評価部106は、S801で検索式のセットと差分情報113を受け取ると、S802で元文書管理部103から元文書を取り出し、S803で元文書に差分情報を適用して新文書を生成し、S804で新文書に対して指定された検索式を評価し、S805で結果を出力部に出力する。
【００６７】
出力部107は各検索式毎にその評価結果を出力する。
【００６８】
(アルゴリズム解説)
ここで、検索式の種類と、差分の種類と、処理過程情報と、差分検索式評価部105の動作との関係について補足する。差分による文書の変更が元文書の処理結果に与える影響は、以下の4つに分類できる。
【００６９】
(1)検索式の評価とは無関係な箇所の変更である。
(2)元文書で検索式に該当した箇所への影響として、
(2-1)元文書で該当した箇所が該当しなくなる。
(2-2)元文書で該当した箇所が引続き該当するが、出力される該当箇所の中が変更される。
(3)元文書で該当しなかった箇所が該当するようになる。
【００７０】
ただし、一つの変更が一つの検索式の結果に与える影響は、(2)と(3)は同時にあり得る(このことを考慮してS734〜S736が設けられている)。(2)と(3)いずれにも該当しない場合が(1)となる。
【００７１】
検索式と差分情報の内容は極めて多様でありその一般的な関係を明確化するのは困難であるため、本発明では差分の与える影響が上記のいずれに該当するかが明確な差分と検索式の組合せの場合には差分情報を用いた計算を行い、それ以外、すなわち差分が元文書に対する検索結果に与える影響が不明な場合には従来技術での通常の検索式評価を行っている。
【００７２】
(2-1)に該当するか否かを調べるには、まず元文書で検索式に該当した箇所を導くための条件となったノードが変更されていないかどうかを調べるが、これを行うための処理過程情報が条件ノードセットである。ただし単純構造式の場合は値に関する制約となる述語を含まないため、値の変化は検索式の結果には影響を与えず、その結果、単純構造式でかつ値差分では(2-1)となる事は無い。述語付式で(2-1)に該当する場合、元文書での結果は新文書では該当しなくなる可能性がある事から、当該箇所のみ検索式の再評価を行う(S721，S722)。
【００７３】
次に、(2-1)にならない場合、(2-2)に該当するか否かを調べるが、これを行うための処理過程情報が結果ノードセットである。これは単純に出力に含まれるノードに変更箇所が含まれるか否かを調べるものであり、該当する場合には、元文書での結果のみを差分で書換えて出力とする(S711，S724)。
【００７４】
一方、(3)に該当するか否かを調べるには、元文書の検索で該当しなかった箇所の中から、差分によって該当する可能性のある箇所を選んでその部分のみ再評価を行う必要がある。ただし単純構造式の場合は値に関する制約となる述語を含まないため、値の変化は検索式の結果には影響を与えず、その結果、単純構造式でかつ値差分では(2-1)となる事は無い。ただし先に述べた通り、単純構造式の場合は値に関する制約となる述語を含まないため、値の変更によって該当箇所が変わる事は無く、よって単純構造式が(3)になる事は無い。また述語式も、値の変更では述語部分を除いた単純構造式相当の部分は変わらず、その中で述語の評価によって元文書では該当していなかった箇所が該当するように変わる可能性があるのみである。この可能性をチェックするために使用する処理過程情報が候補ノードセットである(S731，S733)。
【００７５】
以上の検索アルゴリズムの内容を表形式にまとめたものを図8Bに示す。
【００７６】
次に、本実施の形態の効果について説明する。
【００７７】
本実施の形態では、事前に登録された検索式を分類し、また事前に登録された元文書に対して検索式を適用した結果と処理過程の情報を保持しておき、入力された差分情報を分類して、これら分類結果や処理過程情報から利用可能な検索式評価方法を決定し、差分情報を用いて計算の省力化が可能な場合には省力化された方式を用いる事で、差分情報を用いて高速に構造化文書の検索式を評価する事ができる。
【００７８】
また、本実施の形態では、さらに、検索式を単純構造式、述語付式、これら以外の複雑式に分類し、差分情報を値差分と構造差分に分類する事で、値差分と単純構造式あるいは述語付式の組合せの場合に、元文書に対する検索式の処理結果と、処理過程情報と、差分情報を用いて検索結果を得る事ができる。
【００７９】
(第2の実施の形態)
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【００８０】
図9を参照すると、本発明の第２の実施の形態は、第１の実施の形態の構成に加え、入力された構造化文書114と元文書112との差分情報を計算する差分計算部901と、入力文書を保持する入力文書保存部902とを含む。
【００８１】
これらの手段はそれぞれ概略つぎのように動作する。
【００８２】
本実施の形態の構造化文書処理装置101は、第１の実施の形態と異なり差分情報の代わりに構造化文書114を受け取り、差分計算部901で、入力された構造化文書114と事前に登録されている元文書との差分を計算し差分情報として差分解析部104に出力するとともに、入力文書を、差分計算時に元文書と一致するとみなした入力文書のノードとの対応関係情報とともに入力文書保存部902に保存する。対応関係情報は例えば、該当する元文書のノードと同じIDを入力文書のノードに割り当てる事で実現できる。
【００８３】
また全文検索式評価部106は、第１の実施の形態において差分情報と元文書から新文書を生成する処理の代わりに入力文書保存部902に保存されている文書を取り出し、これを利用する。
【００８４】
また差分検索式評価部105は、第１の実施の形態における検索式が述語付式で差分が値差分の場合の処理で、条件ノードセットや候補ノードセットが示す元文書の一部分を差分情報によって書換える処理の代わりに、入力文書保存部902に保存されている入力文書と元文書のノードの対応関係情報を利用して、書換え対象の元文書の一部に該当する入力文書の一部を決定し、そこに対してのみ検索式を評価する。
【００８５】
本実施の形態により、構造化文書処理装置101への入力が差分情報ではなく構造化文書である場合でも、差分計算の負荷が検索式の文書全体の適用の負荷よりも十分に小さければ、検索式の処理を高速化する事が可能となる。
【００８６】
(第3の実施の形態)
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
【００８７】
図10を参照すると、本発明の第３の実施の形態は、第１の実施の形態の構成に加え、元文書に差分情報を適用した新文書を保存する新文書管理部1001を含む。
【００８８】
これらの手段はそれぞれ概略つぎのように動作する。
【００８９】
第１の実施の形態では、検索式を評価する時に検索式毎に別々に必要に応じて元文書に対して差分情報の一部あるいは全部を適用していたが、これを、新文書管理部1001により元文書への差分情報の適用を一元管理して、適用結果を全ての検索式にまたがって共有するようにし、同じ差分を複数回適用しないようにする。
【００９０】
具体的には、差分解析部104は、全文検索式評価部106および差分検索式評価部105に差分情報を渡すと同時に、新文書管理部1001にも差分情報を渡す。
【００９１】
一方、全文検索式評価部106および差分検索式評価部105は、元文書に差分情報を適用した新文書の一部あるいは全部が必要な場合、必要な箇所を新文書管理部1001に要求して取得するようにする。
【００９２】
新文書管理部1001は、元文書テーブル109から元文書を取り出し、全文検索式評価部106および差分検索式評価部105から新文書の一部あるいは全部を要求されると、要求された箇所に対する新文書の一部が存在しているか否かを調べ、無ければ要求された一部に関連する差分情報のみを元文書に適用した新文書の一部を生成し、これを保存すると同時に要求元にその情報を返す。
【００９３】
これにより、個別の検索式に必要な元文書への差分適用で同じ箇所に対する差分情報の適用を行う必要がある場合に、差分情報毎に適用処理を一度で済ます事ができ、重複した差分適用処理を省く事が可能となる。
【００９４】
なお、第１の実施の形態では差分検索式評価部105で評価できない差分と検索式の組合せは全て全文検索式評価部106で処理するとしたが、これは、これらの組合せを必ず全て全文検索式評価部106で処理しなければならないと制限するものではない。
【００９５】
例えば、本発明とは異なる方式を用いた第３の検索式評価部をさらに備え、本発明の差分検索式評価部105や全文検索式評価部106と組合せて、差分解析部104が、第１の実施の形態で差分検索式評価部105や全文検索式評価部106に割り当てた、差分と検索式の組合せの一部を第３の検索式評価部に割り当てる事は、一般的な技術者であれば容易に想像できるであろう。
【実施例】
【００９６】
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。
【００９７】
図11は本実施例のメッセージフィルタリング装置の構成図である。メッセージフィルタリング装置は、受信したメッセージに対して事前に与えられたフィルタ条件を適用し、結果を外部に出力する。フィルタ条件はXPath式として与え、XPath式で該当したノードとその子孫を結果として出力する。
【００９８】
図11によれば、本実施例のメッセージフィルタリング装置1101は、検索式管理部102と、元文書管理部103と、差分解析部104と、差分検索式評価部105と、全文検索式評価部106と、出力部107と、新文書管理部1001と、通信部1102と、管理部1103とから構成されている。
【００９９】
通信部1102は外部からのメッセージ115を受信し、中に含まれる差分情報を差分解析部104に渡す。管理部1103はメッセージフィルタリング装置1101の管理者がユーザインタフェースを通してフィルタ条件(検索式111)や元文書112をメッセージフィルタリング装置1101に登録する。
【０１００】
構造化文書はXMLを、検索式は全てXPathを使用する。
【０１０１】
(実施例動作)
(実施例動作/事前登録)
ここで、まず管理部1103を通して検索式111として、"/A/B/C"と"/A/B[C=t1]/D"の2つが登録されると、検索式管理部102は両方の検索式の内容をチェックし、"/A/B/C"は単純な親から子への参照関係のみを含むため単純構造式、"/A/B[C=t1]/D"は単純構造式に加えて述語部を含むため述語付式として分類し、結果を検索式テーブル108に保存する。図12の検索式テーブル1201は検索式が登録された検索式テーブル108の例である。
【０１０２】
なおここで、"/A/B/C"はXPathにおいて「ルートノードの下のAというタグの中のBというタグの中のCというタグのノード」という意味であり、"/A/B[C=t1]/D"は「ルートノードの下のAというタグの中のBというタグの中のDというタグのノードで、かつBの中のCというタグの値がt1であるもの」という意味である。
【０１０３】
次に頻繁に使用されるメッセージ(元文書)の雛型として、図13の構造化文書である文書1301が元文書として管理部1103から登録されると、元文書管理部103はその文書を各ノードに出現順にIDを振り、IDと元文書を元文書テーブル109に保存する。ここで、図14はIDを付け木構造として表現した元文書1401であり、カッコ付の数字がIDを示している。
【０１０４】
次に元文書管理部103は、既に登録されているXPath式2つをそれぞれ元文書に対して適用し、その結果と処理過程情報を元文書テーブル109に保存する。この場合、"/A/B/C"の条件を満たすノードは、ID=3とID=8の2つとなるが、これらの結果を導くための条件として評価されたノードは、検索式"/A/B/C"の'A'、'B'、'C'にそれぞれ該当したノードで、ID=3のための条件ノードセットはID=1,ID=2,ID=3で、ID=8のための条件ノードはID=1,ID=7,ID=8となり、結果として出力されるノードはID=3以下であるID=3とID=4、ID=8以下であるID=8とID=9となる。"/A/B/C"は単純構造式なので、候補ノードセットは持たない。
【０１０５】
一方、"/A/B[C=t1]/D"の条件を満たすノードは、ID=5となるが、これの条件として評価されるノードセットは"/A/B[C=t1]/D"の'A'、'B'、'C'、'D'と't1'に該当するテキストノードであるID=1,ID=2,ID=3,ID=4,ID=5となり、出力されるノードはID=5以下であるID=5とID=6となる。さらに、"/A/B[C=t1]/D"は述語付式であり、述語[C=t1]を除いた式"/A/B/D"が該当するが述語[C=t1]によって該当しなくなったノードはID=9の部分が該当しなかったツリーの右側半分の部分であり、候補ノードセットはこの部分の条件ノードセット相当、すなわち、ID=1,ID=7,ID=8,ID=9,ID=10となる。
【０１０６】
図15の元文書テーブル1501は元文書、結果、処理過程情報が登録された元文書テーブル109の例である。
【０１０７】
図16と図17は上記"/A/B/C"と"/A/B[C=t1]/D"のそれぞれの処理過程情報のイメージを図示したものである。すなわち処理過程情報は、元文書の各ノードがXPath式の評価結果に対してどのような関係にあるのかを示すものである。
【０１０８】
(実施例動作/差分情報に対する検索処理実行)
(差分例1)
次に、まず「文書1のID=11のノードを"t5"に置換」という差分情報を含むメッセージ115が通信部1102に届いた場合を考える。これは、図18の新文書1801の構造化文書を、"文書1"との差分情報として表現したものに相当する。まず通信部1102はメッセージ115に含まれる差分情報を抽出し、これを差分解析部104に渡す。差分解析部104は、まず元文書テーブル109に保存されている文書1を取り出し、ID=11のノードが値ノードか否かを調べる。ここでは、ID=11のノードはテキストノードであるから、これは値ノードとなり、かつ、差分情報はこの差分しか含まない事から、この差分情報は値差分に分類される。
【０１０９】
次に差分解析部104は検索式管理部102から登録されている式とその種類の一覧を取得し、差分情報の値差分という分類結果と、検索式の単純構造式および述語付式という分類結果とから、両方の式とも差分情報で処理可能と判断して差分検索式評価部105に検索式と差分情報と差分情報の種類とを渡す。
【０１１０】
次に差分検索式評価部105は、検索式のセットと差分情報と差分情報の種類とを受け取ると、まず検索式"/A/B/C"について元文書管理部103から"/A/B/C"の元文書に対する処理過程情報を取得し、これと差分情報の書換え対象ノードであるID=11とを比較する。この場合、結果ノードセット、条件ノードセットはいずれもID=11を含まないので、新文書1801に対する"/A/B/C"の適用結果は元文書と同一であると判断され、元文書の処理結果であるID=3,ID=8の2つのノード以下の部分が出力部107に送られ、その結果、"t1"、"t3"という検索式の該当箇所が出力される。同様に"/A/B[C=t1]/D"も結果ノードセット、条件ノードセットはいずれもID=11を含まないので、元文書の処理結果であるID=5のノード以下の部分が出力部107に送られ、その結果、"t2"が出力される。
【０１１１】
よってこの場合、XPath式の評価および結果とは無関係の差分情報だったため、差分の適用や検索式の再評価などは一切行われずに結果が出力された事になる。
【０１１２】
(差分例2)
次に、「文書1で、ID=11のノードを"t5"に置換し、ID=4のノードを"t6"に置換」という差分情報を含むメッセージ115が通信部1102に届いた場合を考える。これは、図19の新文書1901の構造化文書を、"文書1"との差分情報として表現したものに相当する。
【０１１３】
この差分情報が差分解析部104に渡されると、差分解析部104はID=4とID=11が共に値ノードか否かを調べ、両方とも値ノードであることから、この差分情報は値差分に分類される。
【０１１４】
次に差分解析部104は検索式管理部102から登録されている式とその種類の一覧を取得し、差分情報の分類結果と、検索式の分類結果とから、両方の式とも差分情報で処理可能と判断して差分検索式評価部105に渡す。
【０１１５】
次に差分検索式評価部105は、検索式のセットと差分情報と差分情報の種類とを受け取ると、まず検索式"/A/B/C"について元文書管理部103から"/A/B/C"の元文書に対する処理過程情報を取得し、これと差分情報の書換え対象ノードであるID=4とID=11とを比較する。この場合、結果ノードセットがID=4を含む事から、差分検索式評価部105は新文書管理部1001にID=4に対する差分適用を指示する。
【０１１６】
新文書管理部1001はまだ何の差分適用も行っていない事から、元文書管理部103から元文書を取り出し、「ID=4のノードを"t6"に置換」という差分を適用してID=4の内容を"t6"に書換えて結果を返し、元文書の処理結果であるID=3,ID=8の2つのノード以下の部分が出力部107に送られ、その結果、"t6"、"t3"という検索式の該当箇所が出力される。
【０１１７】
次に"/A/B[C=t1]/D"の処理過程情報をチェックするが、ここではまず条件ノードセットがID=4を含む事から、差分検索式評価部105は新文書管理部1001にID=4に対する差分適用を指示する。新文書管理部1001は既にID=4に対する差分を適用済みである事から、保存内容を参照して結果を返す。次に差分検索式評価部105は条件ノードセットにあるID=1,2,3,4,5に対して、"/A/B[C=t1]/D"の式の再評価を行う。ここでは"C=t1"の条件が満たされなくなっていることから、元文書に対するID=5という結果は既に条件を満たさなくなっており、新文書に対する結果からは外される。また、候補ノードセットはID=4を含まない事から、ID=1,7,8,9,10のノードに対する式の再評価は行われず、その結果、"/A/B[C=t1]/D"は該当箇所無しとして結果が出力される。
【０１１８】
よってこの場合、XPath式の評価および結果に関連する「ID=4のノードを"t6"に置換」という差分のみが適用され、無関係な「ID=11のノードを"t5"に置換」という差分は適用されない。また式の再評価も、ID=1,2,3,4,5のノードに対する"/A/B[C=t1]/D"の式の評価のみ行われる。"/A/B/C"は式の再評価は行われず、出力結果の変更のみが行われる。
【０１１９】
(差分例3)
次に、「文書1で、ID=9のノードを"t1"に置換」という差分情報を含むメッセージ115が通信部1102に届いた場合を考える。これは、図20の新文書2001の構造化文書を、"文書1"との差分情報として表現したものに相当する。この差分情報が差分解析部104に渡されてから、差分検索式評価部105に渡される所までは差分例1と同じである。
【０１２０】
次に差分検索式評価部105は、検索式のセットと差分情報と差分情報の種類とを受け取ると、検索式"/A/B/C"について処理過程情報をチェックし、結果ノードセットがID=9を含む事から、差分例2の時と同様に新文書管理部1001にID=9に対する差分適用を指示し、ID=3と、ID=8以下のノードとを結果として出力する。
【０１２１】
次に"/A/B[C=t1]/D"の処理過程情報をチェックするが、ここではまず条件ノードセットと結果ノードセットはID=9を含まない事から、元文書での処理結果であるID=5はそのまま結果として出力される。
【０１２２】
一方、ここでは候補ノードセットがID=9を含む事から、新文書管理部1001にID=9に対する差分適用指示を出し、既に差分は適用済みであるから、その適用結果に対して、候補ノードセットに記述されているID=1,7,8,9,10のノードに対して"/A/B[C=t1]/D"を再評価する。この場合、ID=9の置換により述語部に記述された条件が満たされるようになっておりその結果がID=10である事から、ID=10以下のノードが結果として出力され、その結果、差分検索式評価部105は先の元文書での結果とあわせてID=5とID=10の2つを"/A/B[C=t1]/D"の結果として出力する事になる。
【０１２３】
よってこの場合、元文書での評価結果の部分は検索式の再評価は行わず、差分情報による変更で検索式を満たす可能性のある新文書の一部分にのみ満たす可能性のある検索式のみの再評価が行われる。
【０１２４】
(差分例4)
次に、「文書1で、ID=3のノードを"t1"に置換」という差分情報を含むメッセージ115が通信部1102に届いた場合を考える。これは、図21の新文書2101の構造化文書を、"文書1"との差分情報として表現したものに相当する。
【０１２５】
この差分情報が差分解析部104に渡されると、ID=3のノードが値ノードではなく要素ノードであることから、差分は構造差分として分類され、その結果、差分による計算は出来ないと判断され、全文検索式評価部106に差分情報と検索式とが渡される。
【０１２６】
全文検索式評価部106は新文書管理部1001に全ての差分の適用を指示し、出来上がった新文書全体に対して登録されている2つの検索式をそれぞれ評価し、"/A/B/C"に対してはID=8のみを、"/A/B[C=t1]/D"については該当無しを結果として出力する。
【０１２７】
よってこの場合、差分情報が複雑で、元文書での処理結果/処理過程情報と差分情報による差分計算が行えない場合にも、処理効率の向上は行えないものの、検索式の評価結果を出力する事が可能となる。
【０１２８】
(差分例5)
次に、検索式としてさらに、"/A/B/*[2]"というXPathが登録された場合を考える。図22の検索式テーブル2201は"/A/B/*[2]"が追加された検索式テーブル108の一例である。この式は「ルートノードの下のAというタグの中のBというタグの中に現われる任意のタグで2番目に出現するノード」という意味であり、「任意のタグで2番目」という単純な親子関係ではないノード間の関係を含む。この場合、検索式管理部102はこの検索式を複雑式として分類し、結果を検索式テーブル2201に保存する。
【０１２９】
ここで、差分例1と同じく「文書1のID=11のノードを"t5"に置換」という差分情報を含むメッセージ115が通信部1102に届いた場合を考える。
【０１３０】
この場合、差分解析部104は差分情報を値差分に分類し、その結果、検索式"/A/B/C"と"/A/B[C=t1]/D"については、差分例1と同様に差分情報による検索が可能と判断され差分検索式評価部105に渡され、同様に評価される。これら2つの検索式の出力結果も差分例1と同じである。
【０１３１】
一方、"/A/B/*[2]"は複雑式であるため、差分情報の種類によらず、常に全文検索式評価部106に渡される。全文検索式評価部106は新文書管理部1001に全ての差分の適用を指示し、出来上がった新文書全体に対して"/A/B/*[2]"のみを検索し、結果を出力する。この場合、ID=5とID=10のノードが結果として出力される。
【０１３２】
他の差分情報の例の場合も同様に、"/A/B/*[2]"は複雑式であるため、他の検索式の評価方法とは独立に、"/A/B/*[2]"は常に全文検索式評価部106で評価される事になる。
【０１３３】
よってこの場合、検索式が複雑で元文書での処理結果/処理過程情報と差分情報による差分計算が行えない場合にも、そのような検索式のみを全文評価するだけで、他の単純な検索式については可能であれば差分情報を用いた計算が可能となる。
【０１３４】
以上本発明の実施の形態および実施例について説明したが、本発明は以上の例に限定されず、その他各種の付加変更が可能である。また、各実施の形態における構造化文書処理装置101および実施例におけるメッセージフィルタリング装置1101は、ハードウェア的に実現する以外に、コンピュータとプログラムとで実現することができる。プログラムは磁気ディスク等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータ上に前述した各実施の形態における検索式管理部102、元文書管理部103、差分解析部104、差分検索式評価部105、全文検索式評価部106、出力部107、差分計算部901、入力文書保存部902、新文書管理部1001、通信部1102、管理部1103を実現し、また前述した各実施の形態における処理をコンピュータに実行させる。
【産業上の利用可能性】
【０１３５】
本発明によれば、通信メッセージを検索式で指定されたルールによってフィルタリングやモニタリングをする通信装置といった用途に適用できる。
【図面の簡単な説明】
【０１３６】
【図１】本発明の第１の実施の形態の構成を示すブロック図である。
【図２】本発明の第１の実施の形態における検索式テーブルの構成の一例を示す図である。
【図３】本発明の第１の実施の形態における元文書テーブルの構成の一例を示す図である。
【図４】本発明の第１の実施の形態における検索式管理部の動作を示す流れ図である。
【図５】本発明の第１の実施の形態における元文書管理部の動作を示す流れ図である。
【図６Ａ】本発明の第１の実施の形態における差分解析部の動作を示す流れ図である。
【図６Ｂ】本発明の第１の実施の形態における検索式および差分情報の種類の組合せと検索方式との対応関係を示す図である。
【図７】本発明の第１の実施の形態における差分検索式評価部の動作を示す流れ図である。
【図８Ａ】本発明の第１の実施の形態における全文検索式評価部の動作を示す流れ図である。
【図８Ｂ】本発明の第１の実施の形態における検索アルゴリズムの解説図である。
【図９】本発明の第２の実施の形態の構成を示すブロック図である。
【図１０】本発明の第３の実施の形態の構成を示すブロック図である。
【図１１】本発明の実施例の構成を示すブロック図である。
【図１２】本発明の実施例における検索式テーブルの構成の一例を示す図である。
【図１３】本発明の実施例における元文書の解説図である。
【図１４】本発明の実施例におけるＩＤを付与した元文書の解説図である。
【図１５】本発明の実施例における元文書テーブルの構成の一例を示す図である。
【図１６】本発明の実施例における処理過程情報の解説図である。
【図１７】本発明の実施例における処理過程情報の解説図である。
【図１８】本発明の実施例における新文書の解説図である。
【図１９】本発明の実施例における新文書の解説図である。
【図２０】本発明の実施例における新文書の解説図である。
【図２１】本発明の実施例における新文書の解説図である。
【図２２】本発明の実施例における検索式テーブルの構成の一例を示す図である。
【図２３】従来技術の構造化文書処理装置の構成を示すブロック図である。
【符号の説明】
【０１３７】
１０１…構造化文書処理装置
１０２…検索式管理部
１０２ａ…分類部
１０２ｂ…保存部
１０３…元文書管理部
１０３ａ…検索式評価部
１０３ｂ…保存部
１０４…差分解析部
１０４ａ…分類部
１０４ｂ…評価部決定部
１０５…差分検索式評価部
１０６…全文検索式評価部
１０７…出力部
１０８…検索式テーブル
１０９…元文書テーブル
１１１…検索式
１１２…元文書
１１３…差分情報
１１４…構造化文書
１１５…メッセージ
９０１…差文計算部
９０２…入力文書保存部
１００１…新文書管理部
１１０１…メッセージフィルタリング装置
１１０２…通信部
１１０３…管理部
１２０１…検索式テーブル
１３０１、１４０１…元文書
１５０１…元文書テーブル
１６０１、１７０１…元文書
１８０１…新文書１
１９０１…新文書２
２００１…新文書３
２１０１…新文書４
２２０１…検索式テーブル
２３０１…入力部
２３０２…差文計算部
２３０３…差分反映部
２３０４…出力部
２３０５…元文書格納部
２３０６…元文書処理結果格納部
【図１】
2007310617.tif 000003
【図２】
2007310617.tif 000004
【図３】
2007310617.tif 000005
【図４】
2007310617.tif 000006
【図５】
2007310617.tif 000007
【図６Ａ】
2007310617.tif 000008
【図６Ｂ】
2007310617.tif 000009
【図７】
2007310617.tif 000010
【図８Ａ】
2007310617.tif 000011
【図８Ｂ】
2007310617.tif 000012
【図９】
2007310617.tif 000013
【図１０】
2007310617.tif 000014
【図１１】
2007310617.tif 000015
【図１２】
2007310617.tif 000016
【図１３】
2007310617.tif 000017
【図１４】
2007310617.tif 000018
【図１５】
2007310617.tif 000019
【図１６】
2007310617.tif 000020
【図１７】
2007310617.tif 000021
【図１８】
2007310617.tif 000022
【図１９】
2007310617.tif 000023
【図２０】
2007310617.tif 000024
【図２１】
2007310617.tif 000025
【図２２】
2007310617.tif 000026
【図２３】
2007310617.tif 000027