Derivation of Efficient Pattern Matching Algorithms by Fully Lazy Evaluation with Lazy Memo-ization
スポンサーリンク
概要
- 論文の詳細を見る
In fully lazy evaluation, every subexpression is evaluated at most once after all variables in it have been bound. Hence we may regard that a fully lazy evaluator has ability to perform partial computation. According to this standpoint, we have shown that a fully lazy evaluator with lazy memo-ization derives a program which corresponds to the Knuth-Morris-Pratt algorithm from a fairly simple pattern matching program. In this paper, we inspect the derivation method of the KMP algorithm carefully to apply it to a metching problem which has multiple patterns and we have succeeded in obtaining a program which corresponds to the Aho-Corasick algorithm. The result is also applicable to more complex pattern matching problems.
- 1994-11-15
著者
-
Kaneako Keiichi
Department of Mathematical Engineering and Information Physics, Faculty Engineering, University of T
-
Takeichi Masato
Department of Mathematical Engineering and Information Physics, Faculty Engineering, University of T
-
Kaneako Keiichi
Department Of Mathematical Engineering And Information Physics Faculty Engineering University Of Tok
-
Takeichi Masato
Department Of Mathematical Engineering And Information Physics Faculty Engineering University Of Tok
-
Takeichi Masato
Department Of Computer Science The University Of Electro-communications
関連論文
- Derivation of Efficient Pattern Matching Algorithms by Fully Lazy Evaluation with Lazy Memo-ization
- 3M-5 Bidirectional XML Transformation with Bi-X
- 3M-4 依存関係記述スキーマによる双方向XMLアプリケーションの開発(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- 3M-3 双方向変換に基づくウェブパブリッシング支援システムVu-X(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- A Java Library for Bidirectional XML Transformation
- 神経系の双方向マルチスケールシミュレーションと100時間ワークショップ : 東京大学21世紀COEプログラム「情報科学技術戦略コア」
- 2. 情報科学技術戦略コア(21世紀卓越した情報研究拠点プログラムの目指す研究(前編))
- 情報科学技術戦略コア
- 1.マルチコア計算機と基本的な並列化技法(マルチコアを活かすお手軽並列プログラミング)
- 並列プログラムの候補生成と適合性検査による並列化
- 補関数の生成による複製機能付きプログラムの自動双方向化
- 6.双方向変換による高信頼構造化文書処理(第1部:高い生産性を持つ高信頼ソフトウェア作成技術の開発,学と産の連携による基盤ソフトウェアの先進的開発)
- Generator-of-generators に基づく Fortress ライブラリ
- リスト上の最大マーク付け問題を解く並列プログラムの導出
- 木スケルトンによるXPathクエリの並列化とその評価
- 東京大学 情報理工学系研究科 創造情報学専攻の紹介(ラボラトリー)
- 木上の双方向変換を利用したファイルマネージャの実現
- 木上の双方向変換を利用したファイルマネージャの実現
- データマイニングのアルゴリズム記述を容易にする拡張行列演算の提案
- 閻魔 Webインタフェースによるプログラミング教育支援システム
- 決定論的2階パターンとプログラム変換への応用
- 木変換言語の双方向化に関する事例研究(サイバー増大ページ論文概要,新しいソフトウェアの実現,サイバー増大号)
- Relationship between Lambda Hoisting and Fully Lazy Lambda Lifting
- Deriving a Functional Knuth-Morris-Pratt Algorithm by Transformation
- An Alternative Scheme for Evaluating Combinator Expressions
- Consistent Annotations for Scope Rules
- Name Identification for Languages with Explicit Scope Control