- From: Luu Tran <Luu.Tran@Sun.COM>
- Date: Thu, 17 Apr 2003 11:35:28 -0700
- To: www-archive@w3.org
IETF media feature registration WG Graham Klyne
Internet draft Content Technologies
6 April 2000
Expires: October 2000
A revised media feature set matching algorithm
<draft-klyne-conneg-feature-match-02.txt>
Status of this memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as "work in
progress".
To view the entire list of current Internet-Drafts, please check
the "1id-abstracts.txt" listing contained in the Internet-Drafts
Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
(Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au
(Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US
West Coast).
Copyright Notice
Copyright (C) The Internet Society 1999. All Rights Reserved.
Abstract
RFC 2533, "A syntax for describing media feature sets", defines a
format to express media feature sets that represent media handling
capabilities. It also describes an algorithm for matching these
feature sets, which may be used, for example, to determine whether
the capabilities of a sender and receiver are compatible.
This memo describes a revised form of the feature set matching
algorithm, which incorporates lessons learned while implementing
the original algorthm. It is anticipated that this revised
algorithm description will be included in a future revision of RFC
2533. This memo does not affect any of the normative content of
RFC 2533.
Klyne Internet draft [Page 1]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
Table of contents
1. Introduction.............................................2
1.1 Structure of this document ...........................3
1.2 Document terminology and conventions .................3
1.3 Discussion of this document ..........................4
2. Matching feature sets....................................4
2.1 Feature set matching strategy ........................6
2.2 Formulating the goal predicate .......................7
2.3 Replace set expressions ..............................8
2.4 Move logical negations inwards .......................8
2.5 Replace comparisons and logical negations ............8
2.6 Conversion to canonical form .........................9
2.7 Grouping of feature predicates .......................10
2.8 Merge single-feature constraints .....................10
2.9 Presentation of feature comparisons ..................11
3 Worked example............................................11
4. Security considerations..................................16
5. Acknowledgements.........................................16
6. References...............................................17
7. Author's address.........................................18
Appendix A: Amendment history...............................18
Full copyright statement....................................18
1. Introduction
RFC 2533, "A syntax for describing media feature sets" [1], defines
a format to express media feature sets that represent media
handling capabilities. It also describes an algorithm for matching
these feature sets, which may be used, for example, to determine
whether the capabilities of a sender and receiver are compatible.
This memo describes a revised form of the feature set matching
algorithm, which incorporates lessons learned while implementing
the original algorthm. It is anticipated that this revised
algorithm description will be included in a future revision of RFC
2533.
The feature set matching algorithm description in RFC 2533 is not
normative: the logical properties of feature set expressions are
defined independently of any specific algorithm that may be used to
process them. This memo does not affect any of the normative
content of RFC 2533.
Klyne Internet draft [Page 2]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
Differences between the algorithm described in RFC 2533 and the one
in this memo are:
o a different set of primitive feature comparison functions are
used (LE, GE, EQ, NE used here, LE, GE, NL, NG used in RFC 2533).
These yield final results that are more clearly related to the
original feature set expressions.
o the description of how to transform feature comparison syntax to
the four primitive comparison functions is more direct, simpler
and should be easier to understand.
o the separate feature comparison reduction rules for ordered and
unordered value cases are replaced by a single, more obvious, set
of rules applicable to all cases.
o transformation rules are given for presenting the final result
for feature set matching using the feature expression syntax of
RFC 2533.
An implementation in Java of this feature set matching algorithm
has been prepared, and is available for public study and use [15].
1.1 Structure of this document
The main part of this memo addresses the following main areas:
Section 2 describes a the revised feature set matching algorithm.
Section 3 contains a worked example of feature set matching.
1.2 Document terminology and conventions
The following terms are defined in RFC 2533, but are repeated here
because they are crucial to parts of the description that follows.
Feature Collection
is a collection of different media features and
associated values. This might be viewed as describing a
specific rendering of a specific instance of a document
or resource by a specific recipient.
Feature Set
is a set of zero, one or more feature collections.
Klyne Internet draft [Page 3]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
Feature set predicate
A function of an arbitrary feature collection value which
returns a Boolean result. A TRUE result is taken to mean
that the corresponding feature collection belongs to some
set of media feature handling capabilities defined by
this predicate.
NOTE: Comments like this provide additional nonessential
information about the rationale behind this document.
Such information is not needed for building a conformant
implementation, but may help those who wish to understand
the design in greater depth.
1.3 Discussion of this document
Discussion of this document should take place on the content
negotiation and media feature registration mailing list hosted by
the Internet Mail Consortium (IMC):
Please send comments regarding this document to:
ietf-medfree@imc.org
To subscribe to this list, send a message with the body 'subscribe'
to "ietf-medfree-request@imc.org".
To see what has gone on before you subscribed, please see the
mailing list archive at:
http://www.imc.org/ietf-medfree/
2. Matching feature sets
This section presents a procedure for combining feature sets to
determine the common feature collections to which they refer, if
there are any. Making a selection from the possible feature
collections (based on q-values or otherwise) is not covered here.
Matching a feature set to some given feature collection is
esentially very straightforward: the feature set predicate is
simply evaluated for the given feature collection, and the result
(TRUE or FALSE) indicates whether the feature collection matches
the capabilities, and the associated quality value can be used for
selecting among alternative feature collections.
Klyne Internet draft [Page 4]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
Matching a feature set to some other feature set is less
straightforward. Here, the problem is to determine whether or not
there is at least one feature collection that matches both feature
sets (e.g. is there an overlap between the feature capabilities of
a given file format and the feature capabilities of a given
recipient?)
This feature set matching is accomplished by logical manipulation
of the predicate expressions as described in the following sub-
sections.
This procedure requires that the predicates be reduced to a
canonical form. The canonical form used is "disjunctive normal
form". An ABNF [10] syntax for this disjunctive normal form is:
filter = orlist
orlist = "(" "|" andlist ")" / term
andlist = "(" "&" termlist ")" / term
termlist = 1*term
term = "(" "!" simple ")" / simple
where "simple" is defined in RFC 2533, section 4.1 [1]. Thus, the
canonicalized form has at most three levels: an outermost "(|...)"
disjunction of "(&...)" conjunctions of possibly negated feature
value comparisons.
NOTE
The usual canonical form for predicate expressions is
"clausal form". Procedures for converting general
predicate expressions are given in [5] (section 10.2),
[11] (section 2.13) and [12] (section 5.3.2).
"Clausal form" for a predicate is similar to "conjunctive
normal form" for a proposition, being a conjunction
(logical AND) of disjunctions (logical ORs). The related
form used here, better suited to feature set matching, is
"disjunctive normal form", which is a logical disjunction
(OR) of conjunctions (ANDs). In this form, the aim of
feature set matching is to show that at least one of the
disjunctions can be satisfied by some feature collection.
Is this consideration of canonical forms really required?
After all, the feature predicates are just Boolean
expressions, aren't they? Well, no: a feature predicate
is a Boolean expression containing primitive feature
value tests (comparisons), represented by 'item' in the
feature predicate syntax. If these tests could all be
assumed to be independently TRUE or FALSE, then each
could be regarded as an atomic proposition, and the whole
Klyne Internet draft [Page 5]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
predicate could be dealt with according to the
(relatively simple) rules of Propositional Calculus.
But, in general, the same feature tag may appear in more
than one predicate 'item', so the tests cannot be
regarded as independent. Indeed, interdependence is
needed in any meaningful application of feature set
matching, and it is important to capture these
dependencies (e.g. does the set of resolutions that a
sender can supply overlap the set of resolutions that a
recipient can handle?). Thus, we have to deal with
elements of the Predicate Calculus, with some additional
rules for algebraic manipulation.
A description of both the Propositional and Predicate
calculi can be found in [12].
We aim to show that these additional rules are more
unfamiliar than complicated. The construction and use of
feature predicates avoids some of the complexity of
dealing with fully-generalized Predicate Calculus.
2.1 Feature set matching strategy
The overall strategy for matching feature sets, expanded below, is:
1. Formulate the feature set matching hypothesis.
2. Replace "set" expressions with equivalent comparisons.
3. Move logical negations "inwards", so that they are all applied
directly to feature comparisons.
4. Eliminate logical negations, and express all feature comparisons
in terms of just four comparison functions.
5. Reduce the hypothesis to a canonical disjunctive normal form (a
disjunction of conjunctions).
6. For each of the conjunctions, attempt to show that it can be
satisfied by some feature collection.
6.1 Partition the feature value tests into independent feature
groups, such that each group contains tests involving just
one feature tag. Thus, no predicate in a feature group
contains a feature tag that also appears in some other
group.
Klyne Internet draft [Page 6]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
6.2 For each feature group, merge the various constraints to a
minimum form. This process either yields a reduced
expression for the allowable range of feature values, or an
expression containing the value FALSE, which is an
indication that no combination of feature values can satisfy
the constraints (in which case the corresponding conjunction
can never be satisfied).
7. If the remaining disjunction contains at least one satisfiable
conjunction, then the constraints are shown to be satisfiable and
therefore the original two feature sets can be matched together.
The final expression obtained by this procedure, if it is non-
empty, can be used as a statement of the resulting feature set for
possible further matching operations. That is, it can be used as a
starting point for combining with additional feature set constraint
predicate to determine a feature set that is constrained by the
capabilities of several entities in a message transfer path.
NOTE: as presented, the feature matching process
evaluates (and stores) all conjunctions of the
disjunctive normal form before combining feature tag
comparisons and eliminating unsatisfiable conjunctions.
For low-memory systems an alternative approach is
possible, in which each normal form conjunction is
enumerated and evaluated in turn, with only those that
are satisfiable being retained for further use.
2.2 Formulating the goal predicate
A formal statement of the problem we need to solve can be given as:
given two feature set predicates, '(P x)' and '(Q x)', where 'x' is
some feature collection, we wish to establish the truth or
otherwise of the proposition:
EXISTS(x) : (P x) AND (Q x)
i.e. does there exist a feature collection 'x' that satisfies both
predicates, 'P' and 'Q'?
Then, if feature sets to be matched are described by predicates 'P'
and 'Q', the problem is to determine if there is any feature set
satisfying the goal predicate:
(& P Q)
i.e. to determine whether the set thus described is non-empty.
Klyne Internet draft [Page 7]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
2.3 Replace set expressions
Replace all "set" instances in the goal predicate with equivalent
"simple" forms:
T = [ E1, E2, ... En ] --> (| (T=[E1]) (T=[E2]) ... (T=[En]) )
(T=[R1..R2]) --> (& (T>=R1) (T<=R2) )
(T=[E]) --> (T=E)
2.4 Move logical negations inwards
The goal of this step is to move all logical negations so that they
are applied directly to feature comparisons. During the subsequent
step, these logical negations are replaced by alternative
comparison operators.
This is achieved by repeated application of the following
transformation rules:
(! (& A1 A2 ... Am ) ) --> (| (! A1 ) (! A2 ) ... (! Am ) )
(! (| A1 A2 ... Am ) ) --> (& (! A1 ) (! A2 ) ... (! Am ) )
(! (! A ) ) --> A
The first two rules are extended forms of De Morgan's law, and the
third is elimination of double negatives.
2.5 Replace comparisons and logical negations
The predicates are derived from the syntax described in RFC 2533,
and contain primitive value testing functions '=', '<=', '>='. The
primitive tests have a number of well known properties that are
exploited to reach a useful conclusion; e.g.
(A = B) & (B = C) => (A = C)
(A <= B) & (B <= C) => (A <= C)
These rules form a core body of logic statements against which the
goal predicate can be evaluated. The first step in formulating
these rules is to simplify the framework of primitive predicates.
Klyne Internet draft [Page 8]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
The original three comparisons (<=, >=, =) and their negations
yield six possible forms of primitive predicate. These are reduced
to combinations of just four functions, without negations, by the
following transformation rules:
(tag = value) --> (EQ tag value)
(tag <= value) --> (LE tag value)
(tag >= value) --> (GE tag value)
(! (tag = value) ) --> (NE tag value)
(! (tag <= value) ) --> (& (GE tag value) (NE tag value) )
(! (tag >= value) ) --> (& (LE tag value) (NE tag value) )
Thus, we have rules to transform all comparisons and logical
negations into combinations of just 4 relational functions (LE, GE,
EQ, NE).
2.6 Conversion to canonical form
NOTE: Logical negations have been eliminated in the
previous step.
Expand bracketed disjunctions, and flatten bracketed conjunctions
and disjunctions, by repeated application of the following
transformations:
(& (| A1 A2 ... Am ) B1 B2 ... Bn )
--> (| (& A1 B1 B2 ... Bn )
(& A2 B1 B2 ... Bn )
:
(& Am B1 B2 ... Bn ) )
(& (& A1 A2 ... Am ) B1 B2 ... Bn )
--> (& A1 A2 ... Am B1 B2 ... Bn )
(| (| A1 A2 ... Am ) B1 B2 ... Bn )
--> (| A1 A2 ... Am B1 B2 ... Bn )
The result is in "disjunctive normal form", a disjunction of
conjunctions:
(| (& S11 S12 ... )
(& S21 S22 ... )
:
(& Sm1 Sm2 ... Smn ) )
where the "Sij" elements are simple feature comparison forms
constructed during the step at the previous section. Each term
within the top-level "(|...)" construct represents a possible
feature set that satisfies the goal. Note that the order of
entries within the top-level '(|...)', and within each '(&...)', is
immaterial.
Klyne Internet draft [Page 9]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
From here on, each conjunction '(&...)' is processed separately.
Only one of these needs to be satisfiable for the original goal to
be satisfiable.
NOTE: A textbook conversion to clausal form [5,11] uses
slightly different rules to yield a "conjunctive normal
form".
2.7 Grouping of feature predicates
Recall that, from here onwards, each conjunction is
treated separately.
Each simple feature comparison contains a "left-hand" feature tag
and a "right-hand" feature value with which it is compared.
To arrange these into independent groups, simple predicates are
grouped according to their left hand feature tag.
2.8 Merge single-feature constraints
Within each group of each conjunction, apply the predicate
simplification rules given below to eliminate redundant single-
feature constraints. All single-feature predicates are reduced to
an equality or range constraint on that feature, possibly combined
with a number of non-equality statements.
If the constraints on any feature are found to be contradictory
(i.e. resolved to (FALSE) according to the applied rules), the
containing conjunction is not satisfiable and may be discarded.
Otherwise, the resulting expression is a reduced form of the
corresponding original conjunction.
(LE f a) (LE f b) --> (LE f a), a<=b
(LE f b), a>b
(LE f a) (GE f b) --> (FALSE), a<b
(EQ f a) a=b
(LE f a) (EQ f b) --> (FALSE), a<b
(EQ f b), a>=b
(LE f a) (NE f b) --> (LE f a), a<b
(GE f a) (GE f b) --> (GE f b), a<b
(GE f a), a>=b
(GE f a) (EQ f b) --> (EQ f b) a<=b
(FALSE), a>b
(GE f a) (NE f b) --> (GE f a) a>b
Klyne Internet draft [Page 10]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
(EQ f a) (EQ f b) --> (EQ f a), a=b
(FALSE), a!=b
(EQ f a) (NE f b) --> (EQ f a), a!=b
(FALSE), a=b
(NE f a) (NE f b) --> (NE f a), a=b
NOTE: In the above table, occurrences (within a single
conjunction) of the expressions on the left hand side of
"-->" are replced by the right hand side expression, if
and only if the condition after the "," is true. Thus:
(A) (B) --> (R1), C1
(R2), C2
means: "replace "(A) (B)" with "(R1)" if "C1" is true,
or with "(R2)" if "C2" is true, otherwise leave alone.
2.9 Presentation of feature comparisons
If the original feature sets can be matched, the foregoing sections
result in a number of reduced conjunctions that, when joined by a
disjunction, represent the feature set that satisfies all of the
original feature constraints.
The feature set expression thus obtained can be displayed in the
feature expression syntax of RFC 2533 [1] using the following
representations for feature comparison functions:
(EQ tag value) --> (tag = value)
(LE tag value) --> (tag <= value)
(GE tag value) --> (tag >= value)
(NE tag value) --> (! (tag = value) )
3 Worked example
In the example that follows, for improved readability, expressions
are presented throughout using the syntax of RFC 2533. Otherwise,
the transformation steps followed correspond to those described in
the previous section.
This example considers sending a document to a high-end black-and-
white fax system with the following receiver capabilities:
(& (dpi=[200,300])
(color=binary)
(image-coding=[MH,MR]) )
Turning to the document itself, assume it is available to the
sender in three possible formats, A4 high resolution, B4 low
resolution and A4 high resolution colour, described by:
Klyne Internet draft [Page 11]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
(& (dpi=300)
(color=binary)
(image-coding=MR) )
(& (dpi=200)
(color=binary)
(image-coding=[MH,MMR]) )
(& (dpi=300) (dpi-xyratio=1)
(color=[grey,full])
(image-coding=JPEG) )
These three image formats can be combined into a composite
capability statement by a logical-OR operation (to describe
format-1 OR format-2 OR format-3):
(| (& (dpi=300)
(color=binary)
(image-coding=MR) )
(& (dpi=200)
(color=binary)
(image-coding=[MH,MMR]) )
(& (dpi=300)
(color=[grey,full])
(image-coding=JPEG) ) )
The composite document description can be matched with the receiver
capability description by combining the capability descriptions
with a logical AND operation:
(& (& (dpi=[200,300])
(color=binary)
(image-coding=[MH,MR]) )
(| (& (dpi=300)
(color=binary)
(image-coding=MR) )
(& (dpi=200)
(color=binary)
(image-coding=[MH,MMR]) )
(& (dpi=300)
(color=[grey,full])
(image-coding=JPEG) ) ) )
--> Expand value-set notation:
(& (& (| (dpi=200) (dpi=300) )
(color=binary)
(| (image-coding=MH) (image-coding=MR) ) )
(| (& (dpi=300)
(color=binary)
Klyne Internet draft [Page 12]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
(image-coding=MR) )
(& (dpi=200)
(color=binary)
(| (image-coding=MH) (image-coding=MMR) ) )
(& (dpi=300)
(color=grey)
(image-coding=JPEG) )
(& (dpi=300)
(color=full)
(image-coding=JPEG) ) ) )
-->Flatten nested '(&...)':
(& (| (dpi=200) (dpi=300) )
(color=binary)
(| (image-coding=MH) (image-coding=MR) )
(| (& (dpi=300)
(color=binary)
(image-coding=MR) )
(& (dpi=200)
(color=binary)
(| (image-coding=MH) (image-coding=MMR) ) )
(& (dpi=300)
(color=grey)
(image-coding=JPEG) )
(& (dpi=300)
(color=full)
(image-coding=JPEG) ) ) )
--> (distribute '(&...)' over inner '(|...)'):
(& (| (dpi=200) (dpi=300) )
(color=binary)
(| (image-coding=MH) (image-coding=MR) )
(| (& (dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=300) (color=full) (image-coding=JPEG) ) ) )
--> continue to distribute '(&...)' over '(|...)', and flattening
nested '(&...)' and '(|...)' ...:
(| (& (dpi=200) (color=binary) (image-coding=MH)
(| (& (dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=300) (color=full) (image-coding=JPEG) ) ) )
(& (dpi=200) (color=binary) (image-coding=MR)
Klyne Internet draft [Page 13]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
(| (& (dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=300) (color=full) (image-coding=JPEG) ) ) )
(& (dpi=300) (color=binary) (image-coding=MH)
(| (& (dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=300) (color=full) (image-coding=JPEG) ) ) )
(& (dpi=300) (color=binary) (image-coding=MR)
(| (& (dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=300) (color=full) (image-coding=JPEG) ) ) )
Klyne Internet draft [Page 14]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
--> ... until normal form is achieved:
(| (& (dpi=200) (color=binary) (image-coding=MH)
(dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MR)
(dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=300) (color=binary) (image-coding=MH)
(dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=300) (color=binary) (image-coding=MR)
(dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MH)
(dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=200) (color=binary) (image-coding=MR)
(dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=300) (color=binary) (image-coding=MH)
(dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=300) (color=binary) (image-coding=MR)
(dpi=200) (color=binary) (image-coding=MH) )
(& (dpi=200) (color=binary) (image-coding=MH)
(dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=200) (color=binary) (image-coding=MR)
(dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=300) (color=binary) (image-coding=MH)
(dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=300) (color=binary) (image-coding=MR)
(dpi=200) (color=binary) (image-coding=MMR) )
(& (dpi=200) (color=binary) (image-coding=MH)
(dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=200) (color=binary) (image-coding=MR)
(dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=300) (color=binary) (image-coding=MH)
(dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=300) (color=binary) (image-coding=MR)
(dpi=300) (color=grey) (image-coding=JPEG) )
(& (dpi=200) (color=binary) (image-coding=MH)
(dpi=300) (color=full) (image-coding=JPEG) )
(& (dpi=200) (color=binary) (image-coding=MR)
(dpi=300) (color=full) (image-coding=JPEG) )
(& (dpi=300) (color=binary) (image-coding=MH)
(dpi=300) (color=full) (image-coding=JPEG) )
(& (dpi=300) (color=binary) (image-coding=MR)
(dpi=300) (color=full) (image-coding=JPEG) ) )
--> Group terms in each conjunction by feature tag:
(| (& (dpi=200) (dpi=300) (color=binary) (color=binary)
(image-coding=MH) (image-coding=MR) )
(& (dpi=200) (dpi=300) (color=binary) (color=binary)
(image-coding=MR) (image-coding=MR) )
:
Klyne Internet draft [Page 15]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
(etc.)
:
(& (dpi=300) (dpi=300) (color=binary) (color=full)
(image-coding=MR) (image-coding=JPEG) ) )
--> Combine feature tag comparisons and eliminate unsatisfiable
conjunctions:
(| (& (dpi=300) (color=binary) (image-coding=MR) )
(& (dpi=200) (color=binary) (image-coding=MH) ) )
Thus, we see that this combination of sender and receiver options
can transfer a bi-level image, either at 300dpi using MR coding, or
at 200dpi using MH coding.
Points to note about the feature matching process:
o The colour document option is eliminated because the receiver
cannot handle either colour (indicated by '(color=[grey,full])')
or (image-coding=JPEG).
o The high resolution version of the document with '(dpi=300)' must
be sent using '(image-coding=MR)' because this is the only
available coding of the image data that the receiver can use for
high resolution documents. (The available 300dpi document
codings here are MMR and MH, and the receiver capabilities are MH
and MR.)
4. Security considerations
Security considerations are discussed in RFC 2533 [1] and related
documents. This memo does not introduce any additional security
considerations.
5. Acknowledgements
Work to develop the feature set matching algorithm, and to provide
a public implementation, has been supported by 5th Generation
Messaging Ltd.
Thanks also to Paul Hoffman of Internet Mail Consortium for making
the source code [15] available for general access at the IMC web
site.
Klyne Internet draft [Page 16]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
6. References
[1] RFC 2533, "A syntax for describing media feature sets"
Graham Klyne, 5GM/Content Technologies
March 1999.
[2] RFC 2506, "Media Feature Tag Registration Procedure"
Koen Holtman, TUE
Andrew Mutz, Hewlett-Packard
Ted Hardie, NASA
March 1999.
[5] "Programming in Prolog" (2nd edition)
W. F. Clocksin and C. S. Mellish,
Springer Verlag
ISBN 3-540-15011-0 / 0-387-15011-0
1984.
[10] RFC 2234, "Augmented BNF for Syntax Specifications: ABNF"
D. Crocker (editor), Internet Mail Consortium
P. Overell, Demon Internet Ltd.
November 1997.
[11] "Logic, Algebra and Databases"
Peter Gray
Ellis Horwood Series: Computers and their Applications
ISBN 0-85312-709-3/0-85312-803-3 (Ellis Horwood Ltd)
ISBN 0-470-20103-7/0-470-20259-9 (Halstead Press)
1984.
[12] "Logic and its Applications"
Edmund Burk and Eric Foxley
Prentice Hall, Series in computer science
ISBN 0-13-030263-5
1996.
[15] Java source code of feature set matching algorithm
Linked from <http://www.imc.org/ietf-medfree/>
Klyne Internet draft [Page 17]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
7. Author's address
Graham Klyne
Content Technologies Ltd.
1220 Parkview,
Arlington Business Park
Theale
Reading, RG7 4SA
United Kingdom.
Telephone: +44 118 930 1300
Facsimile: +44 118 930 1301
E-mail: GK@ACM.ORG
Appendix A: Amendment history
00a 11-Jun-1999 This memo created to contain a description of a
revised version of the feature set matching
algorithm from RFC 2533 [1].
00b 15-Jun-1999 Some small adjustments to the feature matching
algorithm to align it more closely with the source
code posted. Bring worked example up to date with
current fax feature schema (on which it has been
based).
01a 26-Jul-1999 Add note describing the notation used in the
feature comparison reduction tables.
02a 06-Apr-2000 Re-issued to keep draft available in I-D
repository. Updated contact details.
Full copyright statement
Copyright (C) The Internet Society 1999. All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain
it or assist in its implementation may be prepared, copied,
published and distributed, in whole or in part, without restriction
of any kind, provided that the above copyright notice and this
paragraph are included on all such copies and derivative works.
However, this document itself may not be modified in any way, such
as by removing the copyright notice or references to the Internet
Society or other Internet organizations, except as needed for the
purpose of developing Internet standards in which case the
procedures for copyrights defined in the Internet Standards process
must be followed, or as required to translate it into languages
other than English.
Klyne Internet draft [Page 18]
A revised media feature set matching algorithm 6 April 2000
<draft-klyne-conneg-feature-match-02.txt>
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on
an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Klyne Internet draft [Page 19]
Received on Thursday, 17 April 2003 16:13:25 UTC