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

Question

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

Answer 1

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