- PVSM.RU - https://www.pvsm.ru -
Пример работы алгоритма на сайте Автокадабра.
Наверное, все знают про сервис «Вебвизор», который позволяет записывать действия посетителей вашего сайта и просматривать их в режиме видео. Инструмент интересный, но когда на сайте много посетителей, составить картину жизни сайта проблематично, каждый ролик не посмотришь, и сгруппировать их нельзя.
Гораздо полезней отследить взаимодействие посетителей с сайтом, выяснить чем живёт сайт, с возможностью охватить одновременно множество посетителей. В итоге, появилась идея записывать информацию в виде осмысленного списка действий посетителей:
Запись состоит из двух частей: блок в котором происходит действие посетителя и само действие, например — выделение текста "времени" в блоке "Одна из ключевых особенностей ...". Для этого описания необходимо определить блок на странице и его имя. Если с именем было более-менее понятно, то над выделением блоков пришлось подумать.
Первый шаг — поиск существующих решений этой задачи. Один из них «Метод разбиения веб-страниц на семантические блоки с целью выявления схожих документов» (Д. И. Косинов. Воронежский государственный университет). Здесь определялся наибольший элемент и вынимался из страницы, и так до тех пор пока оставался контент. Чтобы не вытащить сразу весь <BODY>, в функцию веса был введён показатель глубины узла с целью выделять блоки по возможности на более низких уровнях. В процессе реализации и тестирования, выяснилось что проблема возникает в нескольких местах, во первых, требуется правильно подобрать коэффициенты для функции веса, во-вторых, после удаления контента на странице остаются «дырки», и следующий блок получается рваным, например блок 4 на рисунке.
После этого начали прорабатываться свои решения, одним из вариантов было выделять блоки с определенной длиной контента, который оказался не совсем удачным. Как-то вечером пришло другое решение, ставшее окончательным. Суть была проста, зачем искать семантические блоки на странице, когда вёрстка в основном итак объединяет блоки по смыслу, необходимо только определить до какого уровня разбивать блоки и какие именно.
Основная идея алгоритма заключается в предположении, что объединённые общим смыслом элементы веб-страницы зачастую имеют общего родителя в дереве DOM. Экспериментальным путём было установлено, что число обособленных смысловых блоков на странице в среднем равно квадратному корню из числа элементов на самом нижнем уровне дерева DOM (т. е. квадратному корню из числа элементов, не имеющих дочерних).
Коротко алгоритм можно описать следующими шагами:
function getSeparatedNodes(rootObj, numBlocks) {
var nodes = [rootObj];
while (nodes.length < numBlocks) {
var maxWeightNode = nodes[0];
var nodeIndex = 0;
for (var i = 0; i < nodes.length; i++) {
if (((nodes[i].weight > maxWeightNode.weight)
|| (maxWeightNode.lowerChildrenCount == 1)) && (nodes[i].lowerChildrenCount > 1)) {
maxWeightNode = nodes[i];
nodeIndex = i;
}
}
if (maxWeightNode.lowerChildrenCount <= 1) {
break;
}
nodes.splice(nodeIndex, 1);
nodes = nodes.concat(maxWeightNode.children);
}
return nodes;
}
Вес определят, какой следующий элемент будет разбит на дочерние, он учитывает как размер содержимого, так и площадь элемента,
Вес_элемента = log(длина_текста * 0.1 + 1.01) * log(площадь * 0.9 + 0.11).
Больший приоритет отдаётся площади элемента, магические числа 1.01 и 0.11 ограничивают логарифм, чтобы вес оставался положительным числом. Пустые узлы алгоритмом исключаются, поэтому минимальные значения размеров текста и площади составляют единицу. Для объектов, которые не могут содержать внутри текст (изображения, встроенные объекты и т. д.), параметр длина_текста считается как площадь / 140 (140 — среднее значение площади одного символа текста). При подсчёте длины текста исключаются повторяющиеся пробелы, а также не учитывается внутренний текст элементов <STYLE> и <SCRIPT>.
Поиск названия блока достаточно прост:
Ниже представлены примеры, того, что вышло в итоге (картинки кликабельны):
По такому же алгоритму, возможно разделить блок на подблоки:
В живую можно посмотреть здесь [5], также и другие примеры.
Также нашлось множество патентов, по данной тематике, может кому пригодится.
Алгоритм получился рабочим, достаточно простым и понятным, что немаловажно. Из минусов, не слишком устойчив, небольшие изменения кода он переживёт, но при добавлении виджетов на страницу, других изменениях структуры документа, блоки могут разбиться иначе.
Автор: dkuser
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/54205
Ссылки в тексте:
[1] Image: http://habrastorage.org/storage3/f38/991/e86/f38991e8673fe4e028c5b013c8c3c356.png
[2] Image: http://habrastorage.org/storage3/94c/8a1/858/94c8a185853b275128ad68736af0d5e4.png
[3] Image: http://habrastorage.org/storage3/e06/526/f8f/e06526f8f949ad0c46fc5084b243b43d.png
[4] Image: http://habrastorage.org/storage3/326/26b/e59/32626be594617ed47dbfeede36baef4a.jpg
[5] здесь: http://sepyra.com/articles/38
[6] Источник: http://habrahabr.ru/post/210824/
Нажмите здесь для печати.