| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"Dmitri Zhukov" |
| Date: |
17 Sep 2004 02:14:48 AM |
| Object: |
Text search algorithm (implementing telephone book) |
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.
.
|
|
| User: "John Harrison" |
|
| Title: Re: Text search algorithm (implementing telephone book) |
17 Sep 2004 02:19:36 AM |
|
|
"Dmitri Zhukov" <dimazhn@yandex.ru> wrote in message
news:cie2qt$10d6$1@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
.
|
|
|
|
| User: "Kai-Uwe Bux" |
|
| Title: Re: Text search algorithm (implementing telephone book) |
17 Sep 2004 02:47:11 AM |
|
|
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
.
|
|
|
|
|
Related Articles |
We are wholesaler top quality of brand sport shoes, clothes,jersey(NBA, NBL) handbags, sunglasses electronic mobile telephone . such as nike,football shoes, Jordan 1-23, Air Jordan, AF1, DUNK, Air max series, puma, adidas,prada,gucci,hogan shoes, iph
.moderated cross post!!! Implementing functional paradigm with C++
implementing constructors given class declarations
Implementing overloaded operator new[]/delete[]
Implementing fp pattern matching, using C++
Implementing singleton into multiply classes
Implementing library algorithms
implementing Java's Observable in C/C++?
| Implementing virtual concept in c
Implementing license codes
Problem implementing an object factory
implementing begin()
Help on implementing COM on unix
Implementing deque with a couple of vectors?
Implementing Mediator Pattern in C++
|
|
|
