efficient Levenshtein distance

10.15: news.adds/algorithm/efficient Levenshtein distance:
. the Levenshtein distance between two words
is the minimum number of single-character edits
(insertion, deletion, substitution)
required to change one word into the other.
. finding the Lev' distance takes a long time,
on the order of (length of longer string
times length of shorter string),
so we are looking for ways to avoid it .

converting attribute-text to html

4.29: adde/gui/converting attribute-text to html:
. a pyqt text object uses a system of fragments to express
each change in the text's combinations of attributes in
(color, bold shade, underline, italics, superscript, subscript );
but when converting to html,
you want to combine contiguous modes;
eg, say you have 3 words, 1,2,3,
with u=underline, and b=bold;
so, when pyqt gives you:
1(u), 2(b,u), 3(u)
your html writer should be converting that to:
u(1, b(2), 3) .

efficiently panning large documents

2011.9.15: adde/gui/efficiently panning large documents:
. when a window is much smaller than
the document of a network graph,
do you have to keep the whole bit-image in memory?
[9.18:
. the ideal is having a small engine that is
generating a small data set as-needed,
expanding from drawing instructions
into bit maps,
rather than sending expanded pages to off-ram storage;
then again,
speedy solid-state drives are getting common,
and energy is getting precious ... .]

. for saving energy,
a network graph is stored as an image;
for save space and hard drive accesses,
it would be a list of nodes with attributes:
(inout edges, global position, ...).
. a search function given window area
would return any nodes within that region .

. I had this mem-saving scheme for drawing it:
rather than allow panning,
move to birdseye view (zoom out some),
then set your zoom-in box to go there;
the window sized image is kept in memory,
but few or no closups are cached .
. this idea is not that important on a fast computer;
because, you can respond on the fly:

. whichever way the user is panning
find the sections about to be exposed,
and create the images just in time .
. for each section,
you need to know which nodes are in that section,
and then to draw the edges,
you need to know the nodes that connect to
your drawn nodes;
the edge path is a style of line
{linear, Bézier curve, ...}
between the global positions of 2 nodes
which is then mapped across any needed section
but drawn only on currently existing sections
(those expected to be viewed soon).

9.16: edges as objects:
. to help speed things up
by quickly finding per-section edge lists,
you could have an edges list too;
each edge would know:
# the locations of its end-point nodes;
# the points that define how it curves;
# a list of the sections
that the edge's line runs through .

9.16: space walking:
. if you have nodes and edges in 3-d,
then you may want to follow an edge
and see things nearby along the way;
this can be done with some of the previous ideas:
. a line function is a series of global position points,
and for each point you figure the 3-d region,
then you know the nearby regions,
and finally,
you can search the edges list for a region,
to get a list of every edge intersecting that region .

9.16: web.adde/gui/terminology:
. how is the graphics industry using "(sector)?
Portal rendering:

In computer-generated imagery
and real-time 3D computer graphics,
portal rendering is an algorithm
for visibility determination.
For example,
consider a 3D computer game environment,
which may contain many polygons,
only a few of which may be visible on screen
at a given time.
A portal system is based on using
the partitioning of space
to form generalizations about
the visibility of objects within those spaces.
Regions of map space are divided into
polygonal, generally convex, areas called sectors.
Adjacent sectors are linked to one another via
shared dividing polygons termed portals.
Approaches that pre-compute visibility for sectors
are referred to as PVS (potentially visible set) methods.

literateprograms.org

11.5: news.addx/literateprograms.org:

. if you like eiffel add some code to en.literateprograms.org?

dev.eiffel.com/Spread_the_word

oh wow, this is great!

in fact, there is not much eiffel code:

but there is plenty of c code !!!

and java:

. the clean way to find what is getting attention

is the portable.category

. interesting to find out that bignum math is best done by fft.

. literate prog'ing at ltu.

Sedgewick` Algorithms

bk.adda/Sedgewick` Algorithms

10.5:

adda/parse.tree:

. a parse tree is the usual name for what I called an etree (expression tree)

adda/forest:

. a forest is a tree that is not binary;

[10.9:

eg, in the universe of acyclic graphs

lists have only 2 edges, trees 3, and forests > 3 .

. forests can be impl'd with trees

by having one edge leading to the next node extension,

rather than a 2nd child . ]

any node in a forest:

. if a tree has 2 way edges

then any node can be root

but it becomes a forest .

10.6: adda/breadth-first search:

. breadth-first search is done by a

non-recursive pre-order traversal

but where the algorithm replaces the usual stack access

with a queue .