Доброго времени суток! Сегодня мы хотим поделиться своей Developer Story… а также опытом оптимизации стандартных алгоритмов нечеткого поиска под мобильные устройства.
Все началось с просмотра лекций Стэнфордского Университета по курсу “CS193P Developing Apps for iOS”. Но в качестве опытного проекта не хотелось выдать очередной калькулятор. Мы постоянно искали интересную идею для разработки. Как это обычно бывает, идея пришла внезапно, когда мозг уже готовился заснуть… Смысл задумки был достаточно прост: приложение должно определить, как правильно написать слово. А если слово введено пользователем с ошибкой — показать варианты правильного написания. Такое приложение могло оказаться полезным для выезжающих журналистов и студентов (как раз надвигалась зимняя сессия). Каково было наше удивление, когда мы выяснили, что подобных приложений нет! Да, есть словари, которые в лучшем случае пытаются дополнить искомое слово и допускают одну опечатку… Но скорость поиска и размер самого приложения удручают!
Помимо всего вышеперечисленного был еще один стимул поработать с алгоритмами нечеткого поиска, описанными в статье на Хабре. Давно хотелось реализовать подобные алгоритмы и измерить скорость их работы на мобильном устройстве.
Изначально был выбран подход, когда искомое слово сравнивается с каждым элементом из словаря при использовании “расстояния Левенштейна”. Но тест в “боевых” условиях на айфоне показал, что такой поиск занимает в среднем 30-90 секунд — это в словаре всего из 90000 слов! Недопустимо долго! Тогда был выбран другой путь: изначально строить индекс по словарю, используя метод хеширования по сигнатуре. А уже потом искать слово по готовому индексу. Быстро адаптировав приложение под новый метод, мы сразу проверили его на айфоне. И опять провал — создание индекса и, соответственно, старт приложения занимал порядка 90-120 секунд! Не каждый пользователь станет ждать 2 минуты для того, чтобы проверить, правильно ли он написал несколько слов. Приложение требовало еще большей оптимизации.
Следующим шагом стало создание индекса словаря на Mac’е, а также сохранение готового индекса в sqlite-базу. Дальше iOS-устройство загружает уже готовый индекс. Снова рефакторинг и адаптация приложения к новому методу. И наконец-то положительный результат — холодный старт приложения за 7-12 секунд! Затем мы попробовали нагрузить приложение еще больше — словарная база приложения была расширена до 355742 слов (ровно столько уникальных слов удалось собрать из нескольких орфографических и толковых словарей русского языка). После обновления индекса словаря старт приложения стал занимать 10-15 секунд. Но самое главное — то, что теперь поиск слова занимает от нескольких миллисекунд до десяти секунд при большом количестве схожих слов. Этот результат вполне меня устроил. Надо было двигаться дальше.
Чтобы приложением было удобнее пользоваться, мы добавили несколько дополнительных возможностей:
* Группировка результата по категориям: полное совпадения, с изменением одной буквы в слове (и так далее — до трех).
* Любое слово из найденных приложением, можно скопировать в буфер обмена.
Добавлен поиск значения слова в Вики-словаре, Википедии, Яндекс-словаре и Гугл поиске. Но эта возможность требует интернет-соединения.
* Приложение изначально разрабатывалось как универсальное и поддерживающее горизонтальный и вертикальный режимы экрана.
После того, как мы определились с названием приложения, оно “обрело лицо”, и споров по поводу внешнего вида уже не было. Перед глазами стояла школьная доска, на которой красивым учительским почерком выведены прописные буквы. Буквы, которые складываются в самое, пожалуй, популярное правило русского языка: “жи” “ши” пиши с буквой “и”! Чаще всего нам приходится искать и исправлять орфографические ошибки именно в школе. Поэтому школьная атмосфера в названии и оформлении приложения показалась нам наиболее уместной.
Ссылка на страницу проекта
Ссылка на приложение в AppStore: Жи-Ши
Upd1:
Ссылка на бесплатное приложение в AppStore: Жи-Ши Lite
Upd2:
Позже, основываясь на отзывах наших пользователей, мы внесли в приложение следующие изменения:
* Поиск по встроенному толковому словарю (под редакцией Т.Ф. Ефремовой).
* Добавлены действующие правила русского языка (орфография).
Ждем любой конструктивной критики, предложений и пожеланий!
PS: Промокоды для ознакомления:
N7TMEN3HTPHA
EKRTARHTRYRL
PKYJMERYWMKP
L9TYPNEFA7AH
FETYYTW33TLH
NEN6KFPX74HT
NY7HHLNL4X33
NXHEXR7F3L66
N37F7MTYLN77
9RW9JNYJ43X7
M9FFKK6FTYWA
F69YLWNT4PEN
JWKAELJ3YA7X
R7WMNHW37X94
AHJFRJ3HRAMN
96PTNLTXKJ76
LFPNXNHWA799
WFLENJAMJPK4
HRX6T93W644E
M7YR9T4TTJKL
6HXERELJ7YF7
NJMWP3J6FLLR
M39KYPLFYHE7
7LPAEN4L99KP
YWEP4EPMYM6Y
Y7NWK9ERMHYN
KLHH63HFEWJT
LLKY3PPJ3LLL
WHJFRP63WXRP
FK3WWXJ7MPN9
Предыстория
Все началось с просмотра лекций Стэнфордского Университета по курсу “CS193P Developing Apps for iOS”. Но в качестве опытного проекта не хотелось выдать очередной калькулятор. Мы постоянно искали интересную идею для разработки. Как это обычно бывает, идея пришла внезапно, когда мозг уже готовился заснуть… Смысл задумки был достаточно прост: приложение должно определить, как правильно написать слово. А если слово введено пользователем с ошибкой — показать варианты правильного написания. Такое приложение могло оказаться полезным для выезжающих журналистов и студентов (как раз надвигалась зимняя сессия). Каково было наше удивление, когда мы выяснили, что подобных приложений нет! Да, есть словари, которые в лучшем случае пытаются дополнить искомое слово и допускают одну опечатку… Но скорость поиска и размер самого приложения удручают!
Помимо всего вышеперечисленного был еще один стимул поработать с алгоритмами нечеткого поиска, описанными в статье на Хабре. Давно хотелось реализовать подобные алгоритмы и измерить скорость их работы на мобильном устройстве.
Начало работы
Изначально был выбран подход, когда искомое слово сравнивается с каждым элементом из словаря при использовании “расстояния Левенштейна”. Но тест в “боевых” условиях на айфоне показал, что такой поиск занимает в среднем 30-90 секунд — это в словаре всего из 90000 слов! Недопустимо долго! Тогда был выбран другой путь: изначально строить индекс по словарю, используя метод хеширования по сигнатуре. А уже потом искать слово по готовому индексу. Быстро адаптировав приложение под новый метод, мы сразу проверили его на айфоне. И опять провал — создание индекса и, соответственно, старт приложения занимал порядка 90-120 секунд! Не каждый пользователь станет ждать 2 минуты для того, чтобы проверить, правильно ли он написал несколько слов. Приложение требовало еще большей оптимизации.
Оптимизация
Следующим шагом стало создание индекса словаря на Mac’е, а также сохранение готового индекса в sqlite-базу. Дальше iOS-устройство загружает уже готовый индекс. Снова рефакторинг и адаптация приложения к новому методу. И наконец-то положительный результат — холодный старт приложения за 7-12 секунд! Затем мы попробовали нагрузить приложение еще больше — словарная база приложения была расширена до 355742 слов (ровно столько уникальных слов удалось собрать из нескольких орфографических и толковых словарей русского языка). После обновления индекса словаря старт приложения стал занимать 10-15 секунд. Но самое главное — то, что теперь поиск слова занимает от нескольких миллисекунд до десяти секунд при большом количестве схожих слов. Этот результат вполне меня устроил. Надо было двигаться дальше.
Дополнительные возможности
Чтобы приложением было удобнее пользоваться, мы добавили несколько дополнительных возможностей:
* Группировка результата по категориям: полное совпадения, с изменением одной буквы в слове (и так далее — до трех).
* Любое слово из найденных приложением, можно скопировать в буфер обмена.
Добавлен поиск значения слова в Вики-словаре, Википедии, Яндекс-словаре и Гугл поиске. Но эта возможность требует интернет-соединения.
* Приложение изначально разрабатывалось как универсальное и поддерживающее горизонтальный и вертикальный режимы экрана.
Лицо программы
После того, как мы определились с названием приложения, оно “обрело лицо”, и споров по поводу внешнего вида уже не было. Перед глазами стояла школьная доска, на которой красивым учительским почерком выведены прописные буквы. Буквы, которые складываются в самое, пожалуй, популярное правило русского языка: “жи” “ши” пиши с буквой “и”! Чаще всего нам приходится искать и исправлять орфографические ошибки именно в школе. Поэтому школьная атмосфера в названии и оформлении приложения показалась нам наиболее уместной.
Ссылка на страницу проекта
Ссылка на приложение в AppStore: Жи-Ши
Upd1:
Ссылка на бесплатное приложение в AppStore: Жи-Ши Lite
Upd2:
Позже, основываясь на отзывах наших пользователей, мы внесли в приложение следующие изменения:
* Поиск по встроенному толковому словарю (под редакцией Т.Ф. Ефремовой).
* Добавлены действующие правила русского языка (орфография).
Ждем любой конструктивной критики, предложений и пожеланий!
PS: Промокоды для ознакомления:
N7TMEN3HTPHA
EKRTARHTRYRL
PKYJMERYWMKP
L9TYPNEFA7AH
FETYYTW33TLH
NEN6KFPX74HT
NY7HHLNL4X33
NXHEXR7F3L66
N37F7MTYLN77
9RW9JNYJ43X7
M9FFKK6FTYWA
F69YLWNT4PEN
JWKAELJ3YA7X
R7WMNHW37X94
AHJFRJ3HRAMN
96PTNLTXKJ76
LFPNXNHWA799
WFLENJAMJPK4
HRX6T93W644E
6HXERELJ7YF7
NJMWP3J6FLLR
M39KYPLFYHE7
7LPAEN4L99KP
YWEP4EPMYM6Y
Y7NWK9ERMHYN
KLHH63HFEWJT
LLKY3PPJ3LLL
WHJFRP63WXRP
FK3WWXJ7MPN9
