Какой алгоритм помогает идентифицировать повторяющиеся последовательности в DOM?

Question

Есть ли хороший алгоритм, который я мог бы применить к DOM, чтобы привести меня к группам, вероятно, связанных узлов? Конечная цель состоит в том, чтобы получить что-то полезное, чтобы помочь извлекать такие вещи, как оглавление и «ролики блогов» с веб-сайтов. Если что-то подобное уже существует, я был бы рад, если бы кто-нибудь также дал мне знать об этом.

Я понимаю, что это не то, что я могу надеяться сделать детерминистически. Я подозреваю, что причина, по которой может быть какое-то решение, уже кроется в недавнем переходе к «алгоритму сравнения», который имеет дело с общими последовательностями. Я не уверен, что это прыжок или нет, чтобы перейти от «общего» к «повторению» ...

Answer 1

Вам просто нужно выбрать пример «безусловно интересного» узла и придумать хорошее отношение сходства;тогда все похожие узлы будут интересны.Сходство может основываться на таких факторах, как: высота пути к корню, значения атрибутов, имена тегов, позиции среди братьев и сестер, все вышеперечисленное для нескольких уровней родительских узлов и т. Д. Я использовал этот подход, и он работал на удивление хорошо.

Answer 2

«Связанный» - это очень общий термин, поскольку он всегда будет зависеть в значительной степени от того, что представляют собой фактические данные и каковы отношения, которые вы пытаетесь вывести. Я не совсем понимаю, почему вы говорите о «повторяющихся последовательностях» как о метрике «родства». Строго говоря, в DOM на самом деле нет никакой «последовательности» - это дерево, поэтому вы можете говорить только об упорядочении (и, следовательно, об упорядочении) в отношении родительских / дочерних отношений или родственных связей. Я не уверен, что вы имеете в виду что-либо из этого.

Тем не менее, есть некоторые вещи, которые вы можете сказать о DOM. Это деревья, так что, по-моему, вы хотите идентифицировать поддеревья с одинаковой формой?

Один из подходов, который вы могли бы использовать, - это взять два таких DOM и попытаться связать похожие узлы (например, с известными атрибутами или определенными узлами), добавив ребра (делая все это связным графом), а затем вычислить клика .

Кроме того, я не уверен, что есть гораздо более конкретные методы, которые я мог бы предложить без чуть более полного описания проблемы.