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

Text search algorithm (implementing telephone book)

P: n/a
Hello everyone,

I am implementing software which has a medium sized number of text strings
(max 100K) which are represented in a listbox.
I want user to be able to search the string by typing the first letters of
the record and showing coinciding record if any (similar to quickserach
functionality of Norton/Total commander).
So i guess I need some kind of hasing algorithm to be able to find string by
its prefix. Any recommendations?

Dmitri Zhukov.
Jul 22 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a

"Dmitri Zhukov" <di*****@yandex.ru> wrote in message
news:ci***********@alpha2.radio-msu.net...
Hello everyone,

I am implementing software which has a medium sized number of text strings
(max 100K) which are represented in a listbox.
I want user to be able to search the string by typing the first letters of
the record and showing coinciding record if any (similar to quickserach
functionality of Norton/Total commander).
So i guess I need some kind of hasing algorithm to be able to find string
by
its prefix. Any recommendations?

Dmitri Zhukov.


Presumably the strings are sorted. I don't think you need anything as
complicated as a hashing algorithm, you just need binary search.

john
Jul 22 '05 #2

P: n/a
Dmitri Zhukov wrote:
Hello everyone,

I am implementing software which has a medium sized number of text strings
(max 100K) which are represented in a listbox.
I want user to be able to search the string by typing the first letters of
the record and showing coinciding record if any (similar to quickserach
functionality of Norton/Total commander).
So i guess I need some kind of hasing algorithm to be able to find string
by its prefix. Any recommendations?

Dmitri Zhukov.


Maybe the following code has some ideas that you find useful:
#include <string>
#include <set>

typedef std::string String;
typedef std::set< String > StringSet;
typedef StringSet::const_iterator StringSetConstIterator;
StringSetConstIterator
prefix_begin ( StringSet const & the_set,
String const & prefix ) {
return( std::lower_bound( the_set.begin(),
the_set.end(),
prefix ) );
}

StringSetConstIterator
prefix_end ( StringSet const & the_set,
String prefix ) {
// this breaks if the prefix is empty:
++ prefix[ prefix.length()-1 ];
return( std::lower_bound( the_set.begin(),
the_set.end(),
prefix ) );
}
#include <iostream>

int main ( void ) {
StringSet the_set;
the_set.insert( String( "aaa" ) );
the_set.insert( String( "hell" ) );
the_set.insert( String( "hello" ) );
the_set.insert( String( "help" ) );
the_set.insert( String( "zzz" ) );

{
String prefix ("hel" );
StringSetConstIterator from = prefix_begin( the_set, prefix );
StringSetConstIterator to = prefix_end( the_set, prefix );
for ( StringSetConstIterator iter = from; iter != to; ++iter ) {
std::cout << *iter << "\n";
}
}
std::cout << "\n";
{
String prefix ("hell" );
StringSetConstIterator from = prefix_begin( the_set, prefix );
StringSetConstIterator to = prefix_end( the_set, prefix );
for ( StringSetConstIterator iter = from; iter != to; ++iter ) {
std::cout << *iter << "\n";
}
}
}

Best

Kai-Uwe Bux
Jul 22 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.