「オンラインアルゴリズム」の版間の差分

削除された内容追加された内容

インライン

2023年10月12日 (木) 03:51時点における最新版

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

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

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

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

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

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

脚注

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

参考文献

Borodin, A.; El-Yaniv, R. (1998年). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5

外部リンク

Bibliography of papers on online algorithms

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

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

[1]

@@ 1行目: / 1行目: @@
-'''オンラインアルゴリズム'''（[[英語|英]]: '''Online algorithm'''）とは、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していける[[アルゴリズム]]を指す。これに対して、'''オフラインアルゴリズム'''（英: '''Offline algorithm'''）とは、問題を解くのに最初からデータ全体へのアクセスが必要なアルゴリズムを指す。例えば、[[選択ソート]]はオフラインアルゴリズムである。
+'''オンラインアルゴリズム'''（{{lang-en-short|Online algorithm}}）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していける[[アルゴリズム]]を指す。これに対して、'''オフラインアルゴリズム'''（{{lang-en-short|Offline algorithm}}）は、問題を解くのに最初からデータ全体へのアクセスが必要な[[バッチ処理]]型アルゴリズムを指す。例えば、[[挿入ソート]]はオンラインアルゴリズムで、[[選択ソート]]はオフラインアルゴリズムである。
-また、[[時系列]]データを[[リアルタイム]]に処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。
+また、[[時系列]]データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。
 例として、有限な連結[[グラフ理論|グラフ]]における[[最短経路問題]]を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。
+オンラインアルゴリズムは、データをあらかじめすべて用意したり、読みだしたりする必要がなく、少量のデータを逐次読み込んで処理を行うことが可能である。そのため、すべてのデータを保持しておくのが難しいような大規模データ（[[ビッグデータ]]）を扱う状況や、時々刻々とデータが与えられる状況においてよく用いられる<ref>{{Cite web|和書|title=オンラインアルゴリズムで平均値の逐次計算 |url=http://qiita.com/awakia/items/f58e90b3b2562d787aa5|accessdate=2014-10-05}}</ref>。また未来のデータに依拠せず、その時点までに得られたデータだけに依拠し、かつ逐次型で処理を行う特徴がある。
+==オンラインアルゴリズムの例==
+* [[粒子フィルタ]] (Particle filter)
+* [[データ圧縮]]アルゴリズムの多くはストリームアルゴリズムである。[[Lempel–Ziv–Storer–Szymanski|LZSS]]、[[LZ77]]
+==脚注==
+{{reflist}}
 ==関連項目==
 * [[ページ置換アルゴリズム|ページング問題]]
 * [[リアルタイムシステム]]
+* [[ビッグデータ]]
 ==参考文献==
-*{{cite book | authorlink = | author = Borodin, A. | coauthors = El-Yaniv, R. | url = http://www.cs.technion.ac.il/~rani/book.html | title = Online Computation and Competitive Analysis | publisher = Cambridge University Press | year = 1998年 | id = ISBN 0-521-56392-5}}
+*{{cite book | authorlink = | author = Borodin, A. | coauthors = El-Yaniv, R. | url = http://www.cs.technion.ac.il/~rani/book.html | title = Online Computation and Competitive Analysis | publisher = Cambridge University Press | date = 1998年 | id = ISBN 0-521-56392-5}}
 ==外部リンク==
@@ 18行目: / 28行目: @@
 [[Category:アルゴリズム]]
 {{Computer-stub}}
-[[de:Online-Algorithmus]]
-[[en:Online algorithm]]
-[[it:Algoritmo online]]
-[[ko:온라인 알고리즘]]
-[[nl:Online-algoritme]]
-[[pl:Algorytm online]]