WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"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を使って作成できる：

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]

トライに挿入する：

Wolfram Language code: ds["Insert", "abc"]

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

Wolfram Language code: ds["MemberQ", "abc"]

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

Wolfram Language code: ds["MemberQ", "abb"]

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

Wolfram Language code: ds["Strings"]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", 97, 99]

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

Wolfram Language code: ds["Insert", {97, 98, 99}]

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

Wolfram Language code: ds["MemberQ", {97, 98, 98}]

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

Wolfram Language code: ds["MemberQ", {97, 98, 98}]

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

Wolfram Language code: ds["ByteLists"]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]; ds["Insert", "abc"]; ds["Insert", "acb"]; ds["Insert", "bbc"];

すべての項目を返す：

Wolfram Language code: ds["Strings"]

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

Wolfram Language code: ds["Strings", "a"]

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

Wolfram Language code: ds["Strings", "ab"]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", 97, 99]; ds["Insert", {97, 98, 99}]; ds["Insert", {97, 99, 98}]; ds["Insert", {98, 98, 99}];

すべての項目を返す：

Wolfram Language code: ds["ByteLists"]

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

Wolfram Language code: ds["ByteLists", {97}]

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

Wolfram Language code: ds["ByteLists", {97, 98}]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]; ds["Insert", "ab"]; ds["Insert", "abb"]; ds["Insert", "acb"]; ds["Insert", "bbc"];

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

Wolfram Language code: ds["Visualization"]

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

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]; ds["Insert", "d"]

スコープ  (1)

情報  (1)

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "c"]

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

Wolfram Language code: Information[ds]

アプリケーション  (2)

コマンドの完了  (1)

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

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

Wolfram Language code: words = ToLowerCase[ StringReplace[ RandomWord[{"CommonWords", "Noun"}, 1000], "-" -> ""]];

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", "a", "z"]; Scan[(ds["Insert", #])&, words]

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

Wolfram Language code: ds["Strings", "br"]

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

整数の保存  (1)

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

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

Wolfram Language code: trie = CreateDataStructure["ByteTrie", 0, 7]; trie["Insert", IntegerDigits[ 1024, 8]]; trie["ByteLists"]

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

Wolfram Language code: insert[ trie_, num_] := trie["Insert", IntegerDigits[num, 8]]

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

Wolfram Language code: test[trie_, num_] := trie["MemberQ", Developer`FromPackedArray[IntegerDigits[num, 8]]]

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

Wolfram Language code: trie = CreateDataStructure["ByteTrie", 0, 7]; insert[ trie, 123456];

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

Wolfram Language code: test[trie, 123456]

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

おもしろい例題  (1)

可視化  (1)

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

Wolfram Language code: data = Table[ RandomChoice[{97, 98, 99}, RandomInteger[{1, 10}]], {20}]

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

Wolfram Language code: ds = CreateDataStructure["ByteTrie", 97, 99]; Scan[ds["Insert", #]&, data]

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

Wolfram Language code: ds["Visualization"]