Re: String matching on keys of a table

[Francisco Olarte <folarte@...>]

Hi:

> is there anything more sophisticated than linear search, which I can
> do to match a key (string) in a table from a user input, which is only
> a part of that key?

There are lots of things you can do, but you should define it a little better.

> (the whole thing should run on a embedded system under Gentoo Linux.
> There are 400MB of mem...not Gigs of it ... ;)))

That is irrelevant if you do not post how many keys are there in the
table and also which caractereistics do they have, things like wheter
the keys share common prefixes ( I suppose they do otherwise you'll be
limited to a trivial 256 maximum different keys ), and how many keys
there are.

You can use a trie, as suggested by a previous post, but this is gonne
be big if implemented under native lua.

For the general problem I would use an index table with all the keys
sorted. As lua shares strings this will only cost you memory for the
array part of the table, a pointer per key. Then you take the user
string and do a binary search for it. If binary search finds it, then
your starting index is the previous slot, if it doesn't then it is the
insertion point. Then you loop in the table, and while the entry
starts with the user string you have keys with start with it. An
example.

sorted keys = 1:'', 2:a, 3:aa, 4:ab, 5:c, 6:x, 7:z11 8:z12 9:z21

If user input is a, binary search finds  it at 2, then you start
looping and get a, aa, ab and stop when reading c.

If user input is aa, binary search finds  it at 3, then you start
looping and get aa and stop when reading ab.

If user input is z, binary search tells you it should be inserted at
7, and you extract z11, z12, z21

If user input is y, binary search tells you it should be inserted at 7
too, but you will stop at z11 without using any key.

Be careful when implementing binary search, remember to make it easy
you tipically start with low=0, high=count+1, not with 1, count as
some textbooks do.

Also, if you have few keys you could just loop, but as you want to
avoid linear search I supose it is not appropiate.

Francisco Olarte.