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

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.

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.