gisle@ifi.uio.no (Gisle Hannemyr) (08/09/90)
I am storing a number of strings (composed of several words) in a list in RAM. For instance (three strings): John Fitzgerald Kennedy John Frank Oppenheimer Lyndon Bird Johnson I want to look up a string using an unambiguous abbreviation of the words in the string. Ie (given the short list above): J F K => John Fitzgerald Kennedy John Fitzgerald Kennedy => John Fitzgerald Kennedy L => Lyndon Bird Johnson J F => (error, ambiguous) J F L => (error, not found) Typical applications for such a function would be phone directory, or a completing unambiguous command parser. Does anyone have a fast C routine that do the above, or know a clever algorithm to accomplish it. My main requirement is speed. Please mail your replies if possible. I do not read these groups regularly. - gisle hannemyr (Norwegian Computing Center) EAN: C=no;PRMD=uninett;O=nr;S=Hannemyr;G=Gisle (X.400 SA format) gisle.hannemyr@nr.no (RFC-822 format) Inet: gisle@ifi.uio.no UUCP: ...!mcvax!ifi!gisle ------------------------------------------------
ssdken@watson.Claremont.EDU (Ken Nelson) (08/10/90)
I would have responded by mail but your address kept bouncing. How about this approach: When you store your strings store them in some kind of fast access tree, B-tree, AVL, Splay, or perhaps a hashed structure. Save them with the string as the key, and with the initials as the key. example: /* bsearch is a unix function for inserting, or searching into a binary tree. You could replace this with any type of insert into a fast access structure. Don't really try this code it won't work, it is here to explain the concept. */ bsearch("John F. Kennedy",tree,"John F. Kennedy") bsearch("JFK",tree,"John F. Kennedy"); This is pretty fast, and space could be minmized by putting pointers to strings into the tree instead of having a copy of the string in each node of the tree. This approach works for state abbreviations as well, it is really like aliasing when writing parsers, and scanners.... Hope this helps, Ken Nelson Principal Engineer Software Systems Design 3627 Padua Av. Claremont, CA 91711 (714) 624-3402