Text search algorithm (implementing telephone book)

D

Dmitri Zhukov

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.
 
J

John Harrison

Dmitri Zhukov said:
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
 
K

Kai-Uwe Bux

Dmitri said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top