使用存储在大型 XML 文件 (PHP) 中的二叉树森林

Question

我有一个类似 'var1'=>1.05, 'var2'=>0.76,... 的数组和一个存储在 100+ MB XML 文件中的二叉树森林。

<Tree id="1">
<Node id="2">
   <SimplePredicate field="var1" operator="lessOrEqual" value="1.41"/>
   <Node id="4">
     <SimplePredicate field="var2" operator="lessOrEqual" value="1.43"/>
     .......
     </Node>
</Node>
<Node id="3">
   <SimplePredicate field="var1" operator="greaterThan" value="1.41"/>
   .......
</Node>
</Tree>

我想在 PHP 中做的是让每棵树都存储叶子的属性，我将根据每个节点给定的条件在叶子中结束。所以在这个例子中，路径将是 (2)->(4)->...

由于文件大小，很明显XMLReader 是读取每棵树的合适工具。因为树很小，所以可以在处理每个树时将它们存储在内存中。使用树最直接的方法是什么？

Answer 1

您使用 XMLReader 的方向正确。相当方便，它包含方法 expand() which will return a copy of the current node as a DOMNode. This will let you handle each individual Tree in memory with the DOM API.

至于处理节点 - 递归求值和下降。

示例：

$data = [
    'var1' => 1.05,
    'var2' => 0.76
];

$dom    = new DOMDocument();
$xpath  = new DOMXPath($dom);
$reader = new XMLReader();
$reader->open('forest.xml');

// Read until reaching the first Tree.
while ($reader->read() && $reader->localName !== 'Tree');

while ($reader->localName === 'Tree') {
    $tree = $dom->importNode($reader->expand(), true);

    echo evaluateTree($data, $tree, $xpath), "\n";

    // Move on to the next.
    $reader->next('Tree');
}

$reader->close();

function evaluateTree(array $data, DOMElement $tree, DOMXPath $xpath)
{
    foreach ($xpath->query('./Node', $tree) as $node) {
        $field    = $xpath->evaluate('string(./SimplePredicate/@field)', $node);
        $operator = $xpath->evaluate('string(./SimplePredicate/@operator)', $node);
        $value    = $xpath->evaluate('string(./SimplePredicate/@value)', $node);

        if (evaluatePredicate($data[$field], $operator, $value)) {
            // Descend recursively.
            return evaluateTree($data, $node, $xpath);
        }
    }

    // Reached the end of the line.
    return $tree->getAttribute('id');
}

function evaluatePredicate($left, $operator, $right)
{
    switch ($operator) {
        case "lessOrEqual":
            return $left <= $right;
        case "greaterThan":
            return $left > $right;
        default:
            return false;
    }
}

使用存储在大型 XML 文件 (PHP) 中的二叉树森林

Working with a forest of binary trees stored in a large XML file (PHP)

php

xml

parsing

xml-parsing

xmlreader

示例：

输出：