JPH0830620A - 構造検索装置 - Google Patents

Abstract

(57)【要約】 【目的】データの中にタグを挿入して構造を表現し、該
タグが一部で省略可能であるデータから、その構造を高
速に検索する。 【構成】データ保持手段（１１）が、データの中にタグ
を挿入し、該タグにより当該データを部分的に区別して
構造を表現し、該タグが一部で省略可能であるデータを
保持し、型保持手段（１２）は、前記タグにより表現さ
れる構造のひな型が保持する。そのひな型に基づいて、
復元処理手段（１３）が、データ保持手段に保持された
データの中のタグの省略箇所の復元を行う。データ保持
手段に保持しているデータに対し、ユーザにより指定さ
れた構造を検索する際、構造検索手段（１４）は、前記
復元処理手段を制御し、検索対象の構造のタグに関係す
る必要最小限の部分データに対して部分的に構造を復元
する処理を行い、復元された部分データにより検索対象
の構造のタグを検索する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データの中にタグを挿
入し、該タグにより当該データを部分的に区別して構造
を表現し、該タグが一部で省略可能であるデータから、
その構造を高速に検索する構造検索装置に関するもので
ある。例えば、テキスト中にタグを挿入てしテキストを
文書要素に区分して、文書の構造化している構造化文書
から、その構造を検索する文書構造検索装置に利用でき
る。

【０００２】

【従来の技術】従来から、ワークステーション上の文書
編集装置（ワードプロセッサ）など、文書処理を行う文
書編集装置においては、文書の作成を効率よく行うた
め、予じめ、見出し，段落などの複数の文書部品を作成
し、その各々の文書部品の間の関係を定めることによ
り、文書を構造化して編集することが試みられている。

【０００３】このように、文書に対して構造の概念を取
り入れた構造化文書の例としては、例えば、国際規格の
ＯＤＡ（ＩＳＯ８６１３： Open Document Architectur
e）や、ＳＧＭＬ（ＩＳＯ８８７９： Standard General
ized Markup Language）の規格による構造化文書が知ら
れている。ＯＤＡの規格による構造化文書を用いた文書
処理方法の一例は、例えば、特開平５−１３５０５４号
公報に記載されている「文書処理方法」が参照できる。

【０００４】ところで、ＳＧＭＬによる構造化文書は、
従来のテキスト処理システムとの親和性が高く、アメリ
カを中心として普及してきており、既に実用の段階に入
っている。これは、ＳＧＭＬによる構造化文書の手法
が、タグとよばれるマークを文書テキスト中に挿入する
ことで、文書テキストを部分的に区分し（例えば文書部
品として区分し）、その区分の関係を規定して構造化
し、木構造の文書構造を表現する手法であるため、従来
のテキスト処理システムで十分に実現可能であるからで
ある。

【０００５】次に、ＳＧＭＬによる構造化文書を例にと
って、マーク付けされた構造化文書の処理例について説
明する。ＳＧＭＬによる構造化文書では、予じめ文書の
構造のひな型が与えられ、文書の構造は、その与えられ
たひな型の範囲内に制約される。このような文書構造の
ひな型は、ＳＧＭＬにおいては文書型定義（ＤＴＤ：Do
cument Type Definition）と呼ばれる。

【０００６】ＳＧＭＬによる構造化文書では、まず、文
書型定義を規定して、文書の構造を規定する。次に、構
造を表現するために、文書テキスト内にタグと呼ばれる
マークを挿入し、そのタグにより文書テキストを部分的
に区分する。例えば、文書における一つの段落は、名前
が“段落”とされたタグ＜段落＞を用いて、次のように
表現される。 『＜段落＞これは一つの段落です。＜／段落＞』 ここでのタグ＜段落＞が段落の開始を意味し、スタート
タグと呼ばれる。タグ＜／段落＞が段落の終了を意味
し、エンドタグと呼ばれる。つまり、ここでは、タグの
名前が“段落”とされたスタートタグ＜段落＞とエンド
タグ＜／段落＞との２つのタグを用いてマーク付けし、
文書テキストの一部分を文書部品として部分的に区分す
る。つまり、２つのタグの間に挾まれたテキスト部分
が、タグで指示された構造の内容部分を示している。

【０００７】名前が付けられたタグは各々が区別され
て、文書型定義の中で構造上のその位置付けが定義され
る。その意味では、タグが文書の構造を表現している。
したがって、混合が生じない場合において、以下で言う
構造化文書（ＳＧＭＬによる文書）の構造とは、タグと
同義であることを意味しているものとする。

【０００８】また、ＳＧＭＬによる構造化文書（以下、
ＳＧＭＬ文書と略称する）においては、一部のタグの省
略を行うことができる。その場合、省略の可／不可は文
書型定義（ＤＴＤ）により指定する。省略の可／不可の
指定は、スタートタグおよびエンドタグでそれぞれに独
立に指定される。例えば、エンドタグ＜／段落＞を省略
可とする場合は、これが文書型定義内で指定された場合
であり、その場合、先の例は 『＜段落＞これは一つの段落です。』 と記述してもよいことになる。

【０００９】ＳＧＭＬ文書の文書型定義は、例えば、図
１３のように記述される。図１３に示す文書型定義１３
０により制約される文書構造においては、名前が“題”
とされたスタートタグ、“題”のエンドタグ、“段落”
のエンドダク、“図”のエンドタグ、および“図本体”
のエンドタグの各々のタグが、省略可能であることが定
義されている。

【００１０】次に、図１３に示す文書型定義１３０の内
容を具体的に説明する。ここでの文書型定義（ＤＴＤ）
はＳＧＭＬの表記法に従って記述されている。文書型定
義の内容の行の最初の“＜！”はマークアップ宣言区切
り子であり、空白なしに続く次の“ＥＬＥＭＥＮＴ”は
要素宣言キーワードである。つまり、この行の最初の
“＜！ＥＬＥＭＥＮＴ”により、次に続く記述によっ
て、その構造の内容（下部の構造）がどのようになるの
かを指定するための予約語となっている。そして、その
次に記述される項目の名前（文書，章，題，段落，図な
ど）が、対象となるタグの名前を表している。

【００１１】次の記号（“− −”，“− Ｏ”，“Ｏ
Ｏ”など）は、その項目の対象のタグが、スタートタ
グおよびエンドタグの順でそれぞれ省略可能かどうかを
表す記号である。“−”が省略不可を意味し、“Ｏ”が
省略可を意味する。例えば、ここでの記号が“− Ｏ”
であれば、スタートタグは省略不可であり、エンドタグ
は省略可であることを意味している。

【００１２】更に続く次の項目は、タグの下部の構造を
表す定義の規定となっている。ここでの記号“，”は項
目（タグ）が順序立てて出現すること、記号“｜”はど
ちらかの項目であれば良いことを意味し、記号“＊”は
０回以上の繰り返しを意味する。また、記号“？”はそ
れがあってもなくても良いことを意味している。

【００１３】したがって、例えば、タグの下部構造が
“（章題，段落＊，章＊）”と規定されている場合は
『まず、章題があり、その章題の次に段落の０回以上の
繰り返しがあり、更にその次に章の０回以上の繰り返し
がある』という順序で、下部の構造が規定されることを
意味している。具体例で説明すると、図１３に示す文書
型定義１３０の第２行目のように、タグの下部構造が
“（題，（段落｜図）＊，章＊）”と規定されている場
合、『題があり、その次に段落または図の０回以上の繰
り返しがあり、その次に章の０回以上の繰り返しがあ
る』順序で下部の構造が規定されることを意味してい
る。

【００１４】また、第３行目および第４行目に記述され
ているタグの下部構造の“＃ＰＣＤＡＴＡ”はＳＧＭＬ
の予約語の１つであり、構造の規定で、その内容が文字
データであること意味している。したがって、文書型定
義１３０の例では、章を構成する「題」と「段落」のタ
グの下部には文字データが来ることを意味している。

【００１５】つまり、図１３に示す文書型定義（ＤＴ
Ｄ）の意味するところによる文書構造のひな型では、当
該文書が、「章」の繰り返しからなる“＜文書＞”とい
うタグから始まる文書であり、その「章」は、「題」の
次に「段落」または「図」の０回以上の繰り返しがあ
り、更にその次に「章」の０回以上の繰り返しがあるも
のから構成されている。そして、ここでの「題」および
「段落」は文字データから構成される。

【００１６】更に細部の規定として、文書構造の「図」
の内容は、「題」とそれに続く「図本体」から構成され
ると定義され、「図本体」は、例えば外部のイメージフ
ァイルを参照するので、下部構造を持たない（“ＥＭＰ
ＴＹ”）と定義されている。また、ここでの構造のタグ
の省略可／省略不可の指定は、「文書」および「章」は
タグの省略不可であり、「段落」，「図」，および「図
本体」のタグは、エンドタグのみが省略可であり、
「題」は両方のタグが省略可であるということが定義さ
れている。

【００１７】このような文書型定義に従う実際の文書
（以下、対象文書と呼ぶ）の例は、例えば、図１４に示
すようなＳＧＭＬ文書１４０である。なお、この図１４
に示す文書の中では、文書の構造の深さに応じてインデ
ンテーションを変えて表記しているが、この表記は、こ
こでの構造化文書の文書例の説明上、見やすくするため
に行っているだけであり、実際の文書ではインデンテー
ションされないことが多い。

【００１８】図１４を参照して、この例の構造化文書の
ＳＧＭＬ文書１４０を見ると理解されるように、「章」
を構成するその下位の構造の「題」を表すタグは、スタ
ートタグおよびエンドタグは共にこの文書中には現れて
いない。しかし、実体的には、第２行目のタグ“＜章
＞”とその内容部分の“ＳＧＭＬとは”との間のスター
トタグ“＜題＞”は、省略されている形となっている。
なお、このようなタグが省略されているかどうかは、前
述の文書型定義１３０を参照しなければ判別できない。
したがって、対象文書は常にそれに従っている文書型定
義とのセットでないと正確な構造を読み取ることができ
ない。

【００１９】ＳＧＭＬ文書では、このようにタグの省略
が行われるため、ＳＧＭＬ文書を処理する際には、ま
ず、文書構造を解析する処理（ＳＧＭＬパーサによる構
文解析処理）が必要とされる。文書構造の解析の処理で
は、対象文書を解析しながら、文書型定義との照らし合
わせ、対象文書において省略されたタグを復元する処理
が主として行われる。実際の文書処理において実行され
る構文解析処理では、これ以外の処理（属性の復元やエ
ンティティの展開などの処理）も行われるが、ここでは
構造復元の処理のみを注目にしているので、以下の説明
では、構文解析処理は単純に構造復元処理と等価なもの
として説明する。

【００２０】図１４に例示したＳＧＭＬ文書１４０を対
象文書として、タグ（構造）の復元処理を行うと、図１
５に示すようようなＳＧＭＬ文書１５０が得られる。図
１５に示すＳＧＭＬ文書１５０において、下線を引いた
部分は、復元されたタグ（構造）を示している。この対
象文書は、図１３に示すような文書型定義１３０を参照
して、省略されたタグが復元されたものである。すなわ
ち、「章」の構造の規定から、タグ＜章＞の次には必ず
タグ＜題＞が存在しなければならないので、まず、タグ
＜章＞の次にタグ＜題＞を復元し、同様に、タグ＜図＞
の次には必ずタグ＜題＞が存在しなければならないの
で、タグ＜図＞の次にタグ＜題＞を復元する。また、そ
れぞれのエンドタグが省略されているので、内容部分の
次に（対応する次のタグの手前の位置に）、それぞれの
エンドタグ＜／題＞，＜／段落＞などを復元する。この
ようにして下線が引かれたように、各々のタグ（構造）
が復元される。

【００２１】次に、このようにタグが復元され、構造表
現されたＳＧＭＬ文書１５０において、構造を検索する
場合の処理について説明する。構造化文書においては、
文書編集を行う場合、単なるテキストの文字列の検索だ
けでなく、文書構造を利用した構造の検索も文書処理の
重要な処理となる。これは、構造化文書の処理を行う場
合においては、文書構造の構造を利用した編集処理が積
極的に行なわれるためである。

【００２２】構造化文書の検索においては、従来のよう
な文字列の検索（テキスト検索）だけではなく、構造を
積極的に利用した検索が有効に利用される。例えば、文
書内のＳＧＭＬに関連した図を検索したい場合、これま
での検索処理では、文書内を全文検索（文字列検索）を
行い、テキストの文字列からその「関連した図」を捜し
出していた。

【００２３】しかし、文書構造の構造自体を検索に用い
ると、例えば、「図のタイトルにＳＧＭＬを含んでいる
図」や「図の下部構造の題」のように文書構造における
構造を指示して、検索を行うことができ、より対象を絞
った検索を行うことができるようになる。また、その場
合の検索処理も、文書の構造に従って対象範囲を限定し
て検索できるので、検索処理の効率が良くなるという利
点も持つ。

【００２４】前述したように、ＳＧＭＬ文書は、テキス
ト中にマーク付けを行うだけのタグを埋め込んだ形式の
文書アーキテクチャとなっているため、従来のテキスト
処理システムとの親和性が高い。つまり、構造がマーク
付けのタグで表現されるため、構造を検索する際にも特
別な装置あるいは処理プログラムを用いなくても良く、
タグの記号を表す文字列を検索するという文字列検索を
用いて、文書構造の検索を行うことができる。すなわ
ち、従来のテキスト処理装置（文書エディタなど）によ
り、ＳＧＭＬ文書を作成することができ、基本的にはス
タートタグとそれに対応するエンドタグを、タグの文字
列を検索するという従来の文字列検索のテキスト検索手
法を用いて検索することにより、構造検索を行うことが
できる。

【００２５】

【発明が解決しようとする課題】ところで、前述したよ
うに、ＳＧＭＬ文書においては、文書型定義の指定によ
って、タグ（構造）の省略が行われる。従って、場合に
よっては省略可能なタグが検索対象として指定される場
合がある。例えば、前述の図１４に例示したＳＧＭＬ文
書１４０の例で説明すると、利用者が、文書構造から＜
題＞という構造の内容を検索したいと所望して、タグ＜
題＞の指定して検索を行う場合、元のＳＧＭＬ文書で
は、このタグが省略されているため、タグの復元処理を
行ってからでないと、従来のテキスト検索の手法は適用
できない。

【００２６】従って、一般にＳＧＭＬ文書のような表現
形態の構造検索においては、省略された構造（タグ）を
復元するための構造復元処理が不可欠となる。すなわ
ち、検索対象の構造を探索する前には、まず、対象文書
の全体に対して構造復元処理を行って構造（タグ）を復
元し、その後、テキスト検索によって検索対象のタグを
捜し出す処理を行うことになる。

【００２７】構造復元処理は、対象文書の文書型定義を
参照しながら行わなければならないため、複雑な処理を
必要とし、処理時間が長くかかるので、結果として検索
処理に時間がかかる。これは対象文書が長くなるほど、
その構造の復元処理に時間がかかり、検索時間は増大す
る。このため、構造化文書としてＳＧＭＬ文書を扱う上
で、実用上での問題となる。

【００２８】これに対しては、例えば、対象文書（ＳＧ
ＭＬ文書）を保存する際、予じめ省略されたタグを復元
処理した結果を、内部データ構造に変換して保存すると
いう手法が利用できる。この手法を用いると、構造の検
索時の構造復元処理が不要となるので、検索処理速度を
向上させることができる。

【００２９】しかし、上記の手法では、対象文書を内部
データ構造に変換して保持しておく必要があるため、外
部記憶装置などの記憶領域を多く必要とするという欠点
もある。また、頻繁に外部との文書交換を行う場合に
は、結局、その都度、内部データ構造への変換処理（構
造復元処理）が必要になり、結果として、全体的なスル
ープットが向上できないという問題点も生ずる。つま
り、上記の手法は、対象文書を一ヵ所でまとめて管理す
るような大規模な文書データベースには有効ではある
が、単独の文書を処理したり、小規模な構造化文書群を
処理する場合には、概して有効な方法であるとは言えな
い。

【００３０】本発明は、上記のような問題点を解決する
ためになされたものであり、本発明の目的は、データの
中にタグを挿入し、該タグにより当該データを部分的に
区別して構造を表現し、該タグが一部で省略可能である
データから、その構造を高速に検索することができる構
造検索装置を提供することにある。

【００３１】

【課題を解決するための手段】上記のような目的を達成
するため、本発明の第１の特徴とする構造検索装置にお
いては、データの中にタグを挿入し、該タグにより当該
データを部分的に区別して構造を表現し、該タグが一部
で省略可能であるデータを保持するデータ保持手段（１
１）と、前記タグにより表現される構造のひな型を保持
する型保持手段（１２）と、前記構造のひな型に基づい
て、データ保持手段に保持されたデータの中のタグの省
略箇所の復元を行う復元処理手段（１３）と、指定され
た構造を検索する際、前記復元処理手段を制御し、検索
対象の構造のタグに関係する必要最小限の部分データに
対して部分的に構造を復元する処理を行い、復元された
部分データにより検索対象の構造のタグを検索する構造
検索手段（１４）とを備えることを特徴とする。

【００３２】また、本発明の第２の特徴とする構造検索
装置においては、データの中にタグを挿入し、該タグに
より当該データを部分的に区別して構造を表現し、該タ
グが一部で省略可能であるデータを保持するデータ保持
手段（１１１）と、前記タグにより表現される構造のひ
な型を保持する型保持手段（１１２）と、前記構造のひ
な型に基づいて、データ保持手段に保持されたデータの
中のタグの省略箇所の復元を行う復元処理手段（１１
３）と、指定された構造のタグを検索する構造検索手段
（１１４）と、検索対象の構造にかかるタグが省略可能
である場合、ひな型の構造から検索対象の構造より上位
でかつ省略不可の構造のタグを探索する必須構造探索手
段（１１５）と、前記必須構造探索手段により探索され
たタグを用いて、復元処理手段を制御して当該タグに関
係する必要最小限の部分データから部分的に構造復元処
理を行い、構造検索手段を制御して検索対象の構造を検
索する制御手段（１１６）とを備えることを特徴とす
る。

【００３３】また、本発明の第３の特徴とする構造検索
装置においては、データの中にタグを挿入し、該タグに
より当該データを部分的に区別して構造を表現し、該タ
グが一部で省略可能であるデータを保持するデータ保持
手段（１２１）と、前記タグにより表現される構造のひ
な型を保持する型保持手段（１２２）と、前記構造のひ
な型に基づいて、データ保持手段に保持されたデータの
中のタグの省略箇所の復元を行う復元処理手段（１２
３）と、データ保持手段に保持されたデータから指定さ
れた構造のタグを検索する構造検索手段（１２４）と、
検索対象の構造にかかるタグが省略可能である場合、ひ
な型の構造から検索対象の構造より上位でかつ省略不可
の構造のタグを探索する必須構造探索手段（１２５）
と、前記必須構造探索手段により探索されたタグを用い
て、復元処理手段を制御して当該タグに関係する必要最
小限の部分データに構造復元処理を行い、データ保持手
段の対応データを復元データに取り換える制御手段（１
２６）とを備えることを特徴とする。

【００３４】

【作用】本発明の第１の特徴とする構造検索装置におい
ては、データ保持手段（１１）が、データの中にタグを
挿入し、該タグにより当該データを部分的に区別して構
造を表現し、該タグが一部で省略可能であるデータを保
持している。また、型保持手段（１２）は、前記タグに
より表現される構造のひな型を保持している。復元処理
手段（１３）は、この構造のひな型に基づいて、データ
保持手段に保持されたデータの中のタグの省略箇所の復
元を行う。

【００３５】データ保持手段に保持しているデータに対
して、そこから、例えば、ユーザにより指定された構造
を検索する際、構造検索手段（１４）は、前記復元処理
手段を制御し、検索対象の構造のタグに関係する必要最
小限の部分データに対して部分的に構造を復元する処理
を行い、復元された部分データにより検索対象の構造の
タグを検索する。

【００３６】これにより、ここでの構造検索手段（１
４）では、検索対象の構造のタグに関係する必要最小限
の部分データに対してのみ、部分的に構造を復元する処
理を行って、検索対象のタグを検索するので、実質的な
検索時間が短かくて済む。このため、構造の検索が高速
に行える。

【００３７】また、本発明の第２の特徴とする構造検索
装置においては、同じく、データ保持手段（１１１）
が、データの中にタグを挿入し、該タグにより当該デー
タを部分的に区別して構造を表現し、該タグが一部で省
略可能であるデータを保持しており、型保持手段（１１
２）は、前記タグにより表現される構造のひな型を保持
している。復元処理手段（１１３）は、前記構造のひな
型に基づいて、データ保持手段に保持されたデータの中
のタグの省略箇所の復元を行う。

【００３８】データ保持手段に保持しているデータか
ら、例えば、ユーザにより指定された構造を検索する
際、構造検索手段（１１４）が、指定された構造のタグ
を検索するが、その際、必須構造探索手段（１１５）
が、検索対象の構造にかかるタグが省略可能である場
合、ひな型の構造から検索対象の構造より上位でかつ省
略不可の構造のタグを探索する。そして、制御手段（１
１６）が、前記必須構造探索手段により探索されたタグ
を用いて、復元処理手段を制御して当該タグに関係する
必要最小限の部分データから部分的に構造復元処理を施
し、構造検索手段を制御して検索対象の構造を検索する
制御を行う。

【００３９】これにより、ここでの制御手段（１１６）
が、必須構造探索手段（１１５）を用いて、ここから探
索されたタグを用いて、復元処理手段（１１３）を制御
し、当該タグに関係する必要最小限の部分データから部
分的に構造復元処理を施すだけで、検索対象のタグを検
索できるので、実質的な検索時間が短かくて済む。この
ため、構造の検索が高速に行える。

【００４０】また、本発明の第３の特徴とする構造検索
装置においては、同様に、データ保持手段（１２１）
が、データの中にタグを挿入し、該タグにより当該デー
タを部分的に区別して構造を表現し、該タグが一部で省
略可能であるデータを保持しており、型保持手段（１２
２）が、前記タグにより表現される構造のひな型を保持
している。復元処理手段（１２３）は、この構造のひな
型に基づいて、データ保持手段に保持されたデータの中
のタグの省略箇所の復元を行う。

【００４１】構造検索手段（１２４）は、データ保持手
段（１２１）に保持されたデータから指定された構造の
タグを検索するが、その場合、必須構造探索手段（１２
５）は、検索対象の構造にかかるタグが省略可能である
場合、ひな型の構造から検索対象の構造より上位でかつ
省略不可の構造のタグを探索する。そして、制御手段
（１２６）が、前記必須構造探索手段により探索された
タグを用いて、復元処理手段（１２３）を制御して当該
タグに関係する必要最小限の部分データに構造復元処理
を施し、データ保持手段の対応データを復元データに取
り換える。

【００４２】これにより、データ保持手段（１２１）に
は、検索対象のタグが部分的に復元されたデータが、次
々に取り換えられて保持されるので、その後、構造検索
手段（１２４）が、データ保持手段（１２１）に保持さ
れたデータから指定された構造のタグを検索する。この
場合においても、制御手段（１２６）は、必須構造探索
手段（１２５）を用いて、ここから探索されたタグによ
り、更に復元処理手段（１２３）を制御して、当該タグ
に関係する必要最小限の部分データから部分的に構造復
元処理を施すだけで、検索対象のタグを検索できるの
で、実質的な検索時間が短かくて済む。このため、構造
の検索が高速に行える。また、構造の検索が行なわれる
毎に、データ保持手段（１２１）には、検索対象のタグ
が部分的に復元されたデータが順次に取り換えられて保
持されるので、後に行なわれる構造の検索では、構造復
元処理を行なわなくても良い場合もあり、結果的に、実
質的な検索時間が短かくて済むという利点も併せ持つ。

【００４３】このように、本発明の構造検索装置によれ
ば、データの中にタグを挿入し、該タグにより当該デー
タを部分的に区別して構造を表現し、該タグが一部で省
略可能であるデータから、その構造を高速に検索する構
造検索装置が提供される。また、ここでのデータを文書
テキストすることにより、テキスト中にタグを挿入し
て、テキストを文書要素に区分し、文書の構造化してい
る構造化文書から、その構造を高速に検索する構造検索
装置が提供される。

【００４４】

【実施例】以下、本発明の実施例を図面を参照して説明
する。図１は、本発明の第１の実施例にかかる構造検索
装置の構成を示すブロック図である。図１において、１
１は文書データ保持部、１２は型保持部、１３は構造復
元部、１４は構造検索部、１５は必須構造探索部であ
る。１６は構造の検索指示、１７は検索結果を表してい
る。

【００４５】文書データ保持部１１には、文書のテキス
トデータの中にタグを挿入し、該タグにより当該文書テ
キストを部分的に区別して（文書部品として）、構造化
文書とした文書データが保持されている。この文書デー
タは、例えば、先に説明したＳＧＭＬ文書１４０（図１
４）と同様なものであり、タグにより文書の構造が表現
され、そのタグは一部で省略可能であるような文書アー
キクチャの文書データである。その構造化文書の文書デ
ータに対応して、型保持部１２には、タグにより表現さ
れる構造のひな型として、例えば、図１３に示したよう
な文書型定義１３０が保持されている。また、構造復元
部１３は、この型保持部１２に保持されている構造のひ
な型（文書型定義）に基づいて、文書データ保持部１１
に保持された文書データの中のタグの省略箇所の復元を
行う。

【００４６】構造検索部１４は、ユーザあるいは他の装
置から構造の検索指示１６を受けると、文書データ保持
部１１に保持している文書データに対して、その構造の
検索処理を行う。その際、構造検索部１４は、構造復元
部１３を制御して、検索対象の構造のタグに関係する必
要最小限の部分データに対して、部分的に構造を復元す
る処理を行い、復元された部分構造により検索対象の構
造のタグを検索する。

【００４７】ここでの構造検索部１４は、必須構造探索
部１５を処理機能の一部分として含んでおり、必須構造
探索部１５が、検索対象の構造のタグに関係する必要最
小限の部分を探索する。その後、探索された必要最小限
の部分の文書データに対して、構造復元部１３により、
部分的に構造を復元し、その後、復元された部分構造に
よって、文書中の対象となる構造（タグ）を捜し出すと
いう処理を行う。ここでの型保持部１２が保持している
構造のひな型（文書型定義）は、構造復元部１３により
構造復元処理の際に参照され、また、必須構造探索部１
５が、検索対象の構造のタグに関係する必要最小限の部
分を探索する際にも参照される。

【００４８】このようにして、構造検索部１４では、検
索対象の構造のタグに関係する必要最小限の部分データ
に対してのみ、部分的に構造を復元する処理を行い、検
索対象のタグ（構造）を検索し、検索結果１７を出力す
る。このため、ここでの構造化文書の文書データからの
構造の検索は、実質的な検索時間が短かくて済み、構造
の検索が高速に行える。

【００４９】図２は、構造の検索指示を行う場合の操作
画面の一例を示す図である。ユーザあるいは他の装置な
どからの構造の検索要求は、文書エディタにおいて、図
２に示すように、構造検索プロパティのサブウィンドウ
２０を開き、そこで、構造を検索する場合の制約条件を
指定することにより検索指示がなされる。構造検索の制
約条件は、対象構造の指定フィールド２１により、対象
構造を指定し、内容制約の指定フィールド２２により、
内容的な制約を指定し、更に、構造制約の指定フィール
ド２３により、構造を制約する規定の条件を指定する。
これらの３つのフィールドで指定された構造を検索する
上での制約条件は、必ずしも全てが指定されなくても良
く、一部の制約条件だけの指定により、構造検索が実行
されても良い。ただ、その場合には、所望する構造が十
分に絞り切れず、条件を満たす構造が多く検索される可
能性がある。

【００５０】このような制約条件の構造の検索指示１６
が与えられることにより、構造検索部１４は、構造の検
索処理を開始する。次に、ここでの構造検索部１４の処
理内容について、更に詳細に説明する。構造検索部１４
における基本的な構造検索の処理では、ユーザあるいは
他の装置から検索対象である構造（タグ）を受け付け
て、必須構造探索部１５および構造復元部１３を呼び出
して処理依頼を行い、復元された文書の部分構造から、
検索対象である構造（タグ）を捜し出し、ユーザあるい
は装置へ、検索結果を返すという処理を行う。

【００５１】なお、ここでの構造検索部１４に渡される
ユーザからの指示あるいは他の装置からの構造の検索指
示１６の形態は、例えば、ワードプロセッサや文書エデ
ィタなどの文書を直接にユーザが編集する装置など、そ
の装置の形態に合せて、構造検索プロパティシート（図
２）やコマンドによる形態で、その検索指示が与えられ
る。また、ネットワークに接続された装置であるような
場合、例えば、検索サーバのような装置の場合は、その
構造の検索指示は他の装置からネットワークを介して、
あらかじめ定められたプロトコルで与えられることにな
る。いずれにしろ、その構造の検索指示では、与えられ
る情報の内容（構造の制約条件）には差はない。

【００５２】また、ここでの検索結果を出力する提示方
法も同様である。ワードプロセッサや文書エディタなど
の文書を直接にユーザが編集する装置など、その装置の
形態に合せて、検索結果が出力される。例えば、文書エ
ディタなどでは、検索して見つかった箇所を自動的に表
示するという提示方法を用いる。ネットワークに接続さ
れた検索サーバでは、例えば、見つかった部分構造をす
べて、検索を指示した側に送り返すように構成される。

【００５３】図３は、構造検索部１４における構造検索
処理を説明するフローチャートである。次に図３のフロ
ーチャートを参照して、ここでの構造検索処理を説明す
る。外部から構造の検索指示（図２）が与えられ、処理
を開始すると、まず、ステップ３１において、その構造
検索指示の受け付けを行う。次に、ステップ３２におい
て、与えられた検索指示情報のうち対象構造および構造
制約により必須構造を探索する。この処理は、後述する
ように、必須構造探索部１５に対象構造および構造制約
の情報を渡して、そこからの必須構造を得るようにして
も良い。次に、ステップ３３において、探索された必須
構造を構造復元部１３に渡して、検索対象構造を含む復
元部分構造を得る。

【００５４】次に、ステップ３４において、得られた復
元部分構造が“ＮＵＬＬ”であるか否かを判定する。復
元部分構造が“ＮＵＬＬ”であれば、指定の構造にかか
る部分が復元されず、復元を行った構造の中にも検索指
定された構造が存在しないことなので、ステップ３８に
進み、構造検索指示の依頼元に“ＮＵＬＬ”を返して処
理を終了する。また、ステップ３４の判定において、得
られた復元部分構造が“ＮＵＬＬ”でなければ、その復
元部分構造の中で、ユーザにより検索指定された構造を
検索する。そのため、ステップ３５に進み、復元部分構
造から対象構造を検索し、当該構造が検索指定によって
指定された制約（検索条件）を満たしているかを調ベ
る。

【００５５】すなわち、ステップ３５の処理では、復元
部分構造から対象構造を探しだし、その結果が制約（検
索条件）を満足しているかどうかを調べる。ここでの制
約が内容制約の場合は、構造が含まれているテキスト内
容をテキスト検索によって調べる。制約が構造制約の場
合には、型保持部に保持されている当該部分構造にかか
る文書型定義を参照して、対象構造の構造定義を捜し出
し、その構造が条件を満たすかどうかを判定する。例え
ば、当該構造制約が下部にあるいは上位に存在するなど
の構造制約の場合には、探しだした構造が内包されるか
どうかで判定できる。

【００５６】この結果を、次のステップ３６で判定し、
ステップ３６において、検索され構造は制約を満してい
ると判定される場合は、ステップ３７において、検索結
果を依頼元に返して処理を終了する。また、ステップ３
６の判定において、検索された構造が制約を満していな
いと判定される場合は、ステップ３９において、構造の
検索指示の依頼元に“ＮＵＬＬ”を返して処理を終了す
る。

【００５７】なお、ここでの説明では、部分的に復元し
た復元部分を有する文書内に検索対象の構造が含まれて
いるかどうかを一回だけ判定する処理手法について説明
しているが、実際には対象構造が複数含まれている可能
性がある。そのような場合に対しても、ここでの構造検
索処理を対応させるため、例えば、ステップ３４におい
て、復元部分構造が“ＮＵＬＬ”である場合に、文書型
定義を参照して復元する部分構造の階層を更に上位の階
層の構造までに範囲を拡大して、構造の復元を行い、更
に、対象構造を捜しだすような処理方法に変更すればよ
い。

【００５８】この構造検索処理のステップ３４における
対象構造の検索処理では、ユーザが最初に指定した対象
構造を、文書全体の構造が復元された文書でなく、部分
的に復元された構造を有する文書から、その対象構造を
探しだす処理が行われる。次に、このような部分復元さ
れた構造から対象構造のテキスト本体部分を検索する処
理を説明する。

【００５９】図４は、部分復元された構造から対象構造
を検索する処理を説明するフローチャートである。この
部分復元された構造から対象構造を検索する処理では、
ここでの構造が文書テキスト中に挿入されたマーク付け
するためのタグ（例えば＜題＞など）により表現されて
いるので、基本的には、通常のテキスト検索処理と同様
な処理により、タグ（構造）を探し出す処理が行なわれ
る。

【００６０】図４を参照して、部分復元された構造の文
書から対象構造を検索する処理を説明する。この処理を
開始すると、まず、ステップ４０において、変数Ａおよ
びカウンタｉを初期化（値を“０”にリセット）する。
ここでの変数Ａは文書テキスト中の対象構造のスタート
タグの位置を格納しておくための変数であり、カウンタ
ｉは、検索対象が入れ子になっている場合の他の構造
（タグ）に対する処理の制御を行うための変数である。
次に、ステップ４１において、部分構造から対象構造の
スタートタグを探し出し、その位置を変数Ａに代入す
る。対象構造が見つからなかったら、対象構造は文書内
に存在しなかったものとするので、次のステップ４２に
おいて、変数Ａは初期値のままであるか否かを判定す
る。

【００６１】ステップ４２の判定において、変数Ａが初
期値のままと判定された場合、ステップ４３に進み、依
頼元に“ＮＵＬＬ”を返して、ここでの処理を終了す
る。また、ステップ４２の判定において、変数Ａが初期
化のままでない場合、この場合には、部分的に復元され
た文書において対象構造のスタートタグが見つかったこ
となので、次には、対象構造の対応するエンドタグを探
し出し、対象構造のテキスト本体部分を探し出すことに
なる。

【００６２】このため、次に、ステップ４４において、
現在位置（変数Ａの位置）から文書を後方に対象構造
（タグ）を探し出し、対象構造が見つかれば、その位置
Ｂを次の現在位置とする。そして、次のステップ４５に
おいて、探し出された対象構造はスタートタグであるか
否かを判定する。この判定で、見つけられた対象構造が
スタートタグである場合、ここで検索する対象構造が複
数存在し、それらの対象構造と入れ子状態となっている
状態であるので、検索する対象構造のエンドタグの正し
い位置を判定するため、ステップ４６に進み、カウンタ
ｉを＋１して、ステップ４４に戻り、再びステップ４４
からの処理を行う。これにより、入れ子状態となってい
る複数存在する対象構造のスタートタグの個数が、カウ
ンタｉにカウントアップされる。

【００６３】一方、ステップ４５において、探し出され
た対象構造はスタートタグでない場合、見つかった対象
構造はエントタグであるので、ここで探し出された対象
構造のエンドタグが、先に見つけられ、カウントｉによ
りカウントされている入れ子状態の複数の対象構造のス
タートタグに対応しているか否かを判定する。このた
め、次のステップ４７において、カウンタｉが“０”で
あるか否か判定する。この判定でカウンタｉが“０”で
ない場合、前に見つけられた対象構造の入れ子状態のス
タートタグに対応している対象構造のエンドタグである
ので、この場合には、次のステップ４８において、カウ
ンタｉを−１する。そして、ステップ４４に戻り、再び
ステップ４４からの処理を行う。これにより、先の処理
によりカウンタｉがカウントアップされてチェックさ
れ、入れ子状態となっている複数の対象構造のスタート
タグに対応して、そのエンドタグの個数がカウンタｉか
らカウントダウンされる。

【００６４】したがって、このステップ４７の判定にお
いて、カウンタｉの値の“０”が判定できると、正しい
対象構造のスタートタグに対応する正しいエンドタグで
あることが判定される。このため、ステップ４７におい
て、カウンタｉの値が“０”であると判定されると、そ
の場合は、探し出された対象構造のエンドタグが、正し
い対象構造のスタートタグに対応する正しいエンドタグ
であるので、ステップ４９に進み、変数Ａの位置から現
在位置の位置Ｂまでを対象範囲とする結果を依頼元に返
して、ここでの処理を終了する。

【００６５】つまり、ここでの対象構造の検索処理で
は、対象構造のスタートタグの開始位置（Ａの位置）を
探し出してから、更に、文書を後方へ探索し、対象構造
のエンドタグの終了位置（Ｂの位置）を探し出す。探し
ている時に、そのまま次に対象構造のエンドタグ（終了
位置）が見つかれば、それで良いので、直ちに対象範囲
が得られる。しかし、その間に別に対象構造のスタート
タグの見つかると、対象構造が複数存在し、それが入れ
子状態となっているので、この入れ子状態を解消して、
正してく対応するエンドタグを見つける処理（カウンタ
ｉによる処理）を行う。なお、ここでの構造を表現する
タグの表現形式は、スタートタグの＜ＸＸＸ＞に対応し
て、そのエンドタグは、必ず、＜／ＸＸＸ＞のように表
現されるので、テキスト検索処理と同様な検索処理によ
り、それぞれのタグの探索の処理が行われる。

【００６６】次に、必須構造探索部における処理につい
て説明する。必須構造探索部は構造検索部から渡された
検索指示の情報を基に、文書の復元処理を施す必要最小
限の範囲を特定し、その範囲を（構造検索部を介して）
構造復元部に渡すという処理を行う。つまり、必須構造
探索部は文書の復元処理を最小化する場合に必要な処理
の範囲を判定するため利用される。

【００６７】図５は、必須構造探索部の処理フローを示
すフローチャートである。次に、図５を参照して、必須
構造探索部における処理を説明する。ここでの必須構造
探索部の処理では、処理を開始すると、まず、ステップ
５１において、対象構造および構造制約を含む検索指示
を受付ける。次に、ステップ５２において、文書型定義
を参照し、対象構造の内の木構造の階層の最も上位の構
造を特定する。次に、ステップ５３において、特定され
た構造は省略不可であるか否かを判定する。特定された
構造が省略不可でなく、つまり、構造が省略可である場
合、その場合には、次のステップ５４において、文書型
定義を参照し、更に上位の構造を特定する。そして、再
び、ステップ５３に戻り、ステップ５３からの処理を繰
り返し行う。これにより、必ず特定された構造が省略不
可となっている直近の上位の構造が特定される。

【００６８】ステップ５３の判定により、特定された構
造が省略不可となっていることが判定されると、次に、
ステップ５５において、特定された構造について、文書
内の開始位置であるスタートタグを探す。そして、次の
ステップ５６において、スタートタグの開始位置が見つ
かったか否かを判定する。この結果、開始位置が見つか
った場合は、次のステップ５７において、見つかった開
始位置を構造復元部に渡して処理を終了する。また、ス
テップ５６の判定において、開始位置が見つからなかっ
た場合には、ステップ５８に進み、依頼元に“ＮＵＬ
Ｌ”を返して、ここの処理を終了する。

【００６９】次に、この必須構造探索部における処理
を、具体的な文書テキストの構造化された文書要素を例
示して説明する。例えば、与えられた検索指示の対象構
造をＡとし、その検索対象の構造制約には構造Ｂおよび
構造Ｃという構造制約を含むとする。この場合、構造の
検索指示として、ここで与える構造制約の検索式には、
例えば、「構造Ａの下部に構造Ｂと構造Ｃを含む」こと
を意味する制約の条件として、 “Ａ ｉｎｃｌｕｄｅｓ （Ｂ＆Ｃ）” の条件式を与えるか、または、構造制約の検索式にま
「構造Ａの下部には構造Ｂまたは構造Ｃを含まない」こ
とを意味する制約の条件として、 “Ａ ｅｘｃｌｕｄｅｓ （Ｂ｜Ｃ）” の条件式を与えて、構造の検索を指示する。なお、検索
指示で同時に与えられる内容制約に関しては、テキスト
検索の中で判定されるので、必須構造探索部では処理さ
れない。

【００７０】このような構造の検索指示が与えられる
と、検索指示内に指定された構造（タグ）の内、最も木
構造上で上位に位置する可能性のあるものを、型保持部
に保持されている文書型定義を参照して特定する。例え
ば、前述の例においては、構造Ａ，構造Ｂ，および構造
Ｃという３種類の構造（タグ）の関係が検索指示の検索
式により指示されており、これらの構造にかかる文書型
定義として、型保持部における文書型定義が、 ＜！ＥＬＥＭＥＮＴ ｄｏｃ − Ｏ （Ａ，Ｄ？）＞ ＜！ＥＬＥＭＥＮＴ Ａ − Ｏ （Ｂ＊，Ｃ）＞ のように記述されていると、この場合は「文書“ｄｏ
ｃ”は、構造Ａと、次にあってもなくても良い後続する
構造Ｄから構成され、また、構造Ａは、構造Ｂの０回以
上の繰り返しと、これに続く構造Ｃから構成される」こ
とが定義されているので、構造Ａが最も上位に位置する
可能性があると判断される。

【００７１】つまり、ここでの文書“ｄｏｃ”は文書の
根（ｒｏｏｔ）であるとし、木構造の文書構造を根から
探索して、根に最も近い位置にあるノードの構造を最も
上位に位置すると判定する。また、型保持部に保持され
ている文書型定義が、次のように記述されている場合に
は、最も上位に位置する構造が一つに特定できないの
で、その場合は、可能性のあるものすべてを対象とす
る。 ＜！ＥＬＥＭＥＮＴ ｄｏｃ − Ｏ （Ａ，Ｂ？，Ｄ
？）＞ ＜！ＥＬＥＭＥＮＴ Ａ − Ｏ （Ｂ＊， Ｃ）
＞ ＜！ＥＬＥＭＥＮＴ Ｂ − Ｏ （Ａ｜Ｄ）＞ この例の場合、構造Ａあるいは構造Ｂが、共に最も上位
に位置する可能性があると判断する。すなわち、文書型
定義による文書構造の木構造から、この場合は、文書の
根（ｒｏｏｔ）に対して構造Ａと構造Ｂは共に葉（子）
であり、探さは共に同じであるため、構造Ａあるいは構
造Ｂが、共に最も上位に位置する可能性があると判断す
る。

【００７２】次に、特定された最も上位に位置する可能
性のある構造のタグ（以下上位構造と呼ぶ）に関する文
書型定義を参照し、その文書型定義において、構造の開
始位置のマーク（スタートタグ）が省略される可能性が
ある場合（具体的には文書型定義の“Ｏ Ｏ”など）を
判定する。その判定の結果、省略不可である場合はなに
もしないが、省略可であり、省略される可能性のある場
合には、更に上位の省略不可である構造（タグ）からで
ないと、部分構造を確実に特定できないので、その構造
（タグ）から更に上位の構造を辿って、省略不可と定義
されている直近の上位の構造（タグ）を捜し出す。

【００７３】前述した２つの文書型定義の例では、構造
Ａおよび構造Ｂともに、スタートタグは必須であるとさ
れているので何もしない。また、文書型定義が次のよう
に記述されている場合、つまり、 ＜！ＥＬＥＭＥＮＴ ｄｏｃ − Ｏ （Ｘ，Ｙ，Ｚ
？） ＞ ＜！ＥＬＥＭＥＮＴ Ｘ − Ｏ （Ａ，Ｅ＊）
＞ ＜！ＥＬＥＭＥＮＴ Ｙ − Ｏ （Ｂ？，Ｅ＊）
＞ ＜！ＥＬＥＭＥＮＴ Ｚ − Ｏ （Ａ，Ｆ＊）
＞ ＜！ＥＬＥＭＥＮＴ Ａ Ｏ Ｏ ＃ＰＣＤＡＴＡ
＞ ＜！ＥＬＥＭＥＮＴ Ｂ − Ｏ ＃ＰＣＤＡＴＡ
＞ のような場合には、構造Ａのスタートタグは省略可であ
るので、その上位の構造を辿り、構造Ｘおよび構造Ｚを
探し出す。探し出された構造Ｘおよび構造Ｚのスタート
タグは省略不可であり、必須であるとされているで、こ
れらを新たな上位の構造（タグ）とする。また、構造Ｂ
のスタートタグは省略不可であり、必須なので、そのま
まそれを上位の構造（タグ）とする。

【００７４】このようにして上位の構造（タグ）とされ
た各々の構造について、通常のテキスト検索処理によっ
て、文書のテキスト内から当該上位の構造（タグ）の開
始位置のスタートタグを探し出し、探し出された開始位
置を変数Ａに代入する。見つからなければ“ＮＵＬＬ”
を返して処理を終了する。この変数Ａの開始位置が、部
分的に文書構造を復元を行うための処理の開始位置を与
えるものとして、必須構造探索部１５から構造復元部１
３に渡される。これは構造検索部１４の制御のもとに行
なわれる。

【００７５】次に、構造復元部１３の処理について説明
する。図６は、構造復元部の処理フローを示すフローチ
ャートである。ここでの構造復元部１３による構造復元
の処理は、構造検索部１４に制御によって、必須構造探
索部１５により渡された開始位置（スタートタグ）から
処理を開始し、順次に、文書データ保持部１１に保持さ
れている文書データを読み取りながら、部分的に文書構
造を復元する処理が行われる。つまり、型保持部１２に
保持されている文書型定義を参照し、文書の途中から
（指定の開始位置から）省略されている構造（タグ）を
復元する処理を行う。そして、文書の残り全部の構造の
復元を行うことなく、開始位置から最初に存在するスタ
ートタグに対応するエンドタグを処理したところで、処
理を終了する。復元された文書データはそのまま構造検
索部へ渡される。

【００７６】図６を参照して説明する。処理を開始する
と、まず、ステップ６１において、指定された開始位置
まで文書データを読み飛ばし、次のステップ６２におい
て、その位置から次の文書データを読み取る。次に、処
理する文書が正しい処理対象の文書であるか否かを判定
するため、ステップ６３において、最初に処理したスタ
ートタグが、その文書の文書型定義に定義されているタ
グであるか否かを判定する。このステップ６３の判定
で、そのスタートダグが文書型定義に定義されている
（型保持部に保持されている）タグでなければ、ステッ
プ６４に進み、復元エラーの処理を行う。

【００７７】一方、ステップ６３の判定で、スタートダ
グが文書型定義に定義されているタグであることが判定
できると、それに対応するエンドタグまでの文書テキス
トの構造を部分的に復元する処理を行う。このため、次
に、ステップ６５に進み、次の文書データを読み取り、
次のステップ６６において、省略されたタグの復元処理
を行う。そして、次のステップ６７において、最初に処
理したスタートタグの対応のエンドタグを処理したか否
かを判定する。対応のエンドタグの位置までの復元処理
を終了しておらず、このステップ６７の判定で、最初に
処理したスタートタグの対応のエンドタグまでの処理を
終了していることが判定できなければ、ステップ６５に
戻り、ステップ６５からの処理を繰り返し行う。また、
その対応のエンドタグまでの処理を終了していることが
判定できれば、ここでの部分的な構造復元の処理を終了
する。

【００７８】次に、このような部分的に行う構造の復元
処理を具体例で説明する。例えば、文書データ保持部１
１には、図１４に示すようなＳＧＭＬ文書１４０が保持
されており、構造復元部１３に対して、部分的に復元処
理を行う開始位置として、ＳＧＭＬ文書１４０の７行目
の“タグ＜章＞”の位置が与えられたとする。これによ
り、構造復元部１３は、与えられたその開始位置から復
元処理を開始する。構造の復元処理では、図１３に示す
ような文書型定義１３０を参照しながら、処理が進めら
れる。この場合の最初に処理する開始位置の７行目のス
タートタグ“＜章＞”に対応するエンドタグは１１行目
のエンドタグ“＜／章＞”であるので、ここまで処理さ
れたところで、構造復元部の構造復元処理は終了する。

【００７９】また、最初に処理した開始位置のスタート
タグに対応するエンドタグが、省略されている場合であ
っても、その部分的な構造の復元処理により、該当する
対応のエンドタグが復元されるので、復元された省略エ
ンドタグを判定して、部分的な構造の復元処理の終了位
置を判定する。

【００８０】図７は、対応のエンドタグが省略されてい
る場合の構造化文書の構造が部分的に復元される様子を
具体的に説明する図である。図７を参照すると、構造復
元部１３に対して、処理前の文書７０における復元処理
の開始位置として、エンドタグが省略されているスター
トタグ“＜図＞”の位置が与えられたとする。これによ
り、構造復元部１３は、与えられたその位置から文書７
０に対して、構造の復元処理を開始する。この場合に
も、図１３に示すような文書型定義１３０を参照しなが
ら、復元処理が進められる。復元前の文書７０では、最
初に処理する開始位置のスタートタグ“＜図＞”に対応
するエンドタグ“＜／図＞”は見つからない。構造の復
元処理は、文書型定義１３０を参照して、まず、スター
トタグ“＜図＞”の直後に省略されているスタートタグ
“＜題＞”を復元し、次にそれぞれのスタートタグに対
応するエンドタグ“＜／題＞”，“＜／図本体＞”，
“＜／図＞”を順次に復元する。これにより、復元後の
文書７１において、最初に処理を開始した位置のスター
トタグ“＜図＞”に対応するエンドタグ“＜／図＞”が
復元されたところで、ここでの構造復元部の構造復元処
理を終了する。

【００８１】次に、このように構成される本実施例の構
造検索装置における各々の処理要素について、その変形
例について説明する。図８は型保持部に保持される文書
型定義の他の形態を示す図である。前述したように、構
造を復元する際に参照される文書型定義１３０（図１
３）は、型保持部１２に保持されるが、この文書型を定
義する情報の文書型定義の形式は、図１３に示すような
ＳＧＭＬの規定に従ったフォーマットでなくても良く、
例えば、図８に示すようなテーブル形式の文書型定義８
０であっても良い。型保持部１２に保持する場合、この
ようなテーブル形式の形態であると、タグ（構造）を規
定する各々の項目に対して、その内容情報のアクセスが
速く行なえる利点がある。ここでは比較のため、図８に
示すテーブル形式の文書型定義８０の内容は、図１３に
示した文書型定義１３０と同じ内容を示している。

【００８２】また、図９および図１０は、構造の検索指
示の他の一例を説明する図である。前述したように、ユ
ーザや他の装置から与えられる構造の検索指示は、検索
したい対象構造を示すタグ、また、必要に応じて、更に
その構造や内容に関する制約の記述により与えられる。
この場合、更に検索対象となる文書や検索対象の文書が
従っている文書型定義の項目の要素そのもの、あるいは
識別子（群）により与えるようにしても良い。このよう
な構造の検索指示は、検索対象の構造（タグ）とその制
約において、内容あるいは構造に関する制約が、検索対
象となる構造を更に特定するために与えられる。例え
ば、『“ＳＧＭＬ”という文字列を含んでいる“＜題
＞”という構造（タグ）』というようにも指定できる。

【００８３】構造の検索指示は、図２に示したように、
構造検索プロパティのサブウィンドウ２０により、対象
構造の指定（２１）と、構造に関する制約の指定（２
３）とにより、その構造の検索指示が与えられるが、ま
た、例えば、図９に示す構造検索プロパティのサブウィ
ンドウ９０のように、検索対象である対象構造のみを指
定（８１）して検索を指示することができる。また、図
１０に示す構造検索プロパティのサブウィンドウ１００
のように、対象構造を指定（１０１）し、更に内容に関
する制約の指定（１０２）して、ここでの構造の検索指
示とするようにもできる。

【００８４】図２，図９および図１０に示すように、構
造の検索指示の各々の制約の指定フィールド２１〜２
３，９１〜９３，１０１〜１０３において、その制約の
条件の中に記述される“ｅｘｃｌｕｄｅｓ”や“ｉｎｃ
ｌｕｄｅｓ”は、テキストの文字列や構造の制約条件の
関係付けを記述するための予約語であり、これらはそれ
ぞれ「〜を含まない」および「〜を含む」関係付けを意
味している。また、他にも、この種の制約条件の関係を
記述するための予約語としては、「“＝”（完全に一致
する），“＆”（ＡＮＤ関係），“｜”（ＯＲ関係），
“ｓｅｑｕｅｎｃｅ”（〜の並びならなる），ｒｅｐｅ
ａｔ（〜の繰り返しからなる）などの予約語がある。制
約の記述方法については、例えば、特開平５−１３５０
５４公報に記載されている方法など既に幾つかの方法が
知られており、それらを用いれば良いので、ここでの説
明は省略する。

【００８５】また、構造復元部または構造検索部におけ
る構造化文書の構造解析では、公知のコンピュータのプ
ログラミング言語を翻訳するためのコンパイラや自然言
語処理などで用いられる構文解析処理の手法を用いるこ
とができる。実際、ＳＧＭＬ文書の処理に関しては、Ｂ
ｅｌｇｉｕｍのＳｅｍａＧｒｏｕｐによって開発された
Ｍａｒｋ−Ｉｔや、ＳＧＭＬ Ｕｓｅｒｓ Ｇｒｏｕｐ
によって作成され、フリーウェアで配布されているｓｇ
ｍｌｓという処理系が利用できる。これらのソフトウェ
アを利用することにより、ＳＧＭＬ文書の構文解析を行
い、タグの復元処理を行う構造復元部を一部の変更だけ
で容易に構成できる。

【００８６】すなわち、これらのソフトウェアではＳＧ
ＭＬ文書全体を一括して処理するように作られているの
で、本実施例のように文書に対する処理の開始位置を渡
して部分的に復元処理を行うように変更する。すなわ
ち、文書構造を規定する文書型の定義を記述するために
用いられる文法のクラスが文脈自由文法であれば、ある
構造（タグ）に至るまでの過程（文脈）は、それ以降の
制約に影響を与えないので、一部を変更しても処理系の
動作に不具合が生ずることはなく対応できる。

【００８７】具体的に説明すると、ｍａｒｋ−ｉｔやｓ
ｇｍｌｓなどの処理系を利用する場合には、次に説明す
る４つの項目に関して、一部の処理内容を変更すれば、
容易に対応できることになる。

【００８８】１）まず、タグの復元処理を無条件に文書
の先頭から行うようにプログラミングされている部分
を、外部から開始位置（文書ファイル上の位置を差し示
すポインタ）を指定可能であるようにして、指定された
開始位置から処理を行うように変更する。そのため、処
理系の一番始めの処理として、「指定された開始位置ま
で文書ファイルを読み飛ばす」という処理を追加し、そ
の位置からデータを読み始めるようにする。

【００８９】２）最初に処理するスタートタグは、文書
のルート（根）に相当するスタートタグでなくてはなら
ないようにプログラミングされている（そうでないとエ
ラーとして処理される）ので、その部分を、型保持部
（つまりＤＴＤ）内に定義されたタグであれば、任意の
タグから処理を始めてもエラーとして処理しないように
変更する。そのためには、処理の一番最初のステップで
「最初に処理したスタートタグが文書のルートのタグで
なければエラーとする」という処理を行っている部分
を、「最初の処理したスタートタグが、その文書の型定
義に定義されている（型保持部に保持されている）タグ
でなければエラーとする」というように変更する。

【００９０】３）また、最初に処理するスタートタグ
は、ルート（根）のスタートタグであるので、それに対
応するエンドタグを処理したかどうかを判定し、処理が
終っていない時は処理を続行するというように、プログ
ラミングされている部分を、最初に処理したスタートタ
グに対応するエンドタグを処理したかどうかで処理を続
行するように変更する。それには、復元処理の後半部
で、「ルート（根）のエンドタグを処理していれば、復
元処理を続行し、そうでなければ、次の処理を行う」と
いう処理を、「最初に処理したスタートタグに対応する
エンドタグを処理していれば、復元処理を続行し、そう
でなければ、処理を終了する」というように変更する。

【００９１】４）更に、最初に処理するスタートタグ
が、ルート（根）のスタートタグであるので、それに対
応するエンドタグを処理した後、更に文書の残り部分に
何かデータが残っている場合は、エラーとして処理され
るようにプログラミングされている部分を、最初に処理
したスタートタグに対応したエンドタグを処理した後、
文書にデータが残っていても、それをエラーとして処理
しないように変更する。それには、処理の一番最後の部
分で「文書データが残っていればエラーとする」という
処理を行う部分があるので、これを取り除く。

【００９２】次に、本発明の構造検索装置の他の実施例
について説明する。前述した第１の実施例の構造検索装
置（図１）は、構造検索部内に必須構造探索部を内包さ
せた構成となっているが、この構造検索部における必須
構造探索部を別に設けるような構成としても良い。ま
た、構造の検索指示を受け付けた構造検索部は、必須構
造探索部により、検索すべき構造を含む構造化文書の必
要最小限の部分を判定して、構造復元部により部分的に
構造復元を行い、復元された部分データによって検索対
象の構造の検索を行うように構成されているが、別に設
ける制御部によって、これらの処理の制御を効率よく行
い、複数の構造の検索指示の要求に対して能率的に処理
を行うように構成できる。次にこのような変形例を説明
する。

【００９３】図１１は、本発明の第２の実施例にかかる
構造検索装置の構成を示すブロック図である。図１１に
おいて、１１１は文書データ保持部、１１２は型保持
部、１１３は構造復元部、１１４は構造検索部、１１５
は必須構造探索部、１１６は制御部である。また、１１
７は構造の検索指示、１１８は検索結果を表している。

【００９４】第２の実施例の構造検索装置においても、
前述したように、ユーザあるいは他の装置などによる検
索要求が、構造の検索指示１１７として、図２に示すよ
うな形式により指定され、対象構造，内容制約，構造制
約からなる検索指示情報が、構造検索部１１４に与えら
れて、ここでの構造の検索処理が開始される。この検索
処理の制御は、制御部１１６が各々を制御して処理を進
める。構造の検索処理が開始されると、構造検索部１１
４は、検索要求に含まれている検索対象の情報を、必須
構造探索部１１５に渡す。

【００９５】必須構造探索部１１５では、型保持部１１
２に保持されている文書型定義（ＤＴＤ）を参照し、検
索対象である構造（タグ）に関する定義を探し出す。探
し出された検索対象の構造（タグ）に関する定義におい
て、当該構造（タグ）が省略可と表現されている場合
は、更に、型保持部１１２の文書型定義（ＤＴＤ）で定
義され文書構造を辿り、検索対象の構造（タグ）より上
位の構造で、省略不可となっている構造（タグ）を特定
する。そして、ここで特定された構造（タグ）を基点と
して、構造復元部１１３により、部分的に文書構造の復
元を行う。

【００９６】このため、次に、必須構造探索部１１５
は、文書データ保持部１１１に保持されている文書デー
タから、先に特定された省略不可の構造（タグ）を捜し
出し、見つかれば、その省略不可の構造（タグ）と、当
該構造（タグ）の文書データ内での位置を構造復元部１
１３に渡す。

【００９７】構造復元部１１３では受け取った省略不可
の構造（タグ）と、当該構造（タグ）の文書データ内で
の位置により、その位置から文書データにおける文書構
造の復元処理を行う。つまり、与えられた位置を処理開
始の位置として、文書データの文書構造が省略されてい
る構造を復元する。この結果、構造化文書の指定の構造
の位置から、その下部構造の構造（タグ）のみが、構造
復元部１１３により型保持部１１２の文書型定義の情報
を読み出しながら復元される。復元処理を行った結果の
構造化文書の部分構造は、構造検索部１１４に渡され
る。

【００９８】構造検索部１１４では、渡された部分的に
復元処理済の部分文書構造（図７）の中から、ユーザあ
るいは他の装置から指示された検索対象の構造（タグ）
を探し出す。その結果は、検索結果１１８として、構造
の検索指示の要求が出された呼び出し元の装置あるいは
ユーザに返される。

【００９９】なお、ここでのユーザあるいは他の装置な
どによる構造の検索要求は、検索対象の文書や、その検
索対象の文書が従っている文書型定義と共に与えられて
も良い。その場合、検索対象の文書のデータは文書デー
タ保持部１１１に読み込まれて保持され、検索対象の文
書が従っている文書型定義は、型保持部１１２に読み込
まれて保持される。また、検索対象の文書や、その文書
型定義は、同時に両者が与えられなくとも、個々に独立
して与えられるようにしても良い。すなわち、型保持部
１１２に保持される文書型定義は、予じめ内部データと
して保持されており、外部からは検索対象の文書だけが
与えらるようにしても良い。その逆に、検索対象の文書
が内部データとして予じめ保持しており、外部からは文
書型定義のみが与えられるようにしてもよい。

【０１００】この第２の実施例の構造検索装置において
は、構造検索部１１３により部分的に構造が復元処理さ
れた部分構造の文書を、そのまま構造検索部１１４に渡
すようにしているが、ここでの部分的に構造が復元され
た文書を、文書データ保持部に保持されている復元処理
前の対応部分と取り換えるようにすると、次の構造の検
索指示において、同じ部分の構造の検索要求がなされた
場合に、先に復元した部分構造の文書を検索に用いるこ
とができる。これにより、後に行なわれる構造の検索で
は、構造復元処理を行なわなくても良い場合もあり、結
果的に、実質的な検索時間が短かくて済む。次に、この
ような変形例を第３の実施例として説明する。

【０１０１】図１２は、本発明の第３の実施例にかかる
構造検索装置の構成を示すブロック図である。図１２に
おいて、１２１は文書データ保持部、１２２は型保持
部、１２３は構造復元部、１２４は構造検索部、１２５
は必須構造探索部、１２６は制御部である。また、１２
７は構造の検索指示、１２８は検索結果を表している。

【０１０２】第３の実施例の構造検索装置においても、
前述したように、ユーザあるいは他の装置などによる検
索要求が、構造の検索指示１２７として、図２に示すよ
うな形式により指定され、対象構造，内容制約，構造制
約からなる検索指示情報が、構造検索部１２４に与えら
れて、ここでの構造の検索処理が開始される。この検索
処理においても、その処理の制御は、制御部１２６が各
々を制御して処理を進める。構造の検索処理が開始され
ると、構造検索部１２４は、検索要求に含まれている検
索対象の情報（対象構造）を、必須構造探索部１２５に
渡す。

【０１０３】必須構造探索部１２５では、型保持部１２
２に保持されている文書型定義（ＤＴＤ）を参照し、検
索対象である構造（タグ）に関する定義を探し出す。探
し出された検索対象の構造（タグ）に関する定義におい
て、当該構造（タグ）が省略可と表現されている場合
は、更に、型保持部１２２の文書型定義（ＤＴＤ）で定
義され文書構造を辿り、検索対象の構造（タグ）より上
位の構造で、省略不可となっている構造（タグ）を特定
する。そして、ここで特定された構造（タグ）を基点と
して、構造復元部１２３により、部分的に文書構造の復
元を行う。

【０１０４】このため、次に、必須構造探索部１２５
は、文書データ保持部１２１に保持されている文書デー
タから、先に特定された省略不可の構造（タグ）を捜し
出し、見つかれば、その省略不可の構造（タグ）と、当
該構造（タグ）の文書データ内での位置を構造復元部１
２３に渡す。

【０１０５】このように、第３の実施例の構造検索装置
においても、第２の実施例の構造検索装置と同様に、ユ
ーザあるいは他の装置などによる構造の検索指示１２７
が、構造検索部１２４に与えられ、構造検索部１２４
が、構造の検索指示１２７に含まれている検索対象の構
造（タグ）を必須構造探索部１２５に渡すと、必須構造
探索部１２５は、検索対象の構造（タグ）から直近の上
位の省略不可の構造（タグ）を探し出し、その省略不可
の構造（タグ）と、その構造（タグ）が位置する文書デ
ータの文書内の位置の情報を構造復元部１２３に渡す。
また、ここでの必須構造探索部１２５は、構造復元部１
２３にその情報を渡すと同時に構造検索部１２４にも同
じ情報を返す。

【０１０６】構造復元部１２３は、受け取った文書内で
の位置から、部分的な復元処理を開始し、その構造（タ
グ）にかかる下部構造のみの復元処理を、型保持部１２
２から文書型定義を読み出しながら実行する。部分的に
復元処理を行った結果は、文書データ保持部１２１に渡
され、該当する文書の対応する部分と入れ替えられ、書
き換えられる。

【０１０７】一方、必須構造探索部１２５から情報を受
け取った構造検索部１２４は、構造保持部１２１を監視
し、構造復元部１２３によって、文書情報が書き換えら
れるのを待つ。部分的に復元処理を行った結果文書の書
き換えが完了すると、構造検索部１２４は、当初の検索
対象であった構造（タグ）を、必須構造探索部１２５か
ら受け取った省略不可の構造（タグ）の文書内の位置の
情報をもとに、文書データ保持部１２１から読み取っ
て、その対象構造の検索を行う。その結果は、検索結果
１２８として、構造の検索指示の要求が出された呼び出
し元の装置あるいはユーザに返される。

【０１０８】このように、第３の実施例においても、制
御部１２６の制御によって、必須構造探索部１２５を用
いて、ここから探索された構造（タグ）により、復元処
理部１２３を用いて、当該構造（タグ）に関係する必要
最小限の部分データから部分的に構造復元処理を施すだ
けで、検索対象の構造（タグ）を検索できるので、実質
的な検索時間が短かくて済む。このため、構造の検索が
高速に行える。また、構造の検索が行なわれる毎に、デ
ータ保持部１２１には、検索対象のタグが部分的に復元
されたデータが順次に書き換えられて保持されるので、
後に行なわれる構造の検索では、構造復元処理を行なわ
なくても良い場合もあり、結果的に、実質的な検索時間
が短かくて済む。

【０１０９】以上に説明したように、本発明を３つの実
施例により説明したが、本発明を実施する上での各々の
処理要素の組合せは、まだ、幾つかの変形例の構成が可
能である。本発明の構造検索装置の特徴は、このような
処理要素の間のデータの流れではなく、構造の検索時間
を短くするために、構造の検索に必要な箇所のみを部分
的に構造の復元処理を行い構造の検索を行うことであ
り、また、そのために用いる必須構造探索部を備えるこ
とである。また、ここでは、構造化文書の検索対象文書
の保存に際しては、文書全体を一度に復元して内部構造
に変換せず、元の文書の形態で文書データを保存し、当
該文書データが検索対象とされた時、構造復元処理の範
囲をできるだけ最小化して、必要最小限の復元処理を実
行することによって、全体として検索時間を短縮する。

【０１１０】その基本的な考え方は、構造の検索処理を
行うために、構造の復元処理を対象文書全体に対して行
うのではなく、検索対象としてユーザに指定された対象
構造と、検索対象文書の文書型定義とから、構造の復元
処理が必要な部分を特定し、特定された必要な部分だけ
の復元処理を行い、その処理時間を最小限に押さえるよ
うにする。具体的には、文書型定義を参照して、検索対
象の構造（タグ）より文書構造上の上位に位置し、か
つ、その構造（タグ）が省略不可である構造（タグ）を
見つけ出す必須構造探索部を設け、この必須構造探索部
によって見つけられた省略不可の構造（タグ）を、一次
検索として文書の中から探し出し、その結果によって探
し出された部分構造にのみ部分的に構造復元処理を行
う。そして、その処理結果に対して、二次検索として本
来の検索対象の構造（タグ）を探索する。これにより、
元の文書データを対象に検索を行う場合に、検索のため
に文書全体に対して復元処理を適用する必要がなくな
り、構造の探索の処理を高速化できるようになる。

【０１１１】このような本発明の構造検索装置は、ワー
クステーション上における文書編集装置（ワードプロセ
ッサなど）などの文書処理装置の一部分として、文書の
部分構造を検索するための機能として利用できるだけで
なく、自動的に構造化文書の構造部分を検索してきて、
結果を返すようなネットワークに接続されたサービス機
能のように、文書の構造を検索することを行う文書処理
装置一般に利用することができる。また、構造化の対象
は文書に限らず、例えば、構造を持ったデータベースな
どであっても良い。また、本実施例ではデータが表現す
る対象を文書であるとして説明したが、データ表現がこ
こで説明した形式に従っていれば、文書でなくても、本
発明の実施することができ、有効に利用できる。

【０１１２】

【発明の効果】以上に説明したように、本発明の構造検
索装置によれば、データの中にタグを挿入し、該タグに
より当該データを部分的に区別して構造を表現し、該タ
グが一部で省略可能であるデータから、その構造を高速
に検索する構造検索装置が提供される。また、ここでの
データを文書テキストすることにより、テキスト中にタ
グを挿入てしテキストを文書要素に区分して、文書の構
造化している構造化文書から、その構造を高速に検索す
る構造検索装置が提供される。

【図面の簡単な説明】

【図１】 図１は本発明の第１の実施例にかかる構造検
索装置の構成を示すブロック図、

【図２】 図２は構造の検索指示を行う場合の操作画面
の一例を示す図、

【図３】 図３は構造検索部１４における構造検索処理
を説明するフローチャート、

【図４】 図４は部分復元された構造から対象構造を検
索する処理を説明するフローチャート、

【図５】 図５は必須構造探索部の処理フローを示すフ
ローチャート、

【図６】 図６は構造復元部の処理フローを示すフロー
チャート、

【図７】 図７は対応のエンドタグが省略されている場
合の構造化文書の構造が部分的に復元される様子を具体
的に説明する図、

【図８】 図８は型保持部に保持される文書型定義の他
の形態を示す図、

【図９】 図９は構造の検索指示の他の一例を説明する
図、

【図１０】 図１０は構造の検索指示の別の一例を説明
する図、

【図１１】 図１１は本発明の第２の実施例にかかる構
造検索装置の構成を示すブロック図、

【図１２】 図１２は本発明の第３の実施例にかかる構
造検索装置の構成を示すブロック図、

【図１３】 図１３はＳＧＭＬの文書型定義（ＤＴＤ）
の一例を示す図、

【図１４】 図１４はタグが省略されたＳＧＭＬ文書の
一例を説明する図、

【図１５】 図１５は省略されたタグが復元されたＳＧ
ＭＬ文書の一例を説明する図である。

【符号の説明】

１１は文書データ保持部、１２は型保持部、１３は構造
復元部、１４は構造検索部、１５は必須構造探索部であ
る。１６は構造の検索指示、１７は検索結果、１１１は
文書データ保持部、１１２は型保持部、１１３は構造復
元部、１１４は構造検索部、１１５は必須構造探索部、
１１６は制御部、１１７は構造の検索指示、１１８は検
索結果、１２１は文書データ保持部、１２２は型保持
部、１２３は構造復元部、１２４は構造検索部、１２５
は必須構造探索部、１２６は制御部、１２７は構造の検
索指示、１２８は検索結果。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 データの中にタグを挿入し、該タグによ
   り当該データを部分的に区別して構造を表現し、該タグ
   が一部で省略可能であるデータを保持するデータ保持手
   段と、 前記タグにより表現される構造のひな型を保持する型保
   持手段と、 前記構造のひな型に基づいて、データ保持手段に保持さ
   れたデータの中のタグの省略箇所の復元を行う復元処理
   手段と、 指定された構造を検索する際、前記復元処理手段を制御
   し、検索対象の構造のタグに関係する必要最小限の部分
   データに対して部分的に構造を復元する処理を行い、復
   元された部分データにより検索対象の構造のタグを検索
   する構造検索手段とを備えることを特徴とする構造検索
   装置。
2. 【請求項２】 データの中にタグを挿入し、該タグによ
   り当該データを部分的に区別して構造を表現し、該タグ
   が一部で省略可能であるデータを保持するデータ保持手
   段と、 前記タグにより表現される構造のひな型を保持する型保
   持手段と、 前記構造のひな型に基づいて、データ保持手段に保持さ
   れたデータの中のタグの省略箇所の復元を行う復元処理
   手段と、 指定された構造のタグを検索する構造検索手段と、 検索対象の構造にかかるタグが省略可能である場合、ひ
   な型の構造から検索対象の構造より上位でかつ省略不可
   の構造のタグを探索する必須構造探索手段と、 前記必須構造探索手段により探索されたタグを用いて、
   復元処理手段を制御して当該タグに関係する必要最小限
   の部分データから部分的に構造復元処理を行い、構造検
   索手段を制御して検索対象の構造を検索する制御手段と
   を備えることを特徴とする構造検索装置。
3. 【請求項３】 データの中にタグを挿入し、該タグによ
   り当該データを部分的に区別して構造を表現し、該タグ
   が一部で省略可能であるデータを保持するデータ保持手
   段と、 前記タグにより表現される構造のひな型を保持する型保
   持手段と、 前記構造のひな型に基づいて、データ保持手段に保持さ
   れたデータの中のタグの省略箇所の復元を行う復元処理
   手段と、 データ保持手段に保持されたデータから指定された構造
   のタグを検索する構造検索手段と、 検索対象の構造にかかるタグが省略可能である場合、ひ
   な型の構造から検索対象の構造より上位でかつ省略不可
   の構造のタグを探索する必須構造探索手段と、 前記必須構造探索手段により探索されたタグを用いて、
   復元処理手段を制御して当該タグに関係する必要最小限
   の部分データに構造復元処理を行い、データ保持手段の
   対応データを復元データに取り換える制御手段とを備え
   ることを特徴とする構造検索装置。