Subj : Re: Generating an Index
To   : comp.programming
From : Michael Jørgensen
Date : Fri Sep 09 2005 08:25 am


"Mary" <maryjones11289@hotmail.com> wrote in message
news:1126144770.691289.220550@g49g2000cwa.googlegroups.com...
> Hi, I need some assistance with a query. To be honest, I'm not even
> sure it can be done.
>
> I'll try to keep the information limited to only what's relevant to
> what I have and what I am trying to achieve with this query.
>
> I have a table that contains around 100,000 records. For the sake of
> this discussion, assume just two columns:
>
> ID Data
> 1 000000000000
> 2 010000000000
> 3 011111111111
> 4 101100011101
> 5 110100011011
> 6 111100000000
> 7 111100000111
> 8 111100010111
> 9 111100011011
> 10 111111111111

[snip]

> My aim is to somehow sort the data (by creating a third column) so that
> the records are in order of "string distance" or similar. In other
> words, so that similar strings are located next to (or as close as
> possible to) each other.

As others have pointed out, there is no "optimal" solution.

However, I have an idea I would like to share. It is based on "Gray code".

All n-bit binray numbers may be ordered, such that neighboring elemens have
a distance of 1.

For 3-bit numbers one possibility would be
1 000
2 001
3 011
4 010
5 110
6 111
7 101
8 100

My point is now that this defines a *mapping* from the binary number to the
(arbitrarily chosen) index in the left-hand column.

So this mapping produces a ranking of 3-bit numbers. For instance, the
numbers 000 and 111 have index 1 and 6 respectively, i.e. they are now "far
apart" according to this ranking.

It should be possible to write an algorithm that calculates the "Gray code
index" of a given binary number. This index could then be written into your
third column and used to sort by.

-Michael.

.