【Java】 文字列の類似度・レーベンシュタイン距離/ジャロ・ウィンクラー距離 ～ Apache Lucene ～

Javaツール

■ Apache Lucene

 * Apache Lucene (ルーシン) : 全文検索ライブラリ
 * 日本語もサポート

公式サイト

http://lucene.apache.org/core/

■ 用語

レーベンシュタイン距離 / 編集距離 (Levenshtein Distance）

 * 二つの文字列がどの程度異なっているか(逆に言うと、類似度)を示す尺度
例：「kitten」「sitting」 
 0) 「kitten」
 1) 「sitten」（「k」を「s」に置換）
 2) 「sittin」（「e」を「i」に置換）
 3) 「sitting」（「g」を挿入して終了） <= コスト3

ジャロ・ウィンクラー距離 (Jaro-Winkler Distance)

 * レーベンシュタイン距離と同様に、類似度を示す尺度
 * レーベンシュタイン距離より、ミスタイプを検知することが出来る

その他の類似度指標

集合の類似度 
 * ジャッカード係数(Jaccard's Coefficient)
 * ダイス係数(Dice's Coefficient)
 * シンプソン係数(Simpson's Coefficient)
https://media.accel-brain.com/jaccard-dice-simpson/
http://wikiwiki.jp/cattail/?%CE%E0%BB%F7%C5%D9%A4%C8%B5%F7%CE%A5
http://akoide.hatenablog.com/entry/20110215/1297765587
シンプソン係数(Simpson's Coefficient)
http://www.sophia-it.com/content/%E3%82%B7%E3%83%B3%E3%83%97%E3%82%BD%E3%83%B3%E4%BF%82%E6%95%B0
 * コサイン類似度
http://www.cse.kyoto-su.ac.jp/~g0846020/keywords/cosinSimilarity.html
http://mathtrain.jp/cosdistance

■ 設定

[1] Lucene を以下のサイトからダウンロードする（今回は「lucene-6.3.0.zip」）
http://lucene.apache.org/core/
[2] [1]のZIPファイルを解凍し、Jarファイルをインポートする

 * lucene-core-6.3.0.jar
 * lucene-suggest-6.3.0.jar
 * lucene-analyzers-kuromoji-6.3.0.jar
・・・

■ サンプル

import org.apache.lucene.search.spell.JaroWinklerDistance;
import org.apache.lucene.search.spell.LevensteinDistance;

public class Main {

  public static void main(String[] args) {
    LevensteinDistance levensteinDistance = new LevensteinDistance();
    JaroWinklerDistance jaroWinklerDistance = new JaroWinklerDistance();
    
    System.out.println("Result1-1 : " + levensteinDistance.getDistance("けいさん", "けーさん"));
    System.out.println("Result1-2 : " + levensteinDistance.getDistance("とうきょうと", "とーきょうと"));
    System.out.println("Result1-1 : " + jaroWinklerDistance.getDistance("けいさん", "けーさん"));
    System.out.println("Result1-2 : " + jaroWinklerDistance.getDistance("とうきょうと", "とーきょうと"));
  }
}

出力結果

Result1-1 : 0.75
Result1-2 : 0.8333333
Result1-1 : 0.84999996
Result1-2 : 0.9

参考文献

http://qiita.com/ssaito/items/aae5522618d4296c5178
http://d.hatena.ne.jp/Kazuhira/20150920/1442756517
http://web.plus-idea.net/2012/11/levenshtein-jaro-winkler/
http://djangoapplab.com/40/
https://thinkit.co.jp/free/article/0710/17/1/
http://www.ossnews.jp/oss_info/Apache_Lucene
ジャロ・ウィンクラー距離
http://nkdkccmbr.hateblo.jp/entry/2016/08/18/102727
http://web.plus-idea.net/2012/11/levenshtein-jaro-winkler/

関連記事

【Java】 表記ゆれを考える

http://blogs.yahoo.co.jp/dk521123/36659072.html

動的計画法 ～ フィボナッチ数列 を例にして～

レーベンシュタイン距離を計算するためには、動的計画法を用いる
http://blogs.yahoo.co.jp/dk521123/34536896.html

漢字からカタカナを取得する [2] ～ kuromoji編 ～

http://blogs.yahoo.co.jp/dk521123/36627316.html

漢字からカタカナを取得する [3] ～ lucene-gosen編 ～

http://blogs.yahoo.co.jp/dk521123/36627324.html