php - 如何获得不同XML节点的数量？

Question

在递归调用中使用引用时遇到问题。
我所要做的是根据一个元素中不同节点的最大数量来描述一个XML文档，而不预先知道任何节点元素的名称。
考虑本文件：

<Data>
    <Record>
        <SAMPLE>
            <TITLE>Superior Title</TITLE>
            <SUBTITLE>Sub Title</SUBTITLE>
            <AUTH>
                <FNAME>John</FNAME>
                <DISPLAY>No</DISPLAY>
            </AUTH>
            <AUTH>
                <FNAME>Jane</FNAME>
                <DISPLAY>No</DISPLAY>
            </AUTH>
            <ABSTRACT/>
        </SAMPLE>
    </Record>
    <Record>
        <SAMPLE>
            <TITLE>Interesting Title</TITLE>
            <AUTH>
                <FNAME>John</FNAME>
                <DISPLAY>No</DISPLAY>
            </AUTH>
            <ABSTRACT/>
        </SAMPLE>
        <SAMPLE>
            <TITLE>Another Title</TITLE>
            <AUTH>
                <FNAME>Jane</FNAME>
                <DISPLAY>No</DISPLAY>
            </AUTH>
            <ABSTRACT/>
        </SAMPLE>
    </Record>
</Data>

你可以看到， Record有1个或2个 SAMPLE节点，而 SAMPLE有1个或2个 AUTH节点。我正在尝试生成一个数组，该数组将根据每个节点中不同节点的最大数量来描述文档的结构。
所以我想得到这样的结果：

$result = [

  "Data" => [
    "max_count" => 1,
    "elements" => [

      "Record" => [
        "max_count" => 2,
        "elements" => [

          "SAMPLE" => [
            "max_count" => 2,
            "elements" => [

              "TITLE" => [
                "max_count" => 1
              ],
              "SUBTITLE" => [
                "max_count" => 1
              ],
              "AUTH" => [
                "max_count" => 2,
                "elements" => [

                  "FNAME" => [
                    "max_count" => 1
                  ],
                  "DISPLAY" => [
                    "max_count" => 1
                  ]

                ]
              ],
              "ABSTRACT" => [
                "max_count" => 1
              ]

            ]
          ]

        ]
      ]

    ]
  ]

];

为了保持头脑清醒，我使用 sabre/xml来解析xml。
我可以使用引用原始数组的递归调用来获得元素的绝对计数。

  private function countArrayElements(&$array, &$result){
    // get collection of subnodes
    foreach ($array as $node){

      $name = $this->stripNamespace($node['name']);

      // get count of distinct subnodes
      if (empty($result[$name])){
        $result[$name]["max_count"] = 1;
      } else {
        $result[$name]["max_count"]++;
      }

      if (is_array($node['value'])){
        $this->countArrayElements($node['value'], $result[$name]["elements"]);
      }

    }
  }

因此，我的推理是，我也可以通过引用传递数组，并进行比较，这对前两个节点起作用，但是在随后的节点上进行某种重置，从而导致 AUTH节点的计数仅为1。

  private function countArrayElements(&$array, &$previous){

    // get collection of subnodes
    foreach ($array as $node){

      $name = $this->stripNamespace($node['name']);

      // get count of distinct subnodes
      if (empty($result[$name]["max_count"])){
        $result[$name]["max_count"] = 1;
      } else {
        $result[$name]["max_count"]++;
      }

      // recurse
      if (is_array($node['value'])){
        $result[$name]["elements"] = $this->countArrayElements(
          $node['value'],
          $result[$name]["elements"]
        );
      }

      // compare previous max
      if (!empty($previous[$name]["max_count"])){
        $result[$name]["max_count"] = max(
          $previous[$name]["max_count"],
          $result[$name]["max_count"]
        );
      }

    }

    return $result;

  }

我意识到这是一个相当复杂的问题，它只是一个大得多的项目中的一小部分，所以我已经尽可能地为这个mcve分解它，并且我还准备了这些文件的 a special repository并完成了一个phpunit测试。

Answer 1

虽然您的解决方案工作正常，而且考虑到它在O(n*k)时间内运行（其中n是树中的节点数，k是顶点数），但我想我会提出一个替代解决方案，它不依赖数组或引用，而且更通用，而不仅仅是工作对于xml，但是对于任何dom树。这个解决方案也可以在O(n*k)时间内运行，所以它同样有效。唯一的区别是您可以使用generator中的值，而不必首先构建整个数组。
建立问题模型
对我来说，理解这个问题最简单的方法就是把它建模为一个图。如果我们用这种方法对文档建模，我们得到的是级别和顶点。

因此，有效地，这使我们能够分而治之，将问题分解为两个不同的步骤。
将给定垂直节点的基数子节点名计算为sum（垂直）
在水平面（水平面）上找到集合的max。
这意味着，如果我们在此树上执行级别顺序遍历，我们应该能够轻松地生成节点名称的基数作为所有垂直节点的最大和。

换句话说，获取每个节点的不同子节点名是一个基数问题。然后是找到整个水平的最大和的问题。
最小、完整、可验证、自包含的示例
因此，为了提供一个最小、完整、可验证和自包含的示例，我将依赖于扩展php的sum，而不是您在示例中使用的第三方xml库。
可能值得注意的是，这段代码与php 5不向后兼容（因为使用了DOMDocument），因此必须使用php 7才能使此实现正常工作。
首先，我将在yield from中实现一个函数，它允许我们使用generator按级别顺序遍历dom树。

class SpecialDOM extends DOMDocument {
    public function level(DOMNode $node = null, $level = 0, $ignore = ["#text"]) {
        if (!$node) {
            $node = $this;
        }
        $stack = [];
        if ($node->hasChildNodes()) {
            foreach($node->childNodes as $child) {
                if (!in_array($child->nodeName, $ignore, true)) {
                    $stack[] = $child;
                }
            }
        }
        if ($stack) {
            yield $level => $stack;
            foreach($stack as $node) {
                yield from $this->level($node, $level + 1, $ignore);
            }
        }
    }
}

函数本身的机制实际上相当简单。它不依赖于传递数组或使用引用，而是使用 DOMDocument对象本身来构建给定节点中所有子节点的堆栈。然后它可以一次 DOMDocument整个堆栈。这是水平部分。此时，我们依赖递归从堆栈中的每个元素中产生下一级的任何其他节点。
这里有一个非常简单的xml文档来演示这是多么直接。

$xml = <<<'XML'
<?xml version="1.0" encoding="UTF-8"?>

<Data>
    <Record>
        <SAMPLE>Some Sample</SAMPLE>
    </Record>
    <Note>
        <SAMPLE>Some Sample</SAMPLE>
    </Note>
    <Record>
        <SAMPLE>Sample 1</SAMPLE>
        <SAMPLE>Sample 2</SAMPLE>
    </Record>
</Data>
XML;

$dom = new SpecialDOM;
$dom->loadXML($xml);

foreach($dom->level() as $level => $stack) {
    echo "- Level $level\n";
    foreach($stack as $item => $node) {
        echo "$item => $node->nodeName\n";
    }
}

输出将如下所示。

- Level 00 => Data- Level 10 => Record1 => Note2 => Record- Level 20 => SAMPLE- Level 20 => SAMPLE- Level 20 => SAMPLE1 => SAMPLE

So at least now we have a way of knowing what level a node is on and in what order it appears on that level, which is useful for what we intend to do.

Now the idea of building a nested array is actually unnecessary to obtain the cardinality sought by max_count. Because we already have access to the nodes themselves from the DOM tree. Which means we know what elements are contained therein inside of our loop at each iteration. We don't have to generate the entire array at once to begin exploring it. We can do this at a level-order instead, which is actually really cool, because it means you can build a flat array to get to max_count for each record.

Let me demonstrate how that would work.

$max = [];
foreach($dom->level() as $level => $stack) {
    $sum = [];
    foreach($stack as $item => $node) {
        $name = $node->nodeName;
        // the sum
        if (!isset($sum[$name])) {
            $sum[$name] = 1;
        } else {
            $sum[$name]++;
        }
        // the maximum
        if (!isset($max[$level][$name])) {
            $max[$level][$name] = 1;
        } else {
            $max[$level][$name] = max($sum[$name], $max[$level][$name]);
        }
    }
}

var_dump($max);

我们得到的输出应该是这样的。
数组（3）{
〔0〕＝>
数组（1）{
[数据]＝>
INT（1）
}
〔1〕＝>
数组（2）{
[记录] =
INT（2）
[音符]＝>
INT（1）
}
〔2〕＝>
数组（1）{
[样本]＝>
INT（2）
}
}
这证明我们可以计算 yield而不需要引用或复杂的嵌套数组。当排除php数组的单向映射语义时，也更容易理解。
简介
下面是这个代码在示例xml文档中的输出结果。
数组（5）{
〔0〕＝>
数组（1）{
[数据]＝>
INT（1）
}
〔1〕＝>
数组（1）{
[记录] =
INT（2）
}
〔2〕＝>
数组（1）{
[样本]＝>
INT（2）
}
〔3〕＝>
数组（4）{
[题目] = >
INT（1）
[“字幕”]=>
INT（1）
[奥斯]＝>
INT（2）
[“抽象”]=>
int（1）
}
〔4〕＝>
数组（2）{
[ ffNe]）＝>
INT（1）
[“显示”]=>
INT（1）
}
}
这与每个子数组的 max_count相同。
0级
max_count
1级
Data => max_count 1
2级
< >
3级
Record => max_count 2
SAMPLE => max_count 2
TITLE => max_count 1
SUBTITLE => max_count 1
4级
AUTH => max_count 2
ABSTRACT => max_count 1
要在整个循环中获取这些节点的元素，只需查看 FNAME => max_count 1，因为您已经有了树（因此不需要引用）。
您需要将元素嵌套到数组中的唯一原因是，php数组的键必须是唯一的，而且由于您使用节点名作为键，因此需要嵌套以获得树的较低级别，并且仍然正确地构造 DISPLAY => max_count 1的值。所以这是一个数据结构问题，我通过避免在数据结构之后建模解决方案来解决它。