> Hi list,
>
> My current project contains a simple RS232 interface and is to recognise
> typed commands received from a host PC. These commands will be simple,
> short text strings e.g. GAIN, INPUT1 etc. So essentially the problem is
> that I need to take a short text string and see if it matches any of 30
> (or so) text strings contained within program memory (stored using rom
> const char[]="blah"; etc), and return an index number of the matched
> string if there is a positive match.
>
> The first - and most obvious - method I can think of by which to compare
> a given string of characters with a set of tabulated strings is to just
> start at the top of the table, compare the first characters, if no match
> then move down to next string in table, compare first characters again,
> if match then compare the next characters along, etc etc.
>
> But this is a wheel that has already been invented over and over again
> no doubt, and I was wondering if there is a more clever or established
> method that someone could suggest I use.
>
> I know one other way could be to take the checksum of the input string
> and compare that with checksums of the strings in ROM which is a much
> faster process, but this would result in other randomly typed character
> combinations potentially causing a 'match' too, unless there is a more
> clever way of doing it.
>
> Or there is the hash process which I am vaguely familiar with, but I
> don't know if this is what I need.
>
> Code examples for possible solutions would be useful (C or ASM) but a
> basic suggestion about what kind of method to use would be extremely
> helpful too.
>
> Thanks in advance,
>
> Trevor.

Hi Trevor

Create a hash of the string including the string length in the range 1..255 and
prefix it to the string entry in the table. This type of hash is more accurately
referred to as a digest. When you search the table, calculate the digest for the
key (the string that has been entered) and prefix it to the key before you start
your search. During the search an unmatched prefix tells you that the key is
definitely different to the table entry and a matched prefix tells you that the
key might be the same as the table entry. Putting the digest at the start of
both the key and the table entry allows you to do the digest match and the
string confirmation using a single strcmp call within a simple efficient loop.
Don't go overboard on your digest algorithm. A good digest algorithm would be 8
bit CRC a bad one would be simple checksum.

Regards
Sergio Masci

http://www.xcprod.com/titan/XCSB - optimising structured PIC BASIC compiler

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listserv@mitvma.mit.edu with SET PICList DIGEST in the body