先読みとは? わかりやすく解説

さき‐よみ【先読み】

読み方:さきよみ

[名](スル)これから起こるであろうことを予測すること。「景気動向を—して生産調整する


先読み

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/03/13 01:32 UTC 版)

先読みまたはルックアヘッド: 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は生成規則ではなく、意味論的規則である点に注意されたい。これを生成規則として表すことも可能である。しかし、意味論的規則が全て生成規則に変換できるわけではない。

単純な先読みのない構文解析器は次のように動作する。

  1. reduce - Rule3 に基づき '1' を式 E にする。その E はスタックに置かれる。
  2. shift - 入力 '+' から Rule1 が適用可能となることを予測しつつ、スタックに退避する。
  3. reduce - Rule3 に基づき '2' を式 E にする。
  4. reduce - スタック上の E+ と新たな入力 E に対して Rule1 を適用して E とする。
  5. shift - 入力 '*' から Rule2 が適用可能となることを予測しつつ、スタックに退避する。
  6. reduce - Rule3 に基づき '3' を式 E にする。
  7. reduce - スタック上の E* と新たな入力 E に対して Rule2 を適用して E とする。

これによって生成される構文木とコードは、Rule4 が考慮されていないため正しくない。

先読みなしで正しく構文解析するには、次のような対処法がある。

  • ユーザーが括弧付きで式を書く。これが不可能なことも多い。
  • 構文解析器にバックトラック機能を追加し、規則違反が発生したときなどに再試行する。同様の手法はLL法で使われている。
  • reduce 実施を遅延させるような論理を導入し、どちらの規則を先に reduce させるのが適切かを規則に照らして判断する。LR法がこのような手法を採用している。これによって正しい構文解析が可能となるが、状態数が増え、スタックも深くなる。

先読みのある構文解析器では、次のように動作する。

  1. shift - 入力 '1' を Rule3 が適用されることを予想しつつスタックに退避する。即座には reduce しない。
  2. reduce - '+' を先読みして、スタック上の '1' を Rule3 に基づいて E に reduce する。規則上、'+' の前には E しかないため。
  3. shift - 入力 '+' を Rule1 が適用されることを予測しつつスタックに退避する。
  4. shift - 入力 '2' を Rule3 が適用されることを予測しつつスタックに退避する。
  5. reduce - '*' を先読みして、スタック上の '2' を Rule3 に基づいて E に reduce する。規則上、'*' の前には E しかないため。
  6. ここまでで、スタック上には E + E があり、現在の入力は '*' である。従って、Rule1 を適用する reduce を行うという選択肢と、Rule2 に基づいて shift を行うという選択肢がある。Rule4 によれば '*' の方が優先順位が高いので、Rule2 を予測して '*' を shift する。
  7. shift - 入力 '3' を Rule3 が適用されることを予測しつつスタックに退避する。
  8. reduce - 先読みすると入力が終了しているので、スタック上の '3' を Rule3 に基づいて E に reduce する。
  9. reduce - スタック上の E * E を Rule2 に基づき E に reduce
  10. 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} を大きくすることはむしろ処理量の増大による処理遅延と質の兼ね合いになる。

※この「先読み」の解説は、「アルゴリズム遅延」の解説の一部です。
「先読み」を含む「アルゴリズム遅延」の記事については、「アルゴリズム遅延」の概要を参照ください。

ウィキペディア小見出し辞書の「先読み」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ

「先読み」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。



品詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

「先読み」に関係したコラム

  • CFDの株価と債券、金利との関係は

    株価と債券との関係は、逆相関関係にあるといわれています。例えば、株価が上昇すれば債券が下降し、株価が下降すれば債券が上昇します。上のチャートは、アメリカ合衆国の10年国債先物のチャートと、ダウ工業株3...

辞書ショートカット

すべての辞書の索引

「先読み」の関連用語

先読みのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



先読みのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの先読み (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのアルゴリズム遅延 (改訂履歴)、ケンガンアシュラ (改訂履歴)、ミニマックス法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS