There's an alternative to summed-area tables with a small, linear
space cost and linear construction time and space, providing worst-
case
logarithmic-time reduction over arbitrary intervals under arbitrary
semigroup operations, and which supports updates efficiently, unlike
summed-area tables. The algorithm is like twenty fricking lines of
code
if you leave out the "update" and "small" parts.
cf fenwick trees (which could be useful for your rice-coded spelling
correction, if one wished to check single words instead of entire
documents)
also blelloch's parallel prefix sum, which uses straight (non-heap
indexed) array storage
also xanalogical dspative properties are summed leaf-to-root and
widative properties are summed "left"-to-"right"
the former suggests we may apply stokes' theorem to arbitrary graphs
(and also, eg for finite state machines, in higher dimensions)
that is to say: we arrive at the same answer
whether we integrate an operation over the boundary of a given volume
or we integrate the differential of the operation over the volume itself
we often use this equivalence in one direction, eg to break up a
large operation over external storage into a series of small
operations in internal
we also use this equivalence in the opposite direction, eg to perform
a single major update when iterating and updating for each minor
modification would lag
-Dave
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
