インクリメンタルな解析による空間解析器の高速化

• Item type: Trans(1)
• 公開日: 2003-10-15
• タイトル: インクリメンタルな解析による空間解析器の高速化
• タイトル / 言語: en
• タイトル: A Faster Incremental Parsing Algorithm for Spatial Parser
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学大学院工学研究科
• 著者所属: 筑波大学大学院工学研究科
• 著者所属: 筑波大学電子・情報工学系
• 著者所属: 筑波大学電子・情報工学系
• 著者所属(英): en
• 著者所属(英): Doctoral Program in Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Doctoral Program in Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Institute of Information Sciences and Electronics, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Institute of Information Sciences and Electronics, University of Tsukuba
• 著者名: 飯塚, 和久; 亀山, 裕亮; 志築, 文太郎; 田中, 二郎
• 著者名(英): Kazuhisa, Iizuka; Hiroaki, Kameyama; Buntarou, Shizuki; Jiro, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 図式はある規則の基に描かれており，これを文法として定義することができる．この文法を，プログラミング言語の文法に対して図形文法と呼び，矩形や線などの基本図形要素がトークンとして扱われる．また，プログラミング言語と同様に，図形文法に基づいて図式を解析する空間解析器を作ることができる．これをインタラクティブな図形処理システムに適用した場合，ユーザの入力に応じて，トークンが動的に追加・削除されることになる．空間解析器は，これに応じて解析をリアルタイムにやり直す必要が生じる．我々は，すでに提案されている，図形文法を与えることで空間解析器を利用できるシステムを改良し，この解析を高速に行うインクリメンタルな解析器を実現した．高速化のポイントは，解析時に探索するトークンの組合せ数を減少させることにある．我々は，組合せを求める際に，ルールの適用条件に関するグラフを利用した．これにより，ルールが適用できる組合せを効率的に求めることができる．また，前処理を行うことで効率的なグラフの探索を行うことができる．さらに，属性値に関するテーブルを用意することでさらなる高速化が可能であることを述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Diagrams are drawn based on certain rules. Such rules can be de fined as “visual grammars.”A spatial parser is used to analyse a diagram whether the diagram follows a given grammar or not. Previous algorithms that are used in the spatial parsers try to test all the combination of tokens consisting of the diagrams whether the rules can be applicable or not. Therefore, the algorithms are problematic to be used to process diagrams that are inputed and edited dynamically by users because interactivity becomes low. We propose a new spatial parsing algorithm that realizes a faster incremental parsing by improving the existing algorithms. The algorithm examines the rules in a given grammar to construct a dependency graph between conditions of the rules. The graph is used to eliminate combinatorial test of tokens. Moreover, our algorithm examines the graph to find efficient strategies for searching. These improvements decrease the order of analysis in the average case.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 44, 号 SIG13(PRO18), p. 100-109, 発行日 2003-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会