Технологии и подходы в разработке новостного аггрегатора (поиск по новостям) Любимов Валентин Аспирант кафедры АЯ ВМиК Руководитель проекта LiveInternet.ru

Новостная аггрегация Новость – статья в электронном СМИ или же другом источнике. Аггрегация – процедура сбора информации из источников и предоставление пользователю обобщенной информации. Из-за схожей с информационным поиском архитектуры новостную аггрегацию часто называют «поиском по новостям» - News Search.

Архитектура Сбор данных из источников(Crawling) пауки – роботы или же XML экспорт Извлечение информации из данных (Information Extraction) Сортировка по важности (Ranking) Обобщение информации (Clusteristion), создание сюжетов

Сбор данных Характеристики сборки данных Задан ли список источников поиска (сайтов) или источники требуется найти Оговоренный формат данных(например RSS- XML стандарт на экспорт новостей) или произвольный(например – произвольная HTML страница, на которой, среди произвольного набора ссылок и рекламы находится текст статьи) Периодичность обновления, определение необходимости обновить информацию из источника

Если источники известны Простейший подход-список сайтов, за обновлениями которых надо следить, задан. Каждый сайт предоставляет свои обновления в оговоренном формате. Пример- Yandex.Новости. Новостные сайты заключают договор, предоставляют свои данные в формате RSS (несколько расширенном). Простейший пример формата экспорта: передача списка (дата новости, заголовок, текст новости, адрес новости) последних n новостей. Паук по очереди заходит на каждый источник, смотрит есть ли новости, написанные позднее последнего обновления этого источника.

Если источник не предоставляет экспорт в особом формате Используем стандартный «паук», который работает и в случае «поисковых систем». Архитектура: Очередь адресов документов, которые требуется скачать Программа скачивания документа по его адресу Программа извлечения из документа ссылок на другие документы Средства проверки – не скачивался ли документ по данному адресу ранее (или не находится ли он сейчас в очереди на скачивание). Если мы ищем только на заданных сайтах(коллекциях документов) – то ссылки на другие сайты откидываем.

Хэш функция –для тех, для кого это новое понятие String hash(String S); Свойства функции: Входная строка- произвольной длины, результат- фиксированной для данной функции длины (например 32 байта) Каждой входной строке соответствует ровно одна строка- результат. Вероятность того, что двум случайно выбранным входным строкам соответствует одинаковое значение функции, близка к 1/2 n,где n –количество бит в результате функции. Двум «похожим» входным строкам (отличающимся в нескольких символах, например) соответствуют разные и «непохожие» результаты. Хэш функции используются для построения индексов баз данных, в шифровании, средствах обеспечения конфиденциальности и многих других задачах. Известные хэш функции – MD5, SHA-1 и другие

Критерии определения – нужно ли скачать документ с заданным адресом и добавлять ли его в базу Скачивался ли ранее документ ровно с таким адресом. Храним значения хэш функций от адресов документов (таким образом хранение адреса одного документа занимает фиксированное число байт). Храня отсортированно – можем применять двоичный поиск для проверки наличия адреса (вернее значения его хэш-функции в списке). Определение скачивался ли документ ровно с таким же содержимым. Для этого храним список значений хэш- функций для содержимого документа. Если мы вычислили для тела документа хэш-функцию и полученное значение уже нам встречалось, то с большой вероятностью (=1-1/2 256 для функции с результатом размера 32 бита) Определение скачивался ли документ с той же информацией(отличающийся, например, оформлением или рекламными блоками, то есть не совпадающий полностью по тексту) – выявление полудубликатов

Выявление полудубликатов – методы шинглов и Яндекса Делим текст на шинглы – перекрывающиеся области из 20 слов – с 1го по 20е, со 2го по 21е, с 3го до 22 и т.д. Для каждого шингла вычисляем хэш-функцию. Сохраняем как характеристику документа – значения тех хэш-функций, которые оканчиваются символом Z. Таким образом текст из 1000 слов характеризует, в среднем, 4 хэш-значения. Хорошим(экспериментально) критерием похожести документов, является совпадение у них хотя бы одного из чисел-характеристик. Действительно, одно такое совпадение означает, с высокой вероятностью, что совпадают 256 десятисловных фрагментов в сравниваемых документов Метод Яндекса – для всех документов используется единый массив из нескольких сотен слов, которые с большой степенью вероятности представлены во всех документах. Храня для каждого документа количество вхождений каждого из слов вектора – мы хорошо выявляем полудубликаты.

Извлечение данных Задача – вычленить из данных ту информацию, которая требуется. Это могут быть новости, которые требуется «вытянуть» из сложно оформленного сайта или цены на товары из интернет –магазинов. Также в эту проблемную область входит задача определения типа источника, применимости к нему алгоритмов разбора и проверка – похожа ли извлекаемая информация на тот тип информации, которую хочется получить. В простейшем случае, надо по скачанным с сайта страницам понять- новостной это ресурс или нет, интернет-магазин или нет). И если да – получить данные в структурированной форме. В случае, если формат получаемых данных задан, то есть известен принцип размещения информации в них (например XML файл), то задача извлечения решается использованием стандартного парсера для этого формата.

Подходы к обработке данных с неизвестным форматом Случай анализа результатов поисковых систем. При запросе к поисковой системе, она выдает результаты поиска всегда в одном и том же формате. Определить – является ли данная страница результатом запроса к поисковой системе, можно по многократному повторению друг под другом характерных блоков, состоящих из выделенной ссылки, текстового описания, и вспомогательных ссылок внизу. Для того, чтобы извлекать данные из этой поисковой системы, требуется выделить эти блоки, запомнить механизм их выделения – и при обработке других запросов использовать уже созданный шаблон разбора. Так работают метапоисковые системы, которые объединяют в себе ответы многих поисковых систем на данный запрос, причем список поисковых систем не задается программистом, а постоянно обновляется в автоматическом режиме. В российском интернете таких поисковых систем мне не известно.

Анализ новостного сайта В новостном сайте, в отличие от поискового сервиса, все страницы не имеют единого шаблона и внешние признаки новостного сайта, при взгляде на одну его страницу, неочевидны. Для определения – новостной сайт это или нет, требуется скачать страницы этого сайта, отобрать похожие в группы. Обычно, новостной сайт состоит из главной страницы, где стоят некоторые анонсы последних новостей со ссылками на них и ссылки на разделы этих новостей, тоже со ссылками на конкретные новости. Новости обычно создаются по одному шаблону, что можно(хоть и непросто) определить автоматически. Используются различные подходы 1. Геометрический – ищем центральную область, воссоздавая, анализируя разметку, внешний вид документа. В центре – самое главное, то есть статья. 2. Механизм грамматик – «расстояние между шаблонными деревьями».

Представление документа в виде дерева HTML(XML) документ это запись иерархии элементов страницы, поэтому он очевидным образом представляется в виде дерева. HTML doc Text HEAD TITLE BODYP B IMG Расстояние между деревьями – функция от количества вершин одного дерева, которые нужно добавить, удалить или изменить, чтобы получилось второе дерево. Наиболее близкие деревья вероятнее всего соответствуют страницам одного типа, сгенерированным по одному шаблону

Составление шаблона по группе деревьев и извлечение информации. Имея множество страниц с близкими деревьями можно с большой точностью установить структуру информации на странице. Для этого в местах различий выставляются знаки «сколько угодно» «хотя бы один» «один или ноль» и получается обобщенное для данной группы дерево, которому они все удовлетворяют. Обязательные элементы определяются из общих для всех элементах эвристиками. Например – текст статьи должен быть самым длинным текстом на странице. Заголовок должен быть текстом, который ближе всех к странице. Эвристики можно усилить геометрическим подходом, кратко описанным ранее (текст- самый центральный элемент страницы)