はてなブックマーク

KMP法とBM法 ここからは、実際の様々なアルゴリズムを通して、計算量の観点から、それぞれのアルゴリズムの有用性について検討していくことにします。第一弾としてとりあげるのが、文字列検索のアルゴリズムです。 このアルゴリズムは、インターネットの普及と、googleなどの検索エンジンの普及により、現在用いられているもっとも重要なアルゴリズムの一つであるといえるでしょう。文字列検索のアルゴリズムには、KMP法と呼ばれるものと、BM法と呼ばれるものがあります。今回は、まずKMP法について説明します。 KMP法のアルゴリズムの詳細について説明する前に、そもそも文字列検索とはどういうものか、ということについて説明します。文字列検索とは、ある文章の中に、指定した文字列が存在するかどうかを検索することを指します。たとえば、ある本の中から、birdという文字列を検索するということは、その本の文字を頭から解析

BM法 BM法の考え方 応用編第2日目で述べたとおり、BM法や、KMP法よりも、理論的にも実践的にも優れた方法です。KMP法とBM法の大きな違いは、KMP法がパターンを先頭から比較していくのに対して、BM法は、後ろから比較していくという方法をとる点にあります。 BMとは、Boyer-Mooreの略で、やはりKMP法と同様にアルゴリズムの作者の頭文字をとったものです。このアルゴリズムでポイントになるのは、BM法は、不一致になった文字によって、パターンを何文字ずらしていくかを決定するという点にあります。 パターンの分類 このように、パターンの後ろ側から比較を始めていくBM法ですが、この際、その比較結果により、処理は以下の2つに分類されます。 一致しないテキストの文字が、パターンに含まれる文字でない場合 → テキストの注目点をパターンの文字数だけ右にずらす 一致しないテキストの文字が、パターンに

基本編 プログラミングなど、コンピュータの様々な技術について学習する前に、コンピュータの基本である「コンピュータ・リテラシー」について学習しうします。 基本編

入門編 このサイトは、すでにプログラミングの基本を身に付けたプログラマーが、アルゴリズムとデータ構造の学習サイトです。入門編では、最も基本的なアルゴリズムとデータ構造について説明します。プログラミングを始めたばかりか、これから学習する人は、こちらからスタートしてください。

基本編 プログラミングなど、コンピュータの様々な技術について学習する前に、コンピュータの基本である「コンピュータ・リテラシー」について学習しうします。 基本編

計算量とは このサイトでは、さまざまなアルゴリズムを紹介してきましたが、こういったアルゴリズムの性能は、どのように評価すればよいのでしょうか？そもそも、アルゴリズムは、かかった時間で評価することは困難です。なぜなら、同じアルゴリズムで記述されたプログラムでも、実行環境やハードの性能が違えば、まるで違った結果になってしまうからです。 そのため、アルゴリズムの性能を評価するために、計算量(けいさんりょう)という指標が用いられます。計算量には、時間計算量と空間計算量とがあります。 前者は処理時間がどれだけ掛かるのかを表し、後者はどれだけの記憶容量を必要とするかを表します。 多くの場合、単に計算量と言えば、前者の時間計算量のことを指します。 O(オーダー)記法 前述のように、計算量とは、単純に「3秒かかる」といったような表現をしません。 そもそも「3秒」というのは、ある特定のハードの上での結果に過

入門編 このサイトは、すでにプログラミングの基本を身に付けたプログラマーが、アルゴリズムとデータ構造の学習サイトです。入門編では、最も基本的なアルゴリズムとデータ構造について説明します。プログラミングを始めたばかりか、これから学習する人は、こちらからスタートしてください。