問題タブ [prefix-tree]

マップには何万ものレコードがあります。マップ キーは , のような文字列s3://mybucket/some/path/2021/03/03/file.txtでs3://mybucket/some/path/2021/03/04/file.txt、値は0または1です。これまで HashMap を使用していましたが、メモリ使用量が多すぎるため、減らしたいと考えています。

キー値であり、キーパーツの再利用性を利用するものを探しています。自然に頭に浮かぶのは、プレフィックスを格納するために何らかのツリー構造を使用することです。

誰かが適切な実装、できれば軽量を指摘できますか?

ペアのベクトル (symbol : その符号語の長さ) を指定して、シンボルのバイナリ ハフマン ツリーを作成します。そのようなツリーが存在しない場合はエラーになります。

たとえば、入力 { a : 1, b : 2, c: 2} が与えられた場合、出力ツリーは次のようになります。