スペル修正プログラムをJavaScriptで再現＆改悪してみた

いつか読むとtaggingしたまま放置して、ようやく読んだ
スペル修正プログラムはどう書くか（原文はこっち）。

僕もJavaScriptで同じようなものを作ってみました。
（途中まで読んだ速効!Pythonプログラミングが一応役に立った･･･かな？）

仕組みは原文の通り。

ド文系の僕でも読めたので、興味のある人は是非。オススメです。
前半の数式で一瞬怯みますが、ちゃんと文章でも解説してくれてます。

簡単に説明すると、

• トレーニング
  - 英文に出現する単語＆出現数を記憶する。
• タイポ生成
  - 入力内容の1字違い＆2字違いの全パターンを生成。
• 候補提示
  - タイポと記憶した単語を照合し、出現数が最も多いものを候補とする。

って感じです。

ただ、僕のはもっとショボいです。

まず、1文字違いしか考慮してません。（2字違いを計算するとかなり重かった）
あと、10語/sなんてとんでもありません、ムリです。
さらに、精度も駄目です。（流石に6Mのテキストをjsに読ませるわけにはいきません････）
※ 代わりと言ってはなんですが、複数の候補を返せるようにしてみました。

とまぁ、グダグダながらも一応完成。

それを使ったサンプルも作成中。

近日公開！

･･･すいません、大袈裟です。

それでは、今日は以上です。

参考記事とソース（結構長い）は続きに入れます。

[参考記事]

Pythonのスペル修正プログラムをJavaに移植してみました - あるまに@monstar
pythonあまり読めないのでJava製のがあって助かりました。

スペル修正プログラム Ruby版 - Spirit of Apprenticeship (みならいだましい)（ 改 ）
正規表現を参考に。rubyはpython以上にわかりませんでしたが。

それPerlで書けるよ（当たり前だ） - k12uのアレ
perlはやっぱり全く読めませんでした･･･。

[ソース]
サンプル用に余計な機能も付いてます。
そのくせ、XMLHttpRequestとかでファイルをロードするのを忘れてました。
（init()にStringを渡して初期化する形になってます。）

var NWORDS = [];

function words(text) {

	return text.toLowerCase().replace(/[^a-z]+/g, ' ').split(' ');
}

function train(features) {

	var model = [];

	for(var i = 0; i < features.length; i++) {
		model[features[i]] = (model[features[i]]) ? ++model[features[i]] : 1;
	}
	
	return model;
}

function edits1(word) {

	var n = word.length;
	var alphabet = 'abcdefghijklmnopqrstuvwxyz';
	var a = [];
	
	//deletion（削除）
	for(var i = 0; i < n; i++) {
		a[a.length] = word.substring(0, i) + word.substring(i + 1, n);
	}

	//transposition（転位）
	for(var i = 0; i < n - 1; i++) {
		a[a.length] = word.substring(0, i) + word.charAt(i + 1) + word.charAt(i) + word.substring(i + 2, n);
	}

	//alteration（置換）
	for(var i = 0; i < n; i++) {
		for(var j = 0; j < alphabet.length; j++) {
			a[a.length] = word.substring(0, i) + alphabet.charAt(j) + word.substring(i + 1, n);
		}
	}

	//insertion（挿入）
	for(var i = 0; i < n; i++) {
		for(var j = 0; j < alphabet.length; j++) {
			a[a.length] = word.substring(0, i) + alphabet.charAt(j) + word.substring(i, n);
		}
	}
	
	return (a.length != 0) ? a : false;;
}

function known_edit2(word) {
	
	var a = [];
	
	var edited1 = edits1(word);
	
	for(var i = 0; i < edited1.length; i++) {
	
		var edited2 = edits1(edited1[i]);
		
		for(var j = 0; j < edited2.length; j++)  {
				if(NWORDS[edited2[j]]) a[a.length] = edited2[j];
		}
	}
	
	return (a.length != 0) ? a : false;;
}


function known(words) {
	
	var a = [];
	for(var i = 0; i < words.length; i++)  {
		if(NWORDS[words[i]]) a[a.length] = words[i];
	}
	
	return (a.length != 0) ? a : false;;
}

function correct(word) {

// 2文字違いを考慮しないように
//	return (known([word]) || known(edits1(word)) || known_edit2(word) || [word])
	return (known([word]) || known(edits1(word)) || [word])
		.sort(function(a, b) {
			a = (NWORDS[a]) ? NWORDS[a] : 1;
			b = (NWORDS[b]) ? NWORDS[b] : 1;
			return b - a;
		})[0];


}

function corrects(word, num) {

	if(typeof(num) == 'undefined' || num < 1) num = 1;

//入力単語そのままはいらない
//	return (known([word]) || known(edits1(word)) || [word])
	return (known([word]) || known(edits1(word)) || [])
		.sort(function(a, b) {
			a = (NWORDS[a]) ? NWORDS[a] : 1;
			b = (NWORDS[b]) ? NWORDS[b] : 1;
			return b - a;
		}).slice(0, num);
}

//初期化
function init(text) {

	NWORDS = train(words(text));
}

//追加で覚えさせる
function cheat(text) {

	var features = words(text);
	for(var i = 0; i < features.length; i++) {
		NWORDS[features[i]] = (NWORDS[features[i]]) ? ++NWORDS[features[i]] : 1;
	}
	
}

//忘れさせる
function omit() {
	NWORDS = [];
}

以上です。