WEB-Браузер:алгоритм выявления больших нод

Материал из LUWRAIN Wiki
Перейти к: навигация, поиск

Словесное описание алгоритма

Терминология:

  1. вес - число, привязанное к ноде, определяющее сумму весов ее потомков, а для тех листьев (которые видимые и содержат значимую информацию - текст, изображение, ссылки, элементы с с ключевыми словами в названиях стилей и идентификаторов, например search/query и т.п.) у которых нет детей - количество символов для текста + площадь картинки + константа для ссылок + константа (или коэффициент к количеству символов в тексте) для некоторых свойств стилей типа bold
    p.s. для конечных листьев возможно использование только площади как вес элемента, но требуются тесты.
  2. отношение веса элемента к весу документа - это процент соотношения весов корневого элемента (общий вес страницы) и текущего элемента
  3. элемент на удаление - элемент документа, выбранный алгоритмом для перемещения его в отдельный фрейм (NavigationArea), а в исходном документе остается его короткий ярлык.

Определим константы, определяющие различные границы:

  1. Коэффициенты определения веса
  2. Лимит отношения веса элемента к весу всего документа анализа [например 10%], задается в процентах, элементы с соотношением весов их потомков ниже этого значения не могут быть удалены (т.е. сам элемент с низким весом может быть удален, но его дети уже нет)
  3. справедливый общий вес [например 60%], справедливое соотношение [например 50%] и минимальное количество справедливых потомков [например 3].
  4. максимальное количество элементов на удаление [например 3]

Алгоритм определения ноды как кандидата на удаление:

  1. перечисляем потомков, сортируем список потомков по убыванию веса, для каждого проверяем соотношение его веса к предыдущему, пока оно не станет меньше коэффициента 'справедливое соотношение'. если сумма их весов соотносится к весу предка не меньше коэффициента 'справедливый общий вес' и количество этих потомков не меньше 'минимальное количество справедливых потомков' то такой предок -- кандидат на удаление
  2. элементы, вес которых в пределах лимита на удаление, а вес их детей уже нет, так же являются кандидатами на удаление
  3. потомки кандидатов на удаление повторно не рассматриваются (приоритет отдается алгоритму 'справедливого общего веса')
  4. после сбора кандидатов на удаление, сортируем их по убывания веса и берем несколько первых (максимальное количество элементов на удаление) - это и есть искомые элементы

Идеи к рассмотрению

  1. необходимо присмотреться к элементам, чья площадь явно больше чем суммарная площадь ее потомков (при условии их заметного веса)