[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
"Compression, Comparison & Xanalogical Structure
- To: xanadu@xxxxxxxxxxxxx
- Subject: "Compression, Comparison & Xanalogical Structure
- From: Ted Nelson <ted@xxxxxxxxxx>
- Date: Tue, 12 Aug 1997 01:47:54 -0700
- In-reply-to: <33EE8909.47E8@xxxxxxxx>
- Organization: Xanadu Australia
- References: <firstname.lastname@example.org> <email@example.com> <firstname.lastname@example.org>
- Reply-to: xanadu@xxxxxxxxxxxxxxxxx
It's funny, but your e-mail of the other day made me realize,
in a way I hadn't before, the relationship between string compare
and xanalogical address compare.
[Rich, 10 Aug:>
>The problem is the same, whether the "documents" being
>compare are lists of characters or of pointers. If I can solve
>it for strings of characters, it is solved for lists of transclusion
>links or lists of paragraphs or lists of anything else.
[Rich, 10 Aug #2:>
...>Recognizing familiar substrings is the core of both.
Oddly, I hadn't thought of string comparison and pointer
comparison as the same. But that's because the address
comparison is much simpler (see below).
[Rich, 9 Aug:>
>Interesting problem; when you allow segments to
>be rearranged, it is no longer linear with the segment length. It is
>also clearly symmetrical; it doesn't matter which is the "before" and
>which is the "after".
[Rich, 10 Aug #2:>
>The complexity of the problem solved by my COMPARE program grows as the
>product of the lengths of the strings. However, I believe that if you
>allow rearrangement (not just insertion/deletion) the problem becomes
>exponential (like the travelling salesman problem). That is what I
Hmm. I don't think it's so bad. Consider the following.
WHY ADDRESS COMPARISON IS SIMPLER THAN
In address comparison, we compare N pointers to see
which ones point at the same original elements.
A special advantage which makes this simpler is that
the elements pointed to are a unique pool. Each pointer
points no more than once to each element in this pool.
You can compare addresses using two columns: put the
domain of pointers on one side, put the range of addresses
on the other, and then find which unique addresses each
pointer points to. Then list the pointers in some order,
like ascending order of first element pointed to, and find
out which ones overlap.
WHEREAS for string compare, every "a" has to be a potential
match against every other "a," a nightmarishly larger problem.
[Rich, 10 Aug #2:]>
>In our world, the question is of the relative costs of moving (pointing
>to) a very small snippet of text vs. re-typing it. Is it cheaper to
>reference a single letter with a pointer, than to simply enter it as a
>literal? Probably not. What about one word? A sentence? A paragraph?
>Where does the threshold lie?
Xanalogical structure-- especially transclusion-- is not an
issue of efficiency. Cost isn't the problem; the main issue
is literary structure and what works in the literary world of
evolving thought, authorial credit, copyright, royalty and
desirable forms of re-use.
We have reasons to want to see where something comes from
(version management for one user, interest in who-said-what
for more than one user); and to want to clean up copyight.
So transclusion is useful even if it involves electronic overhead.
The point is not to actually *implement* the pure
one-original-no-copies structure, but to *simulate it precisely
in the most efficient way.*
A simpler overall way to say all this, especially when people
say transclusion is "inefficient," is "Compared to *what*?"
If transclusion is a way to get people to make available their
copyrighted material, not doing it this way is a *lot* less efficient.
(Sorry I get ranting.)
(Next e-mail: my best definition of Transclusion so far)
In USA until 10 September 1997:
Ted Nelson, Project Xanadu, 3020 Bridgeway #295, Sausalito CA
Tel. 415/ 331-4422, fax 415/ 332-0136
In Japan after 10 September 1997:
Theodor Holm Nelson, Visiting Professor of Environmental Information
Keio University, Shonan Fujisawa Campus, Fujisawa, Japan
http://www.sfc.keio.ac.jp/~ted/ PERMANENT E-MAIL: ted@xxxxxxxxxx
Home Fax: 0466-46-7368 From USA: 011-81-466-46-7368