By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,498 Members | 1,564 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,498 IT Pros & Developers. It's quick & easy.

Strategy for locating strings based on initial characters

P: n/a
Hello.

Given a sorted collection of strings, what would a good (the best?)
strategy be to allow fast access to an item, based on a search substring
which should match the beginning of the searched item? The actual goal
is to implement a functionality similar to that found in help indices,
where one can locate an item by gradually typing its initial characters.
I expect that some kind of tree structure be present in the solution,
but I am not sure.

Since I am multiposting this to comp.programming and comp.lang.c++, I
would like to make it on-topic on the latter as well by asking whether
the STL provides any algorithms that could help here, assming, for
instance, that the strings are stored in a std::set or sorted std::vector.

Thank you,

--
Ney André de Mello Zunino
Jul 23 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
Ney André de Mello Zunino wrote:

Given a sorted collection of strings, what would a good (the best?)
strategy be to allow fast access to an item, based on a search
substring which should match the beginning of the searched item?
The actual goal is to implement a functionality similar to that
found in help indices, where one can locate an item by gradually
typing its initial characters. I expect that some kind of tree
structure be present in the solution, but I am not sure.


Look up "trie".

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

Jul 23 '05 #2

P: n/a
Ney André de Mello Zunino wrote:
Hello.

Given a sorted collection of strings, what would a good (the best?)
strategy be to allow fast access to an item, based on a search substring
which should match the beginning of the searched item? The actual goal
is to implement a functionality similar to that found in help indices,
where one can locate an item by gradually typing its initial characters.
I expect that some kind of tree structure be present in the solution,
but I am not sure.

Since I am multiposting this to comp.programming and comp.lang.c++, I
would like to make it on-topic on the latter as well by asking whether
the STL provides any algorithms that could help here, assming, for
instance, that the strings are stored in a std::set or sorted std::vector.

Thank you,


I needed something similar at work. My goal was to lookup an object
based on an object name. My implementation used the STL map<key,object>,
because the map stores object sorted and is therefore 2ln(n) for lookups.

The map needs a key that supports the < operator in order to sort the
objects. So I created a class called SortableString that implemented
the < operator using the c function strcmp.

So my template instantiation looked like
map<SortableString, Object*> objectMap;

I believe this sort of implementation would work for what you want to
do. First you would populate the map with a set of SortableStrings with
their text set to the topics of your help articles. The objects would
be pointers to your articles.

When the user types in a partial string you would create a temporary
SortableString object with its text set to the what the user typed in.
You can then use the lower_bound() function to locate the first element
greater than your temporary string (which should be the closest match
amoung all your subject headers. Psuedocode below.

class SortableString {
SortableString(char* string);
~SortableString();
bool operator < (SortableString& other);
};

map<SortableString, ArticleObject*> subjectHeaderMap;
bool AddSubject(char* subject, ArticleObject* article)
{
SortableString* newSubject = new SortableString(subject);
bool rvalue = objectHeaderMap.insert(map<SortableString*,
ArticleObject*>::value_type(newSubject,article).se cond;
return rvalue;
}

bool MatchSubject(char *test_subject, SortableString* found_subject,
ArticleObject** found_article)
{
bool match_found = false;
SortableString* newSubject = new SortableString(subject);
map<SortableString, ArticleObject*>::Iterator iter;

iter = objectHeaderMap.lower_bound(newSubject);
if (iter != objectHeaderMap.end())
{
*found_subject = iter->first;
*found_article = iter->second;
match_found = true;
}

delete newSubject;
return match_found;
}
Jul 23 '05 #3

P: n/a
Ney André de Mello Zunino wrote:
Hello.

Given a sorted collection of strings, what would a good (the best?)
strategy be to allow fast access to an item, based on a search substring
which should match the beginning of the searched item? The actual goal
is to implement a functionality similar to that found in help indices,
where one can locate an item by gradually typing its initial characters.
I expect that some kind of tree structure be present in the solution,
but I am not sure.


Modified binary search should do the job. (Modified, because you're
looking for "first possible match" and "last ditto", and because it
*might* be useful to work incrementally, although I strongly suspect
that would be an unnecessary optimisation.)

--
Chris "electric hedgehog" Dollin
Jul 23 '05 #4

P: n/a

"Ney André de Mello Zunino" <zu****@inf.ufsc.br> wrote in message
news:d4**********@domitilla.aioe.org...
| Hello.
|
| Given a sorted collection of strings, what would a good (the best?)
| strategy be to allow fast access to an item, based on a search substring
| which should match the beginning of the searched item? The actual goal
| is to implement a functionality similar to that found in help indices,
| where one can locate an item by gradually typing its initial characters.
| I expect that some kind of tree structure be present in the solution,
| but I am not sure.
|
| Since I am multiposting this to comp.programming and comp.lang.c++, I
| would like to make it on-topic on the latter as well by asking whether
| the STL provides any algorithms that could help here, assming, for
| instance, that the strings are stored in a std::set or sorted std::vector.

As an idea, I would start by looking into the following:
std::string::find_first_of( Criteria, StartPos );

std::string offers quite a few other members that may also help.

Cheers,
Chris Val
Jul 23 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.