1. 概要

このチュートリアルでは、ブルートフォースアルゴリズムとその特性について学習します。

最初に、組み合わせ論の観点から、より一般的な定式化で記事を定義します。 次に、文字列検索でそのアプリケーションを確認します。

このチュートリアルの最後に、ブルートフォース検索がどのように機能し、実際にそれを実装する方法を理解します。

2. 野蛮な力

ブルートフォースは、考えられるすべての解決策をテストすることによって問題を解決するためのアルゴリズムです。文字列検索の観点からは、考えられるすべての位置をチェックすることによって部分文字列を見つけるためのアルゴリズムです。 無許可の認証に対するブルートフォースの試みが頻繁に発生するため、ネットワークセキュリティの分野で一般的に研究されています。

その名前の理由は、アルゴリズムが、特定の優先順位なしで、すべての可能な解決策を順番に試行するという事実にあります。 この意味で、アルゴリズムは問題の知識を埋め込まないため、問題は鈍いまたは野蛮なものになります。

ここでは、最初に、シーケンスマッチングのより一般的な問題についてブルートフォースアルゴリズムを分析します。 次に、文字列の部分文字列マッチングの簡略化されたバージョンを導出できます。

2.1. 既知の長さのシーケンスに対するブルートフォース

ターゲットシーケンスに含めることができるシンボルがわかっている場合は、ブルートフォース検索が可能です。 そのシーケンスの長さもわかっている場合は、次の順序で続行します。

  1. まず、の繰り返しで構成されるシーケンスを試します
  2. 次に、シーケンスが失敗した場合、の最初の要素をに変更します
  3. これも失敗した場合は、の最初の要素を、のすべての可能な記号に順番に変更します
  4. これも失敗した場合は、の2番目の要素をに変更し、最初から繰り返します
  5. 最後に、の2番目の要素として、考えられるすべての記号を順番にテストします。それが失敗した場合は、解決策が見つかるまで、の他のすべての要素を続行します。

アルゴリズムのフローチャートは次のとおりです。

2.2. 計算時間

アルゴリズムでは、最悪のシナリオで考えられるすべての組み合わせをテストする必要があります。 このため、その計算時間は、のために、漸近的に大きくなります。

パラメータとが増加するにつれて、これは非常に急速に増加することに注意してください。 例として、シーケンスに長さ2と2つの可能なシンボルがある場合、アルゴリズムは可能な最大の組み合わせをテストします。

ただし、シーケンスに長さがあり、一部の基本的なパスワードのようにアルファベットの文字を記号として使用する場合は、次の組み合わせが可能です。

最後に、シンボルセットがASCIIの128文字であり、ターゲットシーケンスの長さが10の場合、可能な組み合わせの数はに近くなります。 1秒あたりの試行を実行した場合、考えられるすべての組み合わせをテストするのに約数年かかります。

また、実際の計算時間には大きなばらつきがあります。 ターゲットシーケンスが検索スペースの特定のセクションにあると信じる理由がないため、完了までの予想時間はです。 代わりに、最初に試行された値がターゲット値である場合の最良のケースはです。

2.3. 未知の長さのシーケンス

ターゲットシーケンスの長さがわからないが、それが有限であることがわかっている場合は、正しい長さが見つかるまで、考えられるすべての長さをテストする必要があります。 これは、最初に長さ1のシーケンスに対してアルゴリズムをテストすることを意味します。これは、時間内に実行できます。

2回目の反復には時間がかかりますが、これは。よりも大幅に長くなります。 したがって、漸近的に大きい場合、最初の2回の反復には時間がかかります。

この議論を繰り返すと、の場合、および漸近的に大きいの場合、固定長のシーケンスの場合と同様に、計算時間は残ります。

3. ブルート-文字列検索の強制

文字列でのブルートフォース検索のアルゴリズムは、前のアルゴリズムと同じ基本原理に基づいています。 ただし、この場合、長さの文字列に長さの部分文字列が含まれているかどうかを検索しています。 もしそうなら、文字列内での位置を知りたいです。

最初に使用例を示し、次にその形式化を示します。

3.1. 真実を求めて

この例では、JaneAustenの有名な引用で「真実」という単語を検索しています。

アルゴリズムの最初のステップでは、文字列の最初の文字を検索語と比較します。

比較が失敗したため、比較をターゲットシーケンスの2番目の要素と、検索語の最初の文字にシフトします。

比較が成功したため、検索語の2番目の要素を、ターゲットシーケンスの次の要素でテストすることができます。

今回はそれほど幸運ではありません。 ただし、前に進み、比較を繰り返し続けることはできます。 インデックス8の要素に到達するまでこれを行います。

ここでは、検索語のすべての要素と、そのインデックスから始まるターゲットシーケンスのすべての要素との順次比較が成功しています。 これは、検索語を、ターゲットシーケンスの間に含まれる文字のサブストリングとして識別したことを意味します。

3.2. アルゴリズムのフローチャート

これは、ブルートフォース文字列検索のフローチャートです。

3.3. 計算時間

アルゴリズムは、最良の場合、0との間に含まれる部分文字列としてターゲットシーケンスを識別することにより、比較を終了します。 最悪の場合、それはそれを間に見つけるか、まったく見つけません。

その時間計算量はであり、文字間の平均比較を実行します。

4. 結論

この記事では、組み合わせ問題と固定長文字列のブルートフォース検索の定義を検討しました。