0

EDIT :

I've followed your good advices and I've used a trie data structure to contain my dictionnary. The structure I have chosen is this one for interested peoples.

But for now I've another issue : the construction of my trie data structure each time I launch my application is very too long ! Maybe my dictionnary is too huge, or maybe the implementation of trie I've chosen is too not appropriate for a simple dictionnary.

So is there a way to conserve this structure even after closing the app like a registered database or if you think the issue is caused by the implementation can you recommend me another one ?

I've got a serious issue with my android's project.

The goal here is to calculate all the words that can be made with a serie of 6 letters

To do that, I've two table in my BDD :

  • 'words' with two columns : '_id'and 'mots'
  • and 'temp' a temporary table with the same columns.

'words' contains all the words of vocabulary (it's huge) and 'temp' contains all the possible combinations of letters that can be made with the 6 letters (3 letters used at least).

I'm tryng to select in the table 'temp' the word which are real so the one which are in the table 'words'. Here is my code to do that :

I do a first selection of the words which contain the good letters (at least 3 letters are used)

db.execSQL("CREATE TABLE temp2 (_id integer primary key autoincrement, mots text not null);");
db.execSQL("INSERT INTO temp2 (_id, mots) SELECT * FROM words WHERE mots like '%"+lettres.tab_char.get(0)+"%' OR mots like '%"+lettres.tab_char.get(1)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(2)+"%' OR mots like '%"+lettres.tab_char.get(3)+"%' OR mots like '%"+lettres.tab_char.get(4)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(5)+"%';");

(lettre.tab_char is an ArrayList(Character) which contains the letters used to make the combinations in temp)

I do a join between the tables 'temp2' and 'temp' :

String MY_QUERY = "SELECT temp2._id, temp2.mots FROM temp2 INNER JOIN temp ON temp2.mots = temp.mots;";
Cursor test =  db.rawQuery(MY_QUERY, null);

After that I put my values into a listview.

It works but it's really really slow : Can you help me please ?

Paul
  • 35
  • 6

2 Answers2

1

In general the algorithm that you're using is really quite inefficient. First you're searching through every entry 6 times using a wildcard match, and then you're joining this gigantic result with your entire dataset again.

SQL is probably not the right place to do this. SQL is good at queries, this is more of a calculation. Do the matching in code.

There are lots of ways you can go about accomplishing this, but finding the right solution depends on your requirements. Can the letters repeat? How big of a vocabulary is "huge"? Does it still fit in a few MB? Does this lookup need to happen near-instantaneously?

Update:

Given your requirements, I have to agree with Joe. It's really more of a data structure than an algorithm, but a trie is the way to go. You should be able to build the trie once while loading the app and then each "match" will be a fairly simple lookup walking down the trie.

kabuko
  • 36,028
  • 10
  • 80
  • 93
  • First, Thank you for you're interest. In fact I want to design a game based on anagrams : you have 6 letters and you have to enter all the word that you can remake with these letters (letters can be used only on time). So I've an algoritm which generate a serie of 6 letters. I've my table of words (379 000 entries) and my table of combinations which I generate with this algorithm : http://www.merriampark.com/comb.htm And these SQL query are the method I found to generate the solution of each level. – Paul Jun 21 '11 at 00:15
1

The algorithm you're looking for is actually called a "trie" (short for retrieval). They are extremely well-suited for this type of calculation (Android actually uses them in the SMS and mail apps to do things like emoticon replacements). If done properly, you will be surprised with the performance you can get from it. I agree with Paul: you definitely should not do the query like you are currently. In fact, many implementations will even load the entire dictionary file into an in-memory trie, and use that trie for word lookup and verification throughout the application's lifetime. The scrabble word list (link is also contained in the question below: twl06.zip) is only 1.9MB, and contains 178k words. The trie in memory should actually be much smaller than 1.9MB, because multiple words will share common prefixes (e.g., "stair" and "stare" will both share the S-T-A prefix, which will then branch off into two leaves ["I" and "R"], and so on...)

Here's a good place to start: Algorithm to generate anagrams

Community
  • 1
  • 1
Joe
  • 42,036
  • 13
  • 45
  • 61
  • Thank you for you're answer Joe. If I understand correctly you're saying that I should keep my algorithm which generate my combinations of letters but that I should test the generated words with a trie data structure (my word list). – Paul Jun 21 '11 at 10:35