PHP中可扩展的Trie实现

Question

在本教程之后,我遇到了Trie数据结构.从最近我一直用PHP编程,我试图用这个来解决讲座的问题.我能够获得正确的答案,但仅适用于较小的输入(输入#10是2,82 MB文件).显然,我的算法不能很好地扩展.它还超过了PHP的默认128 MB内存限制.

我的算法

Trie中存储了一个根节点.每个节点都有一个"子"成员.我使用标准的PHP数组来存储孩子.子键表示一个字符(当前我为每个字符创建一个新节点,az小写,映射到0-25),子值是对另一个节点的引用.

由于问题,每个节点都有"重量"成员.我想优化我的代码,(甚至使用不同的方法从stratch重写它),以便它可以通过大输入的测试.

我对如果可能的话,使用大输入使这个数据结构在PHP中工作的解决方案感兴趣.

我的代码

TrieNode类存储树层次结构.

class TrieNode {
    // weight is needed for the given problem
    public $weight;
    /* TrieNode children, 
    * e.g. [0 => (TrieNode object1), 2 => (TrieNode object2)]
    * where 0 stands for 'a', 1 for 'c'
    * and TrieNode objects are references to other TrieNodes.
    */
    private $children;

    function __construct($weight, $children) {
        $this->weight = $weight;
        $this->children = $children;
    }

    /** map lower case english letters to 0-25 */
    static function getAsciiValue($char) {
        return intval(ord($char)) - intval(ord('a'));
    }

    function addChild($char, $node) {
        if (!isset($this->children)) {
            $this->children = [];
        }
        $this->children[self::getAsciiValue($char)] = $node;
    }

    function isChild($char) {
        return isset($this->children[self::getAsciiValue($char)]);
    }

    function getChild($char) {
        return $this->children[self::getAsciiValue($char)];
    }

    function isLeaf() {
        return empty($this->children);
    }
}

Trie类存储根TrieNode.它可以插入和查询节点.

class Trie {
    /* root TrieNode stores the first characters */
    private $root;

    function __construct() {
        $this->root = new TrieNode(-1, []);
    }

    function insert($string, $weight) {
        $currentNode = $this->root;
        $l = strlen($string);
        for ($i = 0; $i < $l; $i++) {
            $char = $string[$i];
            if(!$currentNode->isChild($char)) {
                $n = new TrieNode($weight, null);
                $currentNode->addChild($char, $n);
            }
            $currentNode->weight = max($weight, $currentNode->weight);
            $currentNode = $currentNode->getChild($char);
        }
    }

    function getNode($string) {
        $currentNode = $this->root;
        $l = strlen($string);
        for ($i = 0; $i < $l; $i++) {
            $char = $string[$i];
            if ($currentNode->isLeaf() || !$currentNode->isChild($char)) {
                return null;
            }
            $currentNode = $currentNode->getChild($char);
        }
        return $currentNode;
    }

    function getWeight($string) {
        $node = $this->getNode($string);
        return is_null($node) ? -1 : $node->weight;
    }
}

测试代码.解析输入并调用Trie对象.

//MAIN / TEST

/*
In case the problem page is down:

e.g.
INPUT
2 1
hackerearth 10
hackerrank 9
hacker

OUTPUT
10

where 2 is the number of inserts, 1 is the number of queries
"string number" is the string to insert and its "weight"
"hacker" is the string to query
10 is maximum the weight of the queried string (hacker -> 10)
*/

$trie = new Trie();
$handle = fopen('test.txt', 'r');
//$handle = STDIN; // <- this is for the online judge
list($n, $q) = fscanf($handle, "%d %d");
for ($i = 0; $i < $n; $i++) { // insert data
    list($s, $weight) = fscanf($handle, "%s %d");
    $trie->insert($s, $weight);
}
for ($i = 0; $i < $q; $i++) { // query data
    $query = trim(strval(fgets($handle)));
    echo $trie->getWeight($query) . PHP_EOL;
}
fclose($handle);

失败

Answer 1

下面是经过以下优化的代码 -

删除了所有不必要的条件检查，例如

1. 不需要检查节点是否是叶子，因为如果节点没有指定字符的子节点，那么它是否是叶子并不重要。
2. 无需在每次添加子节点时检查 {children} 是否已初始化。删除了此检查，将构造函数本身中的 {children} 初始化为空数组。

删除了 {getAsciiValue} 的函数，而是使用简单的关联数组作为。另外，将 {char} 更改为 ascii 值已从 TrieNode 移至 Trie 类，以便我们不需要多次转换它

经过这些优化后，我提出了以下最小解决方案，但这也无法通过测试 #10。在阅读了 PHP 中的数组之后，我了解到 PHP 并不像其他编译语言那样实现数组，相反，PHP 中的任何数组都只是一个有序的哈希映射，并且因为该数组不支持恒定时间操作。/sf/answers/343285001/

还使用SplFixedArray但没有帮助，因为它是一个对象并且具有实例化成本。如果尝试使用大数组来存储整个 Trie 可能会有所帮助。您可以尝试实现使用 SplFixedArray 存储整个 Trie 的解决方案，并检查是否可以使其通过测试 #10。

<?php

/*
 * Read input from stdin and provide input before running code

fscanf(STDIN, "%s\n", $name);
echo "Hi, ".$name;

*/

class TrieNode {
    // weight is needed for the given problem
    public $weight;
    /* TrieNode children, 
    * e.g. [0 => (TrieNode object1), 2 => (TrieNode object2)]
    * where 0 stands for 'a', 2 for 'c'
    * and TrieNode objects are references to other TrieNodes.
    */
    private $children;

    function __construct($weight) {
        $this->weight = $weight;
        $this->children = [];
    }

    function addChild($char, $node) {
        $this->children[$char] = $node;
    }

    function isChild($char) {
        return isset($this->children[$char]);
    }

    function getChild($char) {
        return $this->children[$char];
    }
}

class Trie {
    /* root TrieNode stores the first characters */
    private $root;

    function __construct() {
        $this->root = new TrieNode(-1);
    }

    static $asciiValues = array(
        "a" => 0,
        "b" => 1,
        "c" => 2,
        "d" => 3,
        "e" => 4,
        "f" => 5,
        "g" => 6,
        "h" => 7,
        "i" => 8,
        "j" => 9,
        "k" => 10,
        "l" => 11,
        "m" => 12,
        "n" => 13,
        "o" => 14,
        "p" => 15,
        "q" => 16,
        "r" => 17,
        "s" => 18,
        "t" => 19,
        "u" => 20,
        "v" => 21,
        "w" => 22,
        "x" => 23,
        "y" => 24,
        "z" => 25
    );

    function insert($string, $weight) {
        $currentNode = $this->root;
        $l = strlen($string);
        for ($i = 0; $i < $l; $i++) {
            $char = self::$asciiValues[$string[$i]];
            $currentNode->weight = max($weight, $currentNode->weight);
            if($currentNode->isChild($char)) {
                $childNode = $currentNode->getChild($char);
            } else {
                $childNode = new TrieNode($weight);
                $currentNode->addChild($char, $childNode);
            }
            $currentNode = $childNode;
        }
    }

    function getNodeWeight($string) {
        $currentNode = $this->root;
        $l = strlen($string);
        for ($i = 0; $i < $l; $i++) {
            $char = self::$asciiValues[$string[$i]];
            if (!$currentNode->isChild($char)) {
                return -1;
            }
            $currentNode = $currentNode->getChild($char);
        }
        return $currentNode->weight;
    }
}

$trie = new Trie();
//$handle = fopen('test.txt', 'r');
$handle = STDIN; // <- this is for the online judge
list($n, $q) = fscanf($handle, "%d %d");
for ($i = 0; $i < $n; $i++) { // insert data
    list($s, $weight) = fscanf($handle, "%s %d");
    $trie->insert($s, $weight);
}
for ($i = 0; $i < $q; $i++) { // query data
    //$query = trim(strval(fgets($handle)));
    $query = trim(strval(fgets($handle)));
    echo $trie->getNodeWeight($query) . PHP_EOL;
}
fclose($handle);


?>