Ранее я написал скрипт для программы-оболочки «Windows PowerShell» версии 5.1 (или для «PowerShell» версии 7), работающей в операционной системе «Windows 10». Этот скрипт получает текст из текстового файла с кодом на языке HTML (в кодировке UTF-8 без метки BOM) и помещает его в переменную $html типа System.String. После этого с помощью библиотеки «HTML Agility Pack» содержимое переменной $html конвертируется в объект $dom, содержащий HTML-дерево:
Add-Type -Path "HtmlAgilityPack.1.11.43\lib\netstandard2.0\HtmlAgilityPack.dll"
$dom = New-Object -TypeName "HtmlAgilityPack.HtmlDocument"
$dom.LoadHtml($html)В этой статье я буду разбирать задачу вывода HTML-дерева из объекта $dom в консоль.
Код на языке HTML для тестирования скрипта:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Название страницы</title>
</head>
<body>
<!-- содержимое страницы -->
<p>Текст.</p>
</body>
</html>1. Простой способ
# Обход HTML-дерева
foreach ($node in $dom.DocumentNode.DescendantNodes()) {
# Обработка узла
# ...
}Пояснения к простому способу
Предположим, если код обработки узла будет следующим:
# Обработка узла (вывод в консоль)
$node.Nameто в консоли я получаю такой результат:
#comment
#text
html
#text
head
#text
meta
#text
title
#text
#text
#text
body
#text
#comment
#text
p
#text
#text
#textЛюбой, кто знаком с понятием объектной модели документа («DOM»), сразу поймет, что означают эти результаты. HTML-дерево состоит из узлов разных типов. Корневой узел (он в результат выше не выведен) обладает именем #document. Текстовые узлы обладают именем #text. Узлы-комментарии обладают именем #comment. И, наконец, самые важные узлы, HTML-элементы, обладают именами, совпадающими с названиями соответствующих HTML-тегов.
В результате, приведенном выше, более-менее всё понятно с HTML-элементами, но для текстовых узлов и узлов-комментариев хотелось бы видеть их содержимое, чтобы понять, что это за узлы. Кроме того, хотелось бы убрать из вывода «пустые» текстовые узлы. «Пустые» текстовые узлы содержат только пробельные символы (пробелы, символы новой строки, символы горизонтальной табуляции и тому подобные). Изменим код обработки узла с учетом этих требований:
# Обработка узла (вывод в консоль)
if (("#text" -eq $node.Name) -and ("" -eq $node.OuterHTML.Trim())) {
# Пустые узлы (пробелы, символы новой строки и т.п.) не выводим
} else {
$content = ""; if ("#" -eq $node.Name[0]) {
$content = ", '" + $node.OuterHTML.Trim() + "'" }
$node.Name + $content
}При такой обработке узла я получаю в консоли следующий результат:
#comment, '<!DOCTYPE html>'
html
head
meta
title
#text, 'Название страницы'
body
#comment, '<!-- содержимое страницы -->'
p
#text, 'Текст.'Это уже гораздо лучше. Однако, не хватает визуализации «глубины» для каждого узла. Чем больше у узла узлов-предков, тем «глубже» он находится в HTML-дереве. Традиционно «глубина» узла отображается в консоли шириной отступа от левой границы окна консоли. Чем «глубже» находится узел, тем дальше он отодвигается от левой границы окна консоли. Библиотека «HTML Agility Pack» дает нам возможность узнать об узлах-предках определенного узла с помощью метода Ancestors (документация). Чтобы добавить визуализации HTML-дерева «глубины», изменим код обработки узла (я только добавил две строки и изменил одну из существующих):
# Обработка узла (вывод в консоль)
if (("#text" -eq $node.Name) -and ("" -eq $node.OuterHTML.Trim())) {
# Пустые узлы (пробелы, символы новой строки и т.п.) не выводим
} else {
$content = ""; if ("#" -eq $node.Name[0]) {
$content = ", '" + $node.OuterHTML.Trim() + "'" }
$count = 0; foreach ($ancestor in $node.Ancestors()) { $count++ }
$count = ($count - 1) * 2 # отступ: 2 пробела на уровень, можно менять
(" " * $count) + $node.Name + $content
}При такой обработке узла я получаю в консоли следующий результат:
#comment, '<!DOCTYPE html>'
html
head
meta
title
#text, 'Название страницы'
body
#comment, '<!-- содержимое страницы -->'
p
#text, 'Текст.'Сравните этот результат с тестовым кодом на языке HTML из начала статьи.
Способы обхода дерева
Простой способ хорош своей простотой, но он не обладает гибкостью. Предположим, HTML-дерево потребуется обойти другим способом, не зафиксированным в методе DescendantNodes (документация), предоставляемом библиотекой «HTML Agility Pack». Чтобы это реализовать, нужно представлять, какой способ обхода дерева реализуется внутри метода DescendantNodes, какие способы обхода дерева вообще существуют и как они реализуются.
Метод DescendantNodes реализует обход дерева в глубину, который называют NLR.
Коротко напомню, что означает эта аббревиатура. Обход дерева называют «обходом дерева в глубину» потому, что при таком обходе сначала выполняется проход вглубь до «листа» дерева, а потом выполняется возврат до ближайшей развилки и обход следующей ветки дерева опять как можно дальше вглубь и так далее. Обходу дерева в глубину противопоставляется «обход дерева в ширину». Кроме того, эти два способа не исчерпывают список способов обхода дерева. При обходе дерева в глубину по алгоритму NLR на каждой развилке сначала выполняется обработка текущего узла (эта операция обозначается буквой N от слова «node»), а затем выполняется обход узлов потомков текущего узла слева направо (обозначается буквами L и R от слов «left» и «right»).
При реализации обхода дерева потребуется реализовать «память» для запоминания узлов при обходе. В качестве такой «памяти» обычно используют структуры вроде стека или очереди. Я буду использовать стек. Для работы со стеком буду использовать класс System.Collections.Stack (документация).
Вот описание нужного алгоритма из википедии на псевдокоде (обход бинарного дерева в глубину, итеративный алгоритм, NLR — прямой обход с приоритетом обхода потомков слева направо):
iterativePreorder(node)
if (node = null)
return
s ← empty stack
s.push(node)
while (not s.isEmpty())
node ← s.pop()
visit(node)
//правый потомок заносится первым, так что левый потомок обрабатывается первым
if (node.right ≠ null)
s.push(node.right)
if (node.left ≠ null)
s.push(node.left)Ниже я реализую этот алгоритм на языке PowerShell.
2. Более сложный способ (NLR)
Иногда в простых случаях используют рекурсивный алгоритм обхода дерева, но у него есть известные ограничения (проблема переполнения стека вызовов). Поэтому мне интереснее итеративный алгоритм обхода дерева. В псевдокоде выше показан обход бинарного дерева, то есть дерева, в котором у каждого узла не более двух потомков. Я же буду описывать реализацию обхода дерева, у которого может быть более двух потомков. Итак, вот код:
# Обход HTML-дерева
$stack = New-Object System.Collections.Stack
$stack.Push($dom.DocumentNode);
while ($stack.Count) {
$node = $stack.Pop();
# Обработка узла
# ...
# Если у узла есть потомки (то есть если он — не лист)
if ($node.ChildNodes) {
# Помещаем потомков в стек справа налево, чтобы начать обработку слева
for ($i = $node.ChildNodes.Count - 1; $i -ge 0; $i--) {
$stack.Push($node.ChildNodes[$i])
}
}
}Достаточно тонкий момент — с помещением потомков текущего узла в «память». Так как в качестве «памяти» используется стек (эта структура работает по принципу «LIFO», то есть «последним пришёл — первым вышел»), то потомков в стек приходится помещать в обратном порядке — справа налево, чтобы начать их обрабатывать слева направо. Поэтому коллекцию ChildNodes (документация) проходим от последнего элемента к начальному. Если это делать в «естественном» порядке, от начального к последнему, то получится обход дерева по другому алгоритму — NRL (прямой обход в глубину справа налево), то есть узлы будут обработаны в другом порядке и HTML-дерево в консоли будет отображено по-другому.
Код обработки узла возьмем тот же, что и для описанного выше простого способа обхода дерева. Только я еще добавил код, исключающий вывод в консоль корневого узла HTML-дерева (имя этого узла — #document):
# Обработка узла (вывод в консоль)
if (("#document" -eq $node.Name) -or
(("#" -eq $node.Name[0]) -and ("" -eq $node.OuterHTML.Trim()))) {
# Корневой узел не выводим,
# Пустые узлы (пробелы, символы новой строки и т.п.) не выводим
} else {
$content = ""; if ("#" -eq $node.Name[0]) {
$content = ", '" + $node.OuterHTML.Trim() + "'" }
$count = 0; foreach ($ancestor in $node.Ancestors()) { $count++ }
$count = ($count - 1) * 2 # отступ: 2 пробела на уровень, можно менять
(" " * $count) + $node.Name + $content
}Совместив вышеприведенные код обхода дерева и код обработки узла, я получил у себя на компьютере такой результат:
#comment, '<!DOCTYPE html>'
html
head
meta
title
#text, 'Название страницы'
body
#comment, '<!-- содержимое страницы -->'
p
#text, 'Текст.'Этот результат совпадает с результатом для простого способа обхода дерева из предыдущего раздела статьи. Тестовый файл с кодом на языке HTML — тот же.
3. Способ NRL (меняем порядок обхода потомков)
Я решил продемонстрировать еще два варианта обхода дерева из множества возможных. В случае с HTML-деревом мне пока что достаточно способа обхода NLR. Но в других скриптах (задача обхода дерева — это одна из часто встречающихся задач) могут пригодиться и другие способы обхода. Да и полезно знать, что и как в исходном алгоритме влияет на способ обхода дерева.
Как уже было сказано выше, для изменения алгоритма NLR на NRL достаточно поменять порядок обхода потомков (это измененный фрагмент из вышеприведенного кода):
# Помещаем потомков в стек слева направо, чтобы начать обработку справа
for ($i = 0; $i -le $node.ChildNodes.Count - 1; $i++) {
$stack.Push($node.ChildNodes[$i])
}Вот вывод в консоль HTML-дерева из того же тестового файла:
html
body
p
#text, 'Текст.'
#comment, '<!-- содержимое страницы -->'
head
title
#text, 'Название страницы'
meta
#comment, '<!DOCTYPE html>'Видно, что HTML-элементы, находящиеся на одном и том же уровне глубины, выведены теперь в обратном порядке. Например, директива <!DOCTYPE html> теперь оказалась ниже HTML-элемента html, а, к примеру, HTML-элемент head оказался ниже HTML-элемента body. И так далее.
4. Способ LRN (обратный обход, от листьев)
Тут реализация получилась немного сложнее. Я спрятал ее под спойлером, чтобы не увеличивать длину статьи:
Hidden text
# Функция обработки узла (вывода в консоль)
function visit($node) {
if (("#document" -eq $node.Name) -or
(("#" -eq $node.Name[0]) -and ("" -eq $node.OuterHTML.Trim()))) {
# Корневой узел не выводим,
# Пустые узлы (пробелы, символы новой строки и т.п.) не выводим
} else {
$content = ""; if ("#" -eq $node.Name[0]) {
$content = ", '" + $node.OuterHTML.Trim() + "'" }
$count = 0; foreach ($ancestor in $node.Ancestors()) { $count++ }
$count = ($count - 1) * 2 # 2 пробела на уровень
(" " * $count) + $node.Name + $content
}
}
# Обход HTML-дерева, вывод узлов в консоль
$stack = New-Object System.Collections.Stack
$node = $dom.DocumentNode
$lastNodeVisited = $null
while ($stack.Count -or $node) {
if ($node) {
# Итерация заглубления
$stack.Push($node) # сохраняем узел в стек
if ($node.ChildNodes) { # если есть потомки,
$node = $node.ChildNodes[0] # переходим к левому потомку
} else {
$node = $null # потомка нет
}
} else {
# Итерация обработки листа или возврата наверх
$peekNode = $stack.Peek() # смотрим, но не извлекаем
if ($peekNode.ChildNodes) {
$i = $peekNode.ChildNodes.IndexOf($lastNodeVisited)
if ($i -lt ($peekNode.ChildNodes.Count - 1)) {
# Возврат наверх и переход к следующему потомку справа
$node = $peekNode.ChildNodes[$i + 1]
} else {
# Все потомки обработаны, обработаем родителя
# Обработка узла (не лист)
visit($peekNode)
$lastNodeVisited = $stack.Pop()
}
} else {
# Обработка узла (лист)
visit($peekNode)
$lastNodeVisited = $stack.Pop()
}
}
}Вот результат работы алгоритма LRN (обратный обход, от листьев, с приоритетом обхода потомков слева направо):
#comment, '<!DOCTYPE html>'
meta
#text, 'Название страницы'
title
head
#comment, '<!-- содержимое страницы -->'
#text, 'Текст.'
p
body
htmlВидно, что в каждом заглублении сначала выводятся листья (узлы без потомков) данного HTML-дерева, а затем — узлы с потомками. Например, первое заглубление содержит единственный узел-лист <!DOCTYPE html>. Во втором заглублении сначала выводится узел-лист meta, затем — текстовый узел-лист Название страницы, при возврате из заглубления выводится узел-родитель (не лист) title и так далее.
Заключение
Я собираюсь использовать в своем скрипте первый алгоритм обхода дерева (с помощью метода DescendantNodes, алгоритм NLR) из приведенных в этой статье. Остальной код, реализующий разные алгоритмы обхода дерева, был написан, скорее, для того, чтобы поупражняться с алгоритмами и структурами данных.
