プログラミングで解く数学の問題を集めた「Project Euler」というサイトがあります。

Project Euler

http://projecteuler.net/

上記サイトは英語ですが、問題を日本語訳しているサイトもあります。

Project Euler - PukiWiki

http://odz.sakura.ne.jp/projecteuler/index.php?Project%20Euler

問題を解いて正解すると、その問題のフォーラムを閲覧できるようになり、他の人とコードを見せあったり議論したりできるようになっています。

数学の問題といっても、それほど難易度が高くない問題も用意されているので、数学やアルゴリズムに興味のある人は「Project Euler」に挑戦してみてはいかがでしょうか。

論理だけで自然数という概念を定義したペアノの公理というものがあります。ペアノの公理によると自然数はある5つの条件を満たす、と定義されるそうです。ペアノの公理がどのようなものかは下記リンク先のWikipediaのページを見てください。(ぇ

ペアノの公理 - Wikipedia

http://ja.wikipedia.org/wiki/%E3%83%9A%E3%82%A2%E3%83%8E%E3%81%AE%E5%85%AC%E7%90%86

自然数が満たすべき条件が決められるということは、この条件を満たすようにオブジェクトを定義すれば、それは自然数と同等のオブジェクトになるということです。

ということでプリミティブ型やライブラリの数値型を利用しないで自然数を実装してみました。

package number.natural;

public abstract class PeanoSystem<E> {

    public abstract E zero();
    public abstract E succ(E n);

    public E add(E a, E b) {
	return f(a, b, zero());
    }

    public E sub(E a, E b) {
	return f(zero(), a, b);
    }

    private E f(E a, E b, E c) {
	return b.equals(c) ? a : f(succ(a), b, succ(c));
    }
}

package number.natural;

public class Natural extends PeanoSystem<Object> {

    @Override
    public Object succ(Object n) {
	return new Succ(n);
    }

    @Override
    public Object zero() {
	return new Zero();
    }

    private static class Zero {

	@Override
	public boolean equals(Object obj) {
	    return getClass().isInstance(obj);
	}
    }

    private static class Succ {

	private Object n;

	public Succ(Object n) {
	    this.n = n;
	}

	@Override
	public boolean equals(Object obj) {
	    return getClass().isInstance(obj)
		    && n.equals(getClass().cast(obj).n);
	}
    }
    
    public static void main(String[] args) {
	Natural sys = new Natural();
	Object one = sys.succ(sys.zero());
	Object two = sys.add(one, one);
	Object four = sys.add(two, two);
	Object eight = sys.add(four, four);
	for (Object i = sys.zero(); !i.equals(eight); i = sys.add(i, one)) {
	    System.out.print(".");
	}	
    }
}

演算は足し算と引き算しかできない(しかも引く数が引かれる数より多いと無限ループに陥るという欠陥がある)、十進数表示もできない、メモリ効率は相当に悪いと欠点だらけなのでまったく実用性がありませんが、唯一の長所は int などの数値型と異なり理論的には最大値に限界がありませんので、メモリの許す限り大きな値を表すことができるということでしょうか。まあそれは BigInteger を使えばよいという話ですが。

とはいえ自然数、もっというと数という根源的な概念をさらに分解して考えるというのはなかなかおもしろいものです。

前回はLZ77という圧縮アルゴリズムを実装してみました。今回はLZ77を改良したLZSSというアルゴリズムを実装してみます。

LZ77ではすでに処理された文字列の中に一致する部分があれば、そこを指すポインタ(長さと位置)を生成し、次にその後の一文字を出力する、ということを繰り返す形式でした。 この形式だと、すでに処理された文字列の中に一致する部分がなくても、ポインタを置かなければなりませんでした。 LZSSでは最初の1bitでその後に続くビット列がポインタであるか、文字であるかを表すように改良しています。また、すでに処理された文字列の中に一致する部分があっても、それをポインタで出力するよりも、文字データ出力するほうが効率が良い場合には文字として出力するようにすることでさらに効率が良くなっています。

sample/compress/LZSS.java

package sample.compress;

import java.io.ByteArrayOutputStream;
import java.nio.ByteBuffer;

public class LZSS {

  private static final int LENGTH_SIZE = 8;
  private static final int DISTANCE_SIZE = 11;

  private static final int LOOKAHEAD_SIZE_MAX = (1 << LENGTH_SIZE) - 1;
  private static final int DICTIONARY_SIZE_MAX = 1 << DISTANCE_SIZE;

  public static String encode(byte[] data) {
    ByteBuffer buf = ByteBuffer.wrap(data).asReadOnlyBuffer();
    StringBuilder sb = new StringBuilder();
    while (buf.hasRemaining()) {
      int length = 0, distance = 0;
      int dictSize = Math.min(buf.position(), DICTIONARY_SIZE_MAX);
      for (int i = 0; i < dictSize; i++) {
        int j;
        int lkahSize = Math.min(buf.remaining(), LOOKAHEAD_SIZE_MAX);
        for (j = 0; j < i + 1 && j < lkahSize; j++) {
          int dictDatum = buf.get(buf.position() - i + j - 1);
          int lkahDatum = buf.get(buf.position() + j);
          if (dictDatum != lkahDatum) {
            break;
          }
        }
        if (length < j) {
          length = j;
          distance = i;
        }
      }
      if (length * (1 + Byte.SIZE) < 1 + LENGTH_SIZE + DISTANCE_SIZE) {
        sb.append("0").append(toBits(Byte.SIZE, buf.get()));
      } else {
        sb.append("1").append(toBits(LENGTH_SIZE, length)).append(
            toBits(DISTANCE_SIZE, distance));
        buf.position(buf.position() + length);
      }
    }
    return sb.toString();
  }

  private static String toBits(int size, int b) {
    return size == 0 ? "" : toBits(size - 1, b >> 1) + (b & 1);
  }

  public static byte[] decode(String code) {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    byte[] slide = new byte[DICTIONARY_SIZE_MAX + LOOKAHEAD_SIZE_MAX];
    int off = 0;
    while (!code.isEmpty()) {
      if (code.startsWith("0")) {
        slide[off++] = (byte) Integer.parseInt(code.substring(1,
            1 + Byte.SIZE), 2);
        code = code.substring(1 + Byte.SIZE);
      } else {
        int length = Integer.parseInt(code
            .substring(1, 1 + LENGTH_SIZE), 2);
        int distance = Integer.parseInt(code.substring(1 + LENGTH_SIZE,
            1 + LENGTH_SIZE + DISTANCE_SIZE), 2);
        try {
          System.arraycopy(slide, off - distance - 1, slide, off,
              length);
        } catch (Exception e) {
          e.printStackTrace();
        }
        off += length;
        code = code.substring(1 + LENGTH_SIZE + DISTANCE_SIZE);
      }
      if (off > DICTIONARY_SIZE_MAX) {
        baos.write(slide, 0, off - DICTIONARY_SIZE_MAX);
        System.arraycopy(slide, off - DICTIONARY_SIZE_MAX, slide, 0,
            DICTIONARY_SIZE_MAX);
        off = DICTIONARY_SIZE_MAX;
      }
    }
    baos.write(slide, 0, off);
    return baos.toByteArray();
  }
}