CODEWITHSUNDEEP
javaandroidstringdictionary
Joop
Joop

Reputation: 3788

Data-structure to put in full English dictionary to return quickly all possible word completions from String in android

Problem description

I should somehow load a full English dictionary (at least 650 000 words, possibly over a million) into a data structure that makes it fast and easy to find back all possible ways to end a String of letters in a particular order. You should also be able to find if the String is an actual word.

The way this (game) is setup is that you continually narrow down the possible words by appending new letters to the String. This probably could make it sequentially faster to search as the game goes on and more letters are added. However, if some sort of hash-map way of implementing this is used meeting the constraints that would of course be ideal. I would rather not have the user feel that the game is (a tiny bit) slow(er) in the beginning as there are still a lot of possibilities to complete the string.

Simple example

These are just examples to make it clear what I am trying to do and that it becomes clear that it could be implemented as a narrowing search:

string: app

String[] possibleWords = dataStructure.getCompleteAbleWordsWith("app");
//possibleWords = ["app", "apps", ..., "apple", "apples", ...];

string: appl

String[] possibleWords = dataStructure.getCompleteAbleWordsWith("appl");
//possibleWords = [..., "apple", "apples", ...];

Requirements

since the dictionary is static, does not change at runtime, I would rather have it saved in a compact and easily search-able form or even better have the whole data structure object already be in machine code or something.

What I tried:

  1. I implemented a hash-map that read in all words from the dictionary and search was extremely fast and balanced for complete words. However, this approach felt wrong if I want to do this for all words and their partial forms with a key value pair that indicated true it was a word and false if not for example.
  2. Looked into multi-way trees but I felt that there could be betters ways since the tree would be very, very wide and unbalanced.
  3. Thought about SQLite, using the LIKE keyword. I have next to none experience with databases right now, so I have no clue of the performance of those, in specific on android devices.

Any ideas to get me on the right track?

Upvotes: 1

Views: 744

Answers (1)

Moshe Carmeli
Moshe Carmeli

Reputation: 295

I recommend looking into tries. When learning about them we were told this was a good example of a use for them.

This is from the link:

A common application of a trie is storing a predictive text or autocomplete dictionary, such as found on a mobile telephone. Such applications take advantage of a trie's ability to quickly search for, insert, and delete entries

Upvotes: 1

Related Questions