Zenn
☕

Javaでファジーな文字列マッチングを行う(JavaWuzzy)

2024/04/22に公開
Java
tech

ちょっとした間違えを無視して、候補となる単語リストから単語を抽出したくて、ファジーな文字列マッチングができる JavaWuzzy というライブラリを触ってみました。

Pythonにある FuzzyWuzzy を Java で実装したものになっています。

使い方

me.xdrop:fuzzywuzzy を依存関係に追加します。
今回はGradleプロジェクトで試しました。

implementation 'me.xdrop:fuzzywuzzy:1.4.0'

候補となる単語リストからピックアップするのには、FuzzySearchクラスの extractから始まるメソッドを利用します。

extractOne は1番高いスコアのものを返却します。

FuzzySearch.extractOne("cowboys", List.of("Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"));
// -> (string: Dallas Cowboys, score: 90, index: 3)

extractAll は全ての単語のスコアを返します。(スコア0となったものも含め)

FuzzySearch.extractAll("goolge", List.of("google", "bing", "facebook", "linkedin", "twitter", "googleplus", "bingnews", "plexoogl", "xxx"));
// -> [(string: google, score: 83, index: 0), (string: bing, score: 23, index: 1), (string: facebook, score: 29, index: 2), (string: linkedin, score: 29, index: 3), (string: twitter, score: 15, index: 4), (string: googleplus, score: 75, index: 5), (string: bingnews, score: 29, index: 6), (string: plexoogl, score: 43, index: 7), (string: xxx, score: 0, index: 8)]

スコアでカットオフすることもできます。

FuzzySearch.extractAll("goolge", List.of("google", "bing", "facebook", "linkedin", "twitter", "googleplus", "bingnews", "plexoogl", "xxx"), 40);
// -> [(string: google, score: 83, index: 0), (string: googleplus, score: 75, index: 5), (string: plexoogl, score: 43, index: 7)]

extractSorted は extractAll がスコアでソートされるようになったものです。

FuzzySearch.extractSorted("goolge", List.of("google", "bing", "facebook", "linkedin", "twitter", "googleplus", "bingnews", "plexoogl", "xxx"));
// -> [(string: google, score: 83, index: 0), (string: googleplus, score: 75, index: 5), (string: plexoogl, score: 43, index: 7), (string: facebook, score: 29, index: 2), (string: linkedin, score: 29, index: 3), (string: bingnews, score: 29, index: 6), (string: bing, score: 23, index: 1), (string: twitter, score: 15, index: 4), (string: xxx, score: 0, index: 8)]

試してみる

ちょっとした違いでどんな結果になるか、適当なデータ使って試してみます。

候補とする単語は下記です。

List<String> names = List.of(
    "cat", "catalog", "apple", "people", "Google", "Google Map", "Gmail", "Google Meets");

試してみた結果です。

FuzzySearch.extractOne("Google", names);
// -> (string: Google, score: 100, index: 4)

// 大文字小文字は同一視されてる
FuzzySearch.extractOne("google", names);
// -> (string: Google, score: 100, index: 4)

// 全角半角はダメ
FuzzySearch.extractOne("Ｇｏｏｇｌｅ", names);
// -> (string: Google Map, score: 9, index: 5)

// 1文字違いは似たものとして判定
FuzzySearch.extractOne("gogle", names);
// -> (string: Google, score: 91, index: 4)
FuzzySearch.extractOne("gooogle", names);
// -> (string: Google, score: 92, index: 4)
FuzzySearch.extractOne("googke", names);
// -> (string: Google, score: 83, index: 4)
FuzzySearch.extractOne("foofle", names);
// -> (string: Google, score: 67, index: 4)

FuzzySearch.extractSorted("google", names);
// (string: Google, score: 100, index: 4),
// (string: Google Map, score: 90, index: 5),
// (string: Google Meets, score: 90, index: 7),
// (string: people, score: 50, index: 3),
// (string: apple, score: 36, index: 2),
// (string: Gmail, score: 36, index: 6),
// (string: catalog, score: 31, index: 1),
// (string: cat, score: 0, index: 0)

スコアをいくつまで許容するかは悩みますが、、これを使えば1文字違いくらいの違いは、うまく補完できそうです。

Discussion