簡潔データ構造(アルゴリズム・サイエンスシリーズ 8 数理技法編) [全集叢書]
    • 簡潔データ構造(アルゴリズム・サイエンスシリーズ 8 数理技法編) [全集叢書]

    • ¥3,672111ポイント(3%還元)
    • 在庫あり本日12:00までヨドバシエクストリームサービス便(無料)がお届け
店舗受け取りが可能です
NEWマルチメディアAkibaマルチメディア梅田マルチメディア博多にて24時間営業時間外でもお受け取りいただけるようになりました
100000009002918637

簡潔データ構造(アルゴリズム・サイエンスシリーズ 8 数理技法編) [全集叢書]

価格:¥3,672(税込)
ポイント:111ポイント(3%還元)(¥111相当)
お届け日:在庫あり今すぐのご注文で、本日12:00までヨドバシエクストリームサービス便(無料)がお届けします。届け先変更]詳しくはこちら
出版社:共立出版
販売開始日:2018/02/24
ご確認事項:返品不可

簡潔データ構造(アルゴリズム・サイエンスシリーズ 8 数理技法編) の 商品概要

  • 目次

    第1章 はじめに
    1.1 背景
    1.2 簡潔データ構造の歴史
    1.3 本書の構成

    第2章 基本事項
    2.1 計算モデル
    2.2 標準的な記号と関数
    2.3 情報理論的下限
    2.4 簡潔データ構造
    2.5 エントロピー
    2.6 整数の符号化
    2.7 整数列の符号化

    第3章 基本的な簡潔データ構造
    3.1 ビットベクトルの簡潔データ構造
    3.2 パタンに対するrank/select
    3.3 疎なベクトルの簡潔データ構造
    3.4 非常に疎なベクトルの簡潔データ構造
    3.5 下限
    3.6 実装上の工夫
    3.7 文献ノート

    第4章 ウェーブレット木
    4.1 文字列でのrank/select
    4.2 アルファベットサイズが大きいとき
    4.3 その他の演算
    4.4 ハフマン型ウェーブレット木
    4.5 多分岐ウェーブレット木
    4.6 直接アドレス可能符号
    4.7 直交領域探索
    4.8 文献ノート

    第5章 区間最小値問い合わせ
    5.1 問題の定義
    5.2 RMQをLCAに帰着
    5.3 LCAをRMQに帰着
    5.4 ±1 RMQ問題
    5.5 RMQ問題の定数時間アルゴリズム
    5.6 RMQ問題の4nビットデータ構造
    5.7 RMQ問題の2nビットデータ構造
    5.8 サイズの下限
    5.9 文献ノート

    第6章 順序木
    6.1 LOUDS表現
    6.2 括弧列(BP)表現
    6.3 DFUDS表現
    6.4 BP表現のより簡単なデータ構造
    6.5 動的な簡潔順序木
    6.6 文献ノート

    第7章 文字列検索のデータ構造
    7.1 接尾辞配列
    7.2 接尾辞木
    7.3 圧縮接尾辞配列
    7.4 圧縮接尾辞木
    7.5 文書集合に対するデータ構造
    7.6 文献ノート

    第8章 BW変換
    8.1 ブロックソート圧縮法
    8.2 逆BW変換とLF関数
    8.3 FM-index
    8.4 圧縮接尾辞配列とFM-indexの関係
    8.5 双方向BW変換
    8.6 ラベル付き木の圧縮
    8.7 de Bruijnグラフの圧縮
    8.8 文献ノート

    参考文献
  • 内容紹介

     簡潔データ構造とは,データをエントロピーの限界まで圧縮して保存しつつ,検索等の処理を行う際にはあたかも非圧縮のデータに対してアクセスしているように扱えるデータ構造である。データを圧縮することにより,これまでのデータ構造よりも多くのデータを扱えるようになる。扱うデータによっては 1/100 まで圧縮できる。2000年以降,多くの理論的・実用的データ構造が提案されており,ゲノム情報処理等では実際に使われている。
     本書は,基本的な簡潔データ構造(ビットベクトル,文字列,木構造等)の理論を説明する。初期の簡潔データ構造は非常に難解なものが多く,実装しても性能の出ないことが容易に想像できたが,後に提案されたものは理論的性能を保ったまま簡単化されており,容易に実装可能であり実際の性能も良い。本書ではそのようなデータ構造を中心に説明しているため,簡潔データ構造を実問題に適用する際の助けになると思われる。

簡潔データ構造(アルゴリズム・サイエンスシリーズ 8 数理技法編) の商品スペック

商品仕様
出版社名:共立出版
著者名:定兼 邦彦(著)
発行年月日:2018/02
ISBN-10:4320121740
ISBN-13:9784320121744
判型:A5
対象:専門
発行形態:全集叢書
内容:数学
言語:日本語
ページ数:215ページ
縦:22cm

    共立出版 簡潔データ構造(アルゴリズム・サイエンスシリーズ 8 数理技法編) [全集叢書] に関するレビューとQ&A

    商品に関するご意見やご感想、購入者への質問をお待ちしています!