LIS (Longest Increasing Subsequence) とは最長単調増加シーケンスのこと。数字列(あるいは文字列等、互いに大きさの比較ができるものなら何でもOK)の中から、値が大きくなっていき、もっとも長いシーケンス(数字列)を見つけ出すアルゴリズムのことです.

 -7, 10, 9, 2, 3, 8, 1

例えば,上の数字列では,LIS は -7 2 3 8 になり、その長さは4だ。

また、概念は同じだが、LDS (Longest Decreasing Subsequence、最長単調減少シーケンス) というのもある。

ここでは、i (1<=i<=N、Nはシーケンスの長さ)番目から始まるLIS(またはLDS)の長さについて考える。

上の例では、LIS[i] = { 4, 1, 1, 3, 2, 1, 1 }
      LDS[i] = { 1, 3, 2, 2, 2, 1, 1 } となる。

各データの位置から、LIS(LDS)の長さが分かれば、LISシーケンスを作り出すことができる。

#define SIZE 10000 /* 必要に応じて変更 */
int N; /* データの個数 */
int num[SIZE+3]; /* データ */
int LIS[SIZE+3]; /* LIS長さ */
int LDS[SIZE+3]; /* LDS長さ */
void calc(void)
{
    int i, j;
    int mi, md;
    LIS[N-1] = LDS[N-1] = 1;
    for (i = N-2; i >= 0; i--) {
        mi = md = 0;
        for (j = i+1; j < N; j++) {
            if (num[i] < num[j]) {
                if (LIS[j] > mi) mi = LIS[j];
            } else {
                if (LDS[j] > md) md = LDS[j];
            }
        }
        LIS[i] = mi+1;
        LDS[i] = md+1;
    }
}

計算時間は O(N^2) 。

下のコードはO(nlogn)の高速バージョン。LISのみになっているが、LDSへの対応もそれほど困難ではないだろう。

#define SIZE 10005  /* 配列のサイズ。適宜変更 */
int N;  /* データの個数 */
int max;  /* 計算終了の時点では最長LISの値が入る */
int num[SIZE+3];  /* データ */
int LIS[SIZE+3];  /* それぞれのデータ置からのLIS長さ */
int tmp[SIZE+3];  /* 作業用 */
void calc(void)
{
    int k;
    int lo, hi, mid;
    LIS[N-1] = 1;
    tmp[0] = num[N-1];
    max = 1;
    for (k = N-2; k >= 0; k--) {
        if (tmp[max-1] > num[k]) { tmp[max++] = num[k]; LIS[k] = max; continue; }
        if (tmp[max-1] == num[k]) { LIS[k] = max; continue; }
        lo = 0;
        hi = max;
        while (lo < hi) {
            mid = (lo + hi) >> 1;
            if (tmp[mid] > num[k]) lo = mid+1;
            else hi = mid;
        }
#if 0
        if (lo < max) tmp[lo] = num[k], LIS[k] = lo+1;
        else tmp[max++] = num[k], LIS[k] = max;
#else
        tmp[lo] = num[k], LIS[k] = lo+1;
#endif
    }
}

しばらくは暇が多くなるので,いろいろと書いていきます.UVaでのランキングは順調に上がっていますが,当面 5位を目標にしています.そのハードルを乗り越えれば,2位になることや,もしかしてナンバーワンになるのかもしれません.努力だけは誰にも負けないので,楽しみに見ていきましょう.

さて,アルゴリズムを探しているひとが多いと思いますが,もっとも高速な O(N logN) の LIS プログラムを公開します.

LIS (Longest Increasing Subsequence) とは最長単調増分シーケンスのこと.数字列 (あるいは文字列等.互いに大きさの比較ができるものなら何でもOK) の中から,値が大きく(あるいは小さく)なっていく,もっとも長いシーケンス(数字列)を見つけ出すアルゴリズムのことです.

 -7, 10, 9, 2, 3, 8, 8, 1

例えば,上の数字列では,LIS は -7 2 3 8 になります.数字列の長さ(つまりデータの個数)を N とすると,DP(ダイナミック・プログラミング)による O(N2) のアルゴリズムと,より高速な O(N logN) のアルゴリズム、少なくとも 2種類あることが知れています.

LIS のアルゴリズムについて,ネット上探せば当然色々と見つかります.以下のページもその一例.

http://www.windowsitpro.com/Files/23/24814/Figure_02.gif

ページが削除される可能性もあるので,コピーしておきます.

<Adapted algorithm for finding longest increasing subsequences>
 Let S = ( a1, a2, …, an ) be a sequence of n numbers. The length of the longest increasing subsequence of S is the number of elements in the list of numbers that the following procedure generates.

 Let K = 1, and let L be an empty list of numbers.

 While K <= n
  Inspect L for numbers greater than or equal to ak. If any exist, replace the smallest of them with ak. Otherwise ( when ak is greater than every number in L ), insert ak into the list L.
  Increase K by 1.

書いていることを、上のシーケンスでシミュレーションしてみましょう.

  S = ( -7, 10, 9, 2, 3, 8, 8, 1). N = 8.
 初期状態では, K = 1. リスト(集合) L を空 (Null) とする.
 以下を K <= 8 まで繰り返す.
   K = 1: a1 = -7. リスト L に何もないので,a1 を L に追加します.
   K = 2: a2 = 10. リスト L にある要素 -7 と比較します. a2 のほうが大きいので, L に追加します.これで,リスト L = ( -7, 10 ) になります.
   K = 3: a3 = 9. 同様にリストLにあるすべての要素と比較しますが,10よりも小さいので,10 を a3 に書き換えます.リスト L = ( -7, 9 ) に変わりますが,長さは K=2 のときと同じです.
   K = 4: a4 = 2. 上の9のケースと同様です.9を書き換えて,L = ( -7, 2 ) になります.
   K = 5: a5 = 3: リスト L の中のすべての要素よりも大きいので、L に追加します.追加した結果として, L = ( -7, 2, 3 ) になります.
   K = 6: a6 = 8: こちらも追加になります. L = ( -7, 2, 3, 8 ).
   K = 7: a7 = 8: リスト L に同じ要素が存在しているので,なにもしません.あるいは,同じ書き換え動作をしても構いません.結果は同じなので.
   K = 8: a8 = 1: リストにある要素のうち、a8よりも大きな最小値が 2 ですので,2 を書き換えます.これで、リスト L = ( -7, 1, 3, 8 ) に変わります.

  ここで終了.最終的に得られたリストは L = ( -7, 1, 3, 8 ). L の長さは 4 でした.

さて,丁寧に見てきたように,上のアルゴリズムは正確には LIS を探すものではなく,LIS の長さを探すものでした.つまり,LIS を見つけ出すことには間違っていますが、LIS の長さは正しく算出している と断言していいでしょう.本来ならば,このことを証明しないといけないけれど.

で,計算量を見てみます.リストLへの追加(その時点でのリストの最大値)は最後の位置にのみ行われていること,途中の書き換えも前後の順番を変えるものではないことから,リストは常に昇順でソートされた状態を保っていることが分かります.

ソートされた状態のリスト(配列)から値を探す方法として,2分検索(バイナリサーチ) というアルゴリズムがあります.それに従えば,検索時間は 最悪でも O(log N) で済みます.

個々の ai について O(log N) のバイナリサーチで検索し,ai よりも大きい値の最小値を O(1) で書き換えるか, リストの末尾に O(1) で追加する、という手続きなので,全体的にアルゴリズムの計算時間は O(N log N) になります.

一方、使用するメモリ領域は,入力データのリスト S 以外に, LIS を格納するリスト L も必要なのですが,Lの長さは最悪の場合でも N なので, メモリ領域(空間計算量)は O(N) になります.

両方合わせて、LIS の長さを O(N log N) で算出できるわけです.

以下はC言語によるプログラムです.

LISの長さを求める関数 LIS()

入力データを 配列 S に、データの長さを size にセットして、LIS() 関数を呼び出せば、LISの長さがリターン値として得られます.(配列の長さやデータ型は必要に応じて変えて下さい.)

<LISの長さを求める関数>
 int LIS(void)
   関数値: LISの長さ ( >= 0)
   入力データ: 配列 S.(添え字 0 からデータを入れてください.)
   入力データの長さ: size

汎用性を考えれば,関数のスペックを
  int LIS(int size, int *S)
にし,関数の内部に,LISを格納するためのリスト(配列)L用のメモリ領域をcalloc関数を使って動的に確保するほうがいいかもしれませんが,UVa のプログラムというものは汎用性を考えるよりも,信頼性や,スピードのほうが大事なので,手抜きします.

なお,上記の自作関数のなかでは,少しでも高速になるよう,バイナリサーチをかける前に,まずリストL内の最大値(つまり最後の要素)と比較し,入力データ aiが大きければ,そのまま追加手続きを取ることにしています.

LISの長さはこれで求まるわけですが,肝心のLISそのものを探し出すプログラムについては次回書きます.リストLの書き換えをする前に,その前任の記録を取るだけで済みます.理屈は簡単ですが,プログラムにすると少々判りにくくなるかもしれません.

2分探索木において、木の左右をバランスさせるのが望ましい。木の片寄り方に一定の限度を設けて、挿入と探索の両方を最悪の場合でも O(log n)の計算量でできるようにする。 どのノードにおいても、その左部分木の高さと右部分木の高さの差を、+1、 0、-1のいずれかにする。

この制約を満たす2分探索木をAVL木(AVL-tree、考案者Adelson-Velskii とLandisという2人の旧ソ連数学者の頭文字をとったもの)と呼ぶ。

AVL木は2分探索木であるから、探索のアルゴリズムは2分探索木のと同じだが、データの挿入や削除については、初めは2分探索木のと同様に処理する。しかしその結果として左右の部分木の高さの差が2になるノードがあれば、木を再構成して制約条件を満たすように直す。

AVL木と2分探索木の得失を厳密に評価することは難しい。実験的評価から、 AVL木は十分実用的なアルゴリズムだと考えられる。探索に要する計算量が、平均的にも最悪の場合にも2分探索木より少ない。挿入や削除には余分の手間がかかるが、計算量のオーダは変わらない。ただし、プログラムがやや複雑になるのは欠点。

理論的な観点からは、探索と挿入を同時に O(log n)の計算量で処理できることを初めて示した点でAVL木の価値は大きい。

<関数名>
  search AVL木におけるデータの探索
  insert AVL木におけるノードの挿入
  delete AVL木におけるノードの削除

<形式>
  AVL木におけるデータの探索
    NODE *search(int key);

  AVL木におけるノードの挿入
    NODE *insert(int key);

  AVL木におけるノードの削除
    int delete(int key);

<引数>
  typedef struct _node {
    int key;        /* 比較のキーとなるフィールド */
    int info;        /* その他のフィールド */
    struct _node *left;   /* 左側の子を指す */
    struct _node *right;  /* 右側の子を指す */
    int balance;      /* 左右の部分木の高さの差 */
  } NODE;

  AVL木におけるデータの探索関数において
    key 探索目標とするキーの値

  AVL木におけるノードの挿入関数において
    key 追加したいキーの値

  AVL木におけるノードの削除関数において
    key 削除したいキーの値

<関数値>
  AVL木におけるデータの探索関数について
    探索が成功したときは見つかったノードへのポインタ。
    失敗のときは NULL。

  AVL木におけるデータの挿入関数について
    挿入が成功したときは挿入したノードへのポインタ。
    挿入失敗のときや挿入しようとするキーが既にあったときは NULL。

  AVL木におけるデータの削除関数について
    削除が成功したときは 0。
    削除しようとするキーが存在していないときは -1。

<注意事項>
  AVL木のルートを示すのに、静的変数 root が使われている。

用例

<関数本体>
  avlTree.c

2分木の各ノードにデータがあり、あるノードから見て左側の子孫ノードのデータすべてがこのノードのデータの値より小さく、一方、右側の子孫ノードのデータすべてが大きいという関係が成立するものを2分探索木という。

2分探索木による探索は、ルートから始め、探索キーの値がそのノードのデータより小さいか大きいかによって、左側または右側の子ノードをたどっていく。

<関数名>
  search 2分探索木におけるデータの探索
  insert 2分探索木におけるノードの挿入
  delete 2分探索木におけるノードの削除

<形式>
  2分探索木におけるデータの探索
  NODE *search(int key);

  2分探索木におけるノードの挿入
  NODE *insert(int key);

  2分探索木におけるノードの削除
  int delete(int key);

<引数>
  typedef struct _node {
    int key;       /* 比較のキーとなるフィールド */
    int info;      /* その他のフィールド */
    struct _node *left;  /* 左側の子を指す */
    struct _node *right; /* 右側の子を指す */
  } NODE;

  2分探索木におけるデータの探索関数において
  key 探索目標とするキーの値

  2分探索木におけるノードの挿入関数において
  key 追加したいキーの値

  2分探索木におけるノードの削除関数において
  key 削除したいキーの値

<関数値>
  2分探索木におけるデータの探索関数について
    探索が成功したときは見つかったノードへのポインタ。
    失敗のときは NULL。

  2分探索木におけるデータの挿入関数について
    挿入が成功したときは挿入したノードへのポインタ。
    挿入失敗のときや挿入しようとするキーが既にあったときは NULL。

  2分探索木におけるデータの削除関数について
    削除が成功したときは 0。
    削除しようとするキーが存在していないときは -1。

<注意事項>
  2分探索木のルートを示すのに、静的変数 root が使われている。

用例

<関数本体>
  binaryTree.c

<説明>
  完全につりあいのとれた2分探索木なら、n 個のものを調べるのに必要な比較回数は O(log n) 。しかし、左右のバランスの悪い木では探索時間がかかり、最悪場合の計算量は O(n) 。
  また、削除のプログラムがかなり複雑になってしまうことは、2分探索木の特徴である。考えるべきケースとして、削除しようとするノードが
  ・左側に子ノードをもたない場合
   自分自身を右側の部分木で置き換える。つまり、親ノードから右側の部分木にリンクを張り直す。
  ・左側に子ノードをもつ場合
   左側の部分木から最大のノードを探し出し、自分自身をそのノードで置き換える。リンクの張り直しなど、いくつかの操作が必要。
  探索や挿入の単純なルーチンよりも難しいが、注意深く考える価値があろう。
  なお、2分探索木の性質上、同じ探索キーをもつノードは一つしかないので、同じ探索キーに複数のデータをもつ場合はデータ構造中のinfoを工夫する必要がある。

配列またはリストに並べられたデータがソートされている場合には、本2分探索法を使うと探索時間を大幅に減らすことができる。それは、データ全体を2つのグループに分けて、探すキーがどのグループに属しているかを判定し、属している部分を更に2つの小さなグループに分けて繰り返して調べていく方法だから。

<関数名>
  binarySearch 2分探索

<形式>
  int binarySearch(DATA *data, int nmem, int target);

<引数>
  typedef struct {
    int key;   /* 比較のキーとなるフィールド */
    int info;  /* その他のフィールド */
  } DATA;

  data   (入力) データレコードの配列
  nmem  (入力) レコード配列の大きさ
  target  (入力) 探索目標とするキーの値

<関数値>
  見つかった場合は配列の要素番号(配列の先頭要素の番号は0)。見つからなかった場合は -1。

注意事項
  データレコードのキーデータが昇順に正しくソートされていることが前提条件である。

用例

<関数本体>
  binarySearch.c

<説明>
  1回の比較で探索すべき範囲は半分になるので、探索成功あるいは失敗のどちらの場合でも、計算量は O(log n) 。
  データが降順でソートされている場合は、不等号の向きを変ればよい。

線形探索では先頭から要素を一つ一つ調べるので、後ろにある要素ほど探索時間がかかる。そこで、探索のたびに、見つかった要素を先頭に移動すれば、頻繁に検索されるものほど先頭に集まり、平均探索時間が短くなることが期待できる。このような方法を自己組織化探索という。

しかし、移動は配列にとっては大変時間のかかり作業であり、一方リストならばポインタの付け替えだけですむ。したがって、自己組織化探索では、データはリストにより保持される。

<関数名>
  selfSearch 自己組織化探索

<形式>
  LIST *selfSearch(LIST *list, int target);

<引数>
  typedef struct _list {
    int key;       /* 比較のキーとなるフィールド */
    int info;       /* その他のフィールド */
    struct _list *next; /* つぎの要素 */
  } LIST;

  list   (入力) リストへのポインタ
  target (入力) 探索目標とするキーの値

<関数値>
  見つかった場合はその要素へのポインタ。見つからなかった場合は NULL。

注意事項
  リストが正しく作成されていることが前提。細かいことについてはつぎの用例プログラムを参照すること。

用例

<関数本体>
  selfSearch.c

探索とは多くのデータから望みのデータを見つけることをいう。多くの情報処理で用いられる基本操作の一つ。

線形探索は逐次探索、順探索ともいう。配列またはリストに並べられたデータを一つ一つ順に端から調べるだけの素朴な探索法だ。

<関数名>
  linearSearch 線形探索

<形式>
  int linearSearch(DATA *data, int nmem, int target);

<引数>
  typedef struct {
    int key;  /* 比較のキーとなるフィールド */
    int info;  /* その他のフィールド */
  } DATA;

  data  (入力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  target (入力) 探索目標とするキーの値

<関数値>
  見つかった場合は配列の要素番号(配列の先頭要素の番号は0)。
  見つからなかった場合は -1。

用例

<関数本体>
  linearSearch.c

<説明>
 比較のループを回る回数は、探索が失敗の場合はn回、成功の場合は平均してn/2回。いずれにしても計算量は O(n)。