Text search algorithm (implementing telephone book)

Discussion in 'C++' started by Dmitri Zhukov, Sep 17, 2004.

  1. 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.
    Dmitri Zhukov, Sep 17, 2004
    #1
    1. Advertising

  2. "Dmitri Zhukov" <> wrote in message
    news:cie2qt$10d6$-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
    John Harrison, Sep 17, 2004
    #2
    1. Advertising

  3. Dmitri Zhukov

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Sep 17, 2004
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ed Dror

    Telephone Data Format?

    Ed Dror, Feb 15, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    384
    blackstaronline.net
    Feb 16, 2006
  2. Denis

    programming a telephone

    Denis, Jan 10, 2006, in forum: Java
    Replies:
    6
    Views:
    479
    David N. Welton
    Jan 10, 2006
  3. Daniel H. Knight

    voip telephone

    Daniel H. Knight, Sep 7, 2005, in forum: HTML
    Replies:
    2
    Views:
    380
    Blinky the Shark
    Sep 7, 2005
  4. Replies:
    0
    Views:
    290
  5. Sirisha
    Replies:
    1
    Views:
    442
    Scott M.
    Nov 17, 2006
Loading...

Share This Page