Web教材一覧アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)

素数、文字列探索の基礎

学習のポイント

これまでに、ソートやサーチを例にしてアルゴリズムについて学習してきましたが、ここではポピュラーなアルゴリズムのいくつかを紹介します。
  ユークリッドの互除法:最大公約数を求める方法(→発展:「ユークリッドの互除法」)
  エラトステネスのふるい:素数表を作成する方法(→発展:「素数アルゴリズム」)
  文字列探索:(→発展:「文字列探索」)

キーワード

アルゴリズム、最大公約数、ユークリッドの互除法、素数、エラトステネスのふるい、文字列の探索


素数に関するアルゴリズム

これまでは、素数研究が社会に直接関係することはあまりありませんでした。ところが、電子メールなどの暗号化が必要になりました。その暗号鍵、復号鍵では、「非常に大きいを素因数分解する計算には非常に時間がかかる」ことをベースにしています(→参考:「公開鍵暗号方式の原理」)。そのため、素数に関する関心が高まっているのです。

2,3,5,7,11,13,17,…など、1と自分自身でしか割り切れない数を素数といいます。12=4×3や、18=2×9のように、素数ではない数のことを合成数といい、2、3、4、9など、合成数を割り切れる数を約数といいます。そして、2や3など約数自体が素数であるとき、その約数を素因数といいます。

素数を扱うアルゴリズムは、大きく3つに区分されます。

素数判定
与えられた数nが素数であるかどうかを判定するアルゴリズムです。
n=12のとき、「約数4が見つかったので12は素数ではない」というように、一つの約数を見つければよいことになります。
素因数分解
12=2×2×3、18=2×3×3のように、合成数を構成するすべての素因数とその個数を列挙するアルゴリズムです。素因数分解のほうが複雑になります。一般的には、素数判定のアルゴリズムを発展させて、素因数分解に用いています。
最大公約数
二つの数が与えられたとき、共通の約数のうち、最大のものを最大公約数といいます。例えば、12と18の最大公約数は6になります。
素数判定や素因数分解の計算量が非常に大きいのに比較して、最大公約数は少ない計算量で求められます。それで、素数判定や素因数分解を高速化するアルゴリズムでは、最大公約数のアルゴリズムを利用することが多いのです。

「割り切れる」とは剰余が0のことですので、素数であるかどうかは剰余を求める計算が重要になります。
 プログラムでは、aをbで割ったときの剰余は、
  a mod b (C言語)
  a % b  (Javascript)
で求められます。

ユークリッドの互除法

最大公約数(GCD:Greatest Common Divisor)とは、2つの正整数aとbを素因数分解してときの共通項です。例えば
   a=924(=2×2×3×7×11)
   b=360(=2×2×2×3×3×5)
の最大公約数Gは
   G=2×2×3=12
になります。

なお、最小公倍数(LCM:Least Common Multiple)は、aとbでありきれる最小の整数のことです。
   a=G×(7×11)
   b=G×(2×3×5)
なので、最小公倍数Lは、
   L=G×(7×11)×(2×3×5)
となります。すなわち、
   L=a×b/G=924×360/12=27720
で計算できます。

ユークリッドの互除法は、最大公約数を計算する効率的なアルゴリズムです。

アルゴリズム
正整数a、b(a>b)の最大公約数を求める手順を示します。
  ア aをbで割った剰余をrとする。
  イ rが0ならばbが最大公約数である。
  ウ rが0でないならば、a←b、r←bとして、アへ戻る。
プログラム
  function euclid(a, b) {
    r = a % b;    /* rはa/bの剰余 C言語なら a mod b と記述 */
    while (r > 0) {
      a = b;
      b = r;
      r = a % b;
    }
    return b;
  }
数値例
(a=924、b=360)
   a   b   r
  924 360 204(=924-2×360)
  360 204 158(=360-1×204)
  204 158  48(=204-1×158)
  158  48  12(=158-3×48)
   48  12   0(=48-4×12)
        └─→最小公倍数=12

素数判別

単純なプログラム

与えた数nが素数であるときは1、約数のときは0を戻す、単純なプログラムを示します。
iを2からn-1まで変化させ、そのなかでnを割り切れたら0、どれでも割り切れなかったら1を戻します。
  function prime(n) {
    for(i=2; i<=n-1; i++) {
      if ((n % i) == 0) return 0;
    }
    return 1;
  }
これではあまりにも非効率です。例えば、

  • nが2つの数の積になるのであれば、小さいほうの数は、√の以下になります。iの上限値を√にすべきです。
  • 2で割れないのであれば、それ以上の偶数で割り切れるはsずがありません。iが3以上の場合はiが奇数のときだけチェックすればよいことになります。
それらを考慮すると、次のようになります。
  function prime(n) {
    if ((n % 2) == 0) return 0;
    for(i=3; i<=Math.sqrt(n); i++) {
      if ((n % i) == 0) return 0;
    }
    return 1;
  }

エラトステネスのふるい

上と同様に考えて、nがある数で割りきれないときは、その倍数のチェックをする必要がありません。それで、table[i] という表を用意しておき、iで割り切れたときは、iの倍数kについて、table[k] を0にします。このようにして、素数を求めていくのです。
  function eratosthenes(n) {
    table = new Array(101);
             /* 初期設定:とりあえず2と奇数は素数だと仮定しておく */
    for (i=0; i<= n; i++) table[i] = 0;
    table[2] = 1;
    for (i= 3; i<=n; i=i+2) table[i] = 1;
             /* 3以上、nの平方根以下の奇数について */
    for (i=3; i<=Math.sqrt(n); i=i+2){
      if (table[i] == 0) continue;
             /* 既に倍数になっているならチェックしない */
      for (j=i+i; j<=n; j=j+i) table[j] = 0;
             /* j=2×i、3×i、…は倍数であるとする */
             /* このようにして、ふるいにかけられて、素数が減少する */
    }
    return table[n];
  }

エラトステネスのふるいでは剰余の計算が不要です。その観点からも効率的になります。


文字列の検索

文字列検索とは、テキストの文字列内に、パターンの文字列と一致する部分文字列が存在するかどうかを調べ、存在したならば、その位置を求めるという操作です。
 デジタルデータが急激に増大しています。それらから有用なデータを、容易に入手することが重要になります。データが事前に体系づけて保管されていない場合が多いですし、体系づけられていたとしたとしても、他の切り口で探索することが必要な場合もあります。それに対処するには、検索エンジンのように、与えられた文字列を含むデータを全文探索することが必要になります。
 効率的な探索を行うために、多様な方法がとられていますが、最も基本的な方法が、文字列探索です。
例えば、
   テキストの文字列が「dabdabcabcba」
   パターンの文字列が「abcb」
の場合
                   11
         012345678901
   テキスト: dabdabcabcba
   パターン:        abcb

となるので7を戻し、パターンが「abcx」の場合は、テキストに一致する部分文字列が存在しないので、-1を戻す関数を考えます。

以下、テキストは配列t、パターンは配列pに入っており、テキストの文字列長さをn、パターンの文字列長さをmとします。上の例では、
   t[0]="d", t[1]="a", … , t[11]="a"  n=12
   p[0]="a", p[1]="b", … , p[3]="b"   m=4

となります。(t、pは0から始まり、n、mは個数であることに注意)
 なお、プログラムでは、これらの値はグローバル変数として定義されているものとします。

プログラム

ア function simple() {
イ   var i, j;
ウ   for (i=0; i<=n-m; i++) {
エ     for (j= 0; j<m; j++) {
オ       if (t[i+j] != p[j]) break;
カ     }
キ     if (j == m) return i;
ク   }
ケ   return -1;
コ }

アルゴリズム

t[i]以降とpが一致しているかを調べるには、pのj番目の文字p[j]とt[i+j]を比較することが基本になります(オでの比較)。
下表では、i=3、j=2(i+j=5)のとき、t[5]=bとp[2]=cを比較しています。
      i i+j  n-m n
      ↓ ↓  ↓   ↓
   0123456789101112
t: dabdabcabcba
p:    abcb
        ↑
        j

一致していないならば、それ以上この位置で比較する必要はないので、p全体を右に一つ移動させ(iに1を加えて)pの先頭から(j=0として)比較します(オのbreak)。
一致していれば(図では一致していないが)、jに1を加えて、t[6]=cとp[3]=bと比較します。

キで j=m のときに打ち切っているのは、パターンのすべての文字が一致したときは、j=m-1であり、それがj=mになったときにエ~カのループから出てキへ行くからです。

ウで i≦n-m(12-4=8)としたのは、i=9になると、pが最期までいったとき(j=3になったとき)に、i+j=12となり、オで t[i+j] がtの配列上限を超えてしまう(オーバーフローする)からです。

トレース
iはtの要素番号、jは比較するpの要素番号。i+jが比較位置

i j i+j 0123456789011
      dabdabcabcba
0 0 0 bcb  赤字は不一致を示す→iに1を加えjを0にする
1 0 1  bcb 青字は一致を示す→jに1を加える
1 1 2  bcb
1 1 3  ab
2 0 2   bcb
3 0 3    bcb
4 0 4     bcb
4 1 5     acb
4 2 6     ab
4 3 7     abc
5 0 5      bcb
5 1 6       bcb
7 0 7        bcb
7 1 8        acb
7 2 9        ab
7 3 10        abc  すべて一致
└ 一致位置(戻す値)

計算量
ウでiをn-m回行い、エでjをm回行っています。もし、一致する部分文字列が存在しなかったときは、オがすべてのi、jの組合せで行うことになり、その比較回数は、(n-m)×m回になります。nに対してmが小さいなら、約n×m回の比較になります。それで、この方法の計算量オーダーは O(n×m) になります。

アルゴリズムへ