.comment-link {margin-left:.6em;}
Books & Articles I wrote.

Monday, May 01, 2006


Canonicalize v Normalize

Canonicalize usually means "Transform to canonical form,"
while normalize usually means "Transform to normal form."

Canonical form is a unique form of whatever it is you're looking at allowing
comparing for equality of two items from the space by comparing their
canonical forms for identity. It must be true that every element of the
domain has a canonical form and that the canonicalization function is
idempotent (it doesn't change something already in canonical form).

So when you have a*(b+c), somebody has to decide whether the canonical form
is a*(b+c) or a*b + a*c. The transformation to canonical form of all
expressions involving multiplication and addition is then straightforward
(you have to remember to sort the terms of a sum or product in some
canonical order). Sometimes transforming to canonical form requires a lot
of knowledge; for example, the canonical form of exp(i*pi)+1 is probably
going to be 0 given any reasonable definition of canonical form. In certain
domains, reduction to canonical form is undecidable (would correspond to
being able solve certain hard equations).

Normal form is similar to canonical form, except that it is sometimes not
unique. (For example, in databases, people talk about 1st, 2nd, 3rd and 4th
normal forms for a table structure.)
Probably, when there is just one normal form in the domain, conflating
canonical with normal is relatively harmless.

source : http://lists.xml.org/archives/xml-dev/200307/msg00883.html

This page is powered by Blogger. Isn't yours?

Weblog Commenting and Trackback by HaloScan.com