Поиск полнотекстовых подстрок в iOS

Question

Мне нужно, чтобы мое приложение для iPhone / iPad позволяло быстро выполнять поиск около 10000 записей (примерно по одному абзацу текста) для любой подстроки, содержащейся в записи. Так что, если запись содержит слово «Flame», запросы на «lame» должны совпадать.

В настоящее время я использую SQLite, но поиск "LIKE% term%" слишком медленный для такого количества записей. Включение полнотекстового поиска, похоже, не будет полностью соответствовать моим потребностям, поскольку SQLite поддерживает только символы подстановки префиксов (например, «Flam *», а не «* lame»).

Я экспериментировал с использованием гигантского сгустка текста (~ 350 КБ) и выполнением [NSString rangeOfString: ...], которое, я думаю, использует алгоритм Бойера-Мура. Это быстрее, чем поиск "LIKE% term%", но все же не та скорость, на которую я надеюсь.

Какие-либо предложения по подходам или библиотекам, которые могли бы обеспечить такой масштабируемый поиск по подстроке и которые могли бы работать на iPhone?

Answer 1

Вот несколько вариантов.Я не знаю ни о каких бичах для каждого из них, поэтому вам придется провести некоторое тестирование.

Во-первых, это расширение FTS3 для SQLite.Это должно дать вам быстрый индексированный полнотекстовый поиск: http://regularrateandrhythm.com/regular-rate-rhythm-blog/sqlite3-fts-in-IOS4.html

Тогда как насчет регулярных выражений, которые были введены в iOS 4:
http://developer.apple.com/library/ios/#documentation/Foundation/Reference/NSRegularExpression_Class/Reference/Reference.html

Для версий до iOS 4, вы можете использовать RegexKitLite:
http://regexkit.sourceforge.net/RegexKitLite/index.html

Если вы решите использовать регулярные выражения, посмотрите на эту запись о том, как оптимизировать их:
Как ускорить iPhoneрегулярные выражения с NSRegularExpression?

Answer 2

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

Answer 3

Возможно, рассмотрите возможность объединения вашего второго подхода с асинхронным подходом.Разделите ваш большой блок текста на 5,10, любого размера и ищите их отдельно с тем же количеством потоков.Затем объедините результаты, используя систему координат, которая знает, как правильно расположить совпадения (например, поток 5 искал область 5 и нашел совпадение в позиции 337, которая соответствует документу x, позиции y).Вы обнаружите, что есть предел, когда добавление большего количества потоков не приносит пользы, поэтому это первое, что нужно выяснить.