online algorithm

OR事典

オンラインアルゴリズム

読み方：おんらいんあるごりずむ
【英】：on-line algorithm

実行中には途中までのデータしか入力されておらず, 各時点でそれ以降の入力が未知である状況下で動作するアルゴリズム. 実行前にすべてのデータを入力しておくオフラインアルゴリズムよりも効率が劣る場合がある. オンラインアルゴリズムは, オフラインアルゴリズムとしても用いることができるが, 逆は必ずしも成り立たない. したがって, 入力が次々に生成される環境下で実時間で何らかの計算を行なう場合にはオンラインアルゴリズムが用いられる.

「OR事典」の他の用語

組合せ最適化：

NP困難  TDI性  アルゴリズム  オンラインアルゴリズム  クラスMAX SNP  クラスNC  クラスR

ウィキペディア

オンラインアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/07/19 09:00 UTC 版)

オンラインアルゴリズム（英: Online algorithm）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していけるアルゴリズムを指す。これに対して、オフラインアルゴリズム（英: Offline algorithm）は、問題を解くのに最初からデータ全体へのアクセスが必要なバッチ処理型アルゴリズムを指す。例えば、挿入ソートはオンラインアルゴリズムで、選択ソートはオフラインアルゴリズムである。

また、時系列データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。

例として、有限な連結グラフにおける最短経路問題を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。

オンラインアルゴリズムは、データをあらかじめすべて用意したり、読みだしたりする必要がなく、少量のデータを逐次読み込んで処理を行うことが可能である。そのため、すべてのデータを保持しておくのが難しいような大規模データ（ビッグデータ）を扱う状況や、時々刻々とデータが与えられる状況においてよく用いられる^[1]。また未来のデータに依拠せず、その時点までに得られたデータだけに依拠し、かつ逐次型で処理を行う特徴がある。

オンラインアルゴリズムの例

• 粒子フィルタ (Particle filter)
• データ圧縮アルゴリズムの多くはストリームアルゴリズムである。LZSS、LZ77

脚注

1. ^ “オンラインアルゴリズムで平均値の逐次計算”. 2014年10月5日閲覧。

関連項目

• ページング問題
• リアルタイムシステム
• ビッグデータ

参考文献

• Borodin, A.; El-Yaniv, R. (1998年). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5. http://www.cs.technion.ac.il/~rani/book.html 

外部リンク

• Bibliography of papers on online algorithms

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。