二つの文章がどこまで似ているか判定したい #Java

はじめに

二つの文章の類似度を判断したい場合があります。
例えば、下記文章はどこまで似ているでしょうか。

"WBC第3戦圧勝、侍ジャパン強い！優勝間違いなし"
"WBC第3戦大勝、侍ジャパン頑張れ！"

Apache Luceneを使って、文章間の類似度を計算してみます。

Apache Lucene(アパッチルシーン)とは

※ 引用元: https://ja.wikipedia.org/wiki/Apache_Lucene

Apacheトップレベルプロジェクトの1つで、Java製のFLOSSの検索ライブラリ
強力な文書インデキシング及び検索機能を提供
スペルチェック、ハイライト、テキスト解析機能を提供

文字列の類似度計算に必要なパッケージ

Luceneのorg.apache.lucene.search.spellパッケージを使用します。

類似度計算と関係するクラス(アルゴリズム)は以下四つあります。

JaroWinklerDistance(ジャロ・ウィンクラー距離)
- 個人の名前など短い文字列の類似度を計算
- Wikipediaからジャロ・ウィンクラー距離とは
  - 文字列の先頭部分（接頭辞）が一致している場合により類似度が高いと判別されるよう、ジャロ距離を変形したものである
LevenshteinDistance(レーベンシュタイン距離)
- Wikipediaからレーベンシュタイン距離とは
- 二つの文字列がどの程度異なっているかを示す距離の一種である
  - 1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される
LuceneLevenshteinDistance(ダメラウ・レーベンシュタイン距離)
- Wikipediaからダメラウ・レーベンシュタイン距離
- 2つの単語間で、一方の単語を他方の単語に変換するのに必要な最小の操作回数である
  - ここで1回の「操作」とは1文字の挿入、削除、置換、あるいは2つの隣り合う文字の交換である
NGramDistance(N-Gramバージョンの編集距離)
- ベースとなるのはGrzegorz Kondrak氏の論文 N-gram similarity and distance

検証環境

OS: AlmaLinux 9
Java: OpenJDK 19
Apache Lucene 9.5.0

Apache Lucene をダウンロード

LuceneのBinaryファイルをダウンロードし、展開します。

wget https://dlcdn.apache.org/lucene/java/9.5.0/lucene-9.5.0.tgz
tar zxvf lucene-9.5.0.tgz

Luceneの各種パッケージ(JARファイル)が、modulesディレクトリ格納されています。

ls -l lucene-9.5.0/modules
合計 26936
-rw-r--r--. 1 root root 1897805  1月 26 00:45 lucene-analysis-common-9.5.0.jar
-rw-r--r--. 1 root root   84188  1月 26 00:46 lucene-analysis-icu-9.5.0.jar
-rw-r--r--. 1 root root 4683998  1月 26 00:46 lucene-analysis-kuromoji-9.5.0.jar
... ...
-rw-r--r--. 1 root root 3702014  1月 26 00:45 lucene-core-9.5.0.jar
-rw-r--r--. 1 root root   63953  1月 26 00:45 lucene-demo-9.5.0.jar
-rw-r--r--. 1 root root  240098  1月 26 00:46 lucene-suggest-9.5.0.jar

文字列の類似度を計算するサンプルコード(Java例)

四つのアルゴリズムを使って、それぞれの文章間類似度を計算し、比較しています。

"WBC第3戦圧勝、侍ジャパン強い！優勝間違いなし"
"WBC第3戦大勝、侍ジャパン頑張れ！"

similarity.java

import org.apache.lucene.search.spell.JaroWinklerDistance;
import org.apache.lucene.search.spell.LevenshteinDistance;
import org.apache.lucene.search.spell.LuceneLevenshteinDistance;
import org.apache.lucene.search.spell.NGramDistance;

public class Similarity {
    public static void main(String[] arg) throws Exception {
        String first = "WBC第3戦圧勝、侍ジャパン強い！優勝間違いなし";
        String second = "WBC第3戦大勝、侍ジャパン頑張れ！";

        // 1に近いほど類似度が高い
        JaroWinklerDistance jwd = new JaroWinklerDistance();
        LevenshteinDistance ld = new LevenshteinDistance();
        LuceneLevenshteinDistance lld = new LuceneLevenshteinDistance();
        NGramDistance ngd = new NGramDistance();

        System.out.println("JaroWinklerDistance=" + jwd.getDistance(first, second));
        System.out.println("LevenshteinDistance=" + ld.getDistance(first, second));
        System.out.println("LuceneLevenshteinDistance=" + lld.getDistance(first, second));
        System.out.println("NGramDistance=" + ngd.getDistance(first, second));
    }
}

実行

環境変数CLASSPATHを設定し、プログラムを実行します。
クラスパスには、類似度計算に必要な二つのパッケージを指定します。

lucene-core-9.5.0.jar
lucene-suggest-9.5.0.jar

export CLASSPATH=~/lucene-9.5.0/modules/lucene-core-9.5.0.jar:~/lucene-9.5.0/modules/lucene-suggest-9.5.0.jar
java similarity.java

結果

類似度に関しては、JaroWinklerDistanceの値が一番高いです(1に近いほど似ている)。
文章の内容や構文によっては、それぞれのアルゴリズムの結果が変わる可能性はあります。

JaroWinklerDistance=0.8402778
LevenshteinDistance=0.5416666
LuceneLevenshteinDistance=0.3888889
NGramDistance=0.5625

おわりに

文章間の類似度を、Apache LuceneのAPIを使って計算してみました。
文章の内容を変えながら、色々なパターンを試したくなりました。

二つの文章がどこまで似ているか判定したい