Member Avatar for localp

I need to create a C++ program, that one could get a list of suggestions when he's typing. for example: when we type the letter 'A', a list of words that start with the letter A should display. then when we type another letter 'P', the words should filter and all words that start with 'AP' should be listed, finally. the word 'APPLE' will be selected upon click.

I hope I made my scenario clear. I got a few questions here;

1.) When a person types a letter; say 'A', how can we list all the words below it, do we have to get the values from a database? (and it should be really fast too) or is there any other easy way?

2.) In a mobile phone we have the feature called 'T9', when we type a character it keeps on suggesting words. So is there a small or whatsoever database? how is it working?

3.) Are there any sample programs, that could start working on?

  • 2 Contributors
  • 3 Replies
  • 371 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by mike_2000_17

Dani AI

Generated

Quick practical plan (build-first, optimize-later). wants instant suggestions while typing; pick a GUI toolkit early (Qt is a common cross-platform choice) so you can test interactive latency rather than a console prototype. pointed toward using an indexed source — that is sensible for very large datasets — but for a beginner-friendly, low-latency autocomplete the most common approaches are an in-memory prefix structure or a sorted word list with efficient range lookups. The prefix structure gives constant-time work per typed character (proportional to the prefix length) and is easiest to reason about.

A minimal, practical data structure to implement and experiment with is a Trie (prefix tree). It supports fast insertion and fast prefix enumeration; you can cap suggestions to top-K, store a frequency or score on terminal nodes, and return ranked results. Example sketch (toy, for clarity):

struct TrieNode {
    bool end = false;
    int freq = 0; // higher = more common
    std::unordered_map<char,TrieNode*> next;
    ~TrieNode(){ for(auto &p: next) delete p.second; }
};

void insert(TrieNode* root, const std::string &w, int f=1);
std::vector<std::string> suggest(TrieNode* root, const std::string &prefix, int limit=6);

Use suggest to walk to the prefix node then do a limited DFS to collect up to limit completions, returning the highest-frequency items first (keep a small heap or sort a tiny result list).

Notes about T9 and mobile prediction: T9 maps digits to letter sets, so generate candidates by traversing the trie following those letter sets (or maintain a numeric signature index). Real-world phone IMEs add frequency ranking, short n-gram context, and compressed storage (DAWG / compressed trie) to save memory and speed loads.

Implementation tips and gotchas: load the wordlist once at startup, normalize case, limit returned items (5–10), debounce UI keystrokes to avoid work on every raw key event, and keep incremental state (narrow the previous result set when the user types more). For very large vocabularies, move to a database or a disk-backed prefix index; for learning and small apps, a trie or ternary-search tree is the fastest path to visible results.

Recommended Answers

All 3 Replies

Member Avatar for mike_2000_17

First of all, you need some kind of GUI for this, cin / cout won't be good enough for sure (or a least a lot of trouble). So figure out what you want to use first (Qt, MFC, SDL, whatever..), then you can start to solve that problem.

Second, I'm sure there are already some tools for Qt or MFC that do this.

Finally, yes you will need a database or something to get a dictionary. These would be OS-specific and package-specific (linux). I can't help you much further with that. If you are up for it you can check something like KSpell (open-source spell-checker for linux, takes words and matches them to a dictionary to give suggestions if an exact match is not found), but I presume the source-code will be large.

Member Avatar for localp

Do you know of a good search algorithm (after all its all about matching the word with the dictionary) that i could use ?

Member Avatar for mike_2000_17

Well.. if the dictionary is in a file and in alphabetical order, then a binary search would probably be good enough. But if you deal with a database (which I recommend), then those search algorithm are included in the database server (MySQL, or any other you have access to) so all you have to do is say "find <first_characters>*" and it will find everything that start with your first characters (look up SQL query language for more details on that). You can be pretty sure that the search algorithms in the database is far more efficient than you could ever program yourself (there are people who make a living at perfecting those search algorithms).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.