アルゴリズムとデータ構造
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法)
- データ列の中から、一定のパターン列に一致する箇所を見つける効率の良い方法。見つけたいパターン列に一致しなかった場合に、不一致内容に合わせて、次の合致確認する位置をどれだけずらすかを調整することで、単純に1つずつずらすしていくよりも平均的に数倍の速さで検索が可能になる。ただし、パターン列の内容によっては、早くはならない。:区切り文字検索や、改行文字検索、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
リングバッファ
- 供給側、消費側が1か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法
- 均等色空間
- ポスタリゼーション
- 単純二値化
- グレースケール化
構文解析
- LALR法
- LR構文解析法 LR parsing method
- 再帰下降型構文解析法 Recursive Descent Parsing
- 末尾再帰構文解析
AD変換
数値計算
- Exponentiation by squaring, バイナリ法
- 冪乗演算を効率的に行う方法。
統計解析
- 標準偏差?
- 相関?
- χ二乗検定?
- 重回帰分析?
- 最小二乗法?
- 主成分分析?
オペレーションズ・リサーチ
- 線形計画法?
- 二次計画法?
- 待ち行列?
- PERT?
- 最短路問題?
画像処理
音声処理
タイムストレッチ、ピッチシフト
- フェーズボコーダ?
- Sinusoidal spectral modeling
- SOLA
- Untangling phase and time
並列処理/分散処理
画質評価
- SSIM
- レート歪曲線 / RD曲線 / Rate-Distortion Curve
その他
- 貪欲法?
- ある「最善なる選択」を繰り返して解を求める。途中で選択方法を変えない。「最善なる選択」が見つかるのであれば、非常に効率の良いアルゴリズムとなる。
- 線形計画法?
- Min-Max法?
- α-β法?
- モンテカルロ木探索?
- 線形合同法?
- エラトステネスのふるい?
- 最急降下法?
- k-平均クラスタライング?
画像、映像、音声など
文書