algorithm - バイトの固定長配列のセットでプレフィックスを検索する効率的な方法を実装するにはどうすればよいですか?

Question

たとえば、次のような固定長のバイト配列の大規模なセットがあります。

type Fixed [64]byte

set := make([]Fixed, 10240)

このエントリのほとんどには、明確な 5 ～ 7 バイトのプレフィックスがあります。set指定されたプレフィックスに基づいて要素を見つける効率的な方法を実装するにはどうすればよいですか? 例えば：

set.Find([7]byte{ /*...*/ }) == /* no hit || single hit || multiple hit */

Answer 1

トライが必要なようです。

セットをトライとして保存し、接頭辞を指定すると、ずっと下に移動してノードに到達できます。次に、このノードをルートとするサブツリーをトラバースして、すべてのアイテムを取得します。