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

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

Вы на правильном пути с 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; } } 

Вывод:

 4