Re: Computational complexity of CSS

Hi Andrew,

In my experience CSS2 matching is rather linear in terms of the
number of elements in a document. It is possible to regard a
selector as a regular set. Therefore, a DFA can be created for it.
The element names, in document order, are the events that drive the DFA.
Besides that, "synthetic" events should be generated for the universal
selector and for conditions.

Since several selectors can match at the same time and since the
properties must be cascaded, the DFA should be "multithreaded". This
means that events don't make the DFA step from state to state, but
rather from state-set to state-set. After each step the accept states
must be retrieved from the current state-set. The properties attached
to them should be cascaded according to the specificity.

If you have, for example, 1000 nodes and an average state-set size
of 10, you would have 10000 steps, which are 10000 lookups in the small
next-set of each state in the current state-set. The lookups can be
optimised with a digital tree. In average, only half of the characters
of the element name must be visited.

With this method it is possible to process a document in document order.
As a consequence, it is not required to have a tree repesentation in
memory of the document. It can be implemented in something like a SAX
filter.

Best regards,

Werner.
-- 
Werner Donné  --  Re BVBA
Engelbeekstraat 8
B-3300 Tienen
tel: (+32) 486 425803	e-mail: werner.donne@re.be

Received on Monday, 21 November 2005 12:59:24 UTC