WEB-Браузер:алгоритм выявления больших нод
Материал из LUWRAIN Wiki
Словесное описание алгоритма
Терминология:
- вес - число, привязанное к ноде, определяющее сумму весов ее потомков, а для тех листьев (которые видимые и содержат значимую информацию - текст, изображение, ссылки, элементы с с ключевыми словами в названиях стилей и идентификаторов, например search/query и т.п.) у которых нет детей - количество символов для текста + площадь картинки + константа для ссылок + константа (или коэффициент к количеству символов в тексте) для некоторых свойств стилей типа bold
p.s. для конечных листьев возможно использование только площади как вес элемента, но требуются тесты.
- отношение веса элемента к весу документа - это процент соотношения весов корневого элемента (общий вес страницы) и текущего элемента
- элемент на удаление - элемент документа, выбранный алгоритмом для перемещения его в отдельный фрейм (NavigationArea), а в исходном документе остается его короткий ярлык.
Определим константы, определяющие различные границы:
- Коэффициенты определения веса
- Лимит отношения веса элемента к весу всего документа анализа [например 10%], задается в процентах, элементы с соотношением весов их потомков ниже этого значения не могут быть удалены (т.е. сам элемент с низким весом может быть удален, но его дети уже нет)
- справедливый общий вес [например 60%], справедливое соотношение [например 50%] и минимальное количество справедливых потомков [например 3].
- максимальное количество элементов на удаление [например 3]
Алгоритм определения ноды как кандидата на удаление:
- перечисляем потомков, сортируем список потомков по убыванию веса, для каждого проверяем соотношение его веса к предыдущему, пока оно не станет меньше коэффициента 'справедливое соотношение'. если сумма их весов соотносится к весу предка не меньше коэффициента 'справедливый общий вес' и количество этих потомков не меньше 'минимальное количество справедливых потомков' то такой предок -- кандидат на удаление
- элементы, вес которых в пределах лимита на удаление, а вес их детей уже нет, так же являются кандидатами на удаление
- потомки кандидатов на удаление повторно не рассматриваются (приоритет отдается алгоритму 'справедливого общего веса')
- после сбора кандидатов на удаление, сортируем их по убывания веса и берем несколько первых (максимальное количество элементов на удаление) - это и есть искомые элементы
Идеи к рассмотрению
- необходимо присмотреться к элементам, чья площадь явно больше чем суммарная площадь ее потомков (при условии их заметного веса)