翻訳と辞書 Words near each other ・ 簡易裁判所長 ・ 簡易貫入試験 ・ 簡易軌道 ・ 簡易軽便 ・ 簡易郵便局 ・ 簡易金型 ・ 簡易防湿 ・ 簡易食堂 ・ 簡札 ・ 簡潔 ・ 簡潔データ構造 ・ 簡潔性 ・ 簡潔性の尺度 ・ 簡潔明瞭 ・ 簡牛凡夫 ・ 簡狄 ・ 簡献蕭皇后 ・ 簡王 ・ 簡王 (周) ・ 簡王 (楚) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 簡潔データ構造 ： ミニ英和和英辞書 簡潔データ構造[かんけつでーたこうぞう] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 簡潔 ： [かんけつ] 　 1. (adj-na,n) brevity　2. conciseness　3. simplicity　 ・ ー ： [ちょうおん] 　(n) long vowel mark (usually only used in katakana) ・ 構造 ： [こうぞう] 　【名詞】 1. structure　2. construction　 簡潔データ構造 ： ウィキペディア日本語版 簡潔データ構造[かんけつでーたこうぞう] 簡潔データ構造 (かんけつデータこうぞう、) とは計算機科学の用語で、情報理論的下界に「近い」領域量だけを使いつつ、（他の圧縮形式とは異なり）効率的に質問を受け付けることができるデータ構造を指す。その概念は最初 Jacobson 〔 によって、木、平面的グラフを符号化するために導入された。通常のロスなしデータ圧縮アルゴリズムとは異なり、簡潔データ構造は事前の展開操作をせずに使用することができる。は関連する考え方に基づいているが、圧縮データ構造ではデータ構造のサイズは表現しようとする特定のデータに依存する。 あるデータを保持するために必要な情報理論的に最小のビット数が$Z$だとする。このデータの表現形式は、 * $Z\; +\; O(1)$ビットの領域を必要とする場合、'、 * $Z\; +\; o(Z)$ビットの領域を必要とする場合、''簡潔'' (''succinct'')、 * $O(Z)$ビットの領域を必要とする場合、''コンパクト'' (''compact'') であると呼ばれる。 implicit データ構造は通常、なんらかの順列を用いて情報を保持することに帰着される。よく知られる事例としてはヒープが挙げられる。、 * $Z\; +\; o(Z)$ビットの領域を必要とする場合、''簡潔'' (''succinct'')、 * $O(Z)$ビットの領域を必要とする場合、''コンパクト'' (''compact'') であると呼ばれる。 implicit データ構造は通常、なんらかの順列を用いて情報を保持することに帰着される。よく知られる事例としてはヒープが挙げられる。 ==簡潔辞書== 簡潔索引つき辞書(簡潔ビットベクトル、完備辞書とも呼ぶ)は、''rank/select'' 辞書とも呼ばれ、二分木、$k$分木、多重集合〔や、接尾辞木、接尾辞配列などの多数の簡潔表現手法の基礎をなしている〔。基本的な問題設定は、 $U\; =\; +\; R\_s$x / s\rfloor + R_p\lfloor x / s\rfloor, x \text s 実用上は、ルックアップ表 $R\_p$ をビット命令とより小さい表で置き換え、小ブロックで立っているビットの数を調べるようにすることができる。多くの場合、こうすることで大きなデータセットで簡潔データ構造を用いる際の、キャッシュミスの増大とそれによって起こるルックアップ表がキャッシュから追い出されるという問題に対処できる〔。select質問は、''rank''に用いたものと同じ補助データ構造と二分探索とを合わせることで容易にサポートできるが、そのやり方では最悪の場合 $O(\backslash lg\; n)$ の時間がかかる。$3n/\backslash lg\; \backslash lg\; n\; +\; O(\backslash sqrt\; \backslash lg\; n\; \backslash lg\; \backslash lg\; n)\; =\; o(n)$ ビットの追加領域を用いる、より複雑なデータ構造により、selectは定数時間でサポートできる〔。こうした解決法の多くでは、実用上、漸近的な特長が効果を発揮する至らない場合、$O(\backslash cdot)$記法に隠れた定数が支配的となる。その場合、長ワード命令とワードサイズに揃えたブロックを利用した実装のほうが効率的であることが多い〔。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「簡潔データ構造」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.