遍历复杂的多维数组（PHP 上的 Trie 数据结构，代码改进）

Question

最近我遇到了一个编码挑战，我必须在 php 中构建一个简单的 trie，我设法使用 php 和 foreach 循环来完成它，但我对代码本身（似乎并不可靠）所以我正在尝试使用 php 的迭代器来实现它。

所以，我有一个复杂的数组（一个 trie 树），例如：

array(
  'a' => array(),
  'b' => array(
      'a' => array(
           'c' => array(
                'o' => array(
                     'n' => array()
                 )
            )
       )
  ),
  'x' => array(
         'x' => array(
                'x' => array()
          )
   )
);

而且我想检查 'bacon' 它是否是存储在这个 trie 中的一个词，找到它的过程应该是通过遍历数组并检查它是否嵌套并存在的每个节点，例如：我需要在根中使用键 'b' 的元素，然后在数组 array['b'] 中，我需要检查是否有 array['b']['a'] ，然后 ['b']['a']['c'] 等等。

使用 foreach 循环，我可以通过引用传递新数组并检查键来实现。现在使用迭代器似乎我在敲打代码（事实上，当执行 foreachs php 复制数组时，让我认为这个解决方案可能比使用迭代器使用更多的内存）。

所以到目前为止的代码是一个 while 循环，它有一个条件完成，在失败时停止（当前数组没有我正在搜索的键）或成功（这个词是完整的）：

// OUTSIDE THE LOOP
$finished = false;
$string = 'bacon';
$string = str_split($string);
$queue = new SplQueue();
// Enqueue all the letters to the queue -> skipping this because it's boring

// FIRST WHILE LOOP
$iterator = new ArrayIterator($array);
$iterator->key(); // No match with queue -> check next key

// SECOND WHILELOOP
$iterator->next();
$iterator->key(); // Matches with the key I want do dequeue (B),  
$next =  new ArrayIterator($array[$iterator->key()]);
$queue->dequeue();

// THIRD WHILE LOOP
$next->key();  // Match [A] -> create new iterator
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue();

// 4TH WHILE LOOP
$next->key();  // Match [C] -> create new iterator
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue();

// 5TH WHILE LOOP
$next->key();  // Match [O] -> create new iterator
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue();

// 5TH WHILE LOOP 
$next->key();  // Match [N] 
$next = new ArrayIterator($next[$next->key()]);
$queue->dequeue(); // queue empty, throw success

所以，到目前为止我都是这样，但事实上我在每个循环上创建一个新的 ArrayIterator 这让我很困扰，所以我希望听到是否有人有更好的解决方案来解决这个问题。

提前致谢。

Answer 1

这是递归算法的代码，它将迭代任意数量的级别：

<?php
$trie = array(
    'a' => array(),
    'b' => array(
        'a' => array(
            'c' => array(
                'o' => array(
                    'n' => array()
                )
            )
        )
    ),
    'x' => array(
        'x' => array(
            'x' => array()
        )
    )
);

/**
 * @param string $word
 * @param array $array
 * @param int [$i = 0]
 */
function findWord($word, $array, $i = 0)
{
    $letter = substr($word, $i, 1);
    if (isset($array[$letter])) {
        if ($i == strlen($word) - 1) {
            return true;
        } else if ($i < strlen($word)) {
            return findWord($word, $array[$letter], $i + 1);
        }
    }
    return false;
}

if (findWord('bacon', $trie)) {
    die("Did find word.");
} else {
    die("Didn't find word.");
}

这是迭代算法的代码，它将迭代任意数量的级别并且应该是内存和cpu高效的：

<?php

$trie = array(
    'a' => array(),
    'b' => array(
        'a' => array(
            'c' => array(
                'o' => array(
                    'n' => array()
                )
            )
        )
    ),
    'x' => array(
        'x' => array(
            'x' => array()
        )
    )
);

/**
 * @param string $word
 * @param array $array
 */
function findWord($word, $array)
{
    $tmpArray = $array;
    for ($i = 0; $i < strlen($word); $i++)
    {
        $letter = substr($word, $i, 1);
        if (isset($tmpArray[$letter])) {
            if ($i == strlen($word) - 1) {
                return true;
            } else {
                $tmpArray = $tmpArray[$letter];
            }
        } else {
            break;
        }
    }
    return false;
}

if (findWord('bacon', $trie)) {
    die("Did find word.");
} else {
    die("Didn't find word.");
}

Answer 2

这是使用迭代器解决这个问题的一个很好的挑战。虽然我认为迭代器很棒，但它们迫使你从迭代方法的角度来思考。虽然对于某些问题来说还可以，但是对于像您描述的那样的任务 使用递归更有意义。

所以，我认为您应该接受 @cjohansson 的回答。因为它易于阅读和理解。

但作为概念证明，这里是我使用 RecursiveIteratorIterator 的解决方案。我们必须扩展这个 class 并稍微改变它以满足我们的需要，同时减少不必要的迭代次数：

class TrieRecursiveIteratorIterator extends RecursiveIteratorIterator
{
    protected $word;

    public function __construct(
        $word,
        Traversable $iterator,
        $mode = RecursiveIteratorIterator::LEAVES_ONLY,
        $flags = 0
    ) {
        $this->word = str_split($word);

        parent::__construct($iterator, $mode, $flags);
    }

    public function next()
    {
        if ($this->currentLetterMatched()) {
            $this->updatePrefix();
            $this->setPrefixed();   
        }  

        parent::next();
    }

    protected $prefix = [];
    protected function updatePrefix()
    {
        $this->prefix[$this->getDepth()] = $this->key();
    }

    protected $prefixed = [];
    protected function setPrefixed()
    {
        $this->prefixed = $this->current();
    }

    public function valid()
    {
        if (
            $this->getDepth() < count($this->prefix)
            || count($this->word) === count($this->prefix)
        ) {
            return false;
        }

        return parent::valid();
    }

    public function callHasChildren()
    {
        if ($this->currentLetterMatched()) {
            return parent::callHasChildren();
        }

        return false;
    }

    protected function currentLetterMatched()
    {
        return isset($this->word[$this->getDepth()])
            && $this->key() === $this->word[$this->getDepth()];
    }

    public function testForMatches()
    {
        foreach ($this as $_) {
        }

        return $this;
    }

    public function getPrefix()
    {
        return implode('', $this->prefix);
    }

    public function getPrefixed()
    {
        return $this->prefixed;
    }

    public function matchFound()
    {
        return ($this->word === $this->prefix);
    }

    public function exactMatchFound()
    {
        return ($this->word === $this->prefix) && empty($this->prefixed);
    }

    public function prefixMatchFound()
    {
        return ($this->word === $this->prefix) && !empty($this->prefixed);
    }
}

然后我们可以进行以下操作：

$iterator = new TrieRecursiveIteratorIterator(
    $word,
    new RecursiveArrayIterator($trie),
    RecursiveIteratorIterator::SELF_FIRST
);

$iterator->testForMatches();

之后，我们可以问我们$iterator不同的事情，比如：

如果找到匹配项：$iterator->matchFound()；
如果找到完全匹配：$iterator->exactMatchFound()；
如果有以给定词为前缀的词：$iterator->prefixMatchFound();
获取前缀本身（当找到任何一个匹配项时，前缀将等于给定的单词）：$iterator->getPrefix()；
获取以给定单词为前缀的结尾：$iterator->getPrefixed()。

这里是working demo.

正如您所见，这种实现并不像递归实现那样直接。虽然我是迭代器和 SPL 用法的忠实粉丝，但这不是灵丹妙药，您应该选择更适合您当前需求的工具。

另外，这是域外的，但是我的class违反了Single responsibility principle。为了简单起见，这是故意的。在现实生活中会有另一个 class 将使用我们的迭代器作为依赖项。

遍历复杂的多维数组（PHP 上的 Trie 数据结构，代码改进）

Iterate through complex multidimensional array (Trie data structure on PHP , code Improvement)

php

arrays

iterator

trie

data-structures