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

## はじめに

二つの文章の類似度を判断したい場合があります。
例えば、下記文章はどこまで似ているでしょうか。
- "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`パッケージを使用します。

https://lucene.apache.org/core/8_0_0/suggest/org/apache/lucene/search/spell/package-summary.html

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

- JaroWinklerDistance(ジャロ・ウィンクラー距離)
    - 個人の名前など短い文字列の類似度を計算
    - Wikipediaから [ジャロ・ウィンクラー距離とは](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A3%E3%83%AD%E3%83%BB%E3%82%A6%E3%82%A3%E3%83%B3%E3%82%AF%E3%83%A9%E3%83%BC%E8%B7%9D%E9%9B%A2)
        - 文字列の先頭部分（接頭辞）が一致している場合により類似度が高いと判別されるよう、ジャロ距離を変形したものである
- LevenshteinDistance(レーベンシュタイン距離)
    - Wikipediaから [レーベンシュタイン距離とは](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)
    - 二つの文字列がどの程度異なっているかを示す距離の一種である
        - 1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される
- LuceneLevenshteinDistance(ダメラウ・レーベンシュタイン距離)
    - Wikipediaから [ダメラウ・レーベンシュタイン距離](https://ja.wikipedia.org/wiki/%E3%83%80%E3%83%A1%E3%83%A9%E3%82%A6%E3%83%BB%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)
    - 2つの単語間で、一方の単語を他方の単語に変換するのに必要な最小の操作回数である
        - ここで1回の「操作」とは1文字の挿入、削除、置換、あるいは2つの隣り合う文字の交換である
- NGramDistance(`N-Gram`バージョンの編集距離)
    - ベースとなるのは`Grzegorz Kondrak`氏の論文 [N-gram similarity and distance](https://link.springer.com/chapter/10.1007/11575832_13)

## 検証環境

- OS: AlmaLinux 9
- Java: OpenJDK 19
- Apache Lucene 9.5.0

## Apache Lucene をダウンロード

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

```shell
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`ディレクトリ格納されています。

```shell
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`
```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

```shell
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に近いほど似ている)。
文章の内容や構文によっては、それぞれのアルゴリズムの結果が変わる可能性はあります。

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

## おわりに

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