Japan Advanced Institute of Science and Technology

(1)

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

視覚障害者用音声ブラウザのためのウェブページ構造

解析

Author(s)

加藤, 邦彦

Citation

Issue Date

2006‑03

Type

Thesis or Dissertation

Text version

author

URL

http://hdl.handle.net/10119/1965

Rights

Description

Supervisor:白井清昭, 情報科学研究科, 修士

(2)

修士論文

視覚障害者用音声ブラウザのためのウェブページ構造解析

北陸先端科学技術大学院大学情報科学研究科情報処理学専攻

加藤邦彦

年月

(3)

修士論文

視覚障害者用音声ブラウザのためのウェブページ構造解析

指導教官

白井清昭助教授

審査委員主査

白井清昭助教授

審査委員

島津明教授

審査委員

鳥澤健太郎助教授

北陸先端科学技術大学院大学情報科学研究科情報処理学専攻

加藤邦彦

提出年月年月

(4)

概要

近年のの発達により視覚障害を持つ人であっても計算機を介してさまざまな情報を得ることができるようになっている視覚障害者はページの文字情報を音声で読み上げるツールを用いてウェブブラウジングを行っているが既存のツールには知りたい情報が書かれている場所に辿りつくまでに手間や時間がかかるといった問題点が存在するしたがって本稿ではウェブページの構造解析を行いその構造に基づいてページのセグメンテーションを行い不要な情報を読み飛ばすユーザがリンクを辿ったときリンク先ページの中からユーザが知りたい情報が書かれている位置を推定しその場所から読み上げを開始するという二つのシステムの提案を行うことによってより適切に視覚障害者のウェブブラウジングを支援する新たなツールの開発を行っているそのためにを用いたウェブページセグメンテーション手法やリンクが指すページ内位置の同定手法を考案しそれらの手法の有効性を確認するため実験を行った

(5)

図目次

ウェブページの読み上げの例システム未使用

ウェブページの読み上げの例システム使用

リンクの参照位置親ページ

リンクの参照位置子ページ

セグメンテーションの様子ツリー

で検出されるセグメント

正解セグメント

で検出されるセグメント

ツリー

分割されたセグメント

マージ例処理前

マージ例処理後

セグメンテーション結果クローズテスト

セグメンテーション結果オープンテスト

ニュースページ例^{! "}より抜粋

リンク先の記事ページ例^{! "}より抜粋

後方一致例リンク元ページ

後方一致例リンク先ページ

二行分割例リンク元ページ

二行分割例リンク先ページ

言い換え例リンク元ページ

言い換え例リンク先ページ

誤同定例リンク元ページ誤同定例リンク先ページ

(8)

表目次

セグメンテーション結果クローズテスト

セグメンテーション結果オープンテスト

実験結果同定

実験結果テキスト要素数

実験結果ページタイプ別

ページ詳細

ページ別結果^#$#

タイプ別結果^#$#

ページ詳細

(9)

第章はじめに

近年のの発達によりインターネットを利用し様々なことを行うことができるようになっている視覚障害を持つ人であってもウェブを利用することによって自宅に居ながらにして様々な情報を得ることができるようになった例えばウェブショップを通して買い物をしたり掲示板を用いて他の人と情報交換を行ったりしているそれらの人々は画面の情報を音声化するソフトスクリーンリーダー音声ブラウザを用いてネットブラウジングを行っているしかしそれらのソフトは^&'(ソースのタグ情報を基にテキストを順番に読み上げているだけであるためユーザの目的の箇所まで到達するのに時間と手間がかかるまた表示されている文字情報を単純に音声化するだけではページ全体の構造を把握することは難しいよって^)*+グラフィカルユーザインターフェイスを使用することができない視覚障害者のネットブラウジングの効率的な支援ができるシステムの開発が望まれている

視覚障害者のためのツール

現在の視覚障害者支援を目的としたツールにはスクリーンリーダーや音声ブラウザなどがあるスクリーンリーダーとはウェブブラウザに限らず計算機の画面上に表示されている情報を読み上げるツールで汎用性が高く様々なアプリケーションに対応しているウェブブラウジングを行う際には一般に使用されている^+, ^-./,等のブラウザを利用しそこで表示されている情報を音声化する従って画面上に表示されている情報は一般の人が画面を通して得る情報と全く同じであるしかし視覚障害者はマウスを用いる^)*+を利用することは困難なためそれらのブラウザに対する操作はキーボードを用いて行われるその際の操作方法は各々ウェブブラウザによって異なるが大抵の場合テキスト間の移動はタブキーやカーソルキーなどを用いてクリック操作はエンターキー用いて行う代表的なものとして高知システム開発社の「^012'^3,」や日本⁺⁴社の「^5#」などがある

一方音声ブラウザとはウェブページを音声化することに特化したツールであるスクリーンリーダーとの違いはスクリーンリーダーはウェブブラウジングを行うためのブラウザを別途必要とするのに対し音声ブラウザはそれだけでウェブブラウジングを行うことができるまたテーブルの読み上げ機能やリンクを読み上げる際には声質が変わるといった^&'(タグを利用したウェブページ特有の機能が備わっているユーザインターフェイスに関してはスクリーンリーダーと同様にキーボードを用いて行われている代表的なも

(10)

のとしては日本⁺⁴社の「ホームページリーダー」が挙げられる

しかしこれらのツールは冒頭でも述べたように単純にソースに書かれているテキストを読み上げていくだけであるためページを全て読むにはまた目的の情報まで辿り着くには多大な時間と労力がかかるという問題点がありその問題点はしばしば視覚障害者のウェブ利用の妨げとなっている

提案システム

本研究では実際に視覚障害者の立場でウェブブラウジングを行っている方からの意見を頂き新しい支援システムの構築を目指した本研究で提案する視覚障害者支援システムの概要は次のようなものである

ウェブページの構造を自動解析しセグメントの検出を行いそれに基づいて不必要な箇所の読み飛ばしをナビゲートする

ユーザの目的位置が特定できる場合にはページの読み上げをその箇所から開始するこれらの機能を搭載したウェブブラウザを開発することによって視覚障害者のウェブブラウジングをより適切に支援し音声情報のみでもより効率よく支援することができると考えられる

本稿ではそれらの支援システムの提案を行いさらにそのシステムの中で使用されるウェブページセグメンテーション手法やリンクの参照位置同定の手法を紹介する章の構成は次のとおりである章では本研究の関連研究について章では本研究で提案したシステムの概要について述べる章では本研究で用いたウェブページセグメンテーション手法を章では目的位置の同定を行う手法について紹介する最後に章でまとめを述べる

(11)

第

章関連研究

音声ブラウザ

第章でも述べたように視覚障害者がウェブブラウジングを行う際にはウェブページの文字情報を音声情報に変換する音声ブラウザと呼ばれるツールが用いられる本節では音声ブラウザの中の代表的なものについて紹介する

代表的な音声ブラウザとして日本⁺⁴社の「ホームページ・リーダー」が挙げられるこのソフトにはテーブル読み上げ機能やテキストとリンクで読み上げの声を変化させる機能が備わっているルビ要素やアクセスキー機能への対応などを進めウェブアクセシビリティの標準や規格に対応したページをより良く操作できるようになっている近年多くの場面で使用される⁰⁶文書やマクロメディアの^{6 !"}コンテンツにも対応しこれらを簡単な操作で読み上げることができるまた見出しテーブルデータ入力域を追いかけるモードを提供しておりユーザが高速な操作ができるよう配慮されているこれらの操作はすべてキーボード上で行うことができるさらにテキストのみの画面ではなくレンダリングされたページも表示するためページのアクセシビリティ検査に利用することも可能である本研究では本ソフトを実際に使用しさらに視覚障害者の方にも使用して頂きその中で浮かび上がった問題点を解決するための手法を提案している

他の音声ブラウザとしてアメディア社の「ボイスサーフィン」がある前述したホームページリーダーと同様にページの読み上げをキーボード操作で行うことができ見出しへのジャンプや声の変化といった機能が備わっているこのソフトの特色として「記事本文アクセス」機能が挙げられるこの機能は新聞社のサイトで記事の本文から読み上げを行うための機能として開発され記事のタイトル部分のリンクを選択すると該当のページを読み込み記事本文の先頭を探して読み上げを始める機能である本研究においても同様のシステムの開発を行っている

視覚障害者支援に関する研究

に関する視覚障害者支援を目的とした研究としては前田らの研究が挙げられる

7 8この論文ではユーザの視覚特性に適応してウェブページの文字サイズや背景の色などを変換するシステムが示されていたユーザの視力色盲といった視覚特性に関する情報を蓄積しその情報に基づいてウェブページの文字サイズや色背景色を自動変換するシステムであるしかしこれらは弱視者を対象としたシステムで全盲のユーザを対象としたもの

(12)

となってはいない

また音声ブラウザに関する研究として浅川らの研究が挙げられる⁷ ⁸浅川らはホームページリーダーと呼ばれる音声ブラウザを開発したまたそのシステムにおいてテンキーを用いてユーザとやり取りを行うことや読み上げを行う際に^&'(タグを音声にどのように変換させるかについて紹介している現在までこのホームページリーダーの開発は続けられておりこのツールが視覚障害者のウェブブラウジングに対して有益な支援を行うことができることが実証されているしかし近年の著しいウェブ技術の進歩により^&'(

の多様化ユーザの欲求の変化といった問題が発生しており新たな技術の導入が必要となっているのも事実である

ウェブページ構造化に関する研究

ウェブページの構造認識を目的とした研究として南野らの研究がある⁷⁸南野らはタグ情報の繰り返しから適切な構造の境目を判別しそれを基に構造認識を行う手法を提案している最下層のタグの繰り返しを検出し構造化したならばその構造をグループ化しさらに上の階層で繰り返しを検出するこれをボトムアップに繰り返すことで構造化を行う繰り返しの判定には⁰マッチングを利用しており完全一致で構造化できなかったものに対して⁰マッチを行って再度構造化を試みているこの手法では⁰マッチを利用したことにより非常に計算時間がかかる場合が存在したことが報告されていたウェブブラウジングを行っている際に余りに多くの計算待ちの時間がかかるならユーザに対して適切な支援を行っているとは言えないためこの手法を視覚障害者支援にそのまま適用することは困難であるまた個人サイトのウェブページなど繰り返し構造が明示的でないものも多く繰り返し構造のみでページの構造化を行うのは困難といえるしかしながら繰り返し構造はページの構造を検出する上で重要な特徴となるため本研究でもその他の手法に加えて繰り返し構造に基づいた手法をセグメント検出に適用している

$らはの情報と視覚情報を組み合わせてページの意味構造を認識するシステムを提案している⁷⁸彼らは情報に加えて視覚情報を利用してウェブページをセグメンテーションする^9+0#アルゴリズムを導入している^9+0#アルゴリズムではタグ色サイズといった特徴に基づいてセグメントを抽出しセグメントが検出されなかった箇所では距離タグフォント色のパターンにより水平垂直両方向のセパレータを検出しているそしてそれらを組み合わせることによってウェブページを構造化している彼らは構築した構造を疑似関連フィードバック法に利用しウェブ検索性能が向上したことを実証した本研究ではこれらの構造化の手法を音声ブラウザのために利用するため彼らの手法に新たな手法を組み合わせ視覚障害者支援システムへの適用を行っている彼らの手法の目的は検索性能の向上であり文章を多く含んだウェブページがページセグメンテーションの対象となっていたが本研究では様々な種類のウェブページにおいてセグメンテーションできる手法が必要であるためさらにシステムの改良が求められる

(13)

松本らは構造や繰り返し構造を用いて構造化できないウェブページの構造化に取り組んでいる⁷⁸ 彼らはテキストセグメント階層構造が日本語の係り受け構造と類似していることに着目し値分類による構築アルゴリズムと段階構築アルゴリズムの二つのアルゴリズムを提案しているそのアルゴリズムにおいてテキスト間の係り関係推定を行う際にのパスやインデント情報言語的情報を利用しているページのセグメンテーションに関しては基本単位はブロックレベル要素とされており装飾などに用いられるインラインレベル要素は削除しているまたこの研究の目的は構造構築に焦点を当てたものであるためセグメントの抽出誤りは人手で修正している本研究ではウェブページのセグメントの検出に焦点を当てておりブロックレベル要素だけではなく文字装飾などのインラインレベル要素も利用している

$ :らはウェブページのコンテンツの視覚的類似点に基いてページの意味構造を分析する手法を提案している⁷⁸彼らは人間がレンダリングされたウェブページを見て認識する意味構造を自動獲得することを目指しており視覚的類似点において頻出するパターンを検出するためにヒューリスティックなパターン検出アルゴリズムを適用しているそのアルゴリズムによってパターンを検出した後そのパターンをサフィックスツリーで表しそのツリーを用いてクラスタリングを行っている彼らは提案手法を用いてウェブページの視覚情報に基づいた意味構造を構築できウェブページコンテンツの省略などに利用できると述べている

$!" らはウェブページの^&'(テーブルからシソーラスを抽出する手法を提案している⁷⁸彼らは様々な形の^&'(テーブルから属性と値となる部分を識別抽出しひとつのテーブルにクラスタリングするシステムを開発したそのシステムは^-アルゴリズムを用いたもので教師なし学習によってテーブルの構造を認識しその構造に基づいて属性と値の識別を行っている本研究では^&'(ソース中のテーブルをひとつのセグメント要素として利用しているがより効率的な視覚障害者支援を行っていくうえで彼らの研究で行われているようなテーブル中の属性と値の識別を行っていく必要がある

本研究ではこれらの手法を取り入れつつ新たな手法の開発を目指してきた適切にウェブページの構造解析を行うことにより視覚障害者がウェブブラウジングを行う際に発生する手間を省略し音声のみの情報でも構造の把握を容易にするといったより適切な支援ができると期待できる

(14)

第

章提案システム

この章では本研究で作成する支援ツールの概要を述べる

ウェブページのセグメントに基づくナビゲーション

既存のツールの最大の問題点は音声のみを用いてユーザに情報を伝えるため手間と時間がかかってしまうことであるそれはシステムが読み上げを行う際に^&'(ファイルのソースに書かれているテキスト等をソースの出現順序に従って単純に読み上げを行っていることに起因しているこの点はウェブページの内容理解に関しても問題を発生させるつまりウェブページ内にあるテキストを単純に読み上げるだけでは視覚障害者がページの内容を理解することは困難になり何度も同じページを開かなければならなくなるよって本研究ではウェブページを構造情報に基づいていくつかのセグメントを検出しそのセグメントを利用して読み上げの際に不必要なテキストを読み飛ばすことによって視覚障害者のウェブブラウジングに必要な手間を省略する

例えば既存のツールを使用した場合図のウェブページ中央部分にある「電話帳」にたどり着くには上部から順番にたどって行かなければならないその場合音声しか認識できない視覚障害者にとっては与えられる情報量が多くなりページがどのような構造になっているかを把握することも困難である

そこで本研究で開発するシステムは図のようにウェブページのセグメントを検出する図中の枠線が検出されたセグメントであるこのセグメントに基づいて読み上げ支援を行う本システムの手順は次のとおりである

ページのセグメントの検出を行う

読み上げの際セグメントの箇所ではまずユーザに見出しなどのセグメントの内容を示す情報を提示しその内容を読むかスキップするかを選択させる

スキップが選択されたならばそのセグメントの中に含まれるテキストを読み飛ばし次のテキストを読み上げる

以上の手順によってユーザがページの閲覧を行う際にユーザに対して与えられる情報が省略され必要な手間を減らすことができると考えられる

先ほどの例であれば図を見ると「電話帳」というコンテンツは「調べる」というセグメントの中に存在することになるこれらのセグメントに従ってページ読み上げを行う

(15)

図ウェブページの読み上げの例システム未使用

図ウェブページの読み上げの例システム使用

(16)

場合システムは「買う」という見出しを持ったセグメントがあることをユーザに知らせユーザはそのセグメントを読み上げないと選択することによって「ショッピング」「オークション」「コミック」といったコンテンツを読み飛ばすことができる同じようにして

「知る」「楽しむ」といったセグメントを読み飛ばし素早く「調べる」セグメントの中にある「電話帳」まで辿り付くことができる

これらのシステムを実装するためにはまずウェブページのセグメントを検出する必要があるそこで本研究ではシステムによって検出すべきセグメントを次のように定義したこれらの定義はページの読み上げを行う際に有効であるという観点から作成されている

意味のあるまとまり共通の属性を持つレイアウト上の固まり

要素がつ以上

短すぎるセグメントを作成したとしてもページの読み飛ばしに有効ではないセグメントの先頭に見出しがあることが望ましい

ナビゲートする際に見出しを活用できるため各セグメントは入れ子になっていても良い

ページ全体をカバーしなくても良い

ページの構造構築ではなくページコンテンツの省略を目的としているためこれらのセグメントを検出するための詳しい手法に関しては第章で述べる

ユーザの目的位置から読み上げを開始するシステム

ニュースページの記事を示したリンクをユーザがクリックした場合ユーザは新たに開かれるページの中の記事について関心があると考えることができるその際新たに開かれたページをもう一度最上部から読み上げていくことはユーザにとって余分な手間をかけさせることになる従ってユーザが知りたいと思われる箇所を特定できた場合にはユーザに通知し望むならばその箇所から読み上げを開始することによってウェブページの閲覧をより適切に支援することができる

システムの手順は以下のとおりである

親ページでクリックしたアンカー文字列と類似する文字列をリンク先である子ページの中から探索する

(17)

類似する文字列が検出された場合にはユーザに類似した文字列を検出したことを通知する

ユーザが望めばその箇所から読み上げを開始する

例として図と図を挙げる図のページの中でひとつの記事をクリックした場合既存のツールでは新たに開かれた図ページの読み上げは最上部から開始される従ってユーザは^&'(ソースの前部にある「新聞購読」「電子有料版」といった上部のコンテンツや「社説など」「朝刊から」などの左部のコンテンツを経て記事まで辿り着かなければならない

しかし本システムを使用するならばユーザが親ページにおいて記事をクリックし新たなページが開かれた時点でシステムはアンカー文字列を利用してページ内のリンクが指す箇所を探索するその探索でページ内位置が同定されたならばユーザに対して通知されシステムはその箇所から読み上げを開始するのでユーザは即座に自分が必要とする情報を得ることができる

なお同様のシステムが「ボイス・サーフィン」の中で実装されている本研究ではシステムを実際に作成し本システムの有効性を検証すると共に既存のソフトの中では検出できなかった事例を解析しそれらを検出することのできるシステムの構築を目指した

リンクが指すページ内参照位置の同定手法は第章で詳述する

(18)

図リンクの参照位置親ページ

図リンクの参照位置子ページ

(19)

第

章ウェブページセグメンテーション

節で述べたウェブページの読み飛ばしを行うシステムはウェブページのセグメントに基づいてナビゲートを行うためページのセグメント検出が重要な要素となる従ってページの構造に基づいた適切なセグメンテーションを行う必要がある

本章では本研究において使用したウェブページセグメンテーションの手法について紹介し実際のウェブページを用いて行った実験の結果を示す

提案手法

本研究で作成したシステムの大まかな流れは次のようになっている前処理^;(への変換タグの除去

構造を用いて大きなセグメントを取り出す

大き過ぎるセグメントの分割を行う

見出しと内容が分かれているセグメントのマージを行う

前処理

この説では本研究で作成したシステムの実行のために必要な前処理について述べる

への変換

本システムは^/,のモジュールを用いて実装した^/,のモジュールを使用する場合^&'(文書を^;(文書に変換する必要があるそのため本研究では^'<78 と呼ばれる^&'(文書自動訂正ツールを使用した^'<とは^&'(ソースが⁼の規定に準拠しているかを検査するものでこれを用いるとソース中の^&'(タグの整合性を検査し整合性が取れていない箇所のタグを整える^'<は以下の働きをすることにより^&'(文書の訂正を行う

開始タグと終了タグが必要な^&'(タグにおいて終了タグがないことを検知すると自動的に終了タグを適切な位置に挿入する

(20)

終了タグの出現順序が開始タグと対応していない場合には対応する位置に終了タグを修正する

また^'<には^!.オプションを使用することによって^&'(文書を^;(文書に自動変換する機能も備わっている本研究ではそのオプションを利用し^&'(文書から^;(

文書への変換を行った

タグの除去

'<による文書訂正を行う際にある特定のタグがエラーを引き起こすことが判明したため^'<による処理を行う前に以下のタグを^&'(ソースより除去した

タグの中にあるフォームスクリプト

スタイルシートを使用する部分

を用いたセグメンテーション

本研究で提案する手法はを利用したものである前処理で^'<により^&'(を

;(に変換した後^;(パーザの中に含まれているのモジュールを用いることにより^&'(文書を木構造で表現するその木構造より下記のタグを用いてセグメントを検出する

タグで囲まれている箇所をセグメントとみなす

/

それ自体をセグメントの境界とみなす

" " " " " " ",

セグメンテーションプログラムのアルゴリズムは下記のとおりであるアルゴリズムはセグメンテーションに利用するタグの探索を行う検出ステップと実際に^&'(ソースにセグメント情報を挿入する挿入ステップに分かれている

検出ステップ

ツリー

>

> $-#

(21)

を無視する

> ?

にセグメントマークを付ける

43

>

にセグメントマークを付ける

(

挿入ステップ

ツリー

> セグメントマーク

@ /

の直前に終了キューを挿入

> 43

の前後に開始終了キューを挿入

!

>(

の直前に開始キューを挿入

/

アルゴリズム中の変数を以下に説明する

ツリーにある各タグ

入れ子状態を示すもの^$-# ^,^?

のセグメントタイプ⁴³ ^, ⁽

現在のセグメントの状態を表す初期値^!

終了キューを挿入していないセグメントがある場合^/

終了キューを挿入していないセグメントがない場合^!

(22)

検出ステップでシステムはセグメンテーションに利用できるタグを検出するツリーを上から探索しそこに存在する各^&'(タグが変数に代入されとなるを検出するその際にツリーは深さ優先で探索されるとなるを検出した場合そのにセグメンテーションで使用するためのマークを付与するただし最小の単位のセグメントを検出するためタイプに関しては関数を用いて内部にタイプのタグがないかを確認するタイプのタグが存在するならば

における処理を終了し次のツリーのタグ要素をに代入する存在しなければにマークを付与するこの際に使用される関数とはをとする部分木の中にタイプのタグがないかを確認し存在すれば^$-#をしなければ^?を返す関数であるセグメンテーションに使用するタグを示すマークは各タグに属性として与えているマークが付与されたに対してはさらにのセグメントタイプを示す

変数にセグメントタイプを与えるこの作業をツリーに存在する全てのタグ要素に対して行いセグメンテーションに使用するタグ要素を全て検出する

検出ステップが終了したら次に挿入ステップを開始する挿入ステップでは検出ステップによって検出されたに対して実際にセグメントの開始と終了を示すキューを挿入するそれらのキューは^&'(ソースに影響を与えないようにコメントノードとしてツリーに挿入されるこのステップにおいてもツリーは深さ優先で探索され各タグ要素が変数に代入されるシステムは各の属性をチェックしセグメント属性を持ったに対してキューの挿入処理を行うまず変数を確認し終了していないセグメントがないかを確認する存在するならばの直前に以前のセグメントの終了キューを挿入する次にを確認しがであればの直前と直後に開始キューと終了キューをそれぞれ挿入しに^!を代入するまたがであればの直前に開始キューを挿入しに^/を代入するこれらの作業をツリーに存在する全てのタグ要素に対して行うことによって^&'(ソース上に各セグメントの情報が付与される

図図図はを用いてセグメンテーションする際の様子を図示したものであるこのツリーに対してアルゴリズムを適用した場合システムがどのような動きをするかを説明する

まず検出ステップにおいてのタグがに代入されるタグはセグメントとして使用するタグではないため次のタグ要素であるタグがに代入され同様の理由で次のタグ要素であるタグがに代入されるタグはを満たすためタグにはセグメンテーションに利用することを示す^!:属性が与えられにはが代入されるそして次のタグであるタグがに代入されるこれらの処理を繰り返しタグに対しても^!:属性が与えられにはが代入される

タグがに代入されるとまず関数を利用しその下の部分木に

タイプのタグがないかをチェックするそのようなタグが存在しないのでタグに対して^!:属性が与えられにはが代入されるそして次のタグが

(23)

body

h1 a t ext

t ext t ext

hr t ext t ext

t abl e t r t d a

t d t ext

t r

t abl e t r

i mg

t d a

t d t ext

i mg

t d dl

t ext t ext

t ext

t r t d a

t d t ext

i mg

h1 a t ext

t ext t ext

ul t ext

t ext t ext ht ml

図セグメンテーションの様子ツリー

(24)

ht ml body

h1 ( s eg: T l )

a t ext

t ext t ext

hr ( s eg: T l )

t ext t ext t abl e

( s eg: T b )

t r t d a

t d t ext

t r

t abl e t r

i mg

t d a

t d t ext

i mg

t d dl ^{( s eg: T} ^b ⁾

t ext t ext

t ext

t r t d a

t d t ext

i mg

h1 ( s eg: T l )

a t ext

t ext t ext

ul ^{( s eg: T} ^b ⁾ t ext

t ext t ext

(25)

ht ml

body

h1 ( s eg: T l )

a t ext

t ext t ext

hr ( s eg: T l )

t ext t ext

t abl e

( s eg: T b )

t r t d a

t d t ext

t r

t abl e t r

i mg

t d a

t d t ext

i mg

t d dl ^{( s eg: T} ^b ⁾

t ext t ext

t ext

t r t d a

t d t ext

i mg

h1 ( s eg: T l )

a t ext

t ext t ext

ul ( s eg: T b ) t ext

t ext t ext

BEGIN

END BEGIN

END

BEGIN

END

BEGIN

END END

(26)

に代入され同じように関数を用いるとタイプであるタグが検出されるためにタグが代入されるまで木を探索するそしてにタグが代入されたならば再び関数で入れ子が存在しないか確認しタグに^!:属性が与えられにはが代入される

さらに処理を進めタグとタグに対して^!:属性を付加し各にをそれぞれ代入するこれらの作業によってセグメンテーションに利用できるタグ個とタグを各個ずつ検出することができるそれらのタグに^!:

属性を与えたものが図である

次に挿入ステップの処理を行う検出ステップと同様にタグタグと探索し^!:属性を持つタグがに代入されるとシステムはまずを確認するは初期値の^!なのでシステムはを確認しタグの直前にセグメントの開始キューを挿入するそしてを^/に変え次のタグをに代入するそして次の

!:属性を持つタグがに代入されるとの値は^/なのでシステムはまず先ほどのセグメントの終了を示すキューを挿入するそして先ほどと同じようにタグの直前にセグメントの開始キューを挿入するこの時の値は^/のままである

続くタグの場合でもやはりまず先ほどのセグメントの終了キューを挿入するそしてがなのでタグの直前と直後に開始キューと終了キューを挿入しを^!に変えるこれらの作業を続くタグやタグタグにおいても行うこのようにしてシステムは^&'(ソースにセグメントの開始と終了の情報を付与し図で示されているようなツリーを作成するこのツリーを深さ優先で探索していくことでセグメントを検出することができる

セグメントの分割

構造を用いて大まかなセグメントを検出したら次にセグメントの分割を行うこれは最初に検出したセグメントがしばしば大き過ぎる場合が存在するためである分割の手法としてイメージによる分割とテーブル内の部分木を利用した分割がある

イメージによるセグメント分割

によるセグメント検出を行うと図中で枠線で囲まれた部分がセグメントとして検出されるしかしセグメントの定義に沿って考えるならば「オリジナル・ベストセグメント」と「レストランランキング情報」をひとつのセグメントとして「らくらく幹事さん」と「宴会・パーティを専門スタッフがサポート」を別のひとつのセグメントとして検出すべきである同様にその他のテキストに関しても適切な大きさのセグメントとして検出しなければならない図のように同じイメージが繰り返して出現するセグメントはイメージを箇条書きのアイテムとして使用している場合が多い本研究ではこのようなセグメントに対してイメージを用いた分割手法を適用しセグメントを適切な大きさに分

(27)

図で検出されるセグメント

ぐるなびより抜粋

割する

イメージによる分割とはセグメント内に存在するイメージのうち最多のイメージを検出しそのイメージを境界とみなすことによってより小さなセグメントに分割する手法である手法の手順は以下のとおりである

各初期セグメント内に存在するイメージの各個数を数える

最多のイメージが個以上であれば分割システムを開始する最多のイメージが個未満であれば分割しない

最多のイメージをセグメントの境界とみなしイメージの最初のものから次のイメージまでをひとつのセグメントとする

分割セグメントが個以上のテキストを含んでいるかを検査する

満たしていればイメージの前にセグメントの終了と開始を示すキューを配置する

満たしていなければ次のイメージを先頭とするセグメント分割処理を行う

の作業を繰り返す

(28)

の作業において分割セグメントが作成された場合初期セグメントのキューを削除する

図正解セグメント

最初に述べた図のセグメントの場合イメージによる分割手法を適用するとまず見出しの前にある丸のイメージが最多のイメージとして検出されるそして最初のイメージから次のイメージまでの間にあるテキスト「オリジナル・ベストセレクト」と「レストランランキング情報」をひとつのセグメントとするそしてこのセグメントが定義に合っているかを検査し合っているのでセグメントとして^&'(ソースにセグメントの開始と終了を示すキューを配置するこの手順を繰り返すことによってそれ以後の個のセグメントも検出することができを用いたセグメンテーションではひとつの大きなセグメントとして検出されていたものが図に示されているような個の適切な大きさのセグメントに分割される

テーブル内の部分木を用いたセグメント分割

図で示されているセグメントはに基づいて検出されたものであるこのセグメントも「便利なツール」と「ビジネス」という見出しを持った二つのセグメントに分割する必要があるしかしこれらのセグメントにはイメージが使用されていないため前述のイメージによるセグメント分割手法は適用できない

イメージを含まないセグメントを分割する手法として部分木の類似度を利用したセグメント分割手法を導入したこれはタグ内のタグもしくはタグを

(29)

図で検出されるセグメント

より抜粋

とするの部分木を取り出しそれらの類似度が閾値以上であればの単位で分割する手法であるシステムの手順は以下のとおりである

タグによってセグメンテーションされたセグメントを検出する

タグをとするタグの部分木を作成

作成した部分木から共通部分木を取り出す

共通部分木と各テキストの部分木の最小のものと比較

の類似度が閾値以上であれば各部分木をひとつのセグメントとして分割する

の類似度が閾値未満であればタグをとするタグの部分木を作成し同じ処理を繰り返す

共通部分木の抽出にはデータマイニングツールの^{A,@7 8}を用い全ての部分木に共通する木を抽出するそれらの共通部分木のうちノード数が最大の部分木を用いて類似度を計算するここで述べている類似度とは

最大の共通部分木のノード数

取り出した部分木のうち最小の木のノード数として定義されたものである閾値に関してはに設定した

例として図と図のページ例を示すを用いたセグメンテーションではテーブル部分に囲まれたセグメントとして図のようなセグメントが検出されるしかしセグメントの定義で考えると図に示されているようなセグメントが適切なセグメント

(30)

tr

td ^small nobr a

nobr a nobr a nobr a nobr a nobr a

td ^small a

a

font a a

a

nobr a nobr a

図ツリー

図分割されたセグメント

(31)

であるといえるこのような場合においてテーブル内の部分木を利用した分割が行われるこのテーブル内の構造は図のようになっているタグをとした部分木を作成すると

の形で出力される^A,@を用いこの二つの部分木の最大共通部分木を取り出すと

が取り出される従ってこの二つの部分木の類似度は共通部分木のノード数

取り出した部分木のうち最小の木のノード数 ^>

>

と算出され類似度が閾値の以上であるので各部分木はひとつのセグメントとして分割されるテーブル全体で定義されたひとつの大きなセグメントが図に示されているような適切な大きさのセグメントに分割される

この分割手法はテーブル内の共通部分木を取り出して類似度を判定することによってテーブル内に存在する繰り返し構造を検出する従って本手法は南野らの研究⁷⁸で示されていた繰り返し構造を利用したものである

セグメントのマージ

ここまでに検出されたセグメントは最小の単位のセグメントでありリストタグのようなヘッダ部分を含まないセグメントが存在するしかし本研究の提案システムではヘッダ部分はセグメントの内容を示す重要な手がかりとみなしヘッダ部分が存在するセグメントではヘッダ部分の読み上げを行う従ってセグメントとそのヘッダがつのセグメントになっていないときそれらをマージする必要が生じる本研究で用いた手法は次のようなものである

ヘッダ候補となるテキストを検出する

そのテキストの後方に隣接するセグメントがあるかどうかを探索する

ヘッダ候補とセグメントの間で次の条件を満たす場合それらは隣接しているとみなす

テキストが存在しない

属性を持つイメージが存在しない

属性を持たないイメージが個以下

セグメントが存在すればテキストとセグメントをマージする

(32)

図マージ例処理前図マージ例処理後

中日新聞ホームページより抜粋

ヘッダ候補となるテキストを検出するために以下の特徴を利用している

" " " " " "

"

マージの例として図とのウェブページを示す図で示されているセグメントは^{24 !}セグメンテーションの際にタグにより検出されたセグメントであるこの例を見ても分かるとおりリストタグによって箇条書きにされているものはヘッダを含まない従ってヘッダとなる「ニュース速報」のテキストと隣接するセグメントをマージし図に示されているようなセグメントにしなければならないこの例の場合

「ニュース速報」というテキストはタグによって修飾されているためシステムはこのテキストをヘッダ候補として認識する次に隣接するセグメントの探索を行いタグによるセグメントを検出するその際ヘッダ候補とセグメントの間にテキストやイメージが存在しないかチェックし存在しないのでシステムはヘッダ候補とセグメントをマージし図のようなセグメントを新たに作成する

(33)

実験

評価方法

評価は人手で作成した正解セグメントとシステムによって検出されたセグメントとの比較によって行ったセグメント情報が付与された^&'(ソースよりテキストとイメージのみを取り出しシステムによって付与されたセグメントの位置が正解セグメントの位置と一致しているかを判定したこれは音声ブラウザが読み上げるのはテキストとイメージであるためでこのようにすることによってセグメントのキューが挿入された位置がタグの間で前後したとしても正しく判定することができるさらにイメージに関しては属性を持つイメージのみを取り出しているこれは音声による読み上げの際に属性を持たないイメージはユーザに対して有用な情報を与えることはできないという仮定に基づいている判定はセグメントの開始位置と終了位置が一致しているかどうかを判定した完全一致評価と開始位置のみの一致を判定する半一致評価を行っている完全一致だけでなく半一致評価を行った理由は本システムの主な目的がページの構造化ではなく音声ブラウザにおけるナビゲーションであるためであるつまりページの読み上げをナビゲートする際にはセグメントの開始位置が重要であり終了位置は他のセグメントと重複していない限りは流動的であっても良いという考えに基づいている

使用データ

実験はクローズテストとオープンテストの種類を実施し各テストはのウェブページを用いて行った

クローズテストに用いたウェブページの内訳はポータルサイトページニュースサイトページショッピングサイトページ企業・公的機関のページページ個人サイトページである各ページに対し正解データとしてセグメントの開始と終了箇所を示すコメントを人手で^&'(ソースに挿入したその際に作成された正解セグメントはレンダリングされたページに基づいて判断されているシステムの作成に当たりこれらの個のページに対し実験を行いエラー解析を行うことでシステムの改良を重ねた従ってこれらのウェブページはクローズドなデータといえる

クローズテストとは別にオープンテストも実施したオープンテストに使用したページの内訳はポータルサイトページニュースサイトページ企業・公的機関のページページ個人サイトページであるこれらはシステム開発者ではない第三者によって収集され本研究のセグメントの定義に沿って正解セグメントが付されたものである第三者テストデータを収集することによりシステムに有利なページだけを偏って集められることがないようにした

(34)

実験結果

クローズテスト

20 25 30 35 40 45 50 55 60 65 70 75

SYS4 SYS3

SYS2 SYS1

precision recall SP(precision) SP(recall)

図セグメンテーション結果クローズテスト

表セグメンテーション結果クローズテスト

#$# B B B B B

(35)

オープンテスト

20 25 30 35 40 45 50 55 60 65 70 75

SYS4 SYS3

SYS2 SYS1

precision recall SP(precision) SP(recall)

図セグメンテーション結果オープンテスト

表セグメンテーション結果オープンテスト

#$# B B B B B

(36)

図・表はクローズテストの図・表はオープンテストの各システムの

/,!と^,等のページの平均を示したものである表の中の^!:は正解したセグメント数の平均^/,!は自動検出されたセグメントのうち正解セグメントと一致したものの確率であり^,は正解セグメントのうちシステムがどれだけのセグメントを完全に検出できたかを示す確率となるまた^#0とはセグメントの開始位置のみの^/,!と

, を算出したもの^,!!とは自動検出されたセグメントのうち正解セグメントをまたいでいるものの確率を示したものであり自動検出セグメントのエラー率となる

左の行に書かれている^#$#は各手法を導入したセグメンテーションシステムの種類を指している^#$#は最も単純な^{24 !}のセグメンテーションシステムである

項参照^#$# は^#$#にイメージ分割手法項の「イメージによるセグメント分割」

参照を^#$#はイメージ分割に加えてテーブル分割手法項「テーブル内の部分木を用いたセグメント分割」参照を付加したものである最後の^#$#は^#$#にマージシステム項参照を付加したもので本研究で作成したシステムの最終版となる

実験結果の詳細は付録を参照していただきたい付録ではの個々のウェブページにおける各システムの結果とページのタイプ別に結果をまとめた表を載せた

考察

実験結果より本研究で作成した自動セグメンテーションシステムが一定の成果を挙げていることが確認できた表を見るとクローズテストでは平均で約半数の^Bのセグメントを完全に取り出すことができているこの^Bという数字はあまり良いものとは言えないが開始位置だけで言えば^Bのセグメントが一致しているためこれらのセグメントに関しては終了位置をより適切に検出することのできるセグメンテーション手法を適用することによって完全に検出できるようになる一方^/,!の結果を見るとクローズテストでは半一致の結果がオープンテストでは完全一致と半一致のどちらの結果も分割手法を導入することで^#$#の結果より低くなっているこれは分割によって検出されるセグメントの総数が増加したことが原因と考えられるしかし^,!!は ^B以下に収まっていることからシステムが検出したセグメントが複数の正解セグメントにまたがっていることはほとんどなく更なる手法の改良によって本システムの精度を向上させることができると考えられる

#$# から^#$#までの結果の推移を見るとクローズテストにおいては単純な²

4 !の^#$#にイメージ分割テーブル分割マージの各手法を導入することによって精度が向上していることが確認できる従って本研究で作成したセグメンテーション手法の有効性は明らかであるしかしオープンテストでは^#$#の結果が^#$# の結果より低下していることが確認されたここからテーブル分割手法の改善が必要なことが分かる本手法では行っていないが各テキストにかかるタグの出現順序に関する情報に関して類似度を用いる際には南野らの研究で行われているようなタグをテキストの属性として置き換えることを行う必要もあり将来的にはそのような手法も加えていかなければならない

(37)

と思われるまた分割手法の導入によって^/,!が低下することを防ぐため分割されたセグメントが適切かを判定する際に分割セグメントに特化した判定基準を設ける必要がある

また本研究で用いた正解セグメントは入れ子を許しているがシステムが検出するセグメントは入れ子を許していない従って今後は現在までに開発したシステムの再帰的適用を考慮に入れより適切なセグメントの検出を目指す

その他にも本研究において作成したシステムは^&'(ソースにあるタグ情報のみを使用してセグメンテーションしているが今後はテキストの言語情報やコンテンツ間のレイアウト情報といった現在使用していない情報を利用しヘッダ部分の特定や現行の²

4 !のシステムでは検出することのできないセグメントの検出を行っていきたいまたウェブページのセグメンテーションは本研究の目的である視覚障害者支援だけではなく情報抽出や情報検索といった様々なシステムに有用なものである従ってさらなる精度の向上や汎用性の向上を図っていきたいと考えている

Japan Advanced Institute of Science and Technology