Получить максимальный уровень встраивания элемента в рекурсивно вложенный XML

Question

Для каждого элемента в произвольно рекурсивно вложенном XML мне нужно найти максимальный уровень встраивания.

Так, например, для этого XML

<chorus>
    <l>Alright now lose it <ah>aah <i>aah <ah>a<ah>a</ah>h</ah> aah</i> aah</ah></l>
    <l>Just lose it aah aah aah aah aah</l>
    <l>Go crazy aah aah aah aah aah</l>
    <l>Oh baby <ah>aah aah</ah>, oh baby baby <ah>aah aah</ah></l>
</chorus>

вывод должен выглядеть следующим образом: {"chorus": 0, "l": 0, "ah": 2, "i": 0}

К сожалению, решение ограничено использованием xml.etree.ElementTree.

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

Answer 1

Вы можете использовать модифицированную версию этого примера из документов :

Попробуйте изменить maxDepth и depth в словари, использующие имя элемента (тег) для ключа ...

Python

from xml.etree.ElementTree import XMLParser


class MaxDepth:  # The target object of the parser
    maxDepth = {}
    depth = {}

    def start(self, tag, attrib):  # Called for each opening tag.
        try:
            self.depth[tag] += 1
        except KeyError:
            self.depth[tag] = 0
            self.maxDepth[tag] = 0
        if self.depth[tag] > self.maxDepth[tag]:
            self.maxDepth[tag] = self.depth[tag]

    def end(self, tag):  # Called for each closing tag.
        self.depth[tag] -= 1

    def data(self, data):
        pass  # We do not need to do anything with data.

    def close(self):  # Called when all data has been parsed.
        return self.maxDepth


target = MaxDepth()
parser = XMLParser(target=target)
exampleXml = """
<chorus>
    <l>Alright now lose it <ah>aah <i>aah <ah>a<ah>a</ah>h</ah> aah</i> aah</ah></l>
    <l>Just lose it aah aah aah aah aah</l>
    <l>Go crazy aah aah aah aah aah</l>
    <l>Oh baby <ah>aah aah</ah>, oh baby baby <ah>aah aah</ah></l>
</chorus>"""
parser.feed(exampleXml)
print(parser.close())

Вывод

{'chorus': 0, 'l': 0, 'ah': 2, 'i': 0}

Отредактированный Python (где chorus уже является ElementTree.Element объектом)

import xml.etree.ElementTree as ET
from xml.etree.ElementTree import XMLParser


class MaxDepth:  # The target object of the parser
    maxDepth = {}
    depth = {}

    def start(self, tag, attrib):  # Called for each opening tag.
        try:
            self.depth[tag] += 1
        except KeyError:
            self.depth[tag] = 0
            self.maxDepth[tag] = 0
        if self.depth[tag] > self.maxDepth[tag]:
            self.maxDepth[tag] = self.depth[tag]

    def end(self, tag):  # Called for each closing tag.
        self.depth[tag] -= 1

    def data(self, data):
        pass  # We do not need to do anything with data.

    def close(self):  # Called when all data has been parsed.
        return self.maxDepth


exampleXml = """
<chorus>
    <l>Alright now lose it <ah>aah <i>aah <ah>a<ah>a</ah>h</ah> aah</i> aah</ah></l>
    <l>Just lose it aah aah aah aah aah</l>
    <l>Go crazy aah aah aah aah aah</l>
    <l>Oh baby <ah>aah aah</ah>, oh baby baby <ah>aah aah</ah></l>
</chorus>"""

chorus_element = ET.fromstring(exampleXml)

target = MaxDepth()
parser = XMLParser(target=target)
parser.feed(ET.tostring(chorus_element))
print(parser.close())

Answer 2

Я думаю, что это хороший вариант использования функции str.find (строка, начало, конец): https://www.tutorialspoint.com/python/string_find.htm

Так что, если я правильно понял для каждого элемента между <>, мы посмотрим максимумглубина встраивания этого элемента, так:

• Ищем элемент, сохраняем позицию, в которой мы его находим
• Затем ищем закрывающий соответствующий элемент, сохраняемposition
• снова ищет элемент, но начинается после позиции, в которой мы его нашли в первый раз
• , если позиция второго вхождения элемента найдена до первого вхождения закрытияэлемент, мы добавляем 1 к глубине, и мы начнем смотреть после позиции этого второго вхождения
• , если позиция второго вхождения элемента найдена после первого вхождения закрывающего элемента, они не внедряются, поэтому мы не обновляем глубину и будем следить за положением закрывающего элемента, чтобы найти следующие закрывающие элементы
• rповторяйте до тех пор, пока вы не найдете элемент в подстроке
• повторите для каждого отдельного элемента

Я думаю, что он полностью оптимизируемый, но после нескольких тестов он работает:

import re

string = ("<chorus>"
          "<l>Alright now lose it <ah>aah <i>aah <ah>a<ah>a</ah>h</ah> aah</i> aah</ah></l>"
          "<l>Just lose it aah aah aah aah aah</l>"
          "<l>Go crazy aah aah aah aah aah</l>"
          "<l>Oh baby <ah>aah aah</ah>, oh baby baby <ah>aah aah</ah></l>"
          "</chorus>")

# Start looking for the different nodes
regex = re.compile('\<[a-z]+\>')
# create a set of the nodes and closing nodes so we can iterate trough them
nodes = set(regex.findall(string))
closing_nodes = [node.replace('<', '</') for node in nodes]


depth = {node: '0' for node in nodes}

for node, closing_node in zip(nodes, closing_nodes):
    pos_node = string.find(node) + len(node)
    pos_closing_node = 0
    node_depth = 0
    max_node_depth = 0
    # we keep looking until we do not find our node (then str.find(node) returns -1)
    while pos_node >= 0:
        pos_closing_node = string.find(closing_node, pos_closing_node)
        pos_node = string.find(node, pos_node)
        # if we didnt find the node at all of if we found an occurence of a closing node before the node, we reduce depth by 1
        # and we will be looking for the next closing node next time, so we add the lengh of the closing node to the starting position of our search
        if pos_closing_node < pos_node or pos_node == -1:
            node_depth -= 1
            pos_closing_node = pos_closing_node + len(closing_node)
        else:
            node_depth += 1
            pos_node = pos_node + len(node)
        # we want the max depth so we take the max of the depth values
        max_node_depth = max(max_node_depth, node_depth)
    depth[node] = max_node_depth

print(depth)