AC法をJavaで実装

文献[1]で紹介されているAC法をJavaで実装してみました．

AC法はテキスト内に出現する複数のキーワードを1回走査しただけで検出することができるアルゴリズムです． トライの部分はダブル配列法を使いたいところですが，コード量が多くなるので，今回はTreeMapで済ませました． テストケースの件数が少ないので，もしかするとバグっているかもしれません．

[1]	伊藤 直也, 田中 慎司: Web開発者のための大規模サービス技術入門, 技術評論社, 2010-08

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Comparator;
	import java.util.TreeMap;
	public class AC {
	private Node rootNode;
	public static AC create(String[] keywords) {
	Arrays.sort(keywords, new Comparator<String>() {
	@Override
	public int compare(String keyword1, String keyword2) {
	int result = keyword1.length() - keyword2.length();
	if (result == 0) {
	result = keyword1.compareTo(keyword2);
	}
	return result;
	}
	});
	AC ac = new AC();
	ac.rootNode = new Node();
	ac.rootNode.failureNode = ac.rootNode;
	for (String keyword : keywords) {
	Node currentNode = ac.rootNode;
	for (int i = 0; i < keyword.length(); i++) {
	char label = keyword.charAt(i);
	Node nextNode = ac.g(currentNode, label);
	if (nextNode == null) {
	nextNode = new Node();
	nextNode.failureNode = ac.rootNode;
	currentNode.nextNodeMap.put(label, nextNode);
	}
	currentNode = nextNode;
	}
	currentNode.lengths.add(keyword.length());
	}
	for (String keyword : keywords) {
	Node keywordNode = ac.g(ac.rootNode, keyword);
	for (int i = 1; i < keyword.length(); i++) {
	String suffix = keyword.substring(i);
	Node suffixNode = ac.g(ac.rootNode, suffix);
	if (suffixNode != null) {
	keywordNode.failureNode = suffixNode;
	for (int length : suffixNode.lengths) {
	keywordNode.lengths.add(length);
	}
	break;
	}
	}
	}
	return ac;
	}
	public Result match(String text) {
	Result result = new Result();
	Node currentNode = this.rootNode;
	int position = 0;
	while (position < text.length()) {
	for(int length : currentNode.lengths) {
	Occurrence occurrence = new Occurrence(position - length, length);
	result.occurrences.add(occurrence);
	}
	char label = text.charAt(position);
	Node nextNode = this.g(currentNode, label);
	if (nextNode == null) {
	while (currentNode != this.rootNode) {
	currentNode = this.f(currentNode);
	nextNode = this.g(currentNode, label);
	if (nextNode != null) {
	currentNode = nextNode;
	break;
	}
	}
	}
	else {
	currentNode = nextNode;
	}
	position++;
	}
	return result;
	}
	Node g(Node node, char label) {
	Node nextNode = node.nextNodeMap.get(label);
	return nextNode;
	}
	Node g(Node node, String labels) {
	Node currentNode = node;
	for (int i = 0; i < labels.length(); i++) {
	char label = labels.charAt(i);
	Node nextNode = this.g(currentNode, label);
	if (nextNode == null) {
	return null;
	}
	currentNode = nextNode;
	}
	return currentNode;
	}
	Node f(Node currentNode) {
	return currentNode.failureNode;
	}
	static class Node {
	TreeMap<Character, Node> nextNodeMap;
	Node failureNode;
	ArrayList<Integer> lengths;
	Node() {
	this.nextNodeMap = new TreeMap<Character, Node>();
	this.failureNode = null;
	this.lengths = new ArrayList<Integer>();
	}
	}
	public static class Occurrence {
	public int position;
	public int length;
	public Occurrence(int position, int length) {
	this.position = position;
	this.length = length;
	}
	@Override
	public boolean equals(Object object) {
	if (this == object) {
	return true;
	}
	if (object == null) {
	return false;
	}
	if (!(object instanceof Occurrence)) {
	return false;
	}
	Occurrence other = (Occurrence)object;
	if (this.position != other.position) {
	return false;
	}
	if (this.length != other.length) {
	return false;
	}
	return true;
	}
	@Override
	public int hashCode() {
	final int prime = 31;
	int result = 1;
	result = prime * result + this.position;
	result = prime * result + this.length;
	return result;
	}
	@Override
	public String toString() {
	StringBuilder builder = new StringBuilder();
	builder.append('{');
	builder.append("\"position:\"");
	builder.append(this.position);
	builder.append(",\"length:\"");
	builder.append(this.length);
	builder.append('}');
	return builder.toString();
	}
	}
	public static class Result {
	public ArrayList<Occurrence> occurrences;
	public Result() {
	this.occurrences = new ArrayList<Occurrence>();
	}
	}
	}

view raw AC.java hosted with ❤ by GitHub

	import static org.hamcrest.core.IsEqual.equalTo;
	import static org.junit.Assert.assertThat;
	import java.util.ArrayList;
	import java.util.List;
	import org.junit.Test;
	public class ACTest {
	@Test
	public void test() {
	String[] keywords = new String[] {"he", "hers", "his", "she"};
	String text = "a his hoge hershe xx.";
	@SuppressWarnings("serial")
	List<AC.Occurrence> occurrences = new ArrayList<AC.Occurrence>() {{
	add(new AC.Occurrence( 2, 3));
	add(new AC.Occurrence(11, 2));
	add(new AC.Occurrence(11, 4));
	add(new AC.Occurrence(14, 3));
	add(new AC.Occurrence(15, 2));
	}};
	AC ac = AC.create(keywords);
	AC.Result result = ac.match(text);
	for (int i = 0; i < occurrences.size(); i++) {
	AC.Occurrence expectedOccurrence = occurrences.get(i);
	AC.Occurrence actualOccurrence = result.occurrences.get(i);
	assertThat(expectedOccurrence, equalTo(actualOccurrence));
	}
	}
	}

view raw ACTest.java hosted with ❤ by GitHub

VB CodeをJavaで実装

文献[1]で紹介されているVB CodeをJavaで実装してみました．

また，圧縮の効果も調べてみました． 以下がその結果（一例）です． 140万エントリのID列を想定してランダムに生成した整数列をギャップ列に直して，VC Codeでエンコードしています． 元の整数列が密になる（整数列の長さが増す）ほど，圧縮率が良くなっています． 密になればなるほど，整数間のギャップが小さくなるので，期待通りの結果になりました．

整数列長	圧縮前(B)	圧縮後(B)	圧縮率
1	4	4	1.00
10	40	32	0.80
100	400	260	0.65
1000	4000	1955	0.49
10000	40000	14079	0.35

[1]	伊藤 直也, 田中 慎司: Web開発者のための大規模サービス技術入門, 技術評論社, 2010-08

	import java.io.ByteArrayOutputStream;
	import java.util.ArrayList;
	import java.util.List;
	public class VBCode {
	public static byte[] encode(List<Integer> numbers) {
	ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
	byte[] bytes = new byte[5];
	for (int number : numbers) {
	int offset = 4;
	while (true) {
	bytes[offset] = (byte)(number % 128);
	if (number < 128) {
	break;
	}
	number = number / 128;
	offset--;
	}
	bytes[4] = (byte)(bytes[4] | 0x80);
	byteStream.write(bytes, offset, bytes.length - offset);
	}
	return byteStream.toByteArray();
	}
	public static List<Integer> decode(byte[] bytes) {
	ArrayList<Integer> numbers = new ArrayList<Integer>();
	int number = 0;
	for (int i = 0; i < bytes.length; i++) {
	if (bytes[i] >= 0) {
	number = 128 * number + bytes[i];
	}
	else {
	number = 128 * number + (bytes[i] & 0x7F);
	numbers.add(number);
	number = 0;
	}
	}
	return numbers;
	}
	}

view raw VBCode.java hosted with ❤ by GitHub

	import static org.hamcrest.CoreMatchers.equalTo;
	import static org.junit.Assert.assertThat;
	import java.util.ArrayList;
	import java.util.List;
	import org.junit.Test;
	public class VBCodeTest {
	private static final int MAXVALUE = 14000000;
	@Test
	public void test() {
	int[] lengthes = {1, 10, 100, 1000, 10000, 100000};
	System.out.println("Length\tNumbers Size\tEncoded Numbers Size\tCompression Rate");
	for(int length : lengthes) {
	List<Integer> numbers = createNumbers(1, MAXVALUE, length);
	//System.out.println(toCSV(numbers));
	List<Integer> gaps = createGaps(numbers);
	//System.out.println(toCSV(gaps));
	byte[] encodedGaps = VBCode.encode(gaps);
	//System.out.println(toCSV(encodedGaps));
	List<Integer> decodedGaps = VBCode.decode(encodedGaps);
	//System.out.println(toCSV(decodedGaps));
	assertThat(decodedGaps, equalTo(gaps));
	int numbersSize = Integer.SIZE / Byte.SIZE * numbers.size();
	System.out.print(length);
	System.out.print("\t");
	System.out.print(numbersSize);
	System.out.print("\t");
	System.out.print(encodedGaps.length);
	System.out.print("\t");
	System.out.print((double)encodedGaps.length / numbersSize);
	System.out.println();
	}
	}
	class Pair {
	int lower;
	int upper;
	Pair(int lower, int upper) {
	this.lower = lower;
	this.upper = upper;
	}
	}
	List<Integer> createNumbers(int lower, int upper, int length) {
	ArrayList<Integer> numbers = new ArrayList<Integer>();
	ArrayList<Pair> pairs = new ArrayList<Pair>();
	pairs.add(new Pair(lower, upper));
	LOOP:
	while (true) {
	ArrayList<Pair> nextPairs = new ArrayList<Pair>();
	for (Pair pair : pairs) {
	if (pair.lower == pair.upper) {
	nextPairs.add(pair);
	}
	else {
	int middle = pair.lower + (int)Math.floor(Math.random() * (pair.upper - pair.lower));
	nextPairs.add(new Pair(pair.lower, middle));
	if (nextPairs.size() == length) {
	pairs = nextPairs;
	break LOOP;
	}
	nextPairs.add(new Pair(middle + 1, pair.upper));
	if (nextPairs.size() == length) {
	pairs = nextPairs;
	break LOOP;
	}
	}
	}
	pairs = nextPairs;
	}
	for (Pair pair : pairs) {
	int number = pair.lower + (int)Math.floor(Math.random() * (pair.upper - pair.lower));
	numbers.add(number);
	}
	return numbers;
	}
	List<Integer> createGaps(List<Integer> numbers) {
	List<Integer> gaps = new ArrayList<Integer>(numbers.size());
	gaps.add(numbers.get(0));
	for(int i = 1; i < numbers.size(); i++) {
	gaps.add(numbers.get(i) - numbers.get(i - 1));
	}
	return gaps;
	}
	static int asUint(byte b) {
	return b & 0xFF;
	}
	static String toCSV(int[] array) {
	StringBuilder builder = new StringBuilder();
	if (array.length > 0) {
	builder.append(array[0]);
	}
	for (int i = 1; i < array.length; i++) {
	builder.append(",");
	builder.append(array[i]);
	}
	return builder.toString();
	}
	static String toCSV(byte[] array) {
	StringBuilder builder = new StringBuilder();
	if (array.length > 0) {
	builder.append(asUint(array[0]));
	}
	for (int i = 1; i < array.length; i++) {
	builder.append(",");
	builder.append(asUint(array[i]));
	}
	return builder.toString();
	}
	}

view raw VBCodeTest.java hosted with ❤ by GitHub

[読了]MAKERS

「MAKERS」を読みました．

Chris Anderson: MAKERS, NHK出版, 2012-10

本書についてのメモを以下に記しておきます．

本書は，ビットの世界で起きた変革がアトムの世界でも起きつつあることについて述べられている．それは，経済規模で捉えると，ビットの世界と比べて少なくとも5倍大きい世界での変革であり，21世紀版産業革命と呼ばれるものになるであろう変革である．

ビットの世界で起きた変革は，デジタル技術とネットワーク技術の融合によって生じたものである．それらが，広大なスペースを持つ棚と際限なくそこに並ぶモノをサイバー空間の中に登場させたおかげで，我々は従来より自分の嗜好にあったモノを供給したり消費したりすることが可能になった．そして，個人の嗜好に従ったモノの供給と消費は，ビットの世界に様々なロングテールを出現させた．さらに，ビットの世界では，モノのフリー化も進展している．サイバー空間にある棚に無償のモノが供給されるケースが多くなっているのである．

アトムの世界で起きつつある変革は，先の二つの技術に加え，3Dプリンタに代表される新たな製作技術の登場によって生じている．これらは，モノの製作に必要なツールを企業の工場から個人の工房へと移し，また，個人のアイデアを補強したり，集約したりする場を提供する．これにより，ツールを使いこなすスキルは必要になるものの，自分の嗜好にあうモノを自分自身で製作できるようになる．もう自分が欲しいモノを気長に待つ必要はなくなる．さらに，気が向けば，自分と同じ嗜好の持ち主のためにそれをサイバー空間の棚に置くこともできる．

モノを製作するツールの大衆化とそれを並べる棚の存在がビットの世界で起きた変革をアトムの世界にもたらしている．アトムの世界では，ロングテールの真ん中の部分がごっそり抜け落ちていた．極端に言うと，工場で大量生産されたモノがある頭と，オーダメイドのモノがある尻尾の先は存在するものの，胴と尻尾の大部分にモノは存在しなかったのである（デジタルの世界ではこの部分の売上は全体の3分の1程度あるそうだ）．しかし，アトムの世界で起きつつある変革は，この部分にもモノを供給するようになる．それは，大量でもなく，少量でもなく，小回りの効く中規模なチームが生きていくのに必要な利益を生み出せる量のモノが存在する場所である．そして，自分だけでなく同じ嗜好の持ち主を満足させることができるやりがいのある場所である．

このような新天地が我々のすぐ目の前にある．まだ人が少ないうちに見物だけはしておいたほうがよいかもしれない．とりあえずAutodeskの123Dはダウンロードしてみた．3Dプリンタはどうしようか．

[読了]モチベーション3.0

Daniel H. Pinkのモチベーション3.0を読みました．

Daniel H. Pink: モチベーション3.0―持続する「やる気！」をいかに引き出すか, 講談社, 2010-07

本書についてのメモを以下に記しておきます．

本書は，現代の仕事において良い成果を残すための秘訣について述べられている．それは行動を引き起こすための心の働きの一つであり，内発的動機づけと呼ばれるものである．

動機づけは，生理的動機づけ，外発的動機づけ，そして，内発的動機づけに大別される．生理的動機づけは生き残るための行動を引き出すものであり，外発的動機づけはアメとムチとして周囲から与えられるものである．そして，内発的動機づけは，活動自体からもたらされる満足感によって自身から沸き起こるものである．

生活水準が一定のラインを超えると，生理的動機づけはなりを潜め，人の行動は外発的動機づけと内発的動機づけの影響を受けるようになる．外発的動機づけは，単純あるいは定形的な仕事に効果を発揮する動機づけであり，その比率が高かった近代社会においては十分機能してきた．一方，内発的動機づけは，クリエイティブな仕事に効果を発揮する動機づけであり，その比率が高まる傾向のある現代社会に適している．

動機づけには，種類によって向き不向きがあり，その性質に応じて使い分ける必要がある．例えば，生活水準がある閾値を越えない状況では，生理的動機づけが支配的になり，外発的動機づけや内発的動機づけは機能しなくなる．また，クリエイティブな仕事に外発的動機づけを行うと，内発的動機づけで行うよりその成果は低下する．

先に記したとおり，現代社会はクリエイティブな仕事の比率が高まっている．したがって，今後は外発的動機づけより，内発的動機づけのほうが有効な手段となる場合が多くなることが予想される．

内発的動機づけは，自律性，熟達，目的を拠り所にしている．自らの意志で行動を決め（自律性），意義のあることに打ち込み（熟達），自分以外の利益に貢献する永続的な指針をもつ（目的）ことにより，内発的動機づけのエネルギーを生み出すことができる．