data-structures - 为什么 trie 也被称为“前缀树”？

Question

我正在阅读Wikipedia 上的这篇文章，无意中发现“trie 也称为前缀树”。

我知道 trie 的用法，但为什么叫它“前缀树”？

Answer 1

因为它们可以通过前缀进行搜索。您还可以反转 trie 并找到通配符： http: //phpir.com/tries-and-wildcards。

例如，术语学术将是 cimedaca。使用与以前相同的技术，我们现在可以搜索以某个短语结尾的所有单词，从而允许我们在查询词的开头处理通配符，例如 *cademically。

<?php
function buildTries($words) {
        $trie = new Trie();
        $rtrie = new Trie();
        foreach($words as $word) {
                $trie->add($word);
                $rtrie->add(strrev($word));
        }
        return array('trie' => $trie, 'rtrie' => $rtrie);
}

function searchTries($search, $tries) {
        $terms = explode('*', $search);
        if(count($terms) > 2) {
                return false;
        }

        if(strlen($terms[0]) && strlen($terms[0])) {
                // middle wildcard
                $straight = $tries['trie']->prefixSearch($terms[0]);
                $rev = $tries['rtrie']->prefixSearch(strrev($terms[1]));
                return array_intersect($straight, reverseArray($rev));
        } else if(strlen($terms[1]) ) {
                // leading wildcard
                return reverseArray($tries['rtrie']->prefixSearch(strrev($terms[1])));
        } else {
                // trailing wildcard
                return $tries['trie']->prefixSearch($terms[0]);
        }
}

function reverseArray($keys) {
        $return = array();
        foreach($keys as $key => $value) {
                $return[strrev($key)] = $value;
        }
        return $return;
}

/* Do some searches */

$words = array( 
        'adder',
        'addled',
        'abject',
        'agreement',
        'astronaut',
        'handily', 
        'happily',
        'helpfully'
);
$tries = buildTries($words);

$return = searchTries('h*ly', $tries);
var_dump($return);

$return = searchTries('ha*ly', $tries);
var_dump($return);
?>

两个 var 转储的结果如下所示：

array(3) {
  ["handily"]=>
  NULL
  ["happily"]=>
  NULL
  ["helpfully"]=>
  NULL
}

array(2) {
  ["handily"]=>
  NULL
  ["happily"]=>
  NULL
}