スペルミス修正プログラムを作ろう Ver. Java

「第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー」を読んで、面白そうだし、なんだか作れそうな気がした。

処理の概要はこんな感じ。

• 入力されたキーワードに対して、正しいスペルの候補を返す。
• 正しいスペルの候補ははてなキーワードのリストをから探す。

実装の概要はこんな感じ。

• はてなキーワードのリストからN-gram(今回はbi-gram)インデックスを作成する。
• インデックスから正解の候補を探す。
• 見つかった候補のJaroWinkler距離を求めて、距離の近いものを返す。

いろいろ調べてみると Lucene に以下のようなクラスがあった。

• NGramTokenizer
• JaroWinklerDistance
• LevensteinDistance

名前の通りのクラス。素晴らしい素晴らしい。
N-Gram や JaroWinklerDistance や LevensteinDistance は、調べればすぐに出てくるし、naoyaさんの資料にも簡単な説明があるので、ここでの仮説は割愛する。

そんなわけで、実装してみる。

インデックスを作る

まずはインデックスを作るために、はてなキーワードのリストをダウンロードする。
MacなのでCotEditorで開いてみるが、文字化けする。EUC-JPにしても読み込めない。
仕方ないので、 iconv でUTF-8に変換しようとするが失敗する。いきなり躓く。
いろいろ試したけど上手くいかないので、Windowsでダウンロードして、サクラエディタで文字コードを変換した。
ついでにふりがなはいらないので消した。
こんなテキストファイルができた。

山村活性化
蛭子
47都道府県
製本
隷書体
:

このテキストファイルを一行ずつ読み込んで、インデックスを作成する。
たとえば、 Japan と Java がリストにあったとき、インデックスはこんな感じになる。

Ja , [ Java, Japan ]
av , [ Java ]
va , [ Java ]
ap , [ Japan ]
pa , [ Japan ]
an , [ Japan ]

できた！

候補を検索する

Java を インデックスから検索する場合、まず Java を N-gram で分割する。
Ja / av / va に分割される。それぞれをインデックスから検索する。

Ja , [ Java, Java5, Japan ]
av , [ Java, Java5, Maven ]
va , [ Java, Java5, Advanced ]

こんな感じでヒットしたとしたら、検索結果を以下のようにまとめる。
ヒットした語と、その出現回数をセットにする。

Java , 3
Java5 , 3
Japan , 1
Maven , 1
Advanced , 1

候補が見つかった！

編集距離を求める

見つかった候補を全部調べるのは大変なので、出現回数が2回以上のものを対象とする。
というわけで、調べる対象は Java と Java5 になる。

Java  : 1.0
Java5 : 0.96

Luceneの JaroWinklerDistance を使うと、一致していると 1 が返ってくる。
1に近いものが、編集距離が小さい。
これがスペル修正の候補になる。
今回はスペルの正しい語を検索してみた。
「伊藤直哉」で検索すると、以下のような値になる。

[伊藤直也, 伊藤直人] : 0.8833333

というわけで、できた！

コード

というわけで書いてみた。
Luceneを使っているので、ここからダウンロードする。Lucene 2.4.1 を使った。
実行するには以下の JAR が必要になる。

• lucene-analyzers-2.4.1.jar
• lucene-core-2.4.1.jar
• lucene-spellchecker-2.4.1.jar

インデックスは一度作成して、あとはそれを読み込むだけでいいのだが、パースするコードを書くのが面倒だったので毎回作成している。
コメントを含め、いろいろ適当なのはごめんなさい。

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import org.apache.lucene.analysis.Token;
import org.apache.lucene.analysis.Tokenizer;
import org.apache.lucene.analysis.ngram.NGramTokenizer;
import org.apache.lucene.search.spell.JaroWinklerDistance;
import org.apache.lucene.search.spell.StringDistance;

public class SpellCorrect {

  private static final boolean DEBUGABEL = true;
  private static final int MIN_GRAM = 2;
  private static final int MAX_GRAM = 2;
  
  private static final int MIN_APPEARANCE_COUNT= 2;
  
  public static void main(String[] args) {
    
    String searchWord = "Java";
    String path = "input/keywordlist.csv";
    
    // キーワードリストのパスからインデックスを作成する
    Map<String,Set<String>> indexMap = createIndex(path);
    // インデックスから、候補を検索する
    Map<String,Integer> candidateMap = getCandidateMap(searchWord,indexMap);
    // 候補から、距離を求める
    Map<Float,List<String>> distanceMap = getDistanceMap(searchWord, candidateMap);
    
    for(Float distance : distanceMap.keySet()){
      System.out.println( distanceMap.get(distance).toString() + " : " + distance);
    }
  }
  
  // 候補のMapから距離を求める
  public static Map<Float,List<String>> getDistanceMap(String searchWord, Map<String, Integer> candidateMap){
    // 距離をキーとした、距離の値の逆順でソート済みMap
    Map<Float,List<String>> distanceMap = new TreeMap<Float,List<String>>(Collections.reverseOrder());
    // JaroWinklerky距離を使う
    StringDistance stringDistance = new JaroWinklerDistance();

    for(String word : candidateMap.keySet()){
      int count = candidateMap.get(word);
      // 候補が MIN_APPEARANCE_COUNT 以上出現した場合のみ、距離を求める
      if(count >= MIN_APPEARANCE_COUNT){
        if(DEBUGABEL) System.out.println("Word : " + word + "  Count : " + count);
        // 距離を求める
        Float distance = stringDistance.getDistance(searchWord, word);
        // 同じ距離で複数の語がヒットする可能性があるので、Listにヒットした語をいれる
        List<String> wordList = distanceMap.get(distance);
        if(wordList == null){
          wordList = new ArrayList<String>();
        }
        wordList.add(word);
        distanceMap.put(distance, wordList);
      }
    }
    return distanceMap;
  }
  
  // インデックスから、候補を求める
  public static Map<String, Integer> getCandidateMap(String searchWord, Map<String,Set<String>> indexMap) {
    Map<String, Integer> candidateMap = new TreeMap<String, Integer>();
    Tokenizer tokenizer = new NGramTokenizer( new StringReader(searchWord), MIN_GRAM, MAX_GRAM);
    Token token = new Token();
    try {
      // 検索語をN-gramに分割する
      while ((token = tokenizer.next(token)) != null) {
        String key = token.term();
        if(DEBUGABEL) System.out.println(key);
        // インデックスから検索する
        Set<String> wordSet = indexMap.get(key);
        for (String word : wordSet) {
          if(DEBUGABEL) System.out.println("  " + word);
          // 出現回数を数える
          Integer count = candidateMap.get(word);
          if(count == null){
            count = 0;
          }
          count = count + 1;
          // key に候補となるキーワード、value に出現回数をいれる
          candidateMap.put(word, count);
        }
      }
    } catch (IOException e) {
      e.printStackTrace();
    }
    return candidateMap;
  }
  
  // インデックスを作成する
  private static Map<String, Set<String>> createIndex(String path) {
    Map<String, Set<String>> indexMap = new TreeMap<String, Set<String>>();
    BufferedReader br = null;
    try {
      br = new BufferedReader(new FileReader(new File(path)));
      String line = "";
      while ((line = br.readLine()) != null) {
        if (DEBUGABEL) System.out.print(line + " => ");
        // 例えば MIN_GRAM に 1、 MAX_GRAM に 2 を指定すると、uni-gram と bi-gram で分割できる
        Tokenizer tokenizer = new NGramTokenizer( new StringReader(line), MIN_GRAM, MAX_GRAM);
        Token token = new Token();

        while ((token = tokenizer.next(token)) != null) {
          String key = token.term();
          Set<String> wordSet = indexMap.get(key);
          if (wordSet == null) {
            wordSet = new TreeSet<String>();
          }
          wordSet.add(line);
          // N-gramで分割された語と、元の語をいれる
          indexMap.put(key, wordSet);
          
          if (DEBUGABEL) System.out.print(key + " ");
        }
        if (DEBUGABEL) System.out.println();
      }
    } catch (FileNotFoundException e) {
      e.printStackTrace();
    } catch (IOException e) {
      e.printStackTrace();
    } finally{
      try {
        if(br != null){
          br.close();
        }
      } catch (IOException e) {
        e.printStackTrace();
      }
    }
    return indexMap;
  }
}

実行結果はこんな感じ。

[Java] : 1.0
[Java5] : 0.96
[Java3D, JavaCC, JavaEE, JavaFX] : 0.93333334
[Java EE, Java SE, JavaOne, JavaPOS] : 0.9142857
[Javacomm] : 0.9
:

naoyaさんは はてなブックマークから DF を求めて、それを考慮した結果を出していたけど はてなブックマークのデータが僕にはないので、その部分は実装していない。

Eclipse を使っていたが、実行すると OutOfMemoryError が発生した。
仕方ないので、ファイルを右クリックして、実行ダイアログの引数のVM引数に以下の値を指定した。値は適当。

-Xms128m
-Xmx256m

アルゴリズム部分は Lucene を使っているので、大したことはやっていない。
ちなみに Lucene の API はバージョンごとにがらっと変わるみたい。
Webにある情報は Lucene 1.9 ベースのものが多いような気がする。
そのままやろうとすると、メソッドが無くなっていたり、非推奨になっていたりして大変だった。

もうちょっと実用的にするなら、以下のような処理が必要。

• ちゃんとインデックスを作る
• それを使う
• 複数のファイルからインデックス作成

それでもすべて含めて150行以下で、こんなことができるのは楽しい！

日本語のWordNetなんかも公開されているし、こういう自然言語処理的なことが、とてもやりやすくなったと思う。
自分が大学生のころ、いまくらいの情報と知識があったらな、と思わずにいられない。

参考URL

• 第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー

資料が分かりやすかったので、なんとか実装できた。

• NGramTokenizerとEdgeNGramTokenFilter | 関口宏司のLuceneブログ

コードがあって、Tokenizerの使い方がすぐにわかった。

• 2つの文字列間の距離計算の抽象化（スペルチェック）（2.4） | 関口宏司のLuceneブログ

JaroWinklerDistance と LevensteinDistance の違いと使い方が分かりやすかった。

• 検索エンジンを実装 (1)転置インデックス作成 - Yukun's Blog

転置インデックスを作るときに、参考にさせてもらった。ちょっとずつ実装されていく過程が書いてあるので、理解しやすかった。