Лучший способ поиска слова в словаре 150k слов в приложении для iPhone?

Question

Я разрабатываю простое словарное приложение на французском языке со 150 тыс. Слов и определений.Я ищу лучший способ сделать это.

Сначала я использую sqlite bdd с 150 тыс. слов.я использую команду LIKE для поиска слов, но она очень медленная, например: SELECT * FROM words WHERE word LIKE '% avoi%' LIMIT 0,50;для поиска слова, которое содержит «avoi», например, «avoir» или «savoir».В моей таблице есть индексы столбцов слов, но LIKE не использует индекс, поэтому он очень медленный (2-5) с в 3GS.

После того, как я использую расширение fts3 от sqlite для использования команды MATCH, например: SELECT * FROMслова ГДЕ слово МАТЧ «избежать» * LIMIT 0,50;Гораздо лучше (0,1-0,15 с) в 3GS, но поиск только по слову, начинающемуся со слова «избежать», например «savoir», не дает результата.Команда MATCH не работает с синтаксисом типа ' avoi '

У вас есть идеи по оптимизации этого текстового поиска?

У меня есть очень хороший пример приложения для iphone: Диксел (Роберт Диссионнари), который делает такой поиск очень быстрым.Есть идеи для метода?

спасибо за ответы.

Answer 1

Быстрые словари используют сложные структуры данных, чтобы ограничить поиск методом перебора. Существует много данных о словах, которые можно быстро сохранить и найти

Одна из таких структур данных - это просто порядок слов, основанный на отношениях между буквами, которые они содержат. Например. у вас есть таблица, в которой перечислены все слова, в которых за a следует v. Затем другое для всех слов, которые имеют v, за которым следует o. Поиск произвольной строки avo становится делом объединения таблиц с последовательным AND. Итак:

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

Как только вы получите таблицу всех слов, которые соответствуют нужному шаблону, вы можете быстро его перебрать.

Словари похожи на Dates and Times, они кажутся простыми, потому что мы к ним привыкли, но за кулисами код, необходимый для их работы на компьютерах, обманчиво сложен.