Введение 5
YT и YQL 7
Постановка задачи 10
Обзор литературы 12
Глава 1. Подготовка к решению задачи 14
1.1 Анализ имеющихся данных 14
1.2 Стек технологий 16
1.2.1 Язык запросов 16
1.2.2 Интерфейс 18
1.2.3 YQL и YT 19
Глава 2. Обзор существующих решений 20
2.1 Встроенные возможности языка JavaScript 20
2.2 libxml by Google 22
2.3 Выводы 22
Глава 3. Реализация 24
3.1 Чтение XPath запросов 24
3.2 Поиск данных в дереве 27
3.2.1 Идея алгоритма 27
3.2.2 Реализация 28
3.3 Проблемы, появившиеся при реализации поиска 29
3.3.1 Неограниченное количество узлов между двумя определенными 29
3.3.2 Индексация узлов в дереве 30
3.4 Реализация интерфейса 32
3.4.1 Отправка JSON дерева на страницу с решением поиска по XPath 32
3.4.2 Отображение подходящих запросу узлов 33
3.4.3 Хранение узлов и быстрый доступ к ним 33
3.5 Поиск в YQL 35
Выводы 37
Что уже сделано? 37
Интерфейс для отображения 38
Работа с несколькими документами одновременно 39
Поиск в YQL 40
Дальнейшие улучшения приложения 42
Оптимизация запросов 42
Оптимизация алгоритма 43
Проблема множественных XPath запросов 43
Заключение 44
Список литературы 45
1. Литература 45
2. Ссылки на документации 45
3. Ссылки на сайты с полезной информацией 49
Приложение 50
Приложение A. Список терминов, употребляемых в работе 50
Приложение B. Примеры кода 51
B.1. Пример: работа библиотеки xpath-analyzer 51
B.2. Код функции поиска в документе узлов, подходящих запросу 53
B.3. Код функции поиска, рассматривающий случай неограниченного количества узлов между двумя данными 53
B.4. Код функции, сохраняющий данные по узлам в хэш-таблицы для повторного поиска 54
Приложение C. Примеры рабочего приложения 55
C.1. Начальный интерфейс при загрузке страницы 55
C.2. Поиск в документе 55
C.3. Отображение нескольких документов на странице 56
C.4. Поиск в нескольких документах сразу 56
Купить

Поиск данных в большом наборе - интересная и в то же время сложная задача. Чтобы решить ее, необходимо определить:
• как и по какому критерию проводить поиск;
• оптимальный алгоритм, реализующий поиск;
• что нужно считать выходным результатом.
Каждый день компания Яндекс (далее просто Компания) обрабатывает миллиарды поисковых запросов и выдает на них какой-то ответ. Чтобы оставаться в топе (быть лучшей среди всех поисковых систем), Компания использует множество технологий для улучшения поиска (например, алгоритм Multi-Armed Bandits - алгоритм выдачи поиска, который «подмешивал» в топ поиска к самым популярным сайтам сайты-новички).
Для того, чтобы все эти технологии работали, необходимо каким-то образом сохранять информацию о поведении пользователя на странице выдачи поиска - необходимо сохранять клики, скроллы, сохранять счётчики и т.д. Это помогает понять, где больше всего происходит активности от пользователей на той или иной странице выдачи поиска. У каждой кнопки/ссылки на странице есть счетчик: он показывает, сколько раз пользователи перешли по какой-либо ссылке или нажали на определенную кнопку.
На первых порах эти данные хранились в большой строковой переменной, и для того, чтобы достать из нее какие-то определенные данные, разработчикам нужно было всего лишь написать простой скрипт, который находит подстроку в строке. Это не занимало много времени и сильно не отвлекало разработчиков на написание лишнего кода.
Со временем данные становились все сложнее и больше: они приобрели структуру сложного и большого документа. Для каждой страницы создается документ, который хранит в себе все данные о ссылках на странице, на которые можно перейти (ссылки на счетчики, ссылки на метрики и т.д.).
На данный момент, все данные, которые содержат в себе информацию о счетчиках и метриках, хранятся в платформе YT.
YT - основная платформа для хранения и обработки больших объемов данных в компании Яндекс [27]. Это MapReduce система, направленная на широкий спектр вычислительных задач в области Big Data. Более подробную информацию можно найти в источнике [27] и в видеозаписи конференции «Yet another Conference» в докладе «YT — новая платформа распределённых вычислений».
MapReduce — модель распределенных вычислений, представленная компанией Google, используемая для параллельных вычислений над очень большими, вплоть до нескольких петабайт, наборами данных в компьютерных кластерах (источник - Википедия).
С увеличением сложности и размера данных о счётчиках увеличилось и время их обработки, поиска нужных данных. Если раньше достаточно было написать простой скрипт, который находил подстроку в строке, то теперь необходимо реализовывать обход документа в поисках необходимых данных. Все эти документы хранятся в YT, откуда еще нужно сначала получить необходимые данные, чтобы потом обработать их.
Каждый день сотрудники Компании проверяют правильность работы счетчиков и метрик в выдаче поиска (или же используют эти данные для других задач). Они ищут в большом наборе данных необходимые документы и пытаются достать из них требуемую информацию.
Ниже приведен список недостатков такого подхода к поиску данных:
• нет единого интерфейса доступа к данным;
• каждый раз необходимо реализовывать свой обход документа, на который разработчик/аналитик тратит много времени;
• используются разные инструменты для обхода документа, и не всегда другой человек может понять чужой код, поэтому он вынужден писать свою реализацию поиска;
• написанный код может быть очень плохо оптимизирован либо не сразу работать, что приводит к потере времени на поиск ошибок в написанном скрипте;
• если же аналитик ищет необходимые данные вручную без написания скриптов и программ, то на это уходит очень много временных ресурсов;
• в ситуации, когда необходимых документов много (десятки, тысячи, миллионы, миллиарды), на поиск и последующий анализ данных потребуется очень большое количество времени;
• чем больше критериев при отборе документов, тем сложнее их получить из YT.
YT и YQL
Yandex Query Language (YQL) — универсальный декларативный язык запросов к системам хранения и обработки данных.
С помощью YQL и YT [25, 29] можно за достаточно короткое время получить все документы, которые будут относиться к конкретному поисковому ответу.
Однако, если же разработчикам будут необходимы данные о выдаче поиска, которые будут содержать в объектном ответе «колдунщик» картинок, функциональность YT и YQL не поможет справиться с данной задачей за короткое время.
«Колдунщики» поисковой системы Яндекс — это элементы поисковой выдачи, которые предлагают пользователю ответ на его запрос прямо на странице с результатами поиска.
Рис. 1: Пример «колдунщика» погоды в поисковой системе Яндекс.
Один из вариантов решения данной проблемы заключается в поиске совпадений по ключевым словам в документе, но это приводит к тому, что некоторые данные, которые изначально были необходимы разработчику, не попали в результат и наоборот. В итоге уже во время работы с данными разработчик понимает, что какая-то часть нужных ему данных не пришла, а какие-то данные он вообще не должен был обрабатывать.
Так как эти проблемы возникли в Компании относительно недавно, и появилась острая необходимость в едином инструменте для поиска данных, я решил взяться за эту задачу: разработать единый и удобный интерфейс для поиска и анализа необходимых документов в большом наборе данных.
Данную задачу я нашел очень интересной и актуальной, так как если разработчики получат единый и удобный интерфейс поиска данных, то работа разработчиков по проверке поисковых метрик ускорится в несколько раз.
Сейчас среднее время, уходящее на написание скриптов и запросов, у разработчиков составляет 30 минут. Стоит еще учитывать время, которое потратит разработчик на анализ данных, которые изначально не соответствовали пожеланиям разработчика/аналитика и попали в результат из- за ошибки в написанном коде. Данную оценку времени необходимо уменьшить в несколько раз.
Купить