IFX Mail Archive: RE: IFX> Second IPP fax meeting - Conneg i

IFX Mail Archive: RE: IFX> Second IPP fax meeting - Conneg i

RE: IFX> Second IPP fax meeting - Conneg issue

From: McIntyre, Lloyd (Lloyd.McIntyre@pahv.xerox.com)
Date: Wed Nov 22 2000 - 14:44:03 EST

  • Next message: MAEDA toru: "IFX> Conneg issue"

    The note from Graham Klyne, see below, addresses the conneg combinatory
    explosion issue raised in item 4 of your meeting summary.


    > -----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
    > 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.

    -----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:
    >Any feedback on item 4 below?



    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) (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:

    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.


    Graham Klyne

    This archive was generated by hypermail 2b29 : Wed Nov 22 2000 - 14:45:14 EST