Best way for search word in 150k words dictionnary in a iphone app ?

Question

Hi,

I m developping a simple dictionnary word app in french with 150k words and definitions. i m looking for the best way to do this.

First i use a sqlite bdd with 150k words. i use the LIKE command for word search but it is very slow ex : SELECT * FROM words WHERE word LIKE '%avoi%' LIMIT 0,50; for searching word who contain 'avoi' like 'avoir' or 'savoir'. my table have the word column indexes but LIKE doesn't use index so it is very slow (2-5)s on 3GS.

After i use fts3 extension off sqlite for use MATCH command ex : SELECT * FROM words WHERE word MATCH 'avoi*' LIMIT 0,50; much better (0,1-0,15s) on 3GS but it s only search for word that begin with 'avoi' word like 'savoir' is not in the result. MATCH command doesn't work with syntax like 'avoi'

Have you any ideas for optimize this text search ?

I have a very good exemple of iphone app : Dixel (Robert Disctionnary) who make this kind of search very fast. Any ideas for the method ?

thanks for answers.

Answer 1

Fast dictionaries use complex data structures to limit brute force searching. There is a lot of data about words that can be stored and searched quickly

One such data structure is simply an ordering of words based on the relationships between letters they contain. E.g. you have a table that list all words in which a is followed by a v. Then another for all words that have a v followed by an o. Searching for an arbitrary string avothen becomes a matter merging the tables with sequenced AND. So:

(all words in which `a` is followed by a `v`) AND (all words in which `v` followed by an `o`)

Once you get the table of all words that match have the necessary pattern, you can brute force it quickly.

Dictionaries are like Dates and Times, they seem simple because we are used to them but behind the scenes code needed to make them work on computers is deceptively complex.

Answer 2

The fastest way to search lots of data is a database like SQLite3. The reason databases are fast is their organization of tables. I'm guessing that when you tried the SQLite database, you had one table with every word in it. To get a faster speed, you would need to have a table with every length of word, then within each have 26 tables with the first letter of every word, or any other way they could be organized.