Scoring-based DOM Content Selection with Discrete Periodicity Analysis

Thomas Osterland

1,2

and Thomas Rose

1,2

1

Fraunhofer FIT, Schloss Birlinghoven 1, Sankt Augustin, Germany

2

RWTH Aachen University, Ahornstr. 55, Aachen, Germany

Keywords:

1 INTRODUCTION

The substantial advances in data analytics, machine

learning and stochastic modeling are only a few ex-

amples, that demonstrate the importance of data for

use cases and applications of the future. The world

humans. The document object model (DOM) struc-

tures the content of websites. Thereby, a substantial

part of the DOM is not concerned with the direct pre-

sentation of information, but with the layout and look

to present the information pleasantly, i.e., to improve

the presentation such that a human reader can quickly

and efficiently identify and extract the most important

parts.

readers, it obfuscates the presentation for computer

version is necessary. However, if the model gener-

ation is as simple as clicking on an element on the

website, we can let the user update the model. In par-

ticular, if the model is transferable, such an updated

model can be shared among all users of a software

large, the combined work of many people is required.

In this case, it is an advantage if these people do not

need to be experts in programming, that are capa-

ble of creating regular expressions or XPath defini-

tions. This enables the utilization of crowd worker

platforms, as Amazon’s Mechanical Turk. Our ap-

proach allows the identification of complex selection

patterns based on mouse clicks of a user. This makes

our approach particularly accessible to untrained per-

sonnel.

scoring with discrete periodicity analysis to identify

specific patterns selected by a user. For instance, se-

lecting every second or third row of a table or two

consecutive rows followed by one row that is not se-

lected. These are often properties, that can be easily

expressed in scripting-based selectors as XPath, but

are difficult or elaborate to obtain with click events.

we review related work, that discusses web scraping

and technical approaches to extract specific informa-

further improves the selection results of our approach.

We evaluate the model sizes and the time complexity

of our approach in Section 4 and also discuss experi-

mental results. The results of this paper and potential

future work are discussed in Section 5.

2 RELATED WORK

Glez-Pe

˜

na et al. differentiate three different classes

of web scraping approaches “(i) libraries for general

˜

na et al.,

na et al.

andez et al. present a se-

˜

na et

˜

na et al., 2014).

while in the second there was a simple IDE that pro-

vided visual feedback during development. All test

participants were programmers with varying degrees

of experience.

duced by Glez-Pe

by Krosnick and Oney. However, they discuss in

their related work tools that use Programming-by-

Demonstration (PbD) approaches for the model cre-

ation. One major motivation of PbD is to empower

non-experts to handle complex tasks. Frank (Frank,

1995) demonstrates this for interactive systems by

comparing snapshots before and after a user interac-

tion. Barman et al. (Barman et al., 2016) use this ap-

proach for the selection of DOM elements and similar

replayed for automation. Similar functionality is pro-

vided by the academic tools CoScripter of Leshed et

al. (Leshed et al., 2008) and SUGILITE from Li et al.

(Li et al., 2017). Additionally, there exists a variety

of commercial tools, as Selenium

and Cy-

press Studio

.

Pakle, 2014) an approach to learn extraction rules

from training data. They describe a three step pro-

cedure: In the first step a user can interactively select

statements or provide their own domain-specific lan-

guage. In particular for the use case of web automa-

tion PbD is used to record user interactions. Our ap-

proach employs discrete periodicity analysis to en-

able the selection of complex patterns. Hence, we

target the third category of Glez-Pe

na et al. that en-

ables layman programmers or web users in general to

train models and thus, allow the methodical extraction

https://www.cypress.io/

relationship between elements of different levels in

the DOM tree, root ∈ S the root node, which has

no incoming transitions, i.e., {(v,root) | ∀v ∈ S} *→,

DAGs.

is unambiguous due to the tree structure of the DOM.

Since, the order of elements in the DOM is impor-

tant for the presentation, we define the natural total

order < on a set of siblings, according to their appear-

ance in the DOM. For example in Figure 1 the order

on the set of siblings siblings(BODY) = {HEAD,BODY}

with HEAD < BODY.

the training data provided by the user, as for instance

by selecting some elements. However, a usual DOM

contains a substantial number of equal HTML ele-

ments and CSS classes. The redundancies within the

graph together with the Markov property (memory-

less) of the model lead to poor classification results.

Better results can be obtained, when we increase the

order of the Markov chain. If we increase the order to

the path length of the largest training path, we obtain

the best classification results, but hardly benefit from

For two states s,s

in a path we write s < s

, if s ap-

pears earlier in the path than s

path if s

A path, that is a root path and a leaf path is called

complete. In Figure 1 paths, that contain the div tags

are leaf paths and a non-rigorously written example

for a complete path is ω = html body div.

tener to a website and then construct the path by iter-

course, the approach is not limited to table rows, but

can be also used to extract patterns from arbitrary

HTML elements, as for instance float or CSS grid

screen layouts.

which uses subsets of potential patterns to analyze the

frequency of occurrence of larger patterns. This can

then be used to derive a confidence score, that a cer-

tain pattern appears periodically. The challenge dur-

ing the mining process is that, we assume noisy data,

which means that the pattern will not match exactly at

certain periods.

of periodicity mining as follows: For a time series of

features S = D

,D

,· ·· ,D

, where D

ter at this position, but only on the periodicity of the

surrounding elements.

they define a confidence score, that is based on the

occurrence frequency of a pattern s:

frequency count(s) = |{i | 0 ≤ i ≤ m,s holds in

D

number of pattern repetitions with the confidence

value. If for instance a pattern needs to be at least

two times present in the sequence, we can derive a

minimal bound and only work with patterns that have

at least this confidence. With regard to our content

selection use case, we use this minimal bound (of two

present repetitions), since one occurrence cannot be

identified as periodic and more than two are too much

if a user selects two alternating rows in a table.

) and the number of their oc-

, that we

pattern : s 7→ (x

,· ·· ,x

x

(5)

< · ·· < s

return {s};

r ← M[0];

mod |p

mod |p|] = 1, (p

Algorithm 1: Identify the periods.

the highest frequency of occurrences. If the set M

of selected patterns contains more than one element

we require additional training data, otherwise we will

choose the pattern. We use this selected pattern to

derive those siblings, that match the extrapolated pat-

tern. Note, that we use < (s) = i as a loose syntactic

expression to denote the index of s in the order of its

siblings s

< ·· · < s

and p[i]

p

is part of a detected periodic pattern. We count the

number of states at which this is the case and divide

it by the number of total states in the path. For train-

,a

,a

with

tems G

,G

, that are bisimilar.

and Katoen in particular on the first item, since transi-

tion systems are usually not limited to directed acyclic

states. We defined the labeling function L based on

the TAG and assigned CSS classes. States that share

these properties are considered as equal by our algo-

rithm. The second and the third property enforce the

same branching structure on the tree.

,root,TAG, CSS,L) : s ∈ S for a subtree induced

by choosing a state s ∈ S as its root and only

keep states and transitions, that are connected in

a successor relationship. G

: G × S → G with

the remaining states.

,s, s

,· ·· ,s

,

i.e., the state s is not part of a training path and

s ∈ period(s) is part of an identified pattern we search

for bisimilar subtrees induced by the siblings of s,

that are part of a training path and construct a path

,· ·· ,s

,· ·· ,s

,· ·· ,s

,s, s

,· ·· ,s

?

Figure 2: Example to showcase the necessity of evaluating the bisimilarity of subtrees in case of identified periodicity. The

red lines represent the training paths and the blue path is selected by the periodicity analysis. The question mark indicates the

problem, that a selection path for the subtree cannot be directly deduced from the periodicity analysis of the parent elements.

DOM for the model. We measure execution time and

the correctness of selected elements.

The model size depends directly on the training set.

For a path ω ∈ T we need to store for every state s ∈ ω

training set, and we use the number of states in the

DOM |S| as an upper bound for the pattern. Thus,

we have a complexity of O(|S||CSS| + |S| + |S|

where the first term assumes, that every available CSS

class is assigned to every state in the DOM. The sec-

ond term presents, that every state is unambiguously

mapped to a tag and the third term assumes, that we

need to store for every state a pattern consisting of

we analyzed the number of elements in the DOM, the

average CSS classes assigned to a state and the aver-

age number of siblings of a state collected from the

popular websites mentioned above.

classes and siblings are much smaller than the total

number of DOM elements. Also, the number of CSS

classes assigned to a single DOM element is below

20. Hence, in practice we can expect much smaller

models, than suggested by the worst case analysis.

paths and apply the scoring. The counts of the earlier

scoring can be cached, such that we are not forced to