StringDistance

A fuzzy matching string distance library for Scala and Java that includes Levenshtein distance, Jaro distance, Jaro-Winkler distance, Dice coefficient, N-Gram similarity, Cosine similarity, Jaccard similarity, Longest common subsequence, Hamming distance, and more.

Works with generalized arrays.

For more detailed information, please refer to the API Documentation.

Requires: Java 8+ or Scala 2.11+

---

Contents

1. Add it to your project
2. Using in Scala
3. Using in Scala with implicits
4. Using in Java
5. Using with Arrays
6. Adding your own algorithm
7. Reporting an Issue
8. Contributing
9. License

---

1. Add it to your project ...

Using sbt:

In build.sbt:

libraryDependencies +="com.github.vickumar1981"%%"stringdistance"%"1.2.7"

Using gradle:

In build.gradle:

dependencies {
compile 'com.github.vickumar1981:stringdistance_2.13:1.2.7'
}

Using Maven:

In pom.xml:

<dependency>
<groupId>com.github.vickumar1981</groupId>
<artifactId>stringdistance_2.13</artifactId>
<version>1.2.7</version>
</dependency>

Notes:

• For Scala 2.12, please use the stringdistance_2.12 artifact as a dependency instead.
• For Scala 2.11, please use the stringdistance_2.11 artifact as a dependency instead.

---

2. Scala Usage

Example.scala:

// Scala exampleimportcom.github.vickumar1981.stringdistance.StringDistance._importcom.github.vickumar1981.stringdistance.StringSound._importcom.github.vickumar1981.stringdistance.impl.{ConstantGap, LinearGap}
// Cosine SimilarityvalcosSimilarity:Double=Cosine.score("hello", "chello") // 0.935// Damerau-Levenshtein DistancevaldamerauDist:Int=Damerau.distance("martha", "marhta") // 1valdamerau:Double=Damerau.score("martha", "marhta") // 0.833// Dice CoefficientvaldiceCoefficient:Double=DiceCoefficient.score("martha", "marhta") // 0.4// Hamming DistancevalhammingDist:Int=Hamming.distance("martha", "marhta") // 2valhamming:Double=Hamming.score("martha", "marhta") // 0.667// Jaccard Similarityvaljaccard:Double=Jaccard.score("karolin", "kathrin", 1)
// Jaro and Jaro Winklervaljaro:Double=Jaro.score("martha", "marhta") // 0.944valjaroWinkler:Double=JaroWinkler.score("martha", "marhta", 0.1) // 0.961// Levenshtein DistancevallevenshteinDist:Int=Levenshtein.distance("martha", "marhta") // 2vallevenshtein:Double=Levenshtein.score("martha", "marhta") // 0.667// Longest Common SubsequencevallongestCommonSubSeq:Int=LongestCommonSeq.distance("martha", "marhta") // 5// Needleman WunschvalneedlemanWunsch:Double=NeedlemanWunsch.score("martha", "marhta", ConstantGap()) // 0.667// N-Gram Similarity and DistancevalngramDist:Int=NGram.distance("karolin", "kathrin", 1) // 5valbigramDist:Int=NGram.distance("karolin", "kathrin", 2) // 2valngramSimilarity:Double=NGram.score("karolin", "kathrin", 1) // 0.714valbigramSimilarity:Double=NGram.score("karolin", "kathrin", 2) // 0.333// N-Gram tokens, returns a List[String]valtokens:List[String] =NGram.tokens("martha", 2) // List("ma", "ar", "rt", "th", "ha")// Overlap Similarityvaloverlap:Double=Overlap.score("karolin", "kathrin", 1) // 0.286valoverlapBiGram:Double=Overlap.score("karolin", "kathrin", 2) // 0.667// Smith Waterman SimilaritiesvalsmithWaterman:Double=SmithWaterman.score("martha", "marhta", (LinearGap(gapValue =-1), Integer.MAX_VALUE))
valsmithWatermanGotoh:Double=SmithWatermanGotoh.score("martha", "marhta", ConstantGap())
// Tversky Similarityvaltversky:Double=Tversky.score("karolin", "kathrin", 0.5) // 0.333// Phonetic Similarityvalmetaphone:Boolean=Metaphone.score("merci", "mercy") // truevalsoundex:Boolean=Soundex.score("merci", "mercy") // true

---

3. Scala: Use with Implicits

• To use implicits and extend the String class: import com.github.vickumar1981.stringdistance.StringConverter._

Example.scala

// Scala example using implicitsimportcom.github.vickumar1981.stringdistance.StringConverter._// Scores between two stringsvalcosSimilarity:Double="hello".cosine("chello")
valdamerau:Double="martha".damerau("marhta")
valdiceCoefficient:Double="martha".diceCoefficient("marhta")
valhamming:Double="martha".hamming("marhta")
valjaccard:Double="karolin".jaccard("kathrin")
valjaro:Double="martha".jaro("marhta")
valjaroWinkler:Double="martha".jaroWinkler("marhta")
vallevenshtein:Double="martha".levenshtein("marhta")
valneedlemanWunsch:Double="martha".needlemanWunsch("marhta")
valngramSimilarity:Double="karolin".nGram("kathrin")
valbigramSimilarity:Double="karolin".nGram("kathrin", 2)
valoverlap:Double="karolin".overlap("kathrin")
valoverlapBiGram:Double="karolin".overlap("kathrin", 2)
valsmithWaterman:Double="martha".smithWaterman("marhta")
valsmithWatermanGotoh:Double="martha".smithWatermanGotoh("marhta")
valtversky:Double="karolin".tversky("kathrin", 0.5)
// Distances between two stringsvaldamerauDist:Int="martha".damerauDist("marhta") // 1valhammingDist:Int="martha".hammingDist("marhta")
vallevenshteinDist:Int="martha".levenshteinDist("marhta")
vallongestCommonSeq:Int="martha".longestCommonSeq("marhta")
valngramDist:Int="karolin".nGramDist("kathrin")
valbigramDist:Int="karolin".nGramDist("kathrin", 2)
// N-Gram tokens, returns a List[String]valtokens:List[String] ="martha".tokens(2) // List("ma", "ar", "rt", "th", "ha")// Phonetic similarity of two stringsvalmetaphone:Boolean="merci".metaphone("mercy")
valsoundex:Boolean="merci".soundex("mercy")

---

4. Java Usage

• To use in Java: import com.github.vickumar1981.stringdistance.util.StringDistance

Example.java

// Java exampleimportcom.github.vickumar1981.stringdistance.util.StringDistance;
importcom.github.vickumar1981.stringdistance.util.StringSound;
// Scores between two stringsDoublecosSimilarity = StringDistance.cosine("hello", "chello");
Doubledamerau = StringDistance.damerau("martha", "marhta");
DoublediceCoefficient = StringDistance.diceCoefficient("martha", "marhta");
Doublehamming = StringDistance.hamming("martha", "marhta");
Doublejaccard = StringDistance.jaccard("karolin", "kathrin");
Doublejaro = StringDistance.jaro("martha", "marhta");
DoublejaroWinkler = StringDistance.jaroWinkler("martha", "marhta");
Doublelevenshtein = StringDistance.levenshtein("martha", "marhta");
DoubleneedlemanWunsch = StringDistance.needlemanWunsch("martha", "marhta");
DoublengramSimilarity = StringDistance.nGram("karolin", "kathrin");
DoublebigramSimilarity = StringDistance.nGram("karolin", "kathrin", 2);
Doubleoverlap = StringDistance.overlap("karolin", "kathrin");
DoubleoverlapBiGram = StringDistance.overlap("karolin", "kathrin", 2);
DoublesmithWaterman = StringDistance.smithWaterman("martha", "marhta");
DoublesmithWatermanGotoh = StringDistance.smithWatermanGotoh("martha", "marhta");
Doubletversky = StringDistance.tversky("karolin", "kathrin", 0.5);
// Distances between two stringsIntegerdamerauDist = StringDistance.damerauDist("martha", "marhta");
IntegerhammingDist = StringDistance.hammingDist("martha", "marhta");
IntegerlevenshteinDist = StringDistance.levenshteinDist("martha", "marhta");
IntegerlongestCommonSeq = StringDistance.longestCommonSeq("martha", "marhta");
IntegerngramDist = StringDistance.nGramDist("karolin", "kathrin");
IntegerbigramDist = StringDistance.nGramDist("karolin", "kathrin", 2);
// N-Gram tokens, returns a List<String>List<String> tokens = StringDistance.nGramTokens(2) // List("ma", "ar", "rt", "th", "ha")// Phonetic similarity of two stringsBooleanmetaphone = StringSound.metaphone("merci", "mercy");
Booleansoundex = StringSound.soundex("merci", "mercy");

---

5. Using with Arrays

• You can use the ArrayDistance class just like the StringDistance class, except using a generic array - Array[T] for Scala and T[] for Java.

• Make sure your classes are comparable using == for Scala or .equals for Java

Scala Sample Code:

importcom.github.vickumar1981.stringdistance.ArrayDistance._// Example Levenshtein Distance and ScorevallevenshteinDist=Levenshtein.distance(Array("m", "a", "r", "t", "h", "a"), Array("m", "a", "r", "h", "t", "a")) // 2vallevenshtein=Levenshtein.score(Array("m", "a", "r", "t", "h", "a"), Array("m", "a", "r", "h", "t", "a")) // 0.667

Java Example Code:

• Implement .equals for your class
• Use ArrayDistance with your class

---

6. Adding your own Distance or Scoring Algorithm

1. Create a marker trait that extends StringMetricAlgorithm:

traitCustomAlgorithmextendsStringMetricAlgorithm

2. Create an implementation for that algorithm using an implicit object. Override either the score or the distance method, depending upon whether the object extends DistanceAlgorithm or ScoringAlgorithm.

implicitobjectCustomDistanceextendsDistanceAlgorithm[CustomAlgorithm] {
overridedefdistance(s1: String, s2: String):Int= {
// Implement distance between s1 and s2
}
}
implicitobjectCustomScoreextendsScoringAlgorithm[CustomAlgorithm] {
overridedefscore(s1: String, s2: String):Double= {
// Implement fuzzy score between s1 and s2
}
}

3. Create an object that extends StringMetric using your algorithm as the type parameter, and use the score and distance methods defined in the implicit object.

objectCustomMetricextendsStringMetric[CustomAlgorithm]
valcustomScore:Double=CustomMetric.score("hello", "hello2")
valcustomDist:Int=CustomMetric.distance("hello", "hello2")

---

7. Reporting an Issue

Please report any issues or bugs to the Github issues page.

---

8. Contributing

Please view the contributing guidelines

---

9. License

This project is licensed under the Apache 2 License.