Memoirs of the Graduate School of Science and Engineering Shimane University. Series A

number of downloads : ?
Memoirs of the Graduate School of Science and Engineering Shimane University. Series A 34
2000-12-24 発行

文字列検索アルゴリズムの評価

Evalution of String Search Algorithms
Oodan, Masanori
Satou, Tadamasa
File
Description
String Searching is to find a substring specified in a given string. Some algorithms which aim to improve the speed are known,as frequent character coincidence tests in these strings are done. String Searching al gorithms are generally evaluated by comparing the processing speed. The processing speed is running time,computational complexity,steps on coincidence test and so on. So far,String Searching algorithms has evaluated through theoretical values by them. There could be some problems including input(strings)classes are not considered. This presented to propose a practical evaiuation method for String Searching algorithms and to estabiish the effective algorithms to input classes.

文字列探索は,与えられた文字列中に,探索文字列と呼ばれる文字列と一致する部分列の有無や,その位置を求めるものである.この処理では,両方の文字列を構成している文字の一致比較が頻繁に行われるため,速度の向上を狙った様々なアルゴリズムが知られている.これらのアルゴリズムの優劣評価では,処理速度を基準とするのが一般的である. 処理速度には,実行時間,計算量,文字の比較回数などがあるが,既存の評価では,それらを理論上で算出した値の比較に止まっている.これには,様々な種類の入力(文字列)に配慮されていないなどの問題点がある そこで,より実用的な文字列探索アルゴリズムの評価方法を提案し,入力種別ごとに有効なアルゴリズムを確定した