Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Text search algorithm (implementing telephone book)

Reply
Thread Tools

Text search algorithm (implementing telephone book)

 
 
Dmitri Zhukov
Guest
Posts: n/a
 
      09-17-2004
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.


 
Reply With Quote
 
 
 
 
John Harrison
Guest
Posts: n/a
 
      09-17-2004

"Dmitri Zhukov" <(E-Mail Removed)> wrote in message
news:cie2qt$10d6$(E-Mail Removed)-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


 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      09-17-2004
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
transferring a telephone #/ownership of a telephone # hdtv? VOIP 1 10-18-2006 12:27 PM
Supply Telephone Voice Modular Adapters,Telephone Modular Couplers,Modular Duplex Jack,Triplex Adapters,Telephone extension Cord samul888@vip.163.com Cisco 1 11-13-2005 09:23 AM
Supply Telephone Voice Modular Adapters,Telephone Modular Couplers,Modular Duplex Jack,Triplex Adapters,Telephone extension Cord samul888@vip.163.com Computer Support 0 11-12-2005 06:22 AM
Supply Telephone Voice Modular Adapters,Telephone Modular Couplers,Modular Duplex Jack,Triplex Adapters,Telephone extension Cord samul888@vip.163.com VOIP 0 11-12-2005 06:22 AM



Advertisments