Dev Story Жи-Ши. История о пропавшей «Ы»

Информатор avatar | 11
FavoriteLoading В закладки

ТЕКСТ: ДМИТРИЙ КЛИМКИН. Всем привет! Сегодня мы хотим поделиться своей 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, где разработчики делятся секретами своей внутренней кухни.

Поставьте оценку:

1 Звезд2 Звезды3 Звезды4 Звезды5 Звезд (Нет голосов)
🤓 Хочешь больше? Подпишись на наш Telegramнаш Telegram.
... и не забывай читать наш Facebook и Twitter 🍒
FavoriteLoading В закладки
undefined
iPhones.ru
ТЕКСТ: ДМИТРИЙ КЛИМКИН. Всем привет! Сегодня мы хотим поделиться своей Developer Story… а также опытом оптимизации стандартных алгоритмов под мобильные устройства. Все началось с просмотра лекций Стэнфордского Университета по курсу “CS193P Developing Apps for iOS”. Но в качестве опытного проекта не хотелось выдать очередной калькулятор. Мы постоянно искали интересную идею для разработки. Как это обычно...
Прокомментировать

🙈 Комментарии 11

  1. Epervin avatar
    Epervin9 февраля 2012
    0

    пока не долистал до скрина с таблицами кзалось еще относиттельно ничего.. но как только увидел таблицы.. ужас.

  2. weart avatar
    weart9 февраля 2012
    0

    Да, дизайн страшен.

  3. Epervin avatar
    Epervin9 февраля 2012
    0

    уЗабдьте раз и навсегда про Times New Roman

  4. infinity avatar
    infinity10 февраля 2012
    0

    Таблица действительно вышла ужасная… Менять дизайн однозначно.

    infinity avatar
    infinity10 февраля 2012
    0

    И в поиске, при написании слова результаты должны предлагаться. Зачем набирать огромное слово целиком, если можно набрать первые три буквы и выбрать нужное из предложенных.

  5. kapushon avatar
    kapushon10 февраля 2012
    0

    “The Rules” Бирмана на голову выше

  6. imger avatar
    imger10 февраля 2012
    0

    ребят, наймите дизайнера) честно. идея у вас может нормальная, реализовано тоже, но тут же страшно всё на вид) что ж вы Джобса так обижаете

  7. Бобров Евгений avatar
    Бобров Евгений10 февраля 2012
    0

    В качестве юзабилити хорошо бы добавить автоматическую вставку слова в буфере обмена (как в lingvo для ios).

  8. migmit10 февраля 2012
    0

    Эм… если разработчику только на третьей итерации приходит в голову НЕ генерировать каждый раз одни и те же данные – это очень плохой признак. Честно говоря, прочитав про долгий старт приложения я даже сначала не понял, что происходит, пришлось перечитать.

  9. heximal avatar
    heximal10 февраля 2012
    0

    Не понятно, нафиг вообще вам понадобилась sqlite, какой в ней бенефит? Запросы наипростейшие, никакой сложной аналитики нет, тем более весь поиск реализован не средстами базы. Я бы посмотрел в сторону nosql. Обычное key-value хранилище идеально в данном случае.

  10. Sundukov avatar
    Sundukov10 февраля 2012
    0

    сыровато получилось. на вашем месте я бы пока сделал его бесплатным, чтобы продавать за доллар улучшенную и поправленную версию.

Вы должны авторизоваться или зарегистрироваться для комментирования.

Нашли орфографическую ошибку в новости?

Выделите ее мышью и нажмите Ctrl+Enter.

Как установить аватар в комментариях?

Ответ вот здесь