Luceneでレーベンシュタイン距離を求める

先日、Apache Solrを使った「もしかして検索」や単語のサジェストみたいなところを調べていて、「レーベンシュタイン距離」なるものがあることを知りました。

レーベンシュタイン距離 - Wikipedia

このあたりも参考になりました。

編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー

スペルミス修正プログラムを作ろう

また、Luceneで行った場合のエントリも。

2つの文字列間の距離計算の抽象化（スペルチェック）（2.4） | 関口宏司のLuceneブログ

SolrのSuggesterを試してみる

Wikipediaによれば、レーベンシュタイン距離は2つの文字列がどの程度異なっているかを示す距離で（編集距離）、文字列を何回の手順でもう片方の文字列とするように変形できるか、という感じみたいです。

同じく、Wikipediaのまんまですが、「kitten」を「sitting」と変形するには

kitten
sitten （“k”を“s”に置換）
sittin （“e”を“i”に置換）
sitting （“g”を挿入して終了）

なので、この2単語間のレーベンシュタイン距離は3なのだとか…。

で、Luceneでもこの編集距離を求めることができるらしいのですが、範囲は0.0〜1.0になるそうです。

Luceneでレーベンシュタイン距離を求めるためのクラス

Luceneでレーベンシュタイン距離を求めるためのモジュールとして、「suggest」を使用します。スペルチェック、もしかして機能の一部として提供されています、と。

この機能を表すインターフェースが、「org.apache.lucene.search.spell.StringDistance」となり、floatを返すgetDistance(String, String)メソッドを実装する必要があります。

このStringDistanceの実装クラスは、Lucene 5.3.0では以下の4つが提供されています。

LevensteinDistance
LuceneLevenshteinDistance
JaroWinklerDistance
NGramDistance

すべて「org.apache.lucene.search.spell」パッケージです。

ところで、LevensteinDistanceクラスとLuceneLevenshteinDistanceクラスは、どうしてLevensteinとLevenshteinになっているんでしょう…（hの有無）。

LevensteinDistanceクラスは、コメントを見ると「org.apache.commons.lang.StringUtils#getLevenshteinDistance」を参考に実装されたクラスみたいです。
LuceneLevenshteinDistanceクラスは、Unicodeをフルサポートしている模様（サロゲートペアも考慮してそう）。

JaroWinklerDistanceクラスは、こちらを実装したものみたいです。もうわかりませんけど…。
Jaro–Winkler distance - Wikipedia

NGramDistanceは、こちらが元になっているNGramベースのもののようです。
http://www.cs.ualberta.ca/~kondrak/papers/spire05.pdf

で、説明を見ても正直よくわからないので、動かして結果を見てみましょう。

準備

まずはビルドの定義から。
build.sbt

name := "lucene-levenstein-distance"

version := "0.0.1-SNAPSHOT"

scalaVersion := "2.11.7"

organization := "org.littlewings"

scalacOptions ++= Seq("-Xlint", "-deprecation", "-unchecked", "-feature")

updateOptions := updateOptions.value.withCachedResolution(true)

libraryDependencies ++= Seq(
  "org.apache.lucene" % "lucene-suggest" % "5.3.0",
  "org.scalatest" %% "scalatest" % "2.2.5"
)

「lucene-suggest」モジュールが必要です。確認には、ScalaTestを使います。

テストコードを書く

テストコードの雛形から。
src/test/scala/org/littlewings/lucene/LuceneLevensteinDistanceSpec.scala

package org.littlewings.lucene

import org.apache.lucene.search.spell.{NGramDistance, JaroWinklerDistance, LuceneLevenshteinDistance, LevensteinDistance}
import org.scalatest.FunSpec
import org.scalatest.Matchers._

class LuceneLevensteinDistanceSpec extends FunSpec {
  describe("Lucene Levenstein Distance Spec") {
    // ここに、テストを書く！
  }
}

あとは、この中に編集距離を求めるコードをクラスや使い方ごとに書いていきます。

内容は、適当に選んだものとこちらの内容のかけあわせにしました。

2つの文字列間の距離計算の抽象化（スペルチェック）（2.4） | 関口宏司のLuceneブログ

こんな感じにします。

    it("using LevensteinDistance") {
      val levensteinDistance = new レーベンシュタイン距離算出の実装

      levensteinDistance.getDistance("java", "java") should be ???
      levensteinDistance.getDistance("java", "javo") should be ???
      levensteinDistance.getDistance("java", "jajo") should be ???
      levensteinDistance.getDistance("java", "jojo") should be ???
      levensteinDistance.getDistance("java", "jovo") should be ???

      levensteinDistance.getDistance("磯野カツオ", "磯野カツオ") should be ???
      levensteinDistance.getDistance("磯野カツオ", "磯野カツヲ") should be ???
      levensteinDistance.getDistance("磯野カツオ", "磯野カケヲ") should be ???
      levensteinDistance.getDistance("磯野カツオ", "海野カケヲ") should be ???

      levensteinDistance.getDistance("Saturday", "Sunday") should be ???
      levensteinDistance.getDistance("Solr", "Solar") should be ???
      levensteinDistance.getDistance("Apache Solr", "Apache Lucene") should be ???
      levensteinDistance.getDistance("Apache Hadoop", "Apache Hadoop") should be ???
      levensteinDistance.getDistance("ABC", "XYZ") should be ???
    }

LevensteinDistance

LevensteinDistanceクラスを使用した場合、このような結果になります。

    it("using LevensteinDistance") {
      val levensteinDistance = new LevensteinDistance

      levensteinDistance.getDistance("java", "java") should be (1)
      levensteinDistance.getDistance("java", "javo") should be (0.75)
      levensteinDistance.getDistance("java", "jajo") should be (0.5)
      levensteinDistance.getDistance("java", "jojo") should be (0.25)
      levensteinDistance.getDistance("java", "jovo") should be (0.5)

      levensteinDistance.getDistance("磯野カツオ", "磯野カツオ") should be (1)
      levensteinDistance.getDistance("磯野カツオ", "磯野カツヲ") should be <= (0.8F)
      levensteinDistance.getDistance("磯野カツオ", "磯野カケヲ") should be <= (0.6F)
      levensteinDistance.getDistance("磯野カツオ", "海野カケヲ") should be <= (0.4F)

      levensteinDistance.getDistance("Saturday", "Sunday") should be (0.625F)
      levensteinDistance.getDistance("Solr", "Solar") should be <= (0.8F)
      levensteinDistance.getDistance("Apache Solr", "Apache Lucene") should be <= (0.54F)
      levensteinDistance.getDistance("Apache Hadoop", "Apache Hadoop") should be (1)
      levensteinDistance.getDistance("ABC", "XYZ") should be (0)
    }

equalsでムリそうだったものは、<=を使いました。

あと、2つの文字列が完全に一致する場合は1、全然違うものの場合は0になる、と。

LuceneLevenshteinDistance

LuceneLevenshteinDistanceクラスを使った場合は、このような結果に。

    it("using LuceneLevenshteinDistance") {
      val levensteinDistance = new LuceneLevenshteinDistance

      levensteinDistance.getDistance("java", "java") should be (1)
      levensteinDistance.getDistance("java", "javo") should be (0.75F)
      levensteinDistance.getDistance("java", "jajo") should be (0.5F)
      levensteinDistance.getDistance("java", "jojo") should be (0.25F)
      levensteinDistance.getDistance("java", "jovo") should be (0.5F)

      levensteinDistance.getDistance("磯野カツオ", "磯野カツオ") should be (1)
      levensteinDistance.getDistance("磯野カツオ", "磯野カツヲ") should be <= (0.8F)
      levensteinDistance.getDistance("磯野カツオ", "磯野カケヲ") should be <= (0.6F)
      levensteinDistance.getDistance("磯野カツオ", "海野カケヲ") should be <= (0.4F)

      levensteinDistance.getDistance("Saturday", "Sunday") should be (0.5F)
      levensteinDistance.getDistance("Solr", "Solar") should be <= (0.8F)
      levensteinDistance.getDistance("Apache Solr", "Apache Lucene") should be <= (0.54F)
      levensteinDistance.getDistance("Apache Hadoop", "Apache Hadoop") should be (1)
      levensteinDistance.getDistance("ABC", "XYZ") should be (0)
    }

今回の例ではほとんどLevensteinDistanceクラスを使った時と同じなのですが、この部分の結果が異なりました。

      levensteinDistance.getDistance("Saturday", "Sunday") should be (0.5F)

JaroWinklerDistance

JaroWinklerDistanceクラスを使用した場合の結果は、こちら。

    it("using JaroWinklerDistance") {
      val levensteinDistance = new JaroWinklerDistance

      levensteinDistance.getDistance("java", "java") should be (1)
      levensteinDistance.getDistance("java", "javo") should be <= (0.89F)
      levensteinDistance.getDistance("java", "jajo") should be <= (0.67F)
      levensteinDistance.getDistance("java", "jojo") should be (0.5F)
      levensteinDistance.getDistance("java", "jovo") should be <= (0.67F)

      levensteinDistance.getDistance("磯野カツオ", "磯野カツオ") should be (1)
      levensteinDistance.getDistance("磯野カツオ", "磯野カツヲ") should be <= (0.92F)
      levensteinDistance.getDistance("磯野カツオ", "磯野カケヲ") should be <= (0.82F)
      levensteinDistance.getDistance("磯野カツオ", "海野カケヲ") should be <= (0.6F)

      levensteinDistance.getDistance("Saturday", "Sunday") should be (0.7775F)
      levensteinDistance.getDistance("Solr", "Solar") should be <= (0.96F)
      levensteinDistance.getDistance("Apache Solr", "Apache Lucene") should be <= (0.88F)
      levensteinDistance.getDistance("Apache Hadoop", "Apache Hadoop") should be (1)
      levensteinDistance.getDistance("ABC", "XYZ") should be (0)
    }

LevensteinDistanceクラスやLuceneLevenshteinDistanceクラスを使った時よりも、少し大きめの値になります。

また、JaroWinklerDistanceクラスではしきい値を儲けることができるらしくて、設定したしきい値を越える値には少し補正がかかります。結果としては、数字が大きくなることがあるようです。

    it("using JaroWinklerDistance with threshold") {
      val levensteinDistance = new JaroWinklerDistance
      levensteinDistance.setThreshold(0.5F)

      levensteinDistance.getDistance("java", "java") should be (1)
      levensteinDistance.getDistance("java", "javo") should be <= (0.89F)
      levensteinDistance.getDistance("java", "jajo") should be <= (0.74F)
      levensteinDistance.getDistance("java", "jojo") should be (0.55F)
      levensteinDistance.getDistance("java", "jovo") should be <= (0.71F)

      levensteinDistance.getDistance("磯野カツオ", "磯野カツオ") should be (1)
      levensteinDistance.getDistance("磯野カツオ", "磯野カツヲ") should be <= (0.92F)
      levensteinDistance.getDistance("磯野カツオ", "磯野カケヲ") should be <= (0.82F)
      levensteinDistance.getDistance("磯野カツオ", "海野カケヲ") should be <= (0.6F)

      levensteinDistance.getDistance("Saturday", "Sunday") should be (0.7775F)
      levensteinDistance.getDistance("Solr", "Solar") should be <= (0.96F)
      levensteinDistance.getDistance("Apache Solr", "Apache Lucene") should be <= (0.88F)
      levensteinDistance.getDistance("Apache Hadoop", "Apache Hadoop") should be (1)
      levensteinDistance.getDistance("ABC", "XYZ") should be (0)
    }

実装としては、このあたりですね。
https://github.com/apache/lucene-solr/blob/lucene_solr_5_3_0/lucene/suggest/src/java/org/apache/lucene/search/spell/JaroWinklerDistance.java#L103

NGramDistance

最後は、NGramDistanceクラス。

    it("using NGramDistance") {
      val levensteinDistance = new NGramDistance

      levensteinDistance.getDistance("java", "java") should be (1)
      levensteinDistance.getDistance("java", "javo") should be (0.875F)
      levensteinDistance.getDistance("java", "jajo") should be (0.625F)
      levensteinDistance.getDistance("java", "jojo") should be (0.375F)
      levensteinDistance.getDistance("java", "jovo") should be (0.625F)

      levensteinDistance.getDistance("磯野カツオ", "磯野カツオ") should be (1)
      levensteinDistance.getDistance("磯野カツオ", "磯野カツヲ") should be (0.9F)
      levensteinDistance.getDistance("磯野カツオ", "磯野カケヲ") should be (0.7F)
      levensteinDistance.getDistance("磯野カツオ", "海野カケヲ") should be <= (0.4F)

      levensteinDistance.getDistance("Saturday", "Sunday") should be (0.5625F)
      levensteinDistance.getDistance("Solr", "Solar") should be (0.7F)
      levensteinDistance.getDistance("Apache Solr", "Apache Lucene") should be <= (0.577F)
      levensteinDistance.getDistance("Apache Hadoop", "Apache Hadoop") should be (1)
      levensteinDistance.getDistance("ABC", "XYZ") should be (0)
    }

JaroWinklerDistanceクラスを使った場合とまではいきませんが、こちらもLevensteinDistanceクラスやLuceneLevenshteinDistanceクラスを使った時よりも、少し大きめの値になります。

また、コンストラクタでN-GramのNの部分を決定することができます。デフォルトはBi-Gram（2）です。

ここでは、Tri-Gram（3）でやってみます。

    it("using NGramDistance Tri-Gram") {
      val levensteinDistance = new NGramDistance(3)

      levensteinDistance.getDistance("java", "java") should be (1)
      levensteinDistance.getDistance("java", "javo") should be <= (0.92F)
      levensteinDistance.getDistance("java", "jajo") should be (0.75F)
      levensteinDistance.getDistance("java", "jojo") should be <= (0.46F)
      levensteinDistance.getDistance("java", "jovo") should be (0.625F)

      levensteinDistance.getDistance("磯野カツオ", "磯野カツオ") should be (1)
      levensteinDistance.getDistance("磯野カツオ", "磯野カツヲ") should be <= (0.94F)
      levensteinDistance.getDistance("磯野カツオ", "磯野カケヲ") should be (0.8F)
      levensteinDistance.getDistance("磯野カツオ", "海野カケヲ") should be <= (0.44F)

      levensteinDistance.getDistance("Saturday", "Sunday") should be <= (0.53F)
      levensteinDistance.getDistance("Solr", "Solar") should be <= (0.74F)
      levensteinDistance.getDistance("Apache Solr", "Apache Lucene") should be <= (0.62F)
      levensteinDistance.getDistance("Apache Hadoop", "Apache Hadoop") should be (1)
      levensteinDistance.getDistance("ABC", "XYZ") should be (0)
    }

値が大きくなりました。JaroWinklerDistanceクラスの結果を越えましたね。

で

とまあ、Luceneにおけるレーベンシュタイン距離を求めるクラスをいろいろ試してみたわけですが…わかったようなわからないような…。

ちょっといろいろ試して、少しずつわかるようになればいいかなぁ…。

今回作成したソースコードは、こちらに置いています。
https://github.com/kazuhira-r/lucene-examples/tree/master/lucene-levenstein-distance

CLOVER🍀

That was when it all began.