"ByteTrie" (データ構造)

"ByteTrie"

メンバがバイト列であるトライを表す．

詳細

  • バイトトライは，効率的な挿入だけでなく，メンバシップの検証にも役立つ．
  • CreateDataStructure["ByteTrie", start, end]start から end までの範囲のバイト列用に新しい空の"ByteTrie"を作成する
    Typed[x,"ByteTrie"]x に"ByteTrie"型を与える
  • "ByteTrie"型のデータ構造については，以下の演算が使える．
  • ds["ByteLists"]バイトのリストのリストとして表される，ds に保存されたバイト列を返すtime: O(n)
    ds["ByteLists",s]列 s で始まる，ds に保存されたバイト列を返すtime: O(n)
    ds["ByteRange"]ds が持つことのできるバイトの範囲time: O(1)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["EmptyQ"]ds が要素を持たない場合にTrueを返すtime: O(1)
    ds["FreeQ",s]バイト列 s が ds に保存されていない場合にTrueを返すtime: O(log n)
    ds["Insert",s]バイト列 s を ds に挿入するtime: O(log n)
    ds["Length"]ds に保存されたバイト列の数time: O(1)
    ds["MemberQ",s]バイト列 s が ds に保存されている場合にTrueを返すtime: O(log n)
    ds["NumericArrays"]数列のリストとして表される，ds のバイト列を返すtime: O(n)
    ds["NumericArrays",s]列 s で始まる，ds に保存されたバイト列を返すtime: O(n)
    ds["Strings"]文字列のリストとして表される，ds に保存されたバイト列を返すtime: O(n)
    ds["Strings",s]列 s で始まる，ds に保存されたバイト列を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する
  • "ByteTrie"データ構造に保存されたバイト列は，バイト，文字列，数値配列のリストとして表すことができる．
  • トライは，その要素を保存するのに接頭辞を使うので，ハッシュ計算を使うデータ構造のようなコリジョンの問題が起ることがない．

例題

すべて開くすべて閉じる

例  (6)

新しい"ByteTrie"は，CreateDataStructureを使って作成できる：

トライに挿入する：

バイト列が保存されているかどうかを検証する：

列が保存されていない場合には，Falseが返される：

文字列として表されるバイト列を返すことができる：

バイトの範囲について数値を与えることができる：

バイトのリストを挿入することができる：

バイト列が保存されているかどうかを検証する：

列が保存されていない場合には，Falseが返される：

文字列として表されるバイト列を返すことができる：

複数の項目を含むバイトトライ：

すべての項目を返す：

特定の接頭辞を持つ項目すべてを返す：

項目を選ぶ接頭辞には，複数のバイトを含むことができる：

複数の項目を含むバイトトライ：

すべての項目を返す：

特定の接頭辞を持つ項目すべてを返す：

項目を選ぶ接頭辞には，複数のバイトを含むことができる：

いくつか挿入したバイトトライ：

データ構造の可視化を生成することができる：

赤で色付けされた要素は，実際の項目の最後を示す．

範囲外のバイトを挿入すると，エラーが発生する：

スコープ  (1)

情報  (1)

新しい"ByteTrie"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

アプリケーション  (2)

コマンドの完了  (1)

バイトトライはコマンドの完了に使うことができる．これにはRandomWord関数を使うとよい．

1000個の単語のリストを作成する．ハイフンを削除し，すべてを小文字にする：

バイトトライを作成し，単語を挿入する：

これで特定の接頭辞で始まる単語をすべて効率的に求めることができるようになった：

これらはすべてコマンド完了システムに使うことが可能である．

整数の保存  (1)

整数は，バイト列に分割することによって，バイトライトに保存することができる．

これを行う一つの方法はいくつかの演算が必要であるが，IntegerDigitsを効率的に使うこともできる：

数をバイトトライに挿入するユーティリティ関数：

メンバシップについて検証を行う関数：

バイトトライを作成し，挿入を行う：

メンバシップについて検証を行う：

これらはすべてコマンド完了システムに使うことができる．

おもしろい例題  (1)

可視化  (1)

ランダムな長さのランダムなバイト列の集合：

バイトトライを作成し，バイト列を挿入する：

可視化は，データがどのように配置されているかを示す：