使用存储在大型 XML 文件 (PHP) 中的二叉树森林
Working with a forest of binary trees stored in a large XML file (PHP)
我有一个类似 '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 是读取每棵树的合适工具。因为树很小,所以可以在处理每个树时将它们存储在内存中。 使用树最直接的方法是什么?
您使用 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;
}
}
输出:
4