経緯
RSSリーダーを作っているのだが、登録しているサイトが膨大になり、タイトルからある程度、類似した項目を抽出できないかと調査した。
その結果、ジャロ・ウィンクラー距離にたどり着いたので、とりあえず試してみる。
定義
ジャロ・ウィンクラー距離に最初からたどり着いたわけではなく、レーベンシュタイン距離の方が先にたどり着いた。
ちょっと、判定方法が安易だなと思って、もう少し深く調べたら、ジャロ・ウィンクラー距離にたどり着いたので試してみる
wikipedia
全然意味がわからねぇ。。。
調べた感じ、文字列を置換・編集して同じ文字列になる距離を測ることで、一致度を判定しているらしい。
実装
今回の環境
Java11
IntelliJ IDEA 2022.1.1 (Community Edition)
Gradle 5.5
build.gradle
// https://mvnrepository.com/artifact/org.apache.lucene/lucene-spellchecker
implementation group: 'org.apache.lucene', name: 'lucene-spellchecker', version: '3.6.2'
// https://mvnrepository.com/artifact/org.apache.lucene/lucene-analyzers-kuromoji
implementation group: 'org.apache.lucene', name: 'lucene-analyzers-kuromoji', version: '8.11.1'
↑のやつをdependenciesに加えればイケるはず。
サンプル実装
import org.apache.lucene.search.spell.JaroWinklerDistance;
public class Test {
public static void main(String[] args) {
String str1 = "足なんて飾りです。偉い人にはそれが分からんのです。";
String str2 = "胸なんて飾りです。男にはそれが分からんのです。";
JaroWinklerDistance jaro = new JaroWinklerDistance();
System.out.println(jaro.getDistance(str1, str2));
}
}
※実装内容に他意はありません。
予防線張っておかないと、今の御時世、怖いからね！
使い方は簡単で、JaroWinklerDistanceってのを生成して、getDistanceメソッドで比較したい文字列を渡すだけ。
それだけで結果が見える。
ジャロ・ウィンクラー距離のアルゴリズムは、最初の頃は知りたいと思ったけど、ソース見てその気は失せた。
実行結果
0.91768116
かなり似てる判定になってますね。
逆に、ガンダム語録を変えて比較してみると
String str1 = "足なんて飾りです。偉い人にはそれが分からんのです。";
String str2 = "親父にもぶたれたことないのに！";
0.3777778
ふむ。。。
ちゃんと文章を見ているけど、さすがに、意味や背景は考慮してないな。
所感
できれば、意味を考えて距離計算できるといいんだけどなぁ。。。
たしか、ウィキペディアで該当ページまでたどり着けるまで、どれくらいか判定するサービスが会ったような気がする。
それと組み合わせてみると面白そうだと思った。※やる気はない
あと、いろいろ調べてて思ったけど、ベクトル計算が重要だなと思った。
どのアルゴリズムを見ても、ベクトル計算が必須。
いかに数値に置き換えるかが重要だった。
学生諸君は、ちゃんと数学は勉強したほうがいい。
分からなくても、概要は把握した方がいい。
参考サイト
2つの文字列がどれだけ類似しているかを判定するレーベンシュタイン距離とジャロ・ウィンクラー距離(Java編) | ぱーくん plus idea
