Hatena::ブログ(Diary)

Shimojimojiの日記

2009-01-22 スペル修正プログラムをつくてみた

某博士に紹介してもろた

スペル修正プログラムはどう書くか :

http://www.aoky.net/articles/peter_norvig/spell-correct.htm

を参考にJavaで実装してみますた

はじめに 19:29

日本語コーパスを準備するのが面倒だったので,

誤りモデル => レーベンシュタイン距離

確立モデル => senの辞書

で代用した.

解説 20:00

senの辞書を利用

sen(というかchasen)の辞書dic.csv

単語の原形,生起コスト, ......

という形式になっている。

単語の生起コストは単語の出現確率から計算されているため,

今回は単語の出現確立の代わりにこのコストを使ってみた。

1/(cost + 1000)くらいが大体生起確率ってことで適当に決めうち

レーベンシュタイン距離

単語Aの代わりに単語Bを間違えて入力する確立をレーベンシュタイン距離を使って計算する。

commonslucene両方でレーベンシュタイン距離を計算するクラスが提供されているが

今回はluceneのほうを使ってみた。

StringDistance DIST_ALGO = new LevensteinDistance();
float curDist = DIST_ALGO.getDistance(A, B);

で2つの文字列A,Bの距離が計算できる

はずなんだがなぜか返り値が0...1で

A=Bの場合 1が返り

3文字くらい違うと0が返る

距離というか類似度っぽいなー

まあそのまま誤り確率として利用してみた。

スコアけいさん

適当にしたのような式でスコアを計算して、

最大のものを返す

float curScore = curDist + (1 / (correctStringCost + 1000) * 1000);

検証 20:07

してません><

とりあえず, 辞書に"涼宮ハルヒ"がとうろくされていれば

"涼宮ハヒル"に対して"涼宮ハルヒ"を返してくれるようになってたのでOK

ソース 19:29

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;

import net.java.sen.util.CSVParser;

import org.apache.commons.lang.StringUtils;
import org.apache.lucene.search.spell.LevensteinDistance;
import org.apache.lucene.search.spell.StringDistance;

/*
 * @author yshimoji
 */
public class SpellCollector {

	private String[] WORDS;

	private int[] COSTS;

	private StringDistance DIST_ALGO = new LevensteinDistance();

	private float MIN_DIST = (float) 0.50;

	private int MAX_COST = 60000;

	private class Word {
		//単語の生起コスト
		int cost;

		//単語の原形
		String str;

		//スコア
		float score;

		/**
		 * コンストラクタ。
		 */
		public Word() {
			cost = 0;
			str = "";
			score = 0;
		}

		public Word(String str, int cost) {
			this.str = str;
			this.cost = cost;
			this.score = 0;
		}

		public Word(String str, int cost, float score) {
			this.str = str;
			this.cost = cost;
			this.score = score;
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "string=" + this.str + " cost=" + this.cost + " score=" + this.score;
		}
	};

	public Word correct(String str) {
		//初期化
		Word resWord = new Word("", MAX_COST);
		if (StringUtils.isNotBlank(str)) {
			for (int i = 0; i < WORDS.length; i++) {
				String correctString = WORDS[i];
				int correctStringCost = COSTS[i];
				float curDist = DIST_ALGO.getDistance(str, correctString);
				/**
				 * 距離がある距離より近く
				 * コストが最小(確立が最大)の単語を探す
				 * 
				 * if (curDist >= MIN_DIST) {
					if (correctStringCost <= resWord.cost) {
						resWord.str = correctString;
						resWord.cost = correctStringCost;
					}
				}**/

				/**
				 * スコアが最大の単語を探す
				 * 
				float curScore = curDist + (1 / (correctStringCost + 1000) * 1000);
				if (curScore >= resWord.score) {
					resWord.str = correctString;
					resWord.cost = correctStringCost;
					resWord.score = curScore;
				}
				**/

				/**
				 * 距離がある距離より近く
				 * スコアが最大の単語を探す
				 */
				float curScore = curDist + (1 / (correctStringCost + 1000) * 1000);
				if (curScore >= resWord.score && curDist >= MIN_DIST) {
					resWord.str = correctString;
					resWord.cost = correctStringCost;
					resWord.score = curScore;
				}
			}
		}
		return resWord;
	}

	/**
	 * 
	 * コンストラクタ。
	 */
	public SpellCollector() throws Exception {
		this(System.getProperty("sen.home") + "/dic/dic.csv");
	}

	/**
	 * 
	 * コンストラクタ。
	 */
	public SpellCollector(String dicFile) throws Exception {
		//辞書読み込み
		BufferedReader dicStream = new BufferedReader(new InputStreamReader(new FileInputStream(dicFile), "euc-jp"));
		String t;
		ArrayList < Word > wordList = new ArrayList < Word >();

		while ( ( t = dicStream.readLine()) != null) {
			CSVParser parser = new CSVParser(t);
			String[] csv = parser.nextTokens();
			wordList.add(new Word(csv[0], Integer.parseInt(csv[1])));
		}
		dicStream.close();

		WORDS = new String[wordList.size()];
		COSTS = new int[wordList.size()];
		for (int i = 0; i < wordList.size(); i++) {
			WORDS[i] = wordList.get(i).str;
			COSTS[i] = wordList.get(i).cost;
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		try {
			long startTime = System.currentTimeMillis();
			SpellCollector spellCollector = new SpellCollector("C:/project/workspace/spel/dic/dic_090119.csv");
			System.out.println("Intializing end (" + (System.currentTimeMillis() - startTime) + " ms)");

			startTime = System.currentTimeMillis();
			System.out.println(spellCollector.correct("涼宮ハヒル"));
			System.out.println("spell correction end (" + (System.currentTimeMillis() - startTime) + " ms)");

			startTime = System.currentTimeMillis();
			System.out.println(spellCollector.correct("ガンダム"));
			System.out.println("spell correction end (" + (System.currentTimeMillis() - startTime) + " ms)");

			startTime = System.currentTimeMillis();
			System.out.println(spellCollector.correct("ランダム"));
			System.out.println("spell correction end (" + (System.currentTimeMillis() - startTime) + " ms)");
		} catch (Exception e) {
			// TODO: handle exception
			e.printStackTrace();
		}

	}
}