Сжатая реализация trie?

Question

я прохожу курс Udacity и в одной из лекций (https://www.youtube.com/watch?v=gPQ-g8xkIAQ&feature=player_embedded), профессор дает функцию high_common_bits которая (дословно из лекции) выглядит в псевдокоде:

function high_common_bits(a,b): 
    return: 
    - high order bits that a+b in common 
    - highest differing bit set 
    - all remaining bits clear 

В качестве примера:

a = 10101 
b = 10011 
high_common_bits(a,b) => 10100 

Затем он говорит, что эта функция используется в высоко оптимизированных реализациях попыток. Кто-нибудь знает, какую именно реализацию он имеет в виду?

Answer 1

Сжатый trie хранит префикс в одном узле, а затем ветвится от этого узла к каждому возможному элементу, который был замечен, который начинается с этого префикса.

В этом случае он, по-видимому, делает бит-мудрый trie, поэтому он хранит префикс бит - то есть, биты в начале, что элементы имеют общий ход, идут в одном узле, тогда есть две ветви из этого узел, один для узла для следующего бита, равный 0, а другой для следующего бита - 1. Предположительно, эти узлы также будут сжаты, поэтому они не будут просто хранить следующий единственный бит, а вместо этого хранить количество бит, которые все совпадали в элементах, вставленных в trie до сих пор.

Фактически следующий бит, следующий за данным узлом, может вообще не храниться в следующих узлах. Этот бит может быть неявным в последующей ссылке, поэтому следующие узлы сохраняют только бит после этого.

Answer 2

Если вы ищете высоко оптимизированное побитовое сжатое trie (aka Radix Tree). BSD routing table использует один в своей реализации. Код не легко читается.

Answer 3

Он говорил о кратких попытках, tries, в которых каждому узлу требуется только два бита для хранения (теоретический минимум).

Steve Hanov написал очень доступное сообщение в блоге о Succinct Tries here. Вы также можете прочитать оригинальную бумагу Гая Джейкобсона (написано еще в 1989 году), который представил их here.