パターンマッチングマシンの効率的記憶検索法

• Item type: Journal(1)
• 公開日: 1983-07-15
• タイトル: パターンマッチングマシンの効率的記憶検索法
• タイトル / 言語: en
• タイトル: An Efficient Method for Storing and Retrieving Pattern Matching Machines
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 徳島大学工学部情報工学科
• 著者所属: 徳島大学工学部情報工学科
• 著者所属: 徳島大学工学部情報工学科
• 著者所属: 徳島大学工学部情報工学科
• 著者所属: 徳島大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, Tokushima University
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, Tokushima University
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, Tokushima University
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, Tokushima University
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Systems Engineering, Faculty of Engineering, Tokushima University
• 著者名: 青江, 順一; 東條, 隆; 山本, 米雄; 島田, 良作; 稲田, 裕
• 著者名(英): Junichi, Aoe; Takashi, Tojo; Yoneo, Yamamoto; Ryosaku, Shimada; Hiroshi, Inada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 状態遷移図のインプリメンテーションとして YACC(yet another compiler compiler)の語い解析部で使用されているJohnsonの記憶検索法が有効である.本論文では このJohnsonの方法をさらに改善する手法を提案する.本手法では まずパターンマッチングマシンに対する状態遷移図の特徴を見いだし これをJohnsonの記憶検索法の検索時間と記憶量の改善に利用する.次に 状態遷移図を構成するためのキーワードの長さの情報と状態番号を表現する二つの変数とを利用して 検索アルゴリズムを能率化する.これらの改善法は理論的かつ具体的に評価され Johnsonの方法に対して次の具体的結果が得られた.(1)検索時間は約20%高速化された.(2)マシン全体(検索プログラムと状態遷移表)の記憶量は約10%軽減された.改善された検索プログラムのサイズは Johnsonのものより大きくなるが (2)の結果はこの欠点が状態遷移表の縮小率により十分補償できることを意味している.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 24, 号 4, p. 414-420, 発行日 1983-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764