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

问题描述

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

<节点 id="2"><SimplePredicate field="var1" operator="lessOrEqual" value="1.41"/><节点 id="4"><SimplePredicate field="var2" operator="lessOrEqual" value="1.43"/>......</节点></节点><节点 id="3"><SimplePredicate field="var1" operator="greaterThan" value="1.41"/>......</节点></树>

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

由于文件大小，很明显 XMLReader 是读取每棵树的合适工具.因为这些树非常小，所以它们可以在处理每个树时存储到内存中.处理树的最直接方法是什么?

解决方案

您在使用 XMLReader 时走在正确的轨道上.相当方便的是，它包括方法 expand()将返回当前节点的副本作为 DOMNode.这将使您可以使用 DOM API 处理内存中的每个单独的树.>

至于处理节点 - 递归计算和下降.

示例:

$data = ['var1' =>1.05,'var2' =>0.76];$dom = 新的 DOMDocument();$xpath = new DOMXPath($dom);$reader = new XMLReader();$reader->open('forest.xml');//读取直到到达第一棵树.while ($reader->read() && $reader->localName !=='Tree');while ($reader->localName === '树') {$tree = $dom->importNode($reader->expand(), true);echoevaluateTree($data, $tree, $xpath), "\n";//继续下一个.$reader->next('Tree');}$reader->close();函数评估树(数组 $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);如果 (evaluatePredicate($data[$field], $operator, $value)) {//递归下降.返回评估树($data，$node，$xpath)；}}//到达行尾.返回 $tree->getAttribute('id');}函数评估谓词($left，$operator，$right){开关($运算符){案例lessOrEqual":返回 $left <= $right;案例大于":返回 $left >$对;默认:返回假；}}

输出:

4

I have an array like 'var1'=>1.05, 'var2'=>0.76,... and a forest of binary trees stored in a 100+ MB XML file.

<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>

What I'd like to do in PHP is for each tree to store properties of a leaf in which I'll end up based on the conditions given by each node. So in this example the path will be (2)->(4)->...

Because of the file size it's clear XMLReader is the proper tool for reading each tree. Because the trees are quite small, they can be stored into memory while working with each.What would be the most straightforward way to work with the trees?

解决方案

You're on the right track with XMLReader. Rather conveniently it includes the method 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.

As for handling nodes - evaluate and descend recursively.

---

Example:

$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;
    }
}

---

Output:

4

这篇关于使用存储在大型 XML 文件 (PHP) 中的二叉树森林的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！