先読み
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/03/13 01:32 UTC 版)
 |
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（2012年9月） |
先読みまたはルックアヘッド（英: Lookahead）は、アルゴリズムにおいて未処理の入力の一部を先に参照し、現在の処理での判断に利用することで効率化する方法。
先読みと遅延評価
先読みは、実際に必要になるまで計算を遅延させる遅延評価という技法と対照的である。どちらの技法も時間やメモリ消費量を節約する目的で使われる。先読みは、予め判断を正しく行うことで、後で無駄なバックトラッキングが発生しないようにする。ただし、そのために先読みのオーバーヘッドが若干かかることになる。遅延評価は即座に必要とされないアルゴリズム上の計算を後回しにすることで、時間とメモリ使用量を節約しようとする。遅延評価の応用例として、オペレーティングシステムでのデマンドページングや、コンパイラでの構文解析表の遅延作成がある。
何らかの探索が必要な場合、両方の技法が使われる。アルゴリズム上次に見るべき経路がわかっている場合、遅延評価を使って探索すべき経路をキューやスタックに保持する。次に見るべき経路がわかっていない場合、新たな経路が見るべき経路かどうかを判断するために先読みを使う。
コンパイラも両方の技法を使う。構文解析表を規則から作成する場合は遅延評価が行われ、入力を構文解析する場合には先読みが行われる。
探索問題における先読み
人工知能では、先読みは組合せ最適化の重要な要素であり、問題を表すグラフをどれだけ深く探索すべきかを示すものと言える。コンピュータチェスやコンピュータ囲碁などでは問題を表すグラフの先読みを制限する必要がある。素朴な幅優先探索を行うと、最新のコンピュータでもすぐに全メモリを消費してしまう。そのために先読みに制限を加えることで、アルゴリズムにかかる時間を注意深く制御する。先読みの制限が緩められると、それに対して指数関数的に処理時間が延びる。
より洗練された探索技法としてアルファ・ベータ法などは、部分木全体を考慮から除外することができる。このような技法を使う場合、先読みは単に量的に制限されるのではなく、深さを制限したり、何らかの平均値を制限する形で制限される。
構文解析における先読み
先読みは、コンパイラでの構文解析でも重要な概念である。構文解析器が次に適用すべき生成規則を決定する際に入力トークン列を何個か先読みする。
LL法、LR法、LALR法などの構文解析では、後に括弧つきで先読みするトークン数を記することが多い（LALR(1)など）。
多くのプログラミング言語は、限定的な先読み（1個が典型的）で構文解析できるよう設計されている。というのも先読みを制限した方が構文解析器が効率化されるためである。1990年、Terence Parr は博士論文でANTLRを作成し、この傾向に重大な変化をもたらした。ANTLRは、効率的な LL(k) 構文解析器を生成するパーサジェネレータであり、k として任意の固定値が可能である。
構文解析器は、各トークンを参照したときにとりうるアクションが限られている。
- shift - トークンをスタックに積み、後で reduce する。
- reduce - スタックからトークンを取り出し、生成規則を適用して構文要素を構築する。
- end - 構文解析終了（終了トークンを受け取ったとき）
- error - 構文規則にないトークンの並びが入力された場合
- conflict - shift すべきか reduce すべきか判断できない。また、reduce で適用可能な規則が複数あって判断できない場合もある。
先読みには次の2つの利点がある。
- conflict 発生時、構文解析器が正しい判断をするのを助ける。例えば if 文 は先読みすることで then 節や else 節が完了したことが容易にわかる。
- 状態数を大幅に減らすことができる。C言語で先読みしない構文解析器は約10,000の状態があるが、先読みするとこれを約300に減らせる。
例として、"1 + 2 * 3" という式を構文解析する場合を示す。この場合の生成規則（構文規則）は次の通り。
- Rule1: E → E + E （式は式と式の加算である）
- Rule2: E → E * E （式は式と式の乗算である）
- Rule3: E → number （式は単なる数値である）
- Rule4: + は * より優先順位が低い。
APLなどの一部の例外を除いて、一般に加算よりも乗算が優先順位が高い。従って、上記の例は (1 + (2*3)) と解釈するのが正しい。上記のRule4は生成規則ではなく、意味論的規則である点に注意されたい。これを生成規則として表すことも可能である。しかし、意味論的規則が全て生成規則に変換できるわけではない。
単純な先読みのない構文解析器は次のように動作する。
- reduce - Rule3 に基づき '1' を式 E にする。その E はスタックに置かれる。
- shift - 入力 '+' から Rule1 が適用可能となることを予測しつつ、スタックに退避する。
- reduce - Rule3 に基づき '2' を式 E にする。
- reduce - スタック上の E+ と新たな入力 E に対して Rule1 を適用して E とする。
- shift - 入力 '*' から Rule2 が適用可能となることを予測しつつ、スタックに退避する。
- reduce - Rule3 に基づき '3' を式 E にする。
- reduce - スタック上の E* と新たな入力 E に対して Rule2 を適用して E とする。
これによって生成される構文木とコードは、Rule4 が考慮されていないため正しくない。
先読みなしで正しく構文解析するには、次のような対処法がある。
- ユーザーが括弧付きで式を書く。これが不可能なことも多い。
- 構文解析器にバックトラック機能を追加し、規則違反が発生したときなどに再試行する。同様の手法はLL法で使われている。
- reduce 実施を遅延させるような論理を導入し、どちらの規則を先に reduce させるのが適切かを規則に照らして判断する。LR法がこのような手法を採用している。これによって正しい構文解析が可能となるが、状態数が増え、スタックも深くなる。
先読みのある構文解析器では、次のように動作する。
- shift - 入力 '1' を Rule3 が適用されることを予想しつつスタックに退避する。即座には reduce しない。
- reduce - '+' を先読みして、スタック上の '1' を Rule3 に基づいて E に reduce する。規則上、'+' の前には E しかないため。
- shift - 入力 '+' を Rule1 が適用されることを予測しつつスタックに退避する。
- shift - 入力 '2' を Rule3 が適用されることを予測しつつスタックに退避する。
- reduce - '*' を先読みして、スタック上の '2' を Rule3 に基づいて E に reduce する。規則上、'*' の前には E しかないため。
- ここまでで、スタック上には E + E があり、現在の入力は '*' である。従って、Rule1 を適用する reduce を行うという選択肢と、Rule2 に基づいて shift を行うという選択肢がある。Rule4 によれば '*' の方が優先順位が高いので、Rule2 を予測して '*' を shift する。
- shift - 入力 '3' を Rule3 が適用されることを予測しつつスタックに退避する。
- reduce - 先読みすると入力が終了しているので、スタック上の '3' を Rule3 に基づいて E に reduce する。
- reduce - スタック上の E * E を Rule2 に基づき E に reduce
- reduce - スタック上の E + E を Rule1 に基づき E に reduce
これによって生成される構文木は正しく、先読みしない場合よりも効率的に得られる。以上の方式はLALR法に基づいている。
ウェブ高速化ソフトにおける先読み
ウェブ閲覧高速化ソフトにおいては、見ているページ内のハイパーリンクが示す先をあらかじめ読み込んでおくこと。
 |
この節の加筆が望まれています。 |
一般用法における先読み
- 先を読むこと。
- 発言を最後まで言う前に、後ろの文章を予想すること。早押しクイズで、問題文の読まれていない部分を推理する場合などにおいても使われることがある。
|
この節の加筆が望まれています。 |
先読み
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/01 09:06 UTC 版)
アルゴリズム遅延の要因の1つが先読み/前方参照（英: Look ahead）である。時刻 t {\displaystyle t} の入力信号 x t {\displaystyle x_{t}} を処理する際、時刻 t + N {\displaystyle t+N} の情報を利用することでより良い x t {\displaystyle x_{t}} の処理をできる場合がある。この先データアクセスが先読みである。先読みをおこなう場合、 x t {\displaystyle x_{t}} を処理するために x t + N {\displaystyle x_{t+N}} までの入力を待つ必要がある。つまりストリーム入力をとるアルゴリズムであれば、 N {\displaystyle N} サンプルの先読みは N {\displaystyle N} のアルゴリズム遅延をもたらすことになる。アルゴリズムを設計する際には、先読みで得られる出力の質向上と遅延増大のトレードオフを理解する必要がある。 時刻 t − N {\displaystyle t-N} すなわち過去の信号を後読み（英: Look behind）することは一般にアルゴリズム遅延へは影響しない。なぜならストリーム入力であっても過去の入力は既に手元にあるからである。 N {\displaystyle N} を大きくすることはむしろ処理量の増大による処理遅延と質の兼ね合いになる。
※この「先読み」の解説は、「アルゴリズム遅延」の解説の一部です。
「先読み」を含む「アルゴリズム遅延」の記事については、「アルゴリズム遅延」の概要を参照ください。
「先読み」の例文・使い方・用例・文例
品詞の分類
「先読み」に関係したコラム
-
株価と債券との関係は、逆相関関係にあるといわれています。例えば、株価が上昇すれば債券が下降し、株価が下降すれば債券が上昇します。上のチャートは、アメリカ合衆国の10年国債先物のチャートと、ダウ工業株3...
- 先読みのページへのリンク
