2020年01月24日

JavaScriptの情報共有

アルゴリズムwith JavaScript_4

皆さんこんにちは
今回も私が学んだアルゴリズムとJavaScriptの関係について述べたいと思います。

私が最も記憶に残るアルゴリズムが文字列検索アルゴリズムなので、今日は文字列検索アルゴリズムについてご紹介しようと思います。

文字列検索
文字の中からその中に含まれている文字列を探し出す処理のことです。
日常でもインターネットで検索したり、文書作成、計算など様々な場面で使っています。

ここで検索する対象となる文字列をテキスト
検索しようとする文字列をパターンといいます。

テキストの最前列から最後を検索する処理を前方検索といい、
逆に、テキストの最後から一番先まで検索する処理を後方処理といいます。

力まかせ探索アルゴリズム
テキストの一番前からパターンを比較します。
もし文字とパターンが一致しなければパターンを右に1間移します。 パターンがテキストから外れるまで、この処理を繰り返し検索するアルゴリズムを力まかせ探索アルゴリズムといいます。

しかし、この力まかせ探索アルゴリズムは、文字列が長ければ検索するのに相当時間がかかり、効率的でないアルゴリズムです。

KMPアルゴリズム
さっき紹介してあげた力まかせ探索アルゴリズムは文字を比較しながら、一致しなければ右に1間移すのだが、比較の途中、得た情報を捨てるという意味になります。

一方、KMPアルゴリズムはパターンを右に1間移すことがありません。
比較中に得られた情報を活用して、パターンの何文字目までテキストと一致しているかを確認した後、テキストを基準にパターンの位置を何マス移すかを決めます。

KMPアルゴリズムは、テキストとパターンを比較して、文字が一致しない場合、再び検索しないので、より速く検索できるのが長所です。

しかし、現実的にテーブル作成のための処理が複雑でテーブル利用するアルゴリズムが複雑になるほど、処理時間が長くかかり短い文字に限って効率的なのが短所です。

今回は数多いアルゴリズムの中で、私が学んだJavaScriptと関連したアルゴリズムを紹介しました。
世の中には数多くのアルゴリズムが存在するので、もし興味があれば探しながらアルゴリズムについて知っておくと良いでしょう。
長文を読んでくださってありがとうございます。