Extracting Logical Hierarchical Structure ofHTML Documents Based on Headings
Tomohiro Manabe and Keishi Tajima
Graduate School of Informatics, Kyoto Univ.
Sakyo, Kyoto 606-8501 Japan{manabe@dl.kuis, tajima@i}.kyoto-u.ac.jp

Background• Understanding of structure in web pages isimportant for many applications• Web search• Automatic summarization of web pages• Web information extraction

2

Structure in web
pages• Web pages containvarious types ofstructures

Structure in web
pages• Web pages containvarious types ofstructures• Layout structure,

Header

Menu

Content bodyStructure in web
pages• Web pages containvarious types ofstructures• Layout structure,list or table structure, …

Header

Menu

Content body
Item 1
Item 2Item 3

Structure in web
pages• Web pages containvarious types ofstructures• Layout structure,list or table structure, …

• We focus on hierarchicalheading structure• 78% of pages contain it

Header
Big heading
Small heading

Menu

Small heading

Content
body
Big heading
Item 1
Item 2Item 3

Hierarchicalheading structure

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

7•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

8•Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

9•Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

10•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

11•Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment• Block• A segment with its heading• may contain each other

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

12•Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment• Block• A segment with its heading• may contain each other

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

13•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment• Block• A segment with its heading• may contain each other

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

14•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Hierarchicalheading structure• Heading• Topic description of a segment• Block• A segment with its heading• may contain each other• Hierarchical heading structure• composed of these
15 headings and blocks

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Importance ofheading structure
2010
Mar search engines:
Search• Traditional• This page contains both words• Extracts this page incorrectly• Heading-aware Bool. retrieval:• “March” occurs under “2012”,
not “2010”• Can reject this page correctly

16

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Importance ofheading structure2010 Mar
Search• Traditional search engines:• This page contains both words• return this page incorrectly• Heading-aware Bool. retrieval:• “March” occurs under “2012”,
not “2010”• Can reject this page correctly

17

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Importance ofheading structure2010 Mar
Search• Traditional search engines:• This page contains both words• return this page incorrectly

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History• Heading-aware engines:• “Mar.” occurs under “2012”,
not “2010”• Will not return this page

18

2010
• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Problem to be solved• Hierarchical heading structure is useful• It seems easy to extract the structure

19

Problem to be solved• Hierarchical heading structure is useful• It seems easy to extract the structure• In fact, it’s NOT easy
Our research problem:
Extraction of hierarchical heading structure20

Hierarchical heading structure extraction is
NOT easy• HTML has tags for descripting headings• H1 to H6 and DT tags

21

Hierarchical heading structure extraction is
NOT easy• HTML has tags for descripting headings• H1 to H6 and DT tags

• These tags are not always used or used incorrectly

In our data set:
• Only 32% of headings were tagged by these tags
• Only 67% of components tagged by these tags were headings

22

Hierarchical heading structure extraction is
NOT easy• HTML has tags for descripting headings• H1 to H6 and DT tags

• These tags are not always used or used incorrectly

In our data set:
• Only 32% of headings were tagged by these tags
• Only 67% of components tagged by these tags were headings• More sophisticated extraction method is necessary23

Humans use
visual style• How do humans extract
hierarchical heading
structure?

24

Humans use
visual style• How do humans extract
hierarchical heading
structure?
• They use visual style• consists of various visual
attributes of components• e.g. font-size, color

25

Humans use
visual style• How do humans extract
hierarchical heading
structure?
• They use visual style• consists of various visual
attributes of components• e.g. font-size, color

26

Visual style can be easily detected• Visual style is assigned to each DOM node

• DOM node is a pair of tags or a text fragment split by tags

<LI>
<B>
Jul.
</B>
Construction started.
</LI>

LI

B

Jul.

text

27

Visual style can be easily detected• Visual style is assigned to each DOM node

• DOM node is a pair of tags or a text fragment split by tags

<LI>
<B>
Jul.
</B>
Construction started.
</LI>

LI

B

Jul.

text

28

Visual style can be easily detected• Visual style is assigned to each DOM node

• DOM node is a pair of tags or a text fragment split by tags

<LI>
<B>
Jul.
</B>
Construction started.
</LI>

LI

B

Jul.

text

29

Visual style can be easily detected• Visual style is assigned to each DOM node

• DOM node is a pair of tags or a text fragment split by tags

• Visual style can be easily detected by computers• We use it to extract hierarchical heading structure30

Disadvantages ofexisting methods• There exists some methods
that use visual style of nodes• Existing methods• check nodes one-by-one• compare two nodes andjudge which one is more
likely to be a heading• Their available information
is too limited

31

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Disadvantages ofexisting methods• There exists some methods
that use visual style of nodes• Existing methods• check nodes one-by-one[Okada, Arakawa]• compare two nodes andjudge which one is more
likely to be a heading• Their available information[Okada,limited
Arakawa] H. Okada and H. Arakawa.
is tooAutomated extraction of non <h>-tagged headers in

32

webpages by decision trees. In Proc. of SICE Annual
Conf., pages 2117–2120, 2011.

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Disadvantages ofexisting methods• There exists some methods
that use visual style of nodes• Existing methods• check nodes one-by-one• compare two nodes andjudge which one is more
likely to be a heading[Pembe, Güngör]• They do not use global
information[Pembe, Güngör] F. C. Pembe and T. Güngör. A tree33

learning Approach to web document sectional hierarchy
extraction. In Proc. of ICAART, pages 447–450, 2010.

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Disadvantages ofexisting methods• There exists some methods
that use visual style of nodes• Existing methods• check nodes one-by-one• compare two nodes andjudge which one is more
likely to be a heading• They do not use global
information within given page

34

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Our idea• To use more information,
our method• groups nodes by visual styleinto node sets
• judges if each node set is aset of actual headings• Each node set is• a set of headings of same level• or a set of non-headings

35

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Example node sets

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

• Node sets indicatedby color

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

36•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Example node sets

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

• Node sets indicatedby color
An example set of
actual headings

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

37•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Example node sets

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

• Node sets indicatedby color
An example set of
non-heading
components.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

38•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Outline of our
method
1. Group candidate headings
2. Sort node sets bysignificance of their style
3. For each node set in desc.
order of significance
3.1 Judge if the node set is aset of actual headings
3.2 For actual headings, also
extract corresponding blocks

39

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Outline of our
method
1. Group candidate headings
2. Sort node sets bysignificance of their style
3. For each node set in desc.
order of significance
3.1 Judge if the node set is aset of actual headings
3.2 For actual headings, also
extract corresponding blocks

40

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Outline of our
method0 Kyoto Aquarium

4 is an aquarium in Kyoto, Japan.

1 Overview

5 One of the largest inland aquariums.

1. Group candidate headings 1 Information
2 Holidays
2. Sort node sets by
6 Open throughout the year.
significance of their style
2 Opening Hours
6 From 9 a.m. to 5 p.m.
3. For each node set in desc.
order of significance
1 History
3.1 Judge if the node set is aset of actual headings
3.2 For actual headings, also
extract corresponding blocks

41

2 20107

2 20127•3 Jul. Construction started.
•3 Feb. Construction finished.

7•3 Mar. Opened just as planned.

•3 Jul. 7Welcomed the 1Mth visitor.

Outline of our
method0 Kyoto Aquarium

4 is an aquarium in Kyoto, Japan.

1 Overview

5 One of the largest inland aquariums.

1. Group candidate headings 1 Information
2 Holidays
2. Sort node sets by
6 Open throughout the year.
significance of their style
2 Opening Hours
6 From 9 a.m. to 5 p.m.
3. For each node set in desc.
order of significance
1 History
3.1 Judge if the node set is aset of actual headings
3.2 For actual headings, also
extract corresponding blocks

42

2 20107

2 20127•3 Jul. Construction started.
•3 Feb. Construction finished.

7•3 Mar. Opened just as planned.

•3 Jul. 7Welcomed the 1Mth visitor.

Outline of our
method0 Kyoto Aquarium

4 is an aquarium in Kyoto, Japan.

1 Overview

5 One of the largest inland aquariums.

1. Group candidate headings 1 Information
2 Holidays
2. Sort node sets by
6 Open throughout the year.
significance of their style
2 Opening Hours
6 From 9 a.m. to 5 p.m.
3. For each node set in desc.
order of significance
1 History
3.1 Judge if the node set is aset of actual headings
3.2 For actual headings, also
extract corresponding blocks

43

2 20107

2 20127•3 Jul. Construction started.
•3 Feb. Construction finished.

7•3 Mar. Opened just as planned.

•3 Jul. 7Welcomed the 1Mth visitor.

Outline of our
method0 Kyoto Aquarium

4 is an aquarium in Kyoto, Japan.

1 Overview

5 One of the largest inland aquariums.

1. Group candidate headings 1 Information
2 Holidays
2. Sort node sets by
6 Open throughout the year.
significance of their style
2 Opening Hours
6 From 9 a.m. to 5 p.m.
3. For each node set in desc.
order of significance
1 History
3.1 Judge if the node set is aset of actual headings
3.2 For actual headings, also
extract corresponding blocks

44

2 20107

2 20127•3 Jul. Construction started.
•3 Feb. Construction finished.

7•3 Mar. Opened just as planned.

•3 Jul. 7Welcomed the 1Mth visitor.

Outline of our
method
1. Group candidate headings
2. Sort node sets bysignificance of their style
3. For each node set in desc.
order of significance
3.1 Judge if the node set is aset of actual headings
3.2 For actual headings, also
extract corresponding blocks

45

Kyoto Aquarium

is an aquarium in Kyoto, Japan.

Overview

One of the largest inland aquariums.

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.
•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Step 1. Group candidate headings• Candidate heading nodes: a single text or image node
• Group candidates with exactly the same attribute values

Three types of attributes for grouping
1.
2.
3.

Visual attribute values computed by web browsers• Font-size, font-style, font-weight, text-decoration, and color

Tag path• Sequence of node names between a node and the root
• e.g. /HTML/BODY/TABLE/TR/TD/UL/LI/text()

Height of images

46

Step 2.
Sort node sets by significance of their style
Four sort keys in this priority order
1. Depth of corresponding blocks in hierarchy• because blocks never include blocks at upper levels

2. Font-size
3. Font-weight
4. Document order• because a heading of a parent block usuallyappear earlier than that of a child block47

Step 3.
Scan node sets in order of significance• Our method• recursively scans node setsin the descending order of their significance• When an actual heading set is found,
extracts the blocks corresponding to the headings• Two sub-steps

3.1 Judge if a node set is an actual heading set
3.2 Detect the corresponding blocks from headings

48

Kyoto Aquarium

Step 3.1 Judging if a node
set is actual heading set Overview

is an aquarium in Kyoto, Japan.
One of the largest inland aquariums.

5 heuristic rules• e.g. all headings in one
parent block are unique

Information

Holidays
Open throughout the year.
Opening Hours
From 9 a.m. to 5 p.m.

History

2010• Jul. Construction started.
2012• Feb. Construction finished.

49•

Mar. Opened just as planned.

•

Jul. Welcomed the 1Mth visitor.

Step 3.2
Detecting corresponding blocks from headings• When a node set passed all the rules, our method• regards it is an actual heading set• detects blocks corresponding to the headings• To determine blocks from headings, our method use
correspondence between them and DOM sub-tree• A heading corresponds to a single text or image node
• A block corresponds to a node array,a set of adjoining sibling nodes and their descendants

50

DIV

B

UL

B

2010

LI

2012

B

Jul.

text

UL

LI

B

Feb.

LI

text

B

Mar.

LI

text

B

Jul.

text

51

“2012” DIV
node array“2010”
node array
B

UL

B

2010

LI

2012

B

Jul.

text

UL

LI

B

Feb.

LI

text

B

Mar.

LI

text

B

Jul.

text

DIV

B

UL

B

2010

LI

2012

B

Jul.

text

UL

LI

B

Feb.

LI

text

B

Mar.

LI

text

B

Jul.

text

DIV

B

UL

B

2010

LI

2012

“2010”
headingBJul.

The lowest common ancestorof the headings, “2010” and “2012”
UL

LI“2012”
text headingB

Feb.

LI

text

B

Mar.

LI

text

B

Jul.

text

54

The first node of“2010” node array

The first node of DIV“2012” node array

B

UL

B

2010

LI

2012

B

Jul.

text

UL

LI

B

Feb.

LI

text

B

Mar.

LI

text

B

Jul.

text

55

DIV

The last node of“2010” node array
B

UL

B

2010

LI

2012

B

Jul.

text

The last node of“2012” node array
UL

LI

B

Feb.

LI

text

B

Mar.

LI

text

B

Jul.

text

56

Experimental setting
To evaluate our method• Random 803 pages from ClueWeb09• For excluding spam pages, only pages relevant to someintents in TREC Web track were collected• For each page, 1 of 5 annotators hand-annotatedhierarchical heading structure in its content body
• Fleiss’ Kappa: .693 for headings and .583 for blocks

57

Evaluation result (heading extraction)
MethodDecision tree learning [Okada, Arakawa]Naïve method based on tag names
Our method

Precision Recall F1-score
.084
.884
.154
.668
.320
.433
.638
.569
.602

[Okada, Arakawa] H. Okada and H. Arakawa. Automated extraction of non <h>-tagged headers
in webpages by decision trees. In Proc. of SICE Annual Conf., pages 2117–2120, 2011.

58

Evaluation result (heading extraction)
MethodPrecision Recall F1-score
Decision tree learning [Okada, Arakawa]
.084
.884
.154
Naïve method based on tag names
.668
.320
.433
Our method
.638
.569
.602

• The decision tree learning method did not work well
• Most test pages did not share visual style with training pages[Okada, Arakawa] H. Okada and H. Arakawa. Automated extraction of non <h>-tagged headers
in webpages by decision trees. In Proc. of SICE Annual Conf., pages 2117–2120, 2011.

59

Evaluation result (heading extraction)
MethodDecision tree learning [Okada, Arakawa]Naïve method based on tag names
Our method

Precision Recall F1-score
.084
.884
.154
.668
.320
.433
.638
.569
.602

• The decision tree learning method did not work well
• Most test pages did not share visual style with training pages• Our method achieved a far better recall
retaining about same precision as the naïve method[Okada, Arakawa] H. Okada and H. Arakawa. Automated extraction of non <h>-tagged headers
in webpages by decision trees. In Proc. of SICE Annual Conf., pages 2117–2120, 2011.

60

Evaluation result (block extraction)
MethodPrecision Recall F1-score
VIPS [Cai+]
.215
.070
.106
Our method
.586
.563
.574

[Cai+] D. Cai, S. Yu, J.-R. Wen, and W.-Y. Ma. VIPS: A vision-based page segmentation
algorithm. Technical Report MSR–TR–2003–79, Microsoft Research, 2003.

61

Evaluation result (block extraction)
MethodPrecision Recall F1-score
VIPS [Cai+]
.215
.070
.106
Our method
.586
.563
.574

• VIPS did not work well

• because its extraction target is layout structure• VIPS is complementary to our method[Cai+] D. Cai, S. Yu, J.-R. Wen, and W.-Y. Ma. VIPS: A vision-based page segmentation
algorithm. Technical Report MSR–TR–2003–79, Microsoft Research, 2003.

62

Evaluation result (block extraction)
MethodPrecision Recall F1-score
VIPS [Cai+]
.215
.070
.106
Our method
.586
.563
.574

• VIPS did not work well

• because its extraction target is layout structure• VIPS is complementary to our method• Our method: in accuracy close to heading extraction• Extracted blocks from actual headings by precision of .769

[Cai+] D. Cai, S. Yu, J.-R. Wen, and W.-Y. Ma. VIPS: A vision-based page segmentation
algorithm. Technical Report MSR–TR–2003–79, Microsoft Research, 2003.

63

Conclusion• Extraction of hierarchical heading structure is importantfor various applications of the web• We proposed a method based on an ideathat headings of the same level share their visual style• Our method achieved high recall and satisfactory precision• Our code and data sets will be available online• https://github.com/tmanabe

64