論文

DBSJ Letters Vol.4, No.1

系列順に長期保存するため，ページ更新時に上書きを行う
Web アーカイブにおける時系列閲 サーチエンジンと異なる保存機能を必要とする．なお，我々
覧：単一コレクションへの適用は，長期保存・大容量保存の問題に関して，階層型ストレー

Browsing Algorithm with Time Consis- ジシステムを用いる手法の提案と評価を行った [5]．
本稿では，時系列管理に焦点を当て，アーカイブ運用におtency in Single Collection of Web Archive ける時系列一貫性をもつ閲覧手法を提案する．一般に，デー
小城 正士1
Masashi KOJO
KAWANO

タベースにおけるトランザクションの一貫性は，個々のイベント発生時刻に基づいて議論する．そこで，提案アルゴリズムは，収集時に巡回できたデータ集合である個々のコ
廣瀬 信己2
河野 浩之3
レクションを一貫性があるものと定義し ，各データ間の閲
Nobuki HIROSE
Hiroyuki 覧可能性を，データ更新時刻により求めるものである．

2.

Web アーカイブの現状と問題点近年，Web 情報の文化的・社会的価値に着目し，それらを保Web アーカイブは，バルク収集と選択的収集のアプロー存する試みが世界各国で進められている．我が国では，国立国会チに大別される．バルク収集とは一国全体や世界全体の Web
図書館インターネット 資源選択的蓄積実験事業 (WARP: Web
情報を一括収集する方法であり，選択的収集とはサイト単ARchiving Project) による Web アーカイブ構築が進められ
位や資料単位でセレクションし ，著作権処理を行い収集すているが，データ収集・保存・運用に多くの技術的課題が存在する．
る方法である．以下，代表的 Web アーカイブのデータ管理
本論文では，収集データの時系列管理に焦点を当て，Web アー手法を紹介し ，その閲覧における問題点を述べる．
カイブコレクション閲覧における時系列一貫性のあるリンク参照を，コレクションの収集期間と閲覧対象期間との関係から決定するアルゴリズムを提案する．

2.1

In many countries, web archive projects havebeen promoted continually for preserving culturaland social properties on web systems. In Japan, aproject called WARP (Web ARchiving Project) in
the National Diet Library was promoted, we have
many technical issues of archiving systems such ascollection, preservation and management of web
archive data. In this paper, we focus on the technical issues of the time series management of web
archive collections, and propose an algorithm thatidentifies valid navigation of links preserving theconsistency while browsing web archive, which isbased on the relationship between collecting andbrowsing periods.

1.

はじめにWARP

我が国の国立国会図書館が推進する「国立国会図書館インターネット資源選択的蓄積実験事業 (WARP: Web ARchiving Project) 」は1 ，電子雑誌・政府ウェブ・協力機関ウェブのコレクションからなり，著作権等を処理しながら，選択的収集を行っている．2004 年 6 月 30 日現在，電子雑誌
1,108 タイトル，政府機関 10 タイトル，協力機関 598 タイ
トルを所蔵する．今後，法制度面について国立国会図書館長の諮問機関である納本制度審議会を経た後，立法措置が行われ，2006 年より日本国の Web に対象を広げた収集を開始する予定である [3]．
WARP は，一定期間ごとに Web ページを収集し ，収集日毎にコレクションを形成し，ソースファイルのリンク先アドレスをアーカイブ内のアドレスに書き換えることで，収集サイトの状態を保存する．そのため，収集日以外のサイト状態は保存されない．また，収集対象コンテンツ以外は収集しないため，他サイトへのリンク先の内容等も保存されない．その他，書き換えの困難なファイル (PDF，Flash等) に対応出来ないこと，原本性保証などの問題がある．

現在，インターネットの Web システム上に流通する情報
量は，表層部に 167TB 以上，深層部に 91,850TB 以上存在すると推定される．しかし ，知識流通基盤となるインターネット 上の多様な情報は，従来の出版物に比べ，空間的・ 2.2 Internet Archive
時間的に情報内容と存在が安定しない問題点を抱える．そInternet Archive2は ，現在公開され ている最大の Web
こで，Web 情報を文化資産として体系的に蓄積し，将来にアーカイブである．ページ内リンクのクリック時に，Java渡って長期保存するウェブアーカイブ (Web Archive) プロ
Script によるアーカイブ内のアドレス付加を用いている．なジェクトが，各国国立図書館等を中心に推進されている [1]．
お，指定アーカイブのアドレスにデータが存在しない場合，プロジェクト遂行に関わる主要技術は，Web データ収集・
図 1(a) のように，その時点以前で最も近い時間のデータを検索・保存に大別されるが，単調増加する Web ページを時表示する．そのため，意図したデータと全く違うデータが1 正会員 日本 IBM表示されることがある．
2 非会員

国立国会図書館総務部
南山大学数理情報学部情報通信学科kawano@it.nanzan-u.ac.jp

3 正会員

1

1 http://warp.ndl.go.jp/

2 http://www.archive.org/

日本データベース学会 Letters Vol.4, No.1

論文
また，ページ間のリンク参照を繰り返すと，時間を逆行する閲覧が生じる．例えば，図 1(b) において，12/20/12:00 に収集された xxx.html(1) 内の yyy.html へのリンクを参照した時に，同時間に収集されたデータが存在しない場合，最も近い 12/20/6:00 の yyy.html(2) が開かれる．ここで，(1) に戻るつもりで xxx.html へのリンクを参照しても，(1) と (2)は同時間内にないために，(2) 以前で最も近い 12/20/0:00の (3) が開かれてし まう．以後同様に，ページ間のリンク参照を繰り返すと，(3) → (4) → (5) の時間逆行の閲覧が生じる．

DBSJ Letters Vol.4, No.1
収 集 さ れ て い る の で ，時 間 軸 上 で 12/22/00:00 か ら
01/11/23:59 までを指定した場合は Ver. 9 が，01/11/00:00以降を指定した場合は Ver. 10 が表示される．また，ページ間のリンクを開く場合には，時間軸上の位置によって開くバージョンが 異なるため，図 2(c) において，xxx.htmlから yyy.html へのリンクを開く際に，閲覧している時間が，yyy.html の Ver. 9(12/22) と Ver. 10(01/11) の中間点である 01/01/00:00 より前の時は Ver. 9 を，それ以降の時は Ver. 10 を開く問題などが生じる．

3.

時系列一貫性アルゴリズムの提案

本稿で焦点を当てる時系列管理は，同一 URL のデータが更新された時に，異なるバージョンとして蓄積されたコンテンツを管理・運用する技術であり，アーカイブが飛躍的に増大するにつれて重要となる課題である．
前述のように，既存の Web アーカイブは，収集コレ クションの閲覧単位として，収集時の状態再現を行っている
図 1: Internet Archive の手法
が，実際のユーザーによる閲覧では，収集日以外のサイト
Fig. 1 Format in Internet Archive
状態やサイト間のリンク関係に基づく閲覧要求が生じると予想される．したがって，単一のコレクション内に限定せ2.3 NWA
ず，アーカイブ全体にわたり時系列的な一貫性の高い閲覧アルゴ リズムが重要である．
NWA(Nordic Web Archive) は，北欧各国の国立図書館
なお，一般のデータベースにおいて，その一貫性は，トを主体としたプロジェクトである3 ．NWA Toolset[2] のブランザクション発生時刻に基づいて決定している．よって，ラウザは，同一アドレスのデータが複数バージョンある場
同様に，Web アーカイブにおいても，収集コレクション内合，図 2(a) のように，時間軸上のポインタとして表示し ，の個々のデータ更新時刻から，異なる時点の閲覧イメージ指定日時の閲覧バージョンを表示する．また，軸上のポイの決定が可能である．ただし，コレクション間では，その時ンタ以外を指定した場合，その点より前の一番近いバージョ
点の実際の Web ページの状態が不明であり，閲覧イメージンを表示する．
を簡単に決定できない．そこで，収集時に巡回できたデータ集合であるコレクションを一貫性があると定義し ，データ間の一貫性を決定することを提案する．なお，一貫性を決定するパラメータとして閲覧対象期間を用いることにする．

3.1

収集コレクション内の一貫性のある閲覧

本稿で用いるパラメータを表 1 に示す．なお，コレクショ
ン Sn は，n 回目の収集で集められたデータがアーカイブされた時刻順に並んでいるものとする．

Sn = {P0 (n) · · · Pi (n)Pj (n) · · ·}TA (P0 (n)) ≤ · · · ≤ TA (Pi (n)) ≤ TA (Pj (n)) ≤ · · · (1)SB はアーカイブされたデータの内，閲覧対象期間 [Ts , Te ]内において閲覧可能なデータの集合を表す．これに含まれるデータは，期間内において，単独で全て閲覧可能であるが，データ間のリンクに基づく閲覧は，[Ts , Te ] の状態に依存する．データ Pi (n) からデータ Pj (m) への閲覧が可能であるとき，その状態を
Pi (n), Pj (m) で表し ，相互に閲覧
図 2: NWA の手法が可能である状態を Pi (n), Pj (m)(Pi (n), Pj (m) かつ
Fig. 2 Format in NWA
Pj (m), Pi (n)) で表す．また, 集合 SB における可能な閲
覧状態の集合を L(SB ) で表す．
例 え ば ，図 2(b) に お い て ，ペ ー ジ xxx.html は
ところで，Web ページは時々刻々更新され，ある時間内
12/22/08:17 に Ver. 9 が ，01/11/13:15 に Ver. 10 がで意図していた閲覧と別の時間内で意図していた閲覧は，内3 http://nwa.nb.no/
容更新に応じて異なると考えられる．そのため，その時点
2

日本データベース学会 Letters Vol.4, No.1

論文

DBSJ Letters Vol.4, No.1

表 1: 各種パラメータ
Table 1 Parameters
Crawling[ts (n), te (n)]ts (n)te (n)

Ë::::

Archive Datai:
Pi (n):

n 回目の収集実行期間
開始時刻
終了時刻
収集されたコレクション
アドレス
n 回目の収集において保存された i のデータ．
(存在しない場合は φ)

図 3: コレクション内の一貫性
Fig. 3 Consistency in a Collection

TA (Pi (n)): Pi (n) が Archive された時刻
TU (Pi (n))
: 収集時に取得された Pi (n) の最終更新時刻
Browsing[Ts , Te ]: 閲覧対象期間
Ts: 起点
Te: 終点Pi (n), Pj (n) : Pi (n) から Pj (n) への閲覧Ë: Archive の中の閲覧可能なデータの集合
Ä(Ë ): 集合 Ë における一貫性のある閲覧の集合

を 一貫性があると 定義し たのと同様，Crawler が 収集を行った時間を閲覧対象期間に含む場合，その時点から次に分かっている更新時刻までの間の i のデータを，Pi (n)と する ．つまり，デ ータ Pi (n) の Determinable な 期間
[ TU (Pi (n)), TA (Pi (n)) ] が [ Ts , Te ] に含まれるとき，その後にくる Indeterminable な期間 [ TU (Pi (n)), TU (Pi (n+1)))
においても，Pi (n) を閲覧可能とする．また，閲覧可能なデータが存在しない期間は，その期間内において i のデー
タはアーカイブされていないものとして，閲覧不可とし，iへの閲覧は Not Found を返すものとする．の正確な Web の状態は，アーカイブデータに基づいて再現出来ない．しかしながら，Crawler により収集されたコレクションは，少なくとも Crawler の収集時間範囲に存在し得た正当な状態であり，そのリンク構造は収集時間内において一貫性があると言える．よって，図 3 のように Crawlerによって収集されたコレクション Sn を，その収集が行われた時間内 [ts (n), te (n)] において一貫性がある (Consistent)と定義し，Sn 内のデータ間の閲覧状態は全て正当 (閲覧可能) と考える．

図 4: 閲覧可能なデータ
Fig. 4 Browsable Data
L(Sn ) = {Pi (n), Pj (n)} , (∀i, j Pi (n), Pj (n) ∈ S n )(2)
例えば ，図 4 では ，Pi (n), Pi (n + 1) の Determinable
以下，このコレクションにおける一貫性のある閲覧状態の集合を基準に，個々のデータ間に対する閲覧の一貫性を，閲 な 期 間が [Ts , Te ] に 含 まれ て い る の で ，それ ぞ れ 期 間[TU (Pi (n)), TU (Pi (n + 1))),[TU (Pi (n + 1)), Te ] において閲
覧対象期間 [Ts , Te ] との関係を用いて議論する．
覧可能としているが，Pi (n − 1) は Determinable な期間が含まれていないので閲覧不可であり，期間[Ts , TU (Pi (n)))
3.2 閲覧可能なデータにおいて i は Not Found である．
閲覧対象期間 [ Ts , Te ] を指定した場合，ブ ラウザ上で以上，閲覧対象期間内での個々のデータの閲覧可能性を閲覧されるデータは，その期間内に存在した可能性のある 論じた．しかし，図 4 のように，[Ts , Te ] を広く取った場合，データでなければ ならない．アーカイブ された Pi (n) が ， 一つのアドレスについて閲覧可能なデータが複数存在する．
その時点での i のデータであったと確実に言える期間は， そこで，複数ある閲覧可能データ中から参照するデータをそのデータの最終更新時刻から収集時刻まで ，つまり期 自動的に決定するために，データ間での一貫性のある閲覧
間 [ TU (Pi (n)), TA (Pi (n)) ] である．この期間を “Deter- を定義する．
minable” な期間と呼ぶ．TA (Pi (n)) から次の TU (Pi (n + 1))
までの間は，収集が行われておらず，更新の有無が不明で 3.3 データ間での一貫性のある閲覧あるために，その間の i のデータは Pi (n) であると言い切れない．よって，この期間を “Indeterminable”な期間と呼[ Ts , Te ] 内でデータ Pi (n) から j へのリンクをクリック
ぶ．この期間のうち，少なくとも一部 (もし くは全部) の期 時に，データ Pj (m) の閲覧が妥当であるならば ，閲覧可能間においては，i のデータは Pi (n) であったと推測される. 状態の集合 L(SB ) に状態 Pi (n), Pj (m) を含める．以後，ここで，前述の議論で，収集時に収集したコレクション 様々な状態の L(SB ) を示す．ここでは，誌面の制約上，単3

日本データベース学会 Letters Vol.4, No.1

論文

DBSJ Letters Vol.4, No.1

一コレ クションの場合を記述するが，複数コレクションについても [6] で議論を行っている．
単一コレクションに収まる場合
単一コレクションに収まる場合とは , [ Ts , Te ] が n−1, n+1回目の全てのコレクションデータの Determinable な期間を含まず，全ての Pi (n − 1), Pi (n + 1) が閲覧不可な状態を表す．Pi (n) の閲覧可能性は [Ts , Te ] の状態によって異なる．
まず，相互リンクを持つ二つのデータ Pi (n) と Pj (n) 間のリンクについて考えるが，その際に注目すべき点は，各データの更新時刻 TU (Pi (n)), TU (Pj (n))(常に TU (Pj (n)) <TU (Pi (n)) であるとする) と [Ts , Te ] の関係である．それぞれの間で成り立つ関係は図 5 で表される．

4.

むすび

本稿では，Web アーカイブコレ クション閲覧に際して，時系列一貫性のあるリンク参照を，コレクションの収集期間と閲覧対象区間との関係から決定するアルゴ リズムを提案した．また，提案手法により，既存の Web アーカイブの幾つかの問題を解決できることを述べた．今後，実際のアーカイブへの実装，提案手法の特性に基づく Web データ収集戦略の決定などが必要である．

[謝辞]
本稿の一部は，文部省科学研究費 (16016248) の研究成果による．

[文献][1] Abiteboul, S., Cobena, G., Masanes, J., and Sedrati, G.,“A First Experience in Archiving the French Web,” Research and Advanced Technology for Digital Libraries,
Springer, 2002.

図 5: 閲覧対象期間と最終更新時刻の状態
Fig. 5 Statuses in Browsable Duration and Last ModifiedTime
Case A. Ts < Te < TU (Pj (n)) < TU (Pi (n))
閲覧可能なデータがないので，i, j 共に Not Found.
SB = {φ}[2] Hallgrimsson, P. and Bang, S., “Nordic Web Archive,”
3rd ECDL Workshop on Web Archives, 2003.8, (online),available from http://nwatoolset.sourceforge.net/docs/
nwa@ecdl2003.pdf, (accessed 2005.5.9).
[3] 廣瀬信己, “国立国会図書館におけるウェブ・アーカイビン
グの実践と課題,” 情報処理学会研究報告，Vol.2003, No.51，pp.95-111, 2003．

(3)[4] 河野浩之, 川原稔, “Web 検索におけるテキストマイニング ,”Case B. Ts ≤ TU (Pj (n)) ≤ Te < TU (Pi (n))
人工知能学会誌, Vol.16, No.2, pp.212-218, 2001.
Pj (n) は閲覧可能だが，i の閲覧可能なデータがないため，[5] 小城正士，廣瀬信己，河野浩之，“Web アーカイブにおけるPj (n) から i への閲覧は Not Found ．
SB = {Pj (n)}, L(SB ) = {φ}(4)Case C. Ts < TU (Pj (n)) < TU (Pi (n)) ≤ Te
i と j 共に Pi (n), Pj (n) が閲覧可能である．また，i の更新が行われているので，Pj (n) の意図していた参照と異なっている可能性があるが，i のそれ以前のデータが閲覧不可であるので，Pi (n) を閲覧するのが最も妥当である．
SB = {Pi (n), Pj (n)}, L(SB ) = {Pi (n), Pj (n)}(5)

Case D. TU (Pj (n)) ≤ Ts < TU (Pi (n)) ≤ Te
Case C. と同様．
SB = {Pi (n), Pj (n)}, L(SB ) = {Pi (n), Pj (n)}(6)

Case E． TU (Pj (n)) < TU (Pi (n)) ≤ Ts < Te
Pi (n), Pj (n) 共に閲覧可能で，更新も行われていないので，相互に閲覧可能である．
SB = {Pi (n), Pj (n)}, L(SB ) = {Pi (n), Pj (n)}4

長期ストレージシステムの提案,” DBWeb2004，Vol.2004,
No.14，pp.33-40，2004．

[6] 小城正士，廣瀬信己，河野浩之，“ Web アーカイブにおける時系列参照アルゴ リズムの提案,” DEWS2005，2005．(online), available from http://www.digitalcity.gr.jp/˜satoh/
DEWS2005/procs/papers/6A-o4.pdf, (accessed 2005.5.9).

小城 正士 Masashi KOJO
日本 IBM．2005 京都大学大学院情報学研究科博士前期課程修了. 2003 京都大学工学部情報学科卒業．日本データベース学会会員.
廣瀬 信己 Nobuki HIROSE
国立国会図書館総務部．1997 日本長期信用銀行金融商品開発部．1997 東京大学経済学部経済学科卒業．日本図書館協会個人会員．
河野 浩之 Hiroyuki KAWANO
南山大学数理情報学部教授．1997 京都大学大学院情報学研
究科システム科学専攻助教授．1990 京都大学大学院工学研
究科数理工学専攻博士後期課程研究指導認定退学．情報処
理学会，電子情報意通信学会など 所属．

(7)
日本データベース学会 Letters Vol.4, No.1