アルゴリズムとデータ構造

Last-modified: 2017-01-25 (水) 02:20:55

参考

ソート（並べ替え） Sorting algorithms

  • インサーションソート Insertion sort
  • イントロソート Intro sort
  • カクテルソート Cocktail sort
  • クイックソート Quick sort
  • グノームソート Gnome sort
  • コームソート Comb sort
  • シェルソート Shell sort
  • シェーカーソート Shaker sort
  • スムースソート Smooth sort
  • セレクトソート Selection sort
  • トポロジカルソート Topologic(al) sort
  • バイトニックソート Bitonic sort（GPUと親和性の高いソート法）
  • パケットソート Packet sort
  • バブルソート Bubble sort
  • ヒープソート Heap sort
  • ピジョンホールソート Pigeonhole sort
  • ビンソート Packet sort
  • ペイシャンスソート Patience sort
  • マージソート Merge sort
  • ライブラリソート Library sort
  • ラディックスソート Radix sort
  • 単純挿入ソート Insertion sort
  • 二分挿入ソート
  • 改良挿入ソート Shell sort
  • 選択ソート Selection sort
  • 分布数えソート Packet sort
  • 基数ソート Radix sort
  • フィッシャー・イエイツ Fisher-Yates (シャッフル=ランダムソート)

サーチ（検索） String algorithms

  • 逐次探索 linear search
  • 二分探索 binary search
  • 二分木探索 binary tree search
  • 平衡二分木 balanced binary tree
  • 赤黒二分木 red-black binary tree
  • ハッシュ探索 hash search
  • 線型探索
  • 幅優先探索
  • 深さ優先探索
Boyer-Moore法（BM法）
データ列の中から、一定のパターン列に一致する箇所を見つける効率の良い方法。見つけたいパターン列に一致しなかった場合に、不一致内容に合わせて、次の合致確認する位置をどれだけずらすかを調整することで、単純に１つずつずらすしていくよりも平均的に数倍の速さで検索が可能になる。ただし、パターン列の内容によっては、早くはならない。：区切り文字検索や、改行文字検索、H.264スタートコード位置の特定などに使用可能。
  • Knuth-Morris-Pratt法（KMP法）
Rabin–Karp algorithm, ラビン-カープ文字列検索アルゴリズム
  • 焼きなまし法
  • 山登り法
  • NegaScout（Principal Variation Search - PVS）
  • クラスカル法 Kruskal's algorithm

グラフ理論

Dijkstra's algorithm, ダイクストラ法

配列

Hash Table
Look Up Table
Queue
Stack

リスト構造

Circularly-linked list, 循環リスト
Doubly-linked list, 双方向リスト
Singly-linked list, 片方向リスト
Unrolled linked list

リングバッファ

  • 供給側、消費側が１かNか
  • 供給単位と消費単位が一致しているか

木構造

AA木
AVL木
B Tree, B木
B+ Tree , B+木
B* Tree, B*木
Balanced Tree, 平衡木
Binary Search Tree
Binary Tree, 二分木
Interval Tree
KD Tree
Rectangle Tree
Red-black Tree
Segment Tree
Spray Tree
Suffix Tree
T Tree
Wavelet Tree

補間法 interpolation

  • 最近傍補間 Nearest neighbor interpolation
  • 双線形補間 Bilinear interpolation
  • 三次畳み込み補間 Cubic Convolution interpolation
  • Bicubic interpolation
  • ラグランジュ補間 Lagrange interpolation
  • ニュートン補間 Newton interpolation
  • ネヴィル補間 Neville interpolation
  • 三角関数補間
  • スプライン補間 Spline interpolation
  • Lanczos interpolation
  • FCBI, Fast Curvature Based Interpolation

符号化

  • エントロピー符号化?
  • シャノン・ファノ符号化?
  • ハフマン符号化?
  • ワイル符号化?
  • Elias符号化?
  • 算術符号化?
  • ユニバーサル符号化?
  • LZ符号化?
  • LZB符号化?
  • LZBW符号化?
  • LZ77符号化?
  • LZ78符号化?
  • LZW符号化?

圧縮

  • ランレングス圧縮
  • ハフマン符号化圧縮?
  • Range Coder?
  • BPE (Byte Pair Encoding)
  • LPC (Linear Predictive Coding), 線形予測符号
  • SBR (Spectral band replication)
  • QMF (Quadrature mirror filters)
  • PS (Parametric stereo)
  • WLPC (Warped Linear Predictive Coding), ワープLPC

音声圧縮

AAC
Advanced Audio Coding
AC3
Audio Codec number 3
ADPCM
ALAC
Apple Lossless Audio Codec
ATRAC
Adaptive TRansform Acoustic Coding
DST
Direct Stream Transfer
FLAC
Free Lossless Audio Codec
LDAC
ソニー社が Bluetooth 用に開発したコーデック。
MLP
Meridian Lossless Packing
MP3
MPEG-1 Audio Layer 3
Opus
SBC
Low Complexity Subband Coding。主に、Bluetoothで使用される。
WMA
Windows Media Audio

画像圧縮

GIF
http://www.w3.org/Graphics/GIF/spec-gif89a.txtで規格化。
JPEG
ISO/IEC 10918-1:1994、JIS X 4301で規格化。
JPEG 2000
ISO/IEC 15444-1:2000で規格化。
JPEG PLENO
JPEG XR
ISO/IEC 29199-2:2009で規格化。
JPEG XS
JPEG XT
PNG
ISO/IEC 15948:2004で規格化。
WebP

映像圧縮

  • Daala
  • MotionJPEG
  • MPEG-1
  • MPEG-2
  • H.264 (AVC)
  • H.265 (HEVC)
  • Theora
  • VC-1
  • WebM

減色

  • 誤差拡散
    • ノーマル誤差拡散
    • Floyd & Steinberg
    • Jarvis,Judis and Nink
    • Stucki
    • Sierra 2 Line
    • Stevenson & Arche
    • Burks
  • パターン
  • ノイズ
  • 組織化
  • 組織的ディザ法
  • メディアンカット(中央値分割)
  • k-means法
  • 均等色空間
  • ポスタリゼーション
  • 単純二値化
  • グレースケール化
    • 単純平均法
    • 中間値法
    • 加重平均法
    • Gチャンネル法

構文解析

  • LALR法
  • LR構文解析法 LR parsing method
  • 再帰下降型構文解析法 Recursive Descent Parsing
  • 末尾再帰構文解析

AD変換

  • シャノン理論
  • フルーエンシ理論

数値計算

  • 二分法?
  • ニュートン法?
  • ガウス・ジョルダン法?
  • ガウスの消去法?
  • ガウス・ザイテル法?
  • オイラー法?
  • ルンゲ・クック法?
  • 台形則?
  • シンプソン則?
  • ガウスの公式?
  • ラグランジュ補間?
  • ニュートン補間?
  • スプライン補間?
  • テイラー展開?
  • 高速フーリエ展開(FFT)
  • ホーナーの方法
  • 素数判定法?
  • 素因数分解?
  • モンテカルロ法?
  • ユークリッドの互除法?
Exponentiation by squaring, バイナリ法
冪乗演算を効率的に行う方法。

統計解析

  • 標準偏差?
  • 相関?
  • χ二乗検定?
  • 重回帰分析?
  • 最小二乗法?
  • 主成分分析?

オペレーションズ・リサーチ

  • 線形計画法?
  • 二次計画法?
  • 待ち行列?
  • PERT?
  • 最短路問題?

画像処理

音声処理

タイムストレッチ、ピッチシフト

  • フェーズボコーダ?
  • Sinusoidal spectral modeling
  • SOLA
  • Untangling phase and time

並列処理／分散処理

  • MapReduce?

画質評価

  • SSIM
  • レート歪曲線 / RD曲線 / Rate-Distortion Curve

その他

貪欲法?
ある「最善なる選択」を繰り返して解を求める。途中で選択方法を変えない。「最善なる選択」が見つかるのであれば、非常に効率の良いアルゴリズムとなる。
  • 線形計画法?
  • Min-Max法?
  • α-β法?
  • モンテカルロ木探索?
  • 線形合同法?
  • エラトステネスのふるい?
  • 最急降下法?
  • k-平均クラスタライング?

画像、映像、音声など

文書

  • PDF
  • XML