Есть ли лучший способ справиться с этим поиском по словарю?

Question

Я создаю приложение для iPhone.У меня есть файл .plist, который содержит словарь слов (около 180К из них).

Есть текстовое поле, где пользователь начинает вводить слово.Когда он печатает, я использую метод делегата textField:shouldChangeCharactersInRange:replacementString:, чтобы убедиться, что он вводит только abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.

Когда пользователь впервые нажимает на textField, я загружаю NSMutableArray с именем finalWords (объявленный в заголовке, сохраненный и синтезированный) с содержимым .plist (каждое слово является строкой NSString).Когда пользователь вводит букву, я запускаю это

-(void)filterWordsForString:(NSString *)string
{
  NSRange *range;
  for (int i=[finalWords count]-1 ; i >=0 ; i--)
  {
    range = [[finalWords objectAtIndex:i] rangeOfString:string];
    if (range.location == NSNotFound)
    {
      [finalWords removeObjectAtIndex:i];
    }
  }
}

Моя цель - остановить пользователя всякий раз, когда он вводит строку, которая не является частью реального слова (согласно моему словарю).Этот код работает в том смысле, что он сокращает возможные слова, которые пользователь печатает по ходу дела.Таким образом, как только он печатает букву, которая делает его таким образом, что он не может завершить его до слова, я не позволяю вводить букву.Кроме того, как только есть уникальное завершение, я продолжаю и заполняю textField законченным словом.

Проблема в том, что сначала это мучительно медленно!Для первой буквы требуется несколько секунд, а для второй - не намного меньше.В-третьих, скорость довольно разумная.Есть ли способ, которым я могу резко ускорить этот процесс фильтрации?

Спасибо.

Answer 1

Вы можете отсканировать файл .plist при загрузке приложения и создать алфавитные хеш-таблицы (хеширование - это способ сжатия данных в одно значение, так что сжатие двух слов, которые вы хотите поместить в одно и то же ведро, приведет к одному и тому же значению), который вы затем использовали бы для поиска правильного сегмента на основе первых 1-3 букв, прежде чем даже искать его.Хорошая вещь в хешировании (в отличие от обычного поиска) заключается в том, что вы по сути формируете массив данных, где сгенерированный хеш - это индекс сегмента.Следовательно, после хеширования данных (что может быть дорогостоящей операцией, но выполняется только один раз при загрузке), поиск выполняется так же быстро, как поиск данных в массиве.

РЕДАКТИРОВАТЬ (более детально): Если вы хотите искать на основе буквенных комбинаций, вы можете создать хеш-таблицы на основе шаблонов повторяющихся букв.Скажем, создайте корзину, основанную на хеше der, который будет содержать как spiderpig, так и binder, тогда другой каталог будет основан на hash из spi, который будет содержать «spinach» и «spiderpig».'также (в этом случае spiderpig будет в обоих ведрах).Хеширование очень быстро, если оно реализовано правильно, это движущая сила большинства поисковых систем (поэтому вы видите, что они возвращают миллионы результатов менее чем за секунду).