Работа с лесом двоичных деревьев, хранящихся в большом XML-файле (PHP)

Question

Работа с лесом двоичных деревьев, хранящихся в большом XML-файле (PHP)

У меня есть массив как 'var1'=>1.05, 'var2'=>0.76,... и лес двоичных деревьев, хранящихся в XML-файле размером более 100 МБ.

<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 является подходящим инструментом для чтения каждого дерева. Поскольку деревья довольно маленькие, они могут быть сохранены в памяти при работе с каждым.
Какой самый простой способ работы с деревьями?

0

parsing php xml xml-parsing xmlreader

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы на правильном пути с XMLReader. Скорее удобно, это включает в себя метод expand() который вернет копию текущего узла в виде DOMNode. Это позволит вам обрабатывать каждое отдельное дерево в памяти с помощью 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;
}
}

Выход:

3