Створення пошуку по бібліотеці юним програмістом — як це?

На днях натрапив на публікацію мого ровесника, і вона спонукала мене написати і свою історію про свій проект, який абсолютно так само не допоміг, а тільки завадив вступу у ВНЗ.

image

Вступ
В один прекрасний день я зайшов до бібліотеки за одним розповіддю. Сказавши назву і автора розповіді бібліотекаря, отримав стопку збірників даного автора. Для того щоб знайти серед усього цього різноманіття потрібний розповідь, довелося перебрати всі твори. Набагато легше було б «загугліть» потрібний твір і отримати бажане в кілька кліків.

image

І тоді я замислився: «А чому в бібліотеках досі немає такого? Це ж так зручно!». Природно, як будь-який порядний ледачий програміст, я пішов прямо в пошуковик шукати подібні проекти. І зіткнувся з проблемами. Всі знайдені проекти були або комерційними (платними), або аматорськими та неякісними.

Природно, подібну несправедливість терміново потрібно було вирішувати, незважаючи на дедалі ближчий ЄДІ і вступ до ВУЗУ.

Вибір мови
Першим ділом стало зрозуміло, що без веб-частини не обійтися. Незважаючи на мою особисту непереносимість до веб-програмування, я сів за гугл і почав вивчати це питання.

Слова про швидкодію вже неправда

Після кількох годин я нарешті вибрав потрібну мову. Точніше не мова, а FrameWork RubyOnRails. Чому він? Тому що він використовує повноцінний ООП мову, активно розробляється гігантським ком'юніті і володіє швидким ядром. До того ж, Ruby люблять дівчата (на презентації краще не говорити).

Природно, заснований він був на «прекрасному» мові Ruby. Так як я на рівні Junior знаю Java, вивчити будь-який інший ООП мова для мене не склало праці. Тиждень кожен вечір дивився по 2 лекції і в підсумку міг похвалитися необхідними знаннями синтаксису Ruby. І потім мою самовпевненість опустили… А все тому, що даний FrameWork настільки величезний і різноманітний, що знання Ruby допомогли мені лише трохи. Вивчивши MVC технологію і інші задумки злісних веб-програмістів, я приступив до реалізації проекту.

Авторизація
Першою перешкодою на моєму шляху стала, як це не дивно, авторизація. Я вирішив використовувати технологію OAuth. Принцип її полягає в тому, що використовуються токени замість паролів. Використання токенів дозволяє не турбуватися, що твій пароль вкрадуть, а так само налаштовувати кожен токен під себе (наприклад, можна брати одноразові токени з правами лише на одну операцію). Для зберігання паролів на серверній частині спочатку я вирішив використовувати MD5 шифрування, однак почитав про нього в інтернеті, я вирішив, що даний метод застарів. Злом на нових комп'ютерах здійснюється лише за 1 хвилину. Тому я вирішив використовувати bCrypt, який забезпечує майже 100% захист від розшифровки пароля БД. Так як я вирішив самостійно зробити подібну систему, довелося думати над оптимізацією. В першу чергу, токени довелося перекладати з рядка в числове значення, щоб по БД можна було шукати бінарним пошуком.

image

Здавалося б, що складного може бути у простому шкільному проекті з авторизацією? Почнемо з того, що віконце авторизації я робив 20 годин. А продовжимо тим, що мій проект повністю OpenSource і запускається в локальній мережі, а це означає, що досить розгорнути свій сервер на мобільному, щоб перехоплювати токени. Тому я придумав власну систему перевірки валідності сервера. З кожним токеном сервер видає два значення. ID в базі даних і унікальний нечисленний индетификатор. Кожний раз, коли клієнт хоче перевірити валідність сервера, він відправляє ID сервера, сервер повертає йому индетификатор. І тільки тоді клієнт відправляє серверу токен. Виходить авторизація з двох сторін.

Алгоритм пошуку
image

У всіх подібних проектах слабка сторона — пошук. Я б не хотів, щоб і у моєму проекті присутній такий недолік. Використання готових рішень повністю відмітається з причини того, що всі великі пошуковики потребують з'єднання з інтернетом. Тому до даного питання я підійшов з усією серйозністю. Почитавши книжку про алгоритми, я вирішив, що для порівняння рядків краще використовувати алгоритм відстані Дамерау-Левенштейна, так як він володіє максимальною точністю на шкоду продуктивності, що найбільш важливо для проекту. Але виникла проблема в порівнянні цілих речень. Спочатку я використовував подібний алгоритм, розклавши таблицю порівняння на дерево графів. Досить довго я мучився з цим, але в підсумку отримав не той результат. Тому все зніс і вставив інший алгоритм у порівняння пропозицій. Його принцип простий до божевілля. Якщо слово має менше 3 помилок, прийняти його за правильне і додати в підсумковий індекс 1 бал. Якщо два правильних слова йдуть підряд, додати ще 1 бал. І так далі.

image

Так як пошук досить жорстко заданий, використовувати синтаксичний зміст речення не має сенсу. Тому в майбутньому планується додати фонетичний пошук і далі працювати у бік поліпшення самонавчання системи і централізації всіх даних.

image

Ще одним способом поліпшити якість пошуку стало самонавчання. Справа в тому, що кожен запит записується у БД і при необхідності возомжно видавати додавати бали популярним книгам. Припустимо, користувач «Гоша» любить фантастику. Ми це зрозуміли з того, що кількість знайдених книг по фантастиці набагато перевищує інші жанри. Тому згодом, при видачі результатів пошуку, система пошуку буде додавати користувачеві «Гоша» додаткові бали для книг по фантастиці. До того ж, такий великий пласт статистичних досліджень стати в нагоді.

Природно, даний алгоритм потім обзавівся різними оптимизациями, але про це іншим разом. Такий вибагливий алгоритм я вирішив реалізувати на C++ і зробити місток з Ruby за допомогою плагіна Rice. Ось ще один наочний приклад, чому я вибрав RubyOnRails і не пошкодував.

Розпізнавання зображень
Вирішити проблему швидкої оцифровки бібліотеки допоможе тільки механізми розпізнавання тексту на картинці. Так як підносити до веб-камері ПК зображення для зчитування досить нерозумно, було прийнято рішення розробити мобільний додаток для смартфонів. Написання базової програми зайняло близько тижня тому що в смартфонах активно використовується багатопоточність і досить жорсткі критерії для дизайну програми.

image

Після, провівши глибокий аналіз існуючих рішень, я вибрав Tuser як найкращий безкоштовний open-source продукт, заснований на технології OCR. До того ж, активно підтримуваний Google. Спробувавши з ним погратися, я зрозумів, що такий результат нікуди не годиться. Для точного розпізнавання довелося б досить довго працювати з попередньою обробкою зображення. До того ж, в исходниках даного проекту я виявив кілька грубих алгоритмічних помилок, виправлення яких може затягнутися на доооолго. Тому з сумом у голосі я пішов просити тимчасову ліцензію у Abbyy. Через два тижні щоденних дзвінків, я отримав її. Не можу не відзначити, що документація і Java-обгортка дуже грамотно написані і було одне задоволення працювати з таким продуктом. Однак, механізм розпізнавання далекий від 100% точності. Тому мені довелося робити автоматичне виправлення. За кілька годин я написав бота, який завантажив всю БД книг з популярного сайту labirint.ru. Використавши таку базу і вищезгаданий алгоритм пошуку, точність розпізнавання книг підвищився в рази.

ISBN
image

Незважаючи на очевидну простоту використання зчитування книг, я вирішив використовувати автозаповнення полів через ISBN. Так як завантажити всю БД книг ISBN нерозумно, вирішив використовувати Google Book Api для пошуку ISBN. Так само Offline-користувачам досі доступна БД лабіринту з >200 000 російськомовних книг. До того ж, легко реалізувати сканер штрих-коду книг (на тому ж Abbyy API) і тоді додавання книг буде тільки в задоволення.

Алгоритм надшвидкої оцифровки бібліотеки
image

Я подумав, що непогано було б сфотографувати полку і додати всі книги в електронний каталог. Реалізувати таке легко можливо тільки з використанням безкоштовної бібліотеки OpenCV з вбудованим детектором кордонів Кенні. До того ж, потрібно написати свій алгоритм для більш серйозного аналізу основних ліній книг і відправляти кожен корінець у Abbyy API і отримувати потрібний текст, обробляти його через БД лабіринту і відображати елементи взаємодії з UI поверх сфотографованого зображення. (На жаль, у мене так і не дійшли руки допилити цей функціонал до розуму. Часу немає)

Висновок
image

Низька вартість проекту і велика технологічна база дозволяє отримати доступ до високих і зручним технологіям навіть учням звичайних муніципальних шкіл. Прошу взяти той факт за уваги, що продукт абсолютно відкритий і прекрасно працює без доступу до інтернету. До того ж, ресурсомісткість проекту дозволяє запустити сервер навіть на Raspberry PI, вартістю 20$.

Незважаючи на те, що це мені не допомогло ніяк в житті, я отримав цінний досвід розробки повноцінного сайту й додатка і мені це було дико цікаво. Ну і пару скрінів:

imageimage

Джерела інформації
  • Велике спасибі англомовної аудиторії сайту www.stackoverflow.com
  • Велике спасибі користувачеві habrahabr.ru ntz за серію шикарних статей з нечіткого пошуку
  • Також у проекті були використані матеріали www.wikipedia.org
  • Велике спасибі моїй однокласниці Євгенії Лендрасовой за красиві і яскраві логотипи
  • Велетенське спасибі моєму викладачеві за підтримку в моїх починаннях
  • Велетенське спасибі компанії ABBYY за наданий OCR для розпізнавання тексту. Без нього я б не зміг реалізувати цей проект
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.