ТЕКСТ: ДМИТРИЙ КЛИМКИН. Всем привет! Сегодня мы хотим поделиться своей Developer Story… а также опытом оптимизации стандартных алгоритмов под мобильные устройства.
Все началось с просмотра лекций Стэнфордского Университета по курсу “CS193P Developing Apps for iOS”. Но в качестве опытного проекта не хотелось выдать очередной калькулятор. Мы постоянно искали интересную идею для разработки. Как это обычно бывает, идея пришла внезапно, когда мозг уже готовился заснуть.
Смысл задумки был достаточно прост: приложение должно определить, как правильно написать слово. А если слово введено пользователем с ошибкой – показать варианты правильного написания. Такое приложение могло оказаться полезным для выезжающих журналистов и студентов (как раз надвигалась зимняя сессия). Каково было наше удивление, когда мы выяснили, что подобных приложений нет! Да, есть словари, которые в лучшем случае пытаются дополнить искомое слово и допускают одну опечатку… Но скорость поиска и размеры самих приложений удручают!
Помимо всего вышеперечисленного был еще один стимул поработать с алгоритмами нечеткого поиска, описанными в статье на Хабре. Давно хотелось реализовать подобные алгоритмы и измерить скорость их работы на мобильном устройстве.
НАЧАЛО РАБОТЫ
Изначально был выбран подход, когда искомое слово сравнивается с каждым элементом из словаря при использовании “расстояния Левенштейна”. Но тест в “боевых” условиях на айфоне показал, что такой поиск занимает в среднем 30-90 секунд – это в словаре всего из 90000 слов! Недопустимо долго!
Тогда был выбран другой путь: изначально строить индекс по словарю, используя метод хеширования по сигнатуре. А уже потом искать слово по готовому индексу. Быстро адаптировав приложение под новый метод, мы сразу проверили его на айфоне. И опять провал – создание индекса и, соответственно, старт приложения занимал порядка 90-120 секунд! Не каждый пользователь станет ждать 2 минуты для того, чтобы проверить, правильно ли он написал несколько слов. Приложение требовало еще большей оптимизации.
ОПТИМИЗАЦИЯ
Следующим шагом стало создание индекса словаря на Mac’е, а также сохранение готового индекса в sqlite-базу. Дальше iOS-устройство загружает уже готовый индекс. Снова рефакторинг и адаптация приложения к новому методу. И наконец-то положительный результат – старт приложения за 7-12 секунд! Затем мы попробовали нагрузить приложение еще больше – словарная база приложения была расширена до 355742 слов (ровно столько уникальных слов удалось собрать из нескольких орфографических и толковых словарей русского языка).
После обновления индекса словаря старт приложения стал занимать 10-15 секунд. Но самое главное – то, что теперь поиск слова занимает от нескольких миллисекунд до десяти секунд при большом количестве схожих слов. Этот результат вполне нас устроил. Надо было двигаться дальше.
ДОПОЛНИТЕЛЬНЫЕ ВОЗМОЖНОСТИ
Чтобы приложением было удобнее пользоваться, мы добавили несколько дополнительных возможностей:
1. Группировка результата по категориям: полное совпадения, с изменением одной буквы в слове (и так далее – до трех).
2. Любое слово из найденных приложением, можно скопировать в буфер обмена.
3. Добавлен поиск значения слова в Вики-словаре, Википедии, Яндекс-словаре и Гугл поиске. Но эта возможность требует интернет-соединения.
4. Приложение изначально разрабатывалось как универсальное и поддерживающее горизонтальный и вертикальный режимы экрана.
ЛИЦО ПРОГРАММЫ
После того, как мы определились с названием приложения, оно “обрело лицо”, и споров по поводу внешнего вида уже не было. Перед глазами стояла школьная доска, на которой красивым учительским почерком выведены прописные буквы. Буквы, которые складываются в самое, пожалуй, популярное правило русского языка: “жи” “ши” пиши с буквой “и”! Чаще всего нам приходится искать и исправлять орфографические ошибки именно в школе. Поэтому школьная атмосфера в названии и оформлении приложения показалась нам наиболее уместной.
ДОРАБОТКИ
Позже, основываясь на отзывах наших пользователей, мы внесли в приложение следующие изменения:
– Поиск по встроенному толковому словарю (под редакцией Т.Ф. Ефремовой).
– Добавлены действующие правила русского языка (орфография).
Цена: $0.99 [iTunes link]
Страница проекта: http://vk.com/public_zhi_shi
Данная история опубликована в рамках рубрики Developer Story, где разработчики делятся секретами своей внутренней кухни.
Источник:
