1997年度 修士論文 Web文書の個人ビュー生成のための 操作言語

1997 年度
修士論文
Web 文書の個人ビュー生成のための
操作言語に関する研究
神戸大学大学院 自然科学研究科
情報知能工学専攻
篠原 誠
指導教官
審査教官 主査
副査
田中 克己
田中 克己
上原 邦昭
1998 年 2 月 13 日
1997 年度
修士論文
題目
Web 文書の個人ビュー生成のための
操作言語の研究
神戸大学大学院 自然科学研究科
情報知能工学専攻
967T679N
篠原 誠
指導教官
田中 克己
審査教官 主査
副査
田中 克己
上原 邦昭
1997 年 2 月 13 日
A language for Personal View
Specification of Web documents
Makoto Shinohara
Abstract
This paper propose a language for specifying personal views on a large number of
Web documents available on the Web.
In order to define a personal view on a set of Web documents, one must first
extract the necessary information from the available data and then modify those data
according to one’s need. And a personal view is generated dynamically whenever one
refers to.
Web documents include various information, the available data and the vain data,
and are lack of rigid data structure such as “Database’s Schema”.
On the other hand, Web documents, in general, are semi-structured in nature
since they contain specifc tags in HTML(HyperText Markup Language).
We treat our data to be edge-labeled graph. The proposed language have a SQLlike construction, and apply the pass expression.
Under this assumption, personal views can be specified by extracting necessary
parts from one or more documents and re-structuring those parts with the help of
the proposed language.
Web 文書の個人ビュー生成のための
操作言語に関する研究
篠原 誠
要旨
本研究では、分散して存在している WWW 上の Web 文書中の必要な情報に対し 、
利用者が必要に応じた操作を行い、
「個人ビュー」の生成を定義するための操作言語
を設計し 、その言語を用いた個人ビューシステムの実装を行った。
「個人ビュー」と
は、既存の Web 文書群から利用者の必要な情報を抽出して、それらを再構成して生
成される仮想的な Web 文書のことである。そして、
「個人ビュー」は参照される度に、
現在の Web 文書を基にして常に動的に生成される。
WWW 上に存在している Web 文書には、必要な情報が含まれていても、その文
書中に不要な情報も混在している場合がある。これは、発信される Web 文書の情報
の構造については、あらかじめデータベースのように構造が定義されている訳では無
いためである。そのため、データベースで行われるような、利用者の検索によって必
要な情報のみを抽出し 、それらを要求に応じて再構成しビューを生成できるような利
用形態は考慮されていない。
一方で、Web 文書は HTML(HyperText Markup Language) によって記述された、
タグの階層構造を持つ構造化文書であり、したがって「半構造化データ」とみなすこ
とができる。そこで、本研究では Web 文書を半構造化データのモデルとしてよく用
いられるラベル付グラフとして表現し 、個人ビューを生成する操作をこのグラフ上の
操作の形で定義する、パス表現を用いた SQL-like な構文を持つ操作言語を設計した。
そして、この言語を用いた個人ビューシステムの実装を行った。
目次
1 はじめに
1
2 基本的事項および関連する研究
3
2.1
2.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.1
WWW(World Wide Web) . . . . . . . . . . . . . . . . . . . .
3
2.1.2
HTML(HyperText Markup Language) . . . . . . . . . . . . . .
3
2.1.3
半構造化データ . . . . . . . . . . . . . . . . . . . . . . . . . .
4
関連する研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1
Lorel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2
UnQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.3
W3QL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2.4
MetaCommander . . . . . . . . . . . . . . . . . . . . . . . . .
8
基本的事項
3 Web 文書の個人ビュー
9
3.1
Web 文書の問題点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.2
Web 文書の個人ビュー . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3
個人ビュー生成のための操作
. . . . . . . . . . . . . . . . . . . . . .
4 個人ビュー生成のための操作言語
11
13
4.1
Web 文書の構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2
文書内部の部分特定
. . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.3
特定した要素による個人ビュー生成操作 . . . . . . . . . . . . . . . .
16
4.3.1
18
特定した要素間の制約 . . . . . . . . . . . . . . . . . . . . . .
5 個人ビュー生成システムの実現
13
20
i
5.1 システムの概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
5.2 システムの構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
5.2.1
問い合わせ入力部 . . . . . . . . . . . . . . . . . . . . . . . . .
21
5.2.2
Web 文書解析部 . . . . . . . . . . . . . . . . . . . . . . . . . .
21
5.2.3
問い合わせ処理部 . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.2.4
個人ビュー生成部 . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.3 システムの評価と今後の課題
. . . . . . . . . . . . . . . . . . . . . .
23
5.3.1
システムの評価 . . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.3.2
今後の課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
6 終わりに
26
謝辞
27
参考文献
28
付録
30
ii
第 1 章 はじめに
パーソナルコンピュータの一般への普及とインターネットの爆発的な発達により、
特別な知識を持たない一般の人々が、世界中に張り巡らされたネットワークを通じて
必要とする様々な情報を利用できる環境が整いつつある。その手段として、分散型ハ
イパーテキストシステムである WWW(World Wide Web) 上の Web 文書の必要な情
報を閲覧することが挙げられる。
WWW は、情報発信の手段として最も広く利用されている技術である。その要因
としては、発信できるリソースの多様さ、情報発信の手軽さ、リンクによる情報の関
連付けが可能、と言ったことが挙げられる。また利用者にとっても複雑な操作なしに
連想的にリンクを辿ることで、関連する情報を参照することが可能である。
しかし一方では、発信者が作成した情報をそのままリンクで辿ることによりブラ
ウズするのみであるため、リンク先の情報と利用者の要求する情報とが異なっていた
り、また必要な情報が含まれる Web 文書に辿り着くことができても、その文書中に
不要な情報が混在している場合もある。現在の WWW では、Web 文書内部の必要な
情報に対して、データベースで行われるような、検索によって必要な情報のみを抽出
し 、要求に応じて再構成できるような利用形態は考慮されていない。
そこで、分散している Web 文書の中の利用者が必要とする情報に対し 、編集・カ
スタマイズ等の操作を行い、Web 文書の「個人ビュー」を生成できれば非常に有用
であると考えられる。
また、Web 文書は HTML(HyperText MarkupLanguage) により記述されているた
めに、タグの階層構造を持つ構造化文書であり、タグの出現レベルが特定されていな
いということから「半構造化データ」として扱い、その構造に基づいて個人ビューを
生成することとした。本研究では、Web 文書を、タグの持つ構造に基づいて、半構
造化データモデルにおいて用いられるラベル付グラフで表現した。必要な部分の特定
を行い、それらを編集・カスタマイズし個人ビューを生成する操作を、そのグラフ上
の操作として定義するための言語を設計した。さらに、その言語を用いて個人ビュー
を提供するシステムの実装を行った。
1
以下、第 2 章では本論文における基本的事項および関連研究について述べ、第 3
章では、web 文書の個人ビューについて述べ、第 4 章では、個人ビューのための操作
言語について述べる第 5 章では、本機構を実装したシステムについて述べ、最後の第
6 章では、この論文のまとめを行なう。
2
第 2 章 基本的事項および関連する研究
基本的事項
2.1
2.1.1
WWW(World Wide Web)
WWW は 1989 年にスイスの CERN（ヨーロッパ素粒子物理学研究所）において
提案された、分散型情報システムであり、テキストだけでなく画像（ GIF,JPEG 等）、
動画 (MPEG,QuickTime 等) 、音声 (SunSound 形式等) 、Java アプレットなどの様々
なリソースを統合して扱うことが可能である。
WWW はサーバとクライアントという２種類のプログラムから構成され、サーバ
はインターネット上で公開する情報を蓄積・管理し、クライアントはその情報をブラウ
ザに表示するものである。このシステムに必要な概念としては、HTML （ HyperText
Markup Language ）、HTTP（ HyperText Transfer Protocol ）、URL（ Uniform Resource Locator ）があり、それぞれの動作を簡単に言うとば 、HTML で書かれたテキ
ストを HTTP が解釈し 、URL によって表されるリソースへのアクセスを可能にする
というところである。
• URL
URL(Uniform Resource Locator) とはインターネット上の様々なリソースを統
一的に記述するための記法である。URL を構成する要素は基本的に、プロトコ
ル名、ホスト名、ポート番号、ディレクトリパス名、ファイル名であり、一般
的書式は次のようになる。
scheme://host.domain[port]/path
2.1.2
HTML(HyperText Markup Language)
HTML(HyperText Markup Language) とは、WWW 上の Web 文書の文字やレ イ
アウト等を設定するための言語で、SGML(Standard Generalized Markup Language)
3
を基礎としたものである。HTML は SGML の応用であり、DTD(Document Type Def-
inition, 文書型定義) によって定義されている。しかし急速に広まった WWW の影響
を受けて、現在では文書のレイアウトを表現するための言語となりつつある。そのた
め HTML では、章・節と言った意味的な文書構造の定義がされておらず、意味的構
造が曖昧になっている。
HTML では、タグ (tags) と言われる一連のマーク付けを記述することにより、文
書中の要素を明示している。これらは、文書中で使用される要素の始めと終りを、以
下に示すような形で識別している。
h 要素名 属性名=属性値 i 要素の内容 (文字列) h/要素名 i
通常、要素は hi の間に要素名を入れた開始タグと h/i の間に要素名を入れた終了
タグで囲まれて成り立っている。そして、要素名によって、そのタグで囲まれた文字
列が特徴づけられている。開始タグではその要素に付随する属性を指定することがあ
り、
「属性名=属性値」の形で指定する。タグに書かれる要素名や属性名は大文字・小
文字の区別はされない。Web 文書中では、HTML によってタグで要素付けられた各
文字列が 、文書中において要素毎の入れ子関係により階層構造をなしている。
2.1.3
半構造化データ
半構造化データ [1] とは、次のような特徴を持つデータを指している。
• 構造が不規則なデータの集まりで、はっきりとしたスキーマが定義できないよ
うなデータ群。
• スキーマはあるが非常に緩やかで、全てのデータが厳密にスキーマに適合して
いるとは限らないデータ。
• データベース以外の形で蓄積されており、データベースのようにあらかじめス
キーマが提示されているわけではないようなデータ。
つまり半構造データとは、スキーマ情報がデータとは独立してあらかじめ与えら
れているものではなく、データ情報の中にスキーマ情報が存在するものである。
Web 文書は、HTML で記述されたタグ付きの構造化文書であるが 、個々のタグ
がタグの入れ子構造に於いて、どの深さのレベルに出現するかをあらかじめ定義す
ることができない。そのため、Web 文書は「半構造化データ」とみなすことができ
4
る。最近、このような半構造化データに関して、データベースで行われているよう
な、set-oriented で宣言的な検索を行い、再構成することを目的とした研究が行われ
ている。
Object Exchange Model(OEM)[2]
Object Exchange Model とは、Stanford 大学のデータベースグループが heterogeneous data の 統合システムである TSIMMIS システムのために設計した言語である。
TSIMMIS システムは、様々なソースから取得したデータを、ある統一的なデータモ
デルにマップすることによって統一的なインターフェースを提供するが、そのモデル
として OEM が用いられる。OEM の特徴としては、self-describing object のモデルで
ある、入れ子構造のオブジェクトに対するもの、オブジェクト識別子を持つ、全ての
オブジェクトは基本型もしくは集合型である、などが挙げられる。OEM のオブジェ
クトは 、一つの根を持つグラフと考えられ 、オブジェクト間はノード とラベル付の
エッジによって関連づけられる。
2.2
関連する研究
関連研究として半構造化データのための検索言語である Lorel 、UnQL 、W3QL 、
そして WWW 上での情報統合システムのための言語である MetaCommander を挙
げる。
2.2.1
Lorel
Lorel[4] は Lore(Lightweight Object Repository)[3][5] のために用いられる、Stanford 大学のデータベースグループによって開発された、OEM 上の検索言語である。
Lore とは半構造化データの格納・問い合わせを行えるように設計されたデータベー
スシステムであり、特に WWW 上の HTML 文書を含むドキュメントデータを扱える
ようになっている。ただし 、操作の対象となる各 Web 文書が 、操作するための意味
的構造を持つように統一される必要があり、そのための変換する機構が必要である。
Lorel は、select-from-where の文法を持ち、OQL などのパス表現を用いることの
できる SQL-like な言語を拡張した言語であり、パス表現に正規表現を記述できる機
能と、様々な集合を扱うための自動制約機能を加えたものである。Lorel を用いた検
索文の例は以下のようになる。
5
select DBGroup.Member.Name
where DBGroup.Member.office(.Room%|.Cubicle)?
like “%252”
“ % ”は任意のラベルにマッチするワイルド カード で、Room で始まる全ての文
“ ? ”は指定したラベルパターン
字にマッチする。
“ | ”は二つのラベルの分断を表し 、
があってもなくてもよいことを表す。最後に、
“ like %252 ”はデータが文字列“ 252 ”
で終わることを表している。
本研究と異なり、操作を行うために意味的構造を持つように統一しており、その
ための変換する機構を必要とする。
2.2.2
UnQL
UnQL[6][7] は 、ラベル付エッジグラフの操作言語として Peter Buneman を中心
としたグループによって開発された言語である。スキーマの制約を受けないデータ、
つまり Web site や半構造化データを対象としている。UnQL は 、構造とそれを成す
データ、例えば WWW 上のリンクされた HTML 文書間の関係とリンクを示す値や
HTML ファイルに対して、任意の深さや巡回構造への問い合わせを行うことができ
る。UnQL を用いた検索は次のようになる。
select ”John Doe’s Projects”.p
where * i ”John Doe” i * i ”Project”.p in http://www.research.att.com
www.research.att.com の、“John Doe” でラベル付けされたページから辿れ 、そ
こから更に “Project” によりラベルを付けられたページから辿ることができる全ての
ページを、”John Doe’s Projects”という新しい HTML ページとして返す。X でラベ
ル付けされたページとは、X というラベルを持ったリンクを辿ることによって到達で
きるページのことである。変数 p は、問い合わせを満たす全てのページである。
UnQL では、全ての操作の単位はエッジやノード 個々ではなく、グラフであるの
で、select は新しいグラフとして定義される。つまり、先程の例の結果では、条件を
満たしたノードを持った変数 p のグラフを指す、”John Doe’s Projects”とラベル付け
されたエッジを持った新しく作られたグラフが結果として返されることとなる。
また、UnQL の問い合わせでは循環したグラフを明確にしており、2 次的に目標
とするグラフを辿るものを排除することもできる。
本研究と異なる点は、操作を全てグラフのエッジの操作として行う点である。デー
6
タの区別はなくなり、グラフのラベルによってのみ識別されることとなる。
2.2.3
W3QL
W3QL[8] は 、W3QS(WWW Query System)[9] と呼ばれる WWW を巨大なデー
タベースと見立てて問い合わせ機能を提供するシステムで用いられる言語である。
W3QL の特徴は、SQL-like な構文を持つ、structure と content 双方への問い合わせが
できる、UNIX ベースである、等が挙げられる。
Content Queries は、WWW 上の Web 文書の内容について問い合わせを行うもの
で、これにより WWW 上である条件を満たすページをノードとして選ぶことができ
る。一方、Structure-specifyiing Queries は、WWW 上の Web 文書のリンク関係に基
づく構造的な問い合わせを実現する。得られた WWW 文書はローカルに保存される。
結果はテーブルで与えられ、保存された文書へのリンクを容易に利用することができ
る。検索は次のようにして行われる。
Select n2:
From n1,l1,n2
Where n1 in MyHomePage;
n2 in Technion
Using ISEARCHd
これは、MyHomepage(http://www.cs.technion.ac.il/ konop/index.html) から Tech-
nion のサーバ上へのリンクが張ってあるものを抜き出すものである。この結果とし
て返されるのは、MyHomepage のリンク n1 とそのページ内にある Technion へのア
ンカーおよびイメージタグの属性値 l1 、そして n2 として l1 のリンク先へのアンカー
が表示されたテーブルが返される。n2 はローカルに保存されるので、n2 でのリンク
先はローカルファイルに指定されている。
また、W3QS が Unix ベースのシステムであることから、ローカルに保存したファ
イルに対して Unix コマンド を用いた操作を加えることが可能である。
本研究と異なる点は、ファイルをローカルに保管してそれに対し 、Unix のコマン
ド による操作が行える点である。
7
2.2.4
MetaCommander
MetaCommander[10] は、大阪市立大学の北村泰彦助教授らによって開発された、
WWW 上の情報の収集と統合を目的としたシステムで、その情報の操作を記述するた
めのスクリプト言語がある。MetaCommander は、利用者の記述した操作によって、
WWW 上の複数の HTML 文書からページ単位ではなくさらに細かい単位で情報を切
り出し 、情報統合を行いローカルのファイルに出力させるシステムである。
このスクリプト言語は、ファイルアクセス、制御、計算機能を持っており、より
高度な操作を実現する一方、簡易スクリプトであるので容易に情報統合の操作を記述
することができる。関数としては、WWW 上の Web 文書に対する検索・抽出・整形・
表示の関数群が用意されている。
この言語では、本研究とは異なり、HTML 文書の構造は意味的な構造を持ってい
ないと言う観点から、構造ではなく文字列単位での操作を行う。したがって、Web 文
書中のタグは文字列を切り出すためのキーワード 的なものとして扱われている。関数
としては、リンク等のアンカーを抽出する getAnchor やタグの中の文字列を切り出す
getString 、文字列を指定して抽出する cutString が用意されている。関数の書式は C
言語に近く、関数名引数 1, 引数 2, …となる。記述例は以下のようになる。
getAnchor {
getString {
print
}
}
この記述は、アンカーになっている文字列だけを出力するものである。
8
第 3 章 Web 文書の個人ビュー
本研究では、データベースにおけるビュー機構のように、WWW 上の Web 文書
から利用者が自分の必要とする情報のみを抽出し 、自分の目的に合わせてカスタマイ
ズ等の操作を行い、個人ビューを生成することを目的としている。
そこで、本章では Web 文書の問題点、Web 文書の個人ビュー、その生成のための
操作について述べる。
3.1
Web 文書の問題点
Web 文書の問題点としては、次のようなものが挙げられる。
1. 必要な情報が分散して存在している。
WWW 上の Web 文書は無数のサーバに分散して管理されている。その際、
情報の種類やデータの型とは無関係に管理されている。そのため、利用者は必
要な情報を参照するのに、多数の Web ページへのアクセスを必要とする場合が
ある。検索エンジンやブックマークなどにより、情報を探す手間を省くことは
出来ても、アクセスの手間を省くことは不可能である。
2. 必要な情報と不要な情報が混在している。
Web 文書には様々な情報が公開されており、一文書中に必要な情報と不要な
情報が混在している場合がある。発信される Web 文書の情報の構造について
は、あらかじめデータベースのように構造が定義されているわけではないので、
文書ごとに発信される情報の構造は異なっており、意味的には同じ情報であっ
ても HTML の記述が異なる場合がある。そのため、利用者にとって必要な情報
と不必要な情報との区別が分かりにくい。
3. 利用者による情報の更新ができない。
利用者は発信者が作成した Web 文書を、文書中のリンクを辿ってそのままブ
ラウズし 、そのままの表示を行うだけである。欠けている情報を追加したり、
9
不要な部分を削除したり、利用していて気が付いたことなどを書き込んで表示
させるというような操作を加えることは考慮されていない。
利用者自身が Web 文書中の必要な情報に対して操作を加え、その情報を抽出す
ることができれば 、これらの問題を解決することができる。そこでデータベースの
ビューのように、利用者自身が Web 文書中の必要な情報に対して操作を行い、編集・
カスタマイズして仮想的な個人ビューを生成できれば 、大変有用である。
3.2
Web 文書の個人ビュー
Web 文書を利用者個々人がカスタマイズして「個人ビュー」を生成できれば 、次
のような用途に用いることができる。
1. 個人用新着情報ページの生成
日々更新される Web 文書では 、新着情報という形で更新された情報を提供
しているものがある。利用者が新しい情報のみに興味があったとしても、その
Web 文書中に更新された新しい情報だけでなく、既に見た古い情報も表示され
ている場合には、必要な情報だけでなく不要な情報までもが表示されることに
なる。あらかじめ文書中の新着情報が提供される部分が分かっていれば 、その
部分だけを取り出して表示することができる。
2. 個人用文書の作成。
組織で保有するマニュアル情報や電子教科書等の Web 文書群では、利用者の
状況ごとに必要とする情報が異なっているので、それに合わせて利用者自身の
コメントなどの情報を合成したり、注目している情報のレ イアウトを利用者の
要求に応じて変更することができれば 、利用者の理解を促進することが可能で
ある。
3. 動的な目次ページの生成。
WWW 上に存在している Web 文書群からリンク情報を取り出して、その文
書から辿れるページを表示することで動的に目次ページを作ることが可能であ
る。これにより、必要な情報へ辿り着くまでの迷子現象を解消できると考えら
れる。
4. リンク情報の再活用。
既存の Web 文書から有用なリンク情報を抽出して、他の Web 文書に対して
10
反映することで、必要な情報へのリンクを作ることができる。これにより関連
のなかった Web 文書にも、利用者が有用であると考える情報を反映できる。
こうした個人ビューを実現するためには、Web 文書中で必要な情報を特定し 、カ
スタマイズ等の操作が行われなくてはならない。しかし 、Web 文書はデータベース
のスキーマのように意味的な構造があらかじめ定義され、情報が管理されている訳で
はないので、そのままの状態では Web 文書内部への操作を行うことはできない。
一方で、Web 文書の視覚的なレ イアウトを定義している HTML の構造はタグの
入れ子関係による階層構造をなしていることから、半構造化データであると見なすこ
とができる。また利用者は、HTML で書かれたレ イアウト表示に基づいて、Web 文
書の構造を認識していることから、HTML の階層構造を利用して Web 文書内部の情
報を特定できると考えられる。
そこで本研究では、この HTML がなす階層構造を利用することで、Web 文書一
ページ単位ではなく、より細かいタグレベルでの操作を行い、複数の情報が混在して
いるような文書から必要な部分を抽出し 、個人ビューの生成を行うこととした。
3.3
個人ビュー生成のための操作
Web 文書の個人ビュー生成のための操作は、次のような流れになる。
1. 利用者が必要な情報に関連した Web 文書群を指定する。
2. 文書中の操作の対象となる部分を特定し 、操作を加える。
3. 操作を行い、編集・カスタマイズされた情報を個人ビューとして表示する。
1. に関しては、利用者は既存の Web 文書中の必要な情報を抽出して、その部分
に対して再構成を行い個人ビューを生成することとしている。その際に、必要な情報
の抽出に関係している Web 文書の URL を既に知っているものと想定している。つま
り、利用者が既に有用な情報へ辿り着く方法を知っているものとする。
そして、利用者により指定された Web 文書群は半構造化データとして、一つのグ
ラフにまとめられ、各々の文書はその部分グラフとして扱われるので、操作の際には
各文書間を意識することなく操作が行える。
よって 2. において、Web 文書群から個人ビューを生成するために必要な操作は、
指定された Web 文書群からを個人ビューの構成要素となる部分を特定する操作と、
11
特定された部分を個人ビューとして再構成する操作である。個人ビュー生成の際に要
求される操作としては、次のようなものが挙げられる。
• 対象となる Web 文書群から必要な情報を抽出・出力する。
• 対象となる文書中の不要な情報を削除する。
• 不足しているデータを文書中に追加・挿入する。
• 文書群中のリンクを辿って、新しい情報を操作の対象に加える。
3. では、操作が行われた情報によって構成された仮想的な Web 文書を、個人ビュー
として表示する。個人ビューは仮想的であるために、操作の対象となった WWW 上
の元の Web 文書自体には一切変更を加えることは無い。
12
第 4 章 個人ビュー生成のための操作言語
本章では、Web 文書群から必要な情報を特定する操作とそれらの情報を用いて個
人ビューを生成する操作を行う操作言語について述べる。
4.1
Web 文書の構造
Web 文書の構造を、タグ名 (要素名) 、タグ内に記述される属性、表示される文字
列、の 3 要素に分け、タグをこの 3 要素からなるオブジェクトとして考えることとし
た。またタグが、その階層構造において、出現する深さのレベルがあらかじめ特定で
きないことから、Web 文書を半構造化データとみなして、その構造を Figure4.1 のよ
うなグラフとして扱うこととした。
[src] [alt]
[href]
[Face]
[profile.html]
[face.jpg]
[href]
[book.html]
Figure 4.1: The structure of a Web document
13
また、Web 文書は意味的な構造化が明確に定義されていないことから、レイアウ
ト上でのタグの出現順序が必要であると考え、グラフは順序付グラフとした。レイア
ウト上でのタグの出現順序が関係するのは、例えば hOLiのようにその要素hLIiに対し
て出現順に番号が振られる場合などがある。
Figure 4.1 に於いて、hTAGiはタグ名を、[attribute] は属性名とその値を、{String}
はタグによりマーク付けされ表示されている文字列を表している。そして、図中で線
により囲まれた部分がタグのオブジェクトである。ただし 、表示文字列 String に関
しては、そのタグだけではなく上位タグの表示文字列でもある。
4.2
文書内部の部分特定
Web 文書をこうしたグラフ構造で表現することにより、以下のようなパス表現を
使った SQL-like な構文を用いて、Web 文書内部の必要な部分の特定を行うこととし
た。検索および操作はグラフの構造をなしているタグの階層構造に基づいて行われる
ので、操作の単位となるのはタグである。
セレクト文 ::= select パス表現 where 検索パターン
パス表現 ::= Xhタグ名i | Xhタグ名i{ 文字列 } | Xhタグ名i[タグの中の属性名]
検索パターン ::= & | Xhタグ名i | Xhタグ名i[(検索文字列)]
| Xhタグ名i[(検索文字列)]{(検索文字列)}
hタグ名i ::= H1 | IMG | A | TABLE | UL | …
{タグの中の属性名} ::= src | alt | href | height | width | …
セレクト文では、where 節で指定された検索パターンにマッチする部分グラフの
頂点となるタグを特定し 、これらの部分グラフについて select 節で選択されたパス
表現に当る要素を返す。要素とはそれぞれ 、hタグ名iならば特定されたタグ以下全体
の部分グラフ、hタグ名i[タグの中の属性名] ならば特定されたタグの指定された属性
名に対応する属性値、hタグ名i{ 文字列 } ならば指定されたタグの表示している文字
列である。検索パターンは、パス表現で記述された構造を持ち、各要素を表す括弧 (h
i 、[ ] 、{ }) の中で指定された検索文字列を含むものにマッチし 、かつ各変数 (ここで
は X としている) に対応するタグを束縛する。この変数は一セレクト文中に対し 、働
くものとする。
14
この構文を用いて、figure.4.1 に対して各要素を特定する記述例を以下に記す。
1. この文書全体を求めよ (文書全体が hhtmliで閉じられている場合)。
select X
where Xhhtmli
これにより、この Web 文書の階層構造の頂点であるhHTMLiが特定され、それ
以下の部分グラフが結果として返される。
2. リスト (UL) の中のアンカー (A) の href 属性値を求めよ。
select X[href ]
where hULi XhAi
X で束縛されたhULiの下の階層のhAiが特定され 、hAiの持つ href 属性の下の
属性値が返される。 は次の条件までの階層にそれ以外のタグがあってもよい、
ワイルド カードが繰り返された状態を意味している。この場合は、一般の正規
＾は以下の文字列以外を意味し 、*は 0 回以上
表現における＾hAi*を意味する。
の繰り返しを意味している。この場合、hAiを除くものなら、間に何回あっても
許すという意味である。
3. この Web 文書中のタイトル (TITLE) とイメージ (IMG) の src 属性値を求めよ。
select X{ }&Y[src]
where ZhHTMLi XhTITLEi&ZhHTMLi YhIMGi
hHTMLi以下のグラフから、hTITLEiの持つ文字列とhIMGiの持つ src 属性値が
返される。変数 Z で同一のhHTMLiであることを意味し 、hTITLEiとhIMGiは
同じ hHTMLiの下の部分グラフであることを示している。また、各節で&を用
いることで、同時に複数の要素および条件を指定することができる。
4. 文字列 Book を表示している、リストの要素（ LI ）を求めよ。
select X
where XhLIi{Book}
hLIi以下のグラフに文字列 Book を持つ部分グラフが返される。文字列は上位
のタグの影響も受けていることから、下位のタグ (この場合は hAi) の文字列に
関してもマッチするかど うかを調べる。
where の条件にマッチするかど うかを調べるために、グラフでは親子関係を基に
して深さ優先探索でグラフを辿り、部分グラフの特定を行っている。まず、where の
15
条件にマッチした部分グラフの頂点となるタグを特定し 、select 節で選択された要素
をタグから抽出することとしている。
4.3
特定した要素による個人ビュー生成操作
ここでは前述の記述で特定した Web 文書の部分グラフを用いて、個人ビューを生
成するためのグラフの操作について述べる。
• 個人ビューの仮想ソースへ書き込む。
Output (SELECT)
SELECT で特定した部分グラフを、HTML に変換し仮想ソースに書き込む。出
力したい文字列を、” ” で囲んで指定することも可能である。
• 必要な部分文書の追加、挿入。
Add (SELECT1 SELECT2)
SELECT1 で特定された箇所に対し 、SELECT2 の要素を加える。この際、SELECT2 の要素があるタグ以下の部分グラフならば 、複製された部分グラフが
加えられることとなる。これは 、親を複数もつグラフが存在しないようにし 、
追加したグラフに対する操作が加えられるようにするためである。
Add (select X where XhAi, select X where XhIMGi[face])
これにより、各アンカーhAiの下の部分グラフとして、hIMGi以下の部分グラフ
を追加する。
• 不要な部分文書の削除。
Del (SELECT)
SELECT で指定した要素以下の部分グラフを削除する。削除は、実際にその要
素を消すのではなく、グラフの親子関係を断つことで行われる。したがって、{
文字列 } 中の一部を削除することはできない。
Del (select X where XhAi)
各アンカーhAiを親から切り放すことで、削除を行う。
16
• 必要な部分文書との置換。
Rep (SELECT1、SELECT2)
置換は、SELECT1 で特定された要素を消去し 、その部分に SELECT2 の要素
を加えることで実現されている。Add と同じく、SELECT2 の要素があるタグ
以下の部分グラフならば 、置換されるのは複製された部分グラフである。
Rep (select X where XhAi{Book}, select X where XhIMGi[face])
文字列に Book を含むアンカーhAiを、face を属性値にもつhIMGiと置き換える。
• アンカーを指定しリンク先の文書を読み込む。
Link (SELECT)
アンカーのリンク情報を基にして、リンク先の Web 文書を読み込む。SELECT
では、アンカーを指定する。読み込んだ文書とアンカーの関係は、リンク先と
して読み込んだ文書の頂点に当るタグを確保することで保持する。読み込んだ
文書を指定するには、trace(SELECT) で行うこととし 、SELECT にアンカーを
指定することにより、確保しておいたリンク先の頂点に当るタグを特定する。
trace は where 節の中で用いられる。
Link (select X where XhAi{Book})
文字列に Book を含むアンカーhAiを辿り、リンク先の Web 文書を獲得する。そ
の際、リンク先として、リンク先の Web 文書の頂点のタグを示す変数を確保
する。
trace(select X where XhAi{Book})
文字列に Book を含むアンカーhAiを辿ったリンク先の Web 文書を指す。リン
ク先の Web 文書の頂点のタグを示す変数を返す。
• 変数として確保する。
Var var (SELECT)
SELECT で特定された部分を、変数名 var に代入する。確保されるのは、各部
分グラフの頂点となるタグのリストである。
Var mylist (select X where hULi XhLIi)
mylist に hULiの下のhLIiのタグの識別子のリストを確保する。
17
特定した要素を用いた個人ビュー生成の操作について述べてきたが、追加や挿入・
置換を行う各要素間には、操作可能な要素と操作不可能な要素の関係があると考えら
れる。その制約について、次で挙げることにする。
4.3.1
特定した要素間の制約
本研究では、Web 文書の構成要素を、タグ名 (要素名) 、タグ内に記述される属性、
表示される文字列に分けて考えている。個人ビューを生成する際に HTML として復
元するため、これらの要素間では、お互いの要素に対する操作を全て、許可している
訳ではない。引数として二つの要素間で操作が行われる追加と置換を対象に、このこ
とについて考える。
• SELECT1 が { 文字列 } の場合
– SELECT2 がどのような要素であっても、操作可能。
{ 文字列 } に対しては、どのような要素が操作されたとしても、HTML
に復元した際に表示的な問題は生じない。
ただし、SELECT2 で hタグ名i以下の部分グラフが指定されたときに、グ
ラフの構造を失い文字列として扱われるので、操作が行われた部分に関し
ては構造に基づいた再操作ができない。
• SELECT1 が [タグ内の属性] の場合
– SELECT2 が hタグ名i 、つまりタグ以下の部分グラフであれば 、操作不可
能。
属性を記述している開始タグの中に、タグを入れることはできない。
himg src=”himg src=”xxxx”i”iのような記述は、文法として許されてい
ない。
– SELECT2 が [タグ内の属性] であれば 、操作可能。
対応している属性値であるかは別として、文法的には問題ない。
– SELECT2 が { 文字列 } であれば 、操作可能。
対応している文字列であるかは別として、文法的には問題ない。
• SELECT1 が hタグ名i 、つまりタグ以下の部分グラフの場合
18
– SELECT2 が hタグ名iならば 、操作可能。
行われるのがグラフ同士の追加であれば 、SELECT1 の部分グラフとし
て連結することができ、置換であっても問題なく操作を行える。
– SELECT2 が [タグ内の属性] であれば 、操作可能だが曖昧。
文字列に対する操作なのか、属性に対する操作なのか、判断できないな
いために何処に操作すれば良いのかはっきりしない。
– SELECT2 が { 文字列 } であれば 、操作可能だが曖昧。
文字列に対する操作なのか、属性に対する操作なのか、判断できないな
いために何処に操作すれば良いのかはっきりしない。
以上のように、操作自体が不可能なものや操作の対象が曖昧になってしまう場合
が出てくる。そこで制約としては、操作が許され操作対象がはっきりしているものだ
け操作可能とする。
したがって、制約を設ける操作は、以下の場合とした。
• SELECT1 が [属性] の時に、SELECT2 が hタグ名iの場合
• SELECT1 が hタグ名iの時に、SELECT2 が [属性] の場合
• SELECT1 が hタグ名iの時に、SELECT2 が { 文字列 } の場合
19
第 5 章 個人ビュー生成システムの実現
5.1
システムの概要
本研究では、CGI にて起動される個人ビュー生成プログラムをプログラミング言
語 Perl によって構築した。問い合わせを FORM からの入力として受け取り、それに
基づき個人ビューを生成し 、WWW ブラウザに表示を行う。
Figure 5.1: The construction of Personal View System
20
システムの構成
5.2
5.2.1
問い合わせ入力部
入力用の FORM に対して、個人ビューとして表示したい必要な情報に関係する
Web 文書の URL を URL 指定部で指定し 、操作入力部で操作言語を用いて操作を記
述する。
Figure 5.2: Query Input Field
5.2.2
Web 文書解析部
初期入力として与えられた Web 文書をファイルとして獲得し 、タグに基づいた階
層構造の解析を行い、木構造のグラフを生成する。その際、タグの情報は以下のよう
な情報に分解して管理される。
• 識別子 (tid)
タグ個々を識別するための識別子。識別子は整数として管理している。
• タグ名 (tag name)
タグの持つ名前、文字列である。
• 親のタグの識別子 (Parent)
親に当るタグの識別子を確保。木構造であるので、親は一意に決まる。
21
• 子のタグの識別子のリスト (Child)
子に当るタグの識別子を確保。出現順序についても確保している。
• 文字列 (vstr,endstr)
タグが表示している文字列を確保。
• 属性情報 (Tag)
タグ内にある属性名と属性値を確保。
5.2.3
問い合わせ処理部
問い合わせを受け取り、各操作を行う。セレクト文は、select 節と where 節を”::”
で区切った形で記述する。実際に例を示して、説明を行うこととする。
以下の例は、
「田中研究室のページから辿れるメンバーページに含まれる、各個人
へのアンカーとリンク先を表示せよ。」、と言うものである。
URL 指定部： www.db.cs.kobe-u.ac.jp
操作入力部： link Xhai::Xhai{ メンバー },
output Xhai&Xhai[href]&”hhri”::trace(Xhai::Xhai{ メンバー }) hhtmli Xhai
1. www.db.cs.kobe-u.ac.jp
「田中研究室のページ」の URL(www.db.cs.kobe-u.ac.jp) を指定し 、操作の起
点となる Web 文書を獲得し 、グラフに変換する。
2. link Xhai::Xhai{ メンバー }
表示している文字列に「メンバー」の文字列が含まれているアンカー (Xhai::Xhai{
メンバー }) を辿り、リンク先の Web 文書を獲得する。獲得した文書は解析さ
れてグラフに変換される。
3. output Xhai&Xhai[href]&”hhri”::trace(Xhai::Xhai{ メンバー }) hhtmli Xhai[
e]
獲得した Web 文書を指定し (trace(Xhai::Xhai{ メンバー }) 、その文書中で属性
値に ”e ”を含むアンカー (hai[ e ]) のタグ (hai) 以下のグラフととそのリンク先で
ある href 属性の値 (hai[href]) を横罫線 (hhri) を付けて出力する。
22
5.2.4
個人ビュー生成部
個人ビューとして各操作によって得られ、メモリ上に展開された Web 文書を WWW
ブラウザに表示する。例で示した操作を行った結果の個人ビューは、figure.5.3 である。
Figure 5.3: Personal View
システムの評価と今後の課題
5.3
本研究では、Web 文書が HTML のタグの階層構造を持つ半構造化データである
と言う点に着目し 、その構造に基づいて操作を定義をする言語を開発し 、実装を行
なった。ここでは、他のシステムと比較し評価を行う。
5.3.1
システムの評価
本システムの特徴として、次のようなものが挙げられる。
• 構造に基づいて情報の操作を行える。
タグの階層構造によって、Web 文書の部分特定を行い、操作ができる。HTML
が持つタグの階層構造なので 、表示されているレ イアウトに近い構造であり、
タグに関する知識を有するものであれば 、容易に操作を記述することができる。
23
• 複数の Web 文書データを、一つのグラフに対する操作として扱える。
獲得した Web 文書は全て、一つのグラフとして連結されるので、操作は一つの
グラフに対する操作として記述でき、文書間の関係や URL を意識すること無
く、操作を行うことが可能である。アンカーによるリンク関係を辿り、リンク
先の Web 文書についても操作ができる。
• CGI を用いて実現しているので、利用者は WWW ブラウザのみで個人ビュー
システムを利用できる。
また、本研究ではタグの階層構造に基づいて操作を定義したが、タグ自体はオブ
ジェクトとして扱うこととした。全てをラベル付エッジグラフで扱う場合と比較して
考えてみる。
全てをラベル付エッジグラフとして扱う場合には、全ての値は区別無く扱われ、{
文字列 } 、hタグ名i 、[属性] と言う区別はなくなる。しかし 、実際に Web 文書に対す
る操作を考えると、[属性] と { 文字列 } は区別することは、部分を特定するための手
段の一つであると考えられる。
Web 文書では表示されているのは { 文字列 } であるので、これによる部分特定が
行われるが、ラベル付エッジグラフでは、要素毎の区別がないので、[属性] と適合し
たりする場合等もあると考えられる。
そのため Web 文書内部の部分特定においては、全てをラベル付エッジグラフとし
て扱う利点は余りないと考え、タグにこれらの情報を、タグに関係する値をとして確
保させ、タグを一つのオブジェクトと捉えることとした。そして、タグに基づく階層
構造については、ラベル付エッジグラフとして扱い、Web 文書内部からタグを特定
することとした。
次に、文字列一致による切り出しを用いて、文書から部分を抽出する方法と比較
を行う。
文字列一致による方法では、入れ子構造の中に同じタグが出現したときに対応し
きれない。これに対し 、階層構造に基づいている場合には、同じタグであっても、親
と子の関係があるので特定することが可能である。つまり、構造化文書である Web
文書を扱うには、階層構造に基づいた操作を記述できる方が良いと言える。
したがって、Web 文書をタグの階層構造に基づいて部分の特定を行い、それに対
し操作を記述できることは 、個人ビュー生成の操作言語として有効であると考えら
れる。
24
5.3.2
今後の課題
今後の課題としては、次のようなものが挙げられる。
• 利用者が分かりやすく、より簡単に操作を記述するための、操作言語のグラフィ
カル化。
• リンクに関連した操作の発展。
• タグによる階層構造が、有効でない文書に対する対処。
現在は、部分の特定やさまざまな操作を記述する際に、利用者が直に操作言語を
入力することによって実現している。しかし 、これでは利用者にとっては、どの部分
に関する操作を記述をしているのか、どのような操作が行われているのか理解しに
くい。
そこで 、実際に Web 文書の構造をグラフィカルに利用者に提示し 、そこで可視
的に構造に対する操作が行えれば大変理解しやすく、操作も記述しやすくなるので、
GUI を用いた実装について考える必要がある。
25
第 6 章 終わりに
本研究では、Web 文書の持つ HTML のタグの階層構造に従って、半構造化デー
タとみなし 、その構造に基づいて個人ビュー生成の操作を定義する言語を設計した。
そして、その言語を用いた個人ビューシステムの実装を行った。
本研究の内容を要約すると、以下のようになる。
• Web 文書群からの個人ビュー生成法の提案。
• Web 文書の構造に基づいた、個人ビュー生成のための操作言語の設計。
• 設計した言語を用いた、CGI による個人ビューシステムの実装。
26
謝辞
最初に，研究全般にわたって御指導賜りました田中克己教授ならびに田島敬史助
手に厚く御礼申し上げます。
また、日頃よりさまざまなご協力をいただきました大学院自然科学研究科情報知
能工学専攻の諸先生方に感謝の意をあらわします。
さらに、本研究について御助言を頂きました田中研究室の皆様方や諸先輩方、そ
して本研究に限らずあらゆる分野にわたって御協力してしてくださった学生諸君にも
感謝の意をあらわします。
なかでも、日頃さまざまな面で多大な協力及びサポートをして頂いた田中研究室、
IN310A の方々に深く感謝の意をあらわします。
27
参考文献
[1] S.Abiteboul, ”Querying semi-structured data,” In Proc. of ICDT,volume 1186
of LNCS, pp. 1-18, Jan.1997.
[2] Y. Papakonstantinou, H. Garcia-Molina and J. Widom, ”Object Exchange
Across Heterogeneous Information Sources,” IEEE International Conference on
Data Engineering, pp. 251-260, Mar.1995.
[3] J. McHugh, S. Abiteboul, R. Goldman, D. Quass, and J. Widom, : Lore :
”A Database Management System for Semistructured Data,” SIGMOD Record,
26(3):54-66, Sep.1997.
[4] S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener, ”The Lorel Query
Language for Semistructured Data,” International Journal on Digital Libraries
1(1), XS:68-88, Apr.1997.
[5] http://www-db.stanford.edu/lore/, Lore Home Page
[6] Peter Buneman, Susan Davidson, Gerd Hillebrand and Dan Suciu, ”A Query
Language and Optimization Techniques for Unstructured Data,” In Proc. of
ACM SIGMOD, pp 505-516,jun.1996.
[7] http://www.research.att.com/ e suciu/unql-home.html, UnQL : A Query Language for Web Sites
[8] D.Konopniki and O.Shmueli, : W3QS : ”A Query System for the World-Wide
Web,” In Proc. of the VLDB’95,pp.54-65,1995.
[9] http://www.cs.technion.ac.il/ e konop/w3qs.html, W3QS HOME PAGE
28
[10] 北村泰彦, 野崎哲也, 辰巳昭治, ”スクリプトに基づく WWW 情報統合支援シス
テムとゲノムデータベースへの応用,” 電子情報通信学会「ソフトウェアエージェ
ントとその応用」シンポジウム論文集, pp.87-92,1997.
[11] M.Fernandez et al., ”A Query Language and Processor for Web-Site Management System,” In Proc. of Workshop on Management of Simistructured Data in
conjunction with ACM PODS/SIGMOD’97, 1997.
[12] 篠原 誠、田島 敬史、田中 克己,”HTML 文書の個人ビュー生成のための操作言
語の研究, 第 55 回情報処理学会全国大会 (3) 97-1N-03, pp.70-71, 1997.
29
付録
プログラムリスト
個人ビュー生成プログラム
#!/usr/local/bin/perl
require ’/usr1/people/euglena/sinohara/www/cgi-bin/jcode.pl’;
#日本語コード 変換プログラム
require ’/usr1/people/euglena/sinohara/www/cgi-bin/tree.pl’;
#HTML の解析プログラム
&cgi’header;
&cgi’decode;
foreach $tag (keys(%cgi’tags)) {
$cont = $cgi’tags{$tag};
if ($tag eq "name") { $filename = $cont; }
if ($tag eq "comment") { $search = $cont; }
}
@filenames = split(" ",$filename);
foreach (@filenames) {
&getfile($_);
&tree’parse($in,$host);
}
#各値をリセット
&tagset;
30
&analyze($search);
#入力されたコマンドの解析＆実行
&finish;
#ファイルの削除＆後処理
#####
##### これよりサブルーチン
#####
#入力された操作文を解析
sub analyze {
$commands = $search;
@command = split(/,\s*/,$commands);
foreach (@command){
if ($_ =~ s/^output\s*//){
&output($_);
}elsif ($_ =~ s/^del\s*//) {
&del($_);
}elsif ($_ =~ s/^link\s*//) {
&link($_);
}elsif ($_ =~ s/^add\s*//) {
$_ =~ s/%([^%]*)%//;
&add($_,$1);
}elsif ($_ =~ s/^rep\s*//) {
$_ =~ s/%([^%]*)%//;
&rep($_,$1);
}else{
print "<h1>書き方が違います！</h1>";
&finish;
}
}
}
31
#質問文の解析
sub query {
$quel = $_[0];
@from = ();
#部分木を指定するタグ
@select = ();
#select 節で得られた条件
@ql = split("::",$quel);
if ($ql[1] eq ""){
push(@from,"0");
}else{
@from = &search($ql[1],0);
}
@select = split("&",$ql[0]);
}
#タグに関する検索
sub search {
@result = ();
#結果を確保する配列
$search_tag = $_[0];
#検索条件
$fid = $id = $_[1];
#検索開始タグの ID
$terms = 0;
#検索条件配列のカウンター
&terms($search_tag);
#検索条件を各要素毎に格納
@temp = ();
local(%ck);
$ck{$fid} = 0;
Tag: while($ck{$fid} != 1){
if ($tag_name{$id} =~ /^($SearchTag[$terms])$/i &&
$Tag{$id} =~ m%($SearchAtr[$terms])%i) {
if(&s_match($id,$SearchStr[$terms]) == 1 &&
($id != $temp[@temp-1] || @temp == 0)) {
push(@temp,$id);
unless($SearchTag[$terms+1]){
push(@result,@temp[$T_count]);
$id = $Parent{$temp[0]};
$ck{$temp[$T_count]} = 1;
32
@temp = ();
$terms = 0;
next Tag;
}else{
++$terms;
}
}
}
@child = split(",",$child{$id});
foreach (@child){
unless ($ck{$_} == 1){
$id = $_;
redo Tag;
}
}
$ck{$id} = 1;
if ($id==$temp[@temp-1]){pop(@temp);--$terms;}
$id = $Parent{$id};
}
if (@result == 0){print "<h1>条件にマッチするものがない！</h1>\n";}
@result;
}
#タグの中身から属性値を抽出
sub atr {
$Target = $_[0];
#対象となるタグ ID
$S_atr = $_[1];
#求める属性名
$R_atr = "";
#結果の属性値
if ($Tag{$Target} =~ /($S_atr)\s?=\s?"([^"]*)"/i){
$R_atr = $2;
}
$R_atr;
}
33
#追加
sub add {
$added = $_[0];
#追加する位置を決める条件
$add
#追加されるものの条件
= $_[1];
#問合せ文の解析
&query($add);
@add_from = @from;
@add_select = @select;
#結果をそれぞれ配列に格納
&query($added);
#問合せ文の解析
@added_from = @from;
@added_select = @select;
if ($add_from[0] != 0){
foreach (@add_from){
$from = $_;
foreach (@add_select) {
if ($_ =~ /^"([^"]*)"$/){
$Add .= $1;
}else {
@Select = &search($_,$from);
if ($_ =~ /{}$/){
foreach(@Select){
$Add .= $vstr{$_};
}
}elsif ($_ =~ /\[(.*)\]$/){
foreach(@Select){
$Add .= &atr($_,$1);
}
}else {
foreach(@Select){
$Add .= $_;
}
}
}
34
}
}
}
foreach (@added_from){
$afrom = $_;
if($add_from[0] == 0){
$Add= "";
foreach (@add_select){
if ($_ =~ /^"([^"]*)"$/){
$Add .= $1;
}else{
@Select = &search($_,$afrom);
if ($_ =~ /{}$/){
foreach(@Select){
$Add .= $vstr{$_};
}
}elsif ($_ =~ /\[(.*)\]$/){
foreach(@Select){
$Add .= &atr($_,$1);
}
}else {
foreach(@Select){
$Add .= $_;
}
}
}
}
}
foreach (@added_select){
@Select = &search($_,$afrom);
if ($_ =~ /{}$/){
foreach(@Select){
35
$endstr{$_} .= $Add;
}
}elsif($_ =~ /\[(.*)\]$/){
foreach(@Select){
$Tag{$_} .= $Add;
}
}else {
foreach(@Select){
&copytag($Add,$_);
}
}
}
}
}
#削除
sub del {
$del_tag = $_[0];
&query($del_tag);
@del_from = @from;
@del_select = @select;
foreach(@del_from){
$dfrom = $_;
foreach(@del_select){
@Del = &search($_,$dfrom);
foreach (@Del) {
$child{$Parent{$_}} =~ s/($_),//;
}
}
}
}
#置換
sub rep {
$reped =$_[0];
36
$rep = $_[1];
@Reped = &search($reped,0);
if ($rep =~ /^{(.*)}/){
$rep = $1;
foreach (@Reped) {
if ($child{$Parent{$_}} =~ /^$_,/) {
$vstr{$Parent{$_}} .= $rep;
}elsif ($child{$Parent{$_}} =~ /(\d+,)*(\d+),$_/){
$endstr{$2} .= $rep;
}
$child{$Parent{$_}} =~ s/$_,//;
}
}
}
#アンカーを辿ってページを獲得
sub link {
$anchor = $_[0];
&query($anchor);
@link_from = @from;
@link_select = @select;
foreach(@link_from){
$lfrom = $_;
foreach(@link_select){
@link = &search($_,$lfrom);
foreach (@link) {
if ($Tag{$_} =~ m%href\s?=\s?"(.*)"%i){
&getfile($1);
&tree’parse($in,$host);
&tagset;
}
}
}
37
}
}
#出力
sub output {
$output = $_[0];
#検索文の解析
&query($output);
foreach(@from){
$from = $_;
foreach (@select){
if ($_ =~ /^"([^"]*)"$/){
print $1."\n";
}else{
@Select = &search($_,$from);
if ($_ =~ /{}$/){
foreach(@Select){
print $vstr{$_};
}
}elsif ($_ =~ /\[(.*)\]$/){
foreach(@Select){
print &atr($_,$1);
}
}else {
foreach(@Select){
&out($_);
print $out."\n";
}
}
}
}
}
}
sub out {
#タグ以下の部分木を出力
38
$out ="";
%cl_ck = ();
%op_ck = ();
$inp = $_[0];
$itid = $_[0];
OUT: while($cl_ck{$inp} != 1){
unless($op_ck{$itid} ==1){
$op_ck{$itid} = 1;
$out .= "<".$Tag{$itid}.">".$vstr{$itid}."\n";
}
@child = split(",",$child{$itid});
foreach (@child){
$itid = $_;
unless ($cl_ck{$_} == 1) {
redo OUT;
}else{$itid = $Parent{$itid};}
}
unless ($tag_name{$itid} =~/^(p|hr|br|img|input|option|li|dt|dd)\b/i
|| $tag_name{$itid} =~ /--/) {
$out .= "</".$tag_name{$itid}.">".$endstr{$itid}."\n";
}else{
$out .= $endstr{$itid};
}
$cl_ck{$itid} = 1;
$itid = $Parent{$itid};
}
$out;
}
########
######## タグの設定など 初期動作
39
########
#入力ファイル獲得
sub getfile {
#入力されたファイル名を獲得
$File = $_[0];
if ($File =~ m%http://(.*)%){$File = $1;}
if ($File =~ m%(.*)#.*%) {$File = $1;}
$file = $inpfile = $File;
if ($inpfile =~ /.*\/.*/){$inpfile =~ s/\//;/g;}
if ($file =~ /(.*)\/(.*(html|htm))?$/i) {
$host = $1;
}else {$host = $file;}
unless(-e "/usr1/people/euglena/sinohara/www/Study/files/".$inpfile){
system "/usr/local/bin/wget","-q","-o","hehe","-O",
"/usr1/people/euglena/sinohara/www/Study/files/".$inpfile,$file;
push(@delfile,$inpfile);
if (-z "/usr1/people/euglena/sinohara/www/Study/files/".$inpfile){
print "<h1>URL が間違っています！</h1>";&finish;
}else{
open(IN,"/usr1/people/euglena/sinohara/www/Study/files/"
.$inpfile);
}
$data = "";
while (<IN>) {
&jcode’convert(*_, ’euc’);
$_ =~ s/\n/ /;
$data .= $_;
}
close(IN);
}
$in = $data;
40
}
#終了処理
sub finish {
foreach (@delfile) {
system "/usr/bin/rm",
"/usr1/people/euglena/sinohara/www/Study/files/".$_;
}
exit;
}
#各値をリセット
sub tagset {
$tid = $tree’tid;
#タグの ID
%Tag = %tree’Tag;
#タグの中身
%tag_name = %tree’tag_name;
#タグ名
%endstr = %tree’endstr;
#閉じタグ以降の文字列
%vstr = %tree’vstr;
#タグの効果を受ける文字
%level = %tree’level;
#階層レベル
%Parent = %tree’Parent;
#親タグ
%child = %tree’child;
#子タグ
列
}
#タグに関する情報を設定
sub retagset {
$tree’tid = $tid;
%tree’Tag = %Tag;
%tree’tag_name = %tag_name;
%tree’endstr = %endstr;
%tree’vstr = %vstr;
%tree’level = %level;
%tree’Parent = %Parent;
%tree’child = %child;
}
41
#タグをコピーする
sub copytag {
$cinp = $cid = $_[0];
#コピーするタグ
$cpar = $_[1];
#親になるタグ
@par = ();
#親タグを確保する配列
$stid = $tid;
#初期入力 TID を stid に
確保
local(%cp_ck);
CP: while($cp_ck{$cinp} != 1){
unless($t_ck{$cid} == 1){
$t_ck{$cid} = 1;
++$tid;
$tag_name{$tid} = $tag_name{$cid};
$Tag{$tid} = $Tag{$cid};
$endstr{$tid} = $endstr{$cid};
$vstr{$tid} = $vstr{$cid};
if ($cid == $cinp){
$Parent{$tid} = $cpar;
}else{
$Parent{$tid} = $par[@par-1];
}
push(@par,$tid);
}
@child = split(",",$child{$cid});
foreach (@child){
unless ($cp_ck{$_} == 1) {
$cid = $_;
redo CP;
}
}
$cp_ck{$cid} = 1;
pop(@par);
$cid = $Parent{$cid};
42
}
for ($i=$stid+1; $i<=$tid; $i++){
$level{$i} = $level{$Parent{$i}}+1;$child{$Parent{$i}} .= $i.",";}
&retagset;
}
#条件文を要素毎に分割
sub terms {
$s_term = $_[0];
@SearchTag=@SearchAtr=@SearchStr=();
@searcher = split("_",$s_term);
$T_count = $count = 0;
foreach (@searcher) {
if ($_ =~ /^X/){$T_count = $count;$_ =~ s/^X//;}
if ($_ =~ /(<(.*)>)?(\[(.*)\])?({(.*)})?/) {
($2 ne "")?(push(@SearchTag,$2)):(push(@SearchTag,’.*’));
($4 ne "")?(push(@SearchAtr,$4)):(push(@SearchAtr,’.*’));
($6 ne "")?(push(@SearchStr,$6)):(push(@SearchStr,’.*’));
++$count;
}else{
print "<h1>書き方が違います！</h1>\n";
&finish;
}}
}
sub s_match {
#文字列の検索
$sinp = $sid = $_[0];
$s_str = $_[1];
$return = 0;
local(%ck);
STR: while($ck{$sinp} != 1){
if ($vstr{$sid} =~ m%.*($s_str).*%i
|| $endstr{$sid} =~ m%.*($s_str).*%i) {
43
$return = 1;
last;
}
@child = split(",",$child{$sid});
foreach (@child){
unless ($ck{$_} == 1) {
$sid = $_;
redo STR;
}
}
$ck{$sid} = 1;
$sid = $Parent{$sid};
}
$return;
}
package cgi;
sub header {print "Content-type: text/html\n\n";}
sub decode {
local ($args, $n_read, *terms, $tag, $value);
if ($ENV{’REQUEST_METHOD’} eq "POST"){
$n_read = sysread(STDIN, $args, $ENV{’CONTENT_LENGTH’});
}else{
$args = $ENV{’QUERY_STRING’};
}
@terms = split(’&’, $args);
foreach (@terms) {
($tag, $value) = split(/=/, $_, 2);
44
$value =~ s/\+/ /g;
$value =~ s/%([a-fA-F0-9][a-fA-F0-9])/pack("C", hex($1))/eg;
&jcode’convert(*_, ’euc’);
$tags{$tag} = $value;
}
}
Web 文書解析プログラム
#!/usr/local/bin/perl
package tree;
sub parse {
$in = $_[0];
$host = $_[1];
@server = split("/",$host);
$server = $server[0];
@parent = ();
push(@parent,0);
$Tag{0} = "root";
$tag_name{0} = "root";
$vstr{0} = "";
$endstr{0} = "";
$level{0} = 0;
while ($in =~ /<([^<]*)>(.*)/) {
$tag = $1;
$in = $2;
if ($in =~ /^([^<]*)</) {
$str = $1;
}else{
$str = "";
}
45
unless ($tag =~ /^\//){
++$tid;
$level{$tid} = @parent;
$vstr{$tid} = $str;
if ($tag =~ /\s/) {
if ($tag =~/(.*(href|src|codebase|action|background)
\s?=\s?")(.*)(".*)/i) {
$for = $1;
$url = $3;
$bak = $4;
unless ($url =~ /^(http|mailto)/){
if ($url =~ /^\.\//){$url =~ s/^\.//;}
if ($url =~ /^\//) {
$Url = "http://".$server.$url;
}elsif ($url =~ /^#/) {
$Url = $url;
}else{
$url = "/".$url;
$Url = "http://".$host.$url;
}
$tag = $for.$Url.$bak;
}
}
@Tag = split(/\s/,$tag);
$tag_name{$tid} = @Tag[0];
$Tag{$tid} = join(’ ’,@Tag);
if ($in =~ /<\/($tag_name{$tid})>/i) {
push(@parent,$tid);
}
}else{
$tag_name{$tid} = $tag;
46
$Tag{$tid} = $tag;
unless ($tag_name{$tid} =~ /^(hr|br|option)\b/i) {
if ($tag_name{$tid}
=~/$tag_name{$parent[$level{$tid}-1]}/i
&& $tag_name{$tid} =~ /^(li|dd|dt|p)\b/i){
pop(@parent);
$level{$tid} = @parent;
}
push(@parent,$tid);
}
}
$Parent{$tid} = $parent[$level{$tid}-1];
}else{
if ($tag_name{$parent[@parent-1]} =~ /^(dd|dt|li|p)\b/i) {
pop(@parent);
}
$endstr{$parent[@parent-1]} = $str;
if ($tag =~ /^\/($tag_name{$parent[@parent-1]})\b/i){
pop(@parent);
$str = "";
}else{}
}
}
for ($i=1; $i<=$tid; $i++){$child{$Parent{$i}} .= $i.",";}
}
47