Платон Ефимов SemperPeritus

Данная статья является перевом статьи от Mladen Rakonjac

Очень сложно найти один проект, который охватывал бы всё новое в разработке под Android в Android Studio 3.0, поэтому я решил написать его. В этой статье мы разберём следующее:

1. Android Studio 3
2. Язык программирования Kotlin
3. Варианты сборки
4. ConstraintLayout
5. Библиотека привязки данных Data Binding
6. Архитектура MVVM + паттерн repository (с mapper'ами) + Android Manager Wrappers
7. RxJava2 и как это помогает нам в архитектуре
8. Dagger 2.11, что такое внедрение зависимости, почему вы должны использовать это.
9. Retrofit (Rx Java2)
10. Room (Rx Java2)

Каким будет наше приложение?

Наше приложение будет самым простым, которое охватывает все перечисленные выше вещи: у него будет только одна функция, которая извлекает все репозитории пользователя googlesamples из GitHub, сохраняет эти данные в локальной базе данных и показывает их пользователю.

Я попытаюсь объяснить как можно больше строк кода. Вы всегда можете посмотреть код, который я опубликовал на GitHub.

В предыдущей статье я рассказал как создать сервер и клиент на Python 3, используя встроенные сокеты. Но у этого приложения было много недостатков, которые я попытаюсь исправить в этой и последующих статьях.

Так какими же недостатками обладает наше приложение?

• Отсылается один единственный пакет, длина которого не может превышать заранее заданной границы в 1 Кбайт.
• Приложение без проверки передаёт аргумент, принятый из сети, в оболочку (URL).
• Недостаток функциональности. Мы не можем, например, скачать все изображения с Хабра, или скачать отдельный хаб.

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

Описание протокола

Мы использовали «голый» протокол TCP для передачи данных между сервером и клиентом. TCP — это потоковый протокол, он передаёт данные последовательным набором байт. Передавая команду с аргументами по сети в первой версии нашего приложения мы читали только 1024 байт данных из принятого пакета. Но что делать, если данные не помещаются в 1024 байт? Выход только один — разбить данные на несколько пакетов на одном хосте и «склеить» их в один кусок при получении на другом хосте. Но как узнать когда заканчивается одна команда (с её аргументами) и начинается другая? Для этого нам нужно нужно знать, какова длина всего передаваемого сообщения.

Так как заранее узнать длину сообщения у нас не получиться, придётся передавать её в одном из пакетов. Разумеется, делать это лучше в самом начале первого пакета. Выделив под хранение длины сообщения всего 4 байта, мы сможем передать сообщение длиной свыше 4 млрд символов! Длина сообщения — это информация о нём, то есть, часть заголовка, заголовка нашего протокола. Какого протокола спросите вы? Если верить Википедии, то

Протокол передачи данных — набор соглашений интерфейса логического уровня, которые определяют обмен данными между различными программами.

Мы договорились, что будем передавать данные в нескольких пакетах по TCP, а в начале данных первого пакета будет храниться длина всего сообщения в байтах. Таким образом мы разработали наш простой протокол! Нужно помнить, что наш протокол основан на TCP, а значит, обладает теми же особенностями, что и последний.

Проект был написан скорее в учебных целях (научиться сетевому программированию в Python), чем в практических. Такую же роль несёт и статься, ведь сейчас вряд ли кто-то будет скачивать сайты, чтобы прочитать пару статеек (за исключением некоторых случаев, когда подобное реально может пригодится).

Не так давно качество мобильного интернета в моём городе стало постепенно ухудшаться из-за возрастающей на сети операторов нагрузки и некоторые сайты, требующие большое количество соединений (зависимые файлы страницы) стали загружаться ну ОЧЕНЬ медленно. По вечерам скорость опускается на столько, что некоторые сайты могут полностью загружаться в течении нескольких десятков секунд.

Есть несколько способов решения данной проблемы, но я решил выбрать немного необычный для нашего времени способ. Я решил скачивать сайты. Конечно, данных способ не подходит для крупных сайтов, вроде Хабра, тут разумнее использовать парсер, но можно скачать и отдельный хаб, список пользователей, или только свои публикации с помощью HTTrack Website Copier, применив фильтры. Например, чтобы скачать хаб Python с Хабра нужно применить фильтр "+habrahabr.ru/hub/python/*".

Этот способ можно использовать ещё в нескольких целях. Например, чтобы скачать сайт, или его часть, перед тем, как вы окажитесь без интернет-соединения, например, в самолёте. Или для того, чтобы скачать заблокированные на территории РФ сайты, если скачивать их через Tor, что будет очень медленно, или через компьютер в другой стране, где данных сайт не запрещён, а потом передать его на компьютер, находящийся в РФ, что будет гораздо быстрее для многостраничных сайтов. Таким образом мы может скачать, например, xHamster Wikipedia через сервер в Германии или Нидерландах и получить сайт в сжатом виде по SFTP, FTP, HTTP или другому, удобному для вас, протоколу. Если, конечно, места хватит, для такого большого сайта :)

Ну что, начнём!?

В предыдущей части мы узнали как выполнить запрос к построенному индексу и теперь мы можем получить ссылки на документы, в которых встречается то, что мы запросили. Но есть проблема: это просто список документов, в которой, возможно, есть то, что нам нужно. Он не отсортирован по важности, для нас, информации, содержащейся в документе. Про эту проблему мы и поговорим в этой части.

Ранжирование результатов запросов

Заключительным шагом в построении поискового движка является создание системы для ранжирования документов по их релевантности к запросу. Это наиболее сложная часть, поскольку она не имеет прямого технического решения: она требует творчества и вашего собственного взгляда. В этой мы реализуем TF-IDF ранжирование (от англ. TF — term frequency (частота слова) и IDF — inverse document frequency (обратная частота документа)), которое является одним из простейших способов сортировки наших документов. В этой части не будет никакого кода, но вы можете изучить финальную версию движка на GitHub. Мы только изучим теорию TF-IDF, а его реализация довольно проста, причем большая часть работы делается во время построения индекса.

Так что, термин «частота» является первой частью нашей систему ранжирования? Ну, это именно то, что приходит на ум, когда вы его слышите: количество раз, которое встречается каждое слово в конкретном документе. Термин частота, как метрика, не учитывает запрос: он предполагает, что документ — это просто амбивалентный набор маркеров, и точное представление о нём можно получить всего лишь пересчитав, сколько раз каждый маркер (слово) встречается. Это не совсем точное предположение, но оно широко используется в области классификации документов. Формально, он больше известен как модель “мешок слов”.

В предыдущей части мы построили индекс, но мы всё ещё не можем выполнять запросы по нему. Про это я и расскажу в этой статье.

Выполнение запросов к индексу

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

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

Примечание: во всех примерах кода ниже, каждая функция будет использовать в переменную с именем ‘invertedIndex’, которая генерируется в предыдущей части статьи. Для полного понимания происходящего ниже вы можете ознакомиться с финальным результатом на GitHub.

Мы собираемся реализовать стандартные запросы в первую очередь. Простой способ реализовать их — разбить запрос на слова (маркеры, как описано выше), получить список за каждое слово, документы в которых они встречаются, а затем объединить все эти списки. Вот как мы выполним запрос для одного слова:

Просматривая ленту новостей я наткнулся на рекомендацию от Типичного Программиста на статью «Implementing a Search Engine with Ranking in Python», написанную Aakash Japi. Она меня заинтересовала, подобного материала в рунете не очень много, и я решил перевести её. Так как она довольно большая, я разделю её на 2-3 части. На этом я заканчиваю своё вступление и перехожу к переводу.

Каждый раз как я использую Quora, я в конечном итоге вижу по крайней мере вопрос вроде этого: кто-нибудь спрашивает, как работает Google и как они могли бы превзойти его по поиску информации. Большинство вопросов не настолько смелые и дезинформирующие, как этот, но все они выражают подобное чувство, и в этом они передают значительное непонимание того, как работают поисковые системы.

Но в то время как Google является невероятно сложным, основная концепция поисковой системы, которые ищут соответствия и оценивают (ранжируют) результаты относительно поискового запроса не представляет особой сложности, и это может понять любой с базовым опытом программирования. Я не думаю, что в данный момент возможно превзойти Google в поиске, но сделать поисковой движок — вполне достижимая цель, и на самом деле это довольно поучительное упражнение, которое я рекомендую попробовать.

Это то, что я буду описывать в этой статье: как сделать поисковую систему для локальных текстовых файлов, для которых можно обрабатывать стандартные запросы (по крайней мере, одно из слов в запросе есть в документе) и фразу целиком (появляется вся фраза в тексте) и может ранжировать с использованием базовой TF-IDF схемы.

Есть два основный этапа в разработке поискового движка: построение индекса, а затем, используя индекс, ответить на запрос. А затем мы можем добавить результат рейтинга (TF-IDF, PageRank и т.д.), классификацию запрос/документ, и, возможно, немного машинного обучения, чтобы отслеживать последние запросы пользователя и на основе этого выбрать результаты для повышения производительности поисковой системы.

Итак, без дальнейших церемоний, давайте начнем!