Paul,
The note from Graham Klyne, see below, addresses the conneg combinatory
explosion issue raised in item 4 of your meeting summary.
Lloyd
> -----Original Message-----
> From: pmoore@peerless.com [mailto:pmoore@peerless.com]
> Sent: Monday, November 20, 2000 8:56 AM
> To: ifx@pwg.org
> Subject: IFX> Second IPP fax meeting
>
>
---snip---
>
> 4. We discussed conneg. Somebody with actual implementation
> experience pointed
> out that it was very unwieldy - you get a combinatory
> explosion in most
> non-trivial cases. Still nobody has come up with a better idea.
>
---snip---
-----Original Message-----
From: Graham Klyne [mailto:GK@Dial.pipex.com]
Sent: Tuesday, November 21, 2000 1:35 PM
To: McIntyre, Lloyd
Subject: Re: FW: IFX> Second IPP fax meeting
At 10:34 AM 11/21/00 -0800, you wrote:
>Graham,
>Any feedback on item 4 below?
Lloyd,
Yes...
Combinatorial explosion can be an issue; for most expressions, I think it
is manageable in all but the most memory-constrained environments. I think
the fax examples are about as complex as an expression should get. To
minimize the combinatorial effect, my suggestions are:
(a) don't attempt to expand or simplify an expression until actually trying
to match another,
(b) use a generate/test strategy that discards unmatched options before
proceeding to generate the next. In some cases, a whole branch of the
expression tree can be discarded without further expansion. In any case,
only possible matches are stored.
(c) try to keep simple alternatives (set expressions) together; e.g.
rather than expanding
(feature=[a,b,c])
to
(| (feature=a) (feature=b) (feature=c))
keep it as a primitive comparison. This will require an extension to the
simple expression processing logic so that expressions like:
(& (F=[a,b,c]) (F=[a,c,e] )
can be reduced to:
(F=[a,c])
I think it is also possible to perform a degree of "factorization" on the
feature expressions, so that alternative constructs containing features not
mentioned elsewhere are kept intact (rather than transformed to disjunctive
normal form), without changing the ultimate result.
I have been planning to add some of these improvements to my sample code,
but had never got around to it.
When reducing to disjunctive normal form, the main cause of combinatorial
explosion is inner disjunctions:
(& (| (A) (B) (C) )
(| (D) (E) (F) ) )
gives rise to:
(| (& (A) (D) )
(& (A) (E) )
(& (A) (F) )
(& (B) (D) )
(& (B) (E) )
(& (B) (F) )
(& (C) (D) )
(& (C) (E) )
(& (C) (F) ) )
so any heuristic that limits unnecessary expansion of these can reduce the
combinatorial effects. This factor might be considered in designing the
construction and combination of feature sets.
#g
------------
Graham Klyne
(GK@ACM.ORG)
This archive was generated by hypermail 2b29 : Wed Nov 22 2000 - 14:45:14 EST