[091labs-public] SQLite query returns empty cursor

[Carles Sentis]

I'm making a Crossword Solver for android. In which I have a database with 1/4 millions word stored in tables.

I have the bit for matching patterns like: "t??ble" where the query by just removing the ? by an _ makes the query simple and easy

and returning: treble and tumble.

I'm having trouble searching for anagrams of words. For example if I enter "pits" I would like to get: pits, spits, tips.

Now, with normal sql I would make a search for: 

searchWord LIKE '[pits][pits][pits][pits]'

And this should give me all the words I'm looking for (correct me if I'm wrong!) but it's not working. I've tried different things but every time I enter any

query with square brackets in SQLite doesn't seem to recognize it and just returns an empty cursor.

I didn't seem to be able to find any thing about it on the Internet.  

[Domhnall Walsh]

Hi Carles:

I'm no SQLite guru, though looking at http://www.sqlite.org/lang_expr.html I'd imagine replacing "LIKE" with "REGEXP" might produce what you're trying to do in your question.

However, admittedly without having put an enormous amount of thought into it, your query expression looks flawed to me. Wouldn't [pits][pits][pits][pits] match anything that contained those four letters (or any subset thereof)? While the likes of "pppp" or "stst" would technically match but almost certainly isn't in your database, so would (for example) "pips", "sits" or "sips", which while being valid English words, aren't actually anagrams of "pits"? Similarly while "step" matches "pets" and "pest" correctly in this way it'd also match "sees", "tees", "sets", and presumably other non-anagram (yet valid) words. 

It also wouldn't (shouldn't?) match "spits" like you've mentioned as it's a letter too long, isn't it?

I can't think of a guaranteed bulletproof easy way to do this off the top of my head, but some dusty memory in a corner of my brain suggests that I'd start with taking your dictionary file, and for each word compute a second "word" where the constituent letters are sorted in alphabetical order, and then doing the same to your search word and matching those in your query instead. 

Using your example, and a handy web site at this link, we have a list of anagrams for "pits": "tips", "spit", and of course "pits". I'd associate each of these with the equivalent sorted list of letters ("ipst") in your database, then in your query match the "sorted" word against the "sorted" search term rather than the approach you're taking. I reckon that little bit of precomputing will make your life MUCH easier (sort of a "sortedSearchWord LIKE 'ipst'") and should make the whole process much faster at the cost of a slightly larger database. Or at least this all makes sense right now while I'm not fully awake.

Hope it helps.

Domhnall.

[Carles Sentis]

I thought already on about what you said. Alphabetizing every word and storing this as another column in the database table. The only problem that I'm having with this is that this is for the Android where space is always an issue and double storing 1/4 million word is doubling my database footprint which I don't like.

Word length vary from 3 to 24 letters long and there are thousands of every length, double storing seems very impracticable. I'm trying to cut down on database size as much as I can. I'm now thinking on alphabetising every word and then creating a unique hash for that word which hopefully storing an INT will be much better than VARCHAR(24) in some cases.

If anybody else has more ideas I'm all ears

Thank you Domhnall for the inspiration...

[Domhnall Walsh]

Well, if you had one table with the sorted values and one with the unsorted values, you don't need to double your database. You'd then only need to store one "sorted" copy for each set of anagrams and cross-reference them using integer/long ID numbers?

Are you using a public word list?

[Carles Sentis]

That is a very good idea. I'm now thinking on what will take less space:

• What you just mention. Having a separate table with sorted words
• Storing a hash key for every word together with its unsorted word.
• And now I'm thinking I could have the separated table like before but hashing all the sorted words

I think the last one may be the one to go with...

Thank you Domhnall...

[Domhnall Walsh]

Out of curiosity, Carles, are you looking to design an algorithm that can create multi-word anagrams or is it one input word to produce 0 or more one-word anagrams?

--
Quidquid latine dictum sit, altum sonatur.
(Whatever is said in Latin sounds profound)

[Carles Sentis]

I may start simple by just looking for word using the same letters and of the same length but I would like to expand it to look for shorter words of the given word. So, if the user enters 10 char I would give all the possible words made with those letters from 10 char long, 9...  8... and so on. Another possibility would be to enter wildcards in the anagram, just like in the crosswords. I'll see how I get along. 

What is the public word list things you mention earlier?

'

[Domhnall Walsh]

I grabbed one from ispell. Look here: http://wordlist.sourceforge.net/

I'm fiddling with a mechanism for this in Python; I've been out of the loop for too long so am using this as an excuse to get back on the saddle. If I come up with anything useful I'll share it with you.

For the moment, I've attached a list of about 118k English words I cobbled together from a subset of the ispell data (it's not a small subset!) in text form, one word per line, and a CSV file showing the anagrams I found (first column is the sorted letter list, second and later columns are actual words (according to that list) that match those sorted letters. May be of some use to you. From those 118k words, this list is actually only 8k rows, so that would easily enough lend itself to a mobile database.

Domhnall.