Moved bigram code into it's own algorithm. Will be used in other metrics.

8 files changed, 101 insertions, 18 deletions

diff --git a/core/source/core/scala/org/hashtree/stringmetric/FilterableAlgorithm.scala b/core/source/core/scala/org/hashtree/stringmetric/FilterableAlgorithm.scala
index f59781d..b58a2c3 100755
--- a/core/source/core/scala/org/hashtree/stringmetric/FilterableAlgorithm.scala
+++ b/core/source/core/scala/org/hashtree/stringmetric/FilterableAlgorithm.scala
@@ -2,5 +2,5 @@ package org.hashtree.stringmetric
 
 /** Marks those which leverage traits of a filterable [[org.hashtree.stringmetric.Algorithm]]. */
 trait FilterableAlgorithm[T, F <: Filter[T]] extends Algorithm[T] {
-	def compute(t: T)(implicit f: F): Option[T]
+	def compute(t: T)(implicit f: F): Option[AnyRef]
 }
\ No newline at end of file
diff --git a/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableAlgorithm.scala b/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableAlgorithm.scala
index 2f6287e..53cb917 100755
--- a/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableAlgorithm.scala
+++ b/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableAlgorithm.scala
@@ -2,5 +2,5 @@ package org.hashtree.stringmetric
 
 /** Marks those which leverage traits of a filterable and configurable [[org.hashtree.stringmetric.Algorithm]]. */
 trait FilterableConfigurableAlgorithm[T, O, F <: Filter[T]] extends Algorithm[T] {
-	def compute(t: T)(o: O)(implicit f: F): Option[T]
+	def compute(t: T)(o: O)(implicit f: F): Option[AnyRef]
 }
\ No newline at end of file
diff --git a/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableStringAlgorithm.scala b/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableStringAlgorithm.scala
index af9af1a..f223fd3 100755
--- a/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableStringAlgorithm.scala
+++ b/core/source/core/scala/org/hashtree/stringmetric/FilterableConfigurableStringAlgorithm.scala
@@ -2,5 +2,5 @@ package org.hashtree.stringmetric
 
 /** Marks those which leverage traits of a string based [[org.hashtree.stringmetric.FilterableConfigurableAlgorithm]]. */
 trait FilterableConfigurableStringAlgorithm[O] extends FilterableConfigurableAlgorithm[String, O, StringFilter] with StringAlgorithm {
-	def compute(charArray: Array[Char])(o: O)(implicit stringFilter: StringFilter): Option[Array[Char]]
+	def compute(charArray: Array[Char])(o: O)(implicit stringFilter: StringFilter): Option[AnyRef]
 }
\ No newline at end of file
diff --git a/core/source/core/scala/org/hashtree/stringmetric/FilterableStringAlgorithm.scala b/core/source/core/scala/org/hashtree/stringmetric/FilterableStringAlgorithm.scala
index f6cff27..ff6827d 100755
--- a/core/source/core/scala/org/hashtree/stringmetric/FilterableStringAlgorithm.scala
+++ b/core/source/core/scala/org/hashtree/stringmetric/FilterableStringAlgorithm.scala
@@ -2,5 +2,5 @@ package org.hashtree.stringmetric
 
 /** Marks those which leverage traits of a string based [[org.hashtree.stringmetric.FilterableAlgorithm]]. */
 trait FilterableStringAlgorithm extends FilterableAlgorithm[String, StringFilter] with StringAlgorithm {
-	def compute(charArray: Array[Char])(implicit stringFilter: StringFilter): Option[Array[Char]]
+	def compute(charArray: Array[Char])(implicit stringFilter: StringFilter): Option[AnyRef]
 }
\ No newline at end of file
diff --git a/core/source/core/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetric.scala b/core/source/core/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetric.scala
index 64447d6..08e0419 100755
--- a/core/source/core/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetric.scala
+++ b/core/source/core/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetric.scala
@@ -10,12 +10,14 @@ object DiceSorensenMetric extends StringMetric with FilterableStringMetric {
 		val ca2 = stringFilter.filter(charArray2)
 
 		if (ca1.length == 0 || ca2.length == 0) None
+		else if (ca1.length < 2 || ca2.length < 2) Some(0d) // Because length is less than that of bigram, it will always be 0.
 		else if (ca1.sameElements(ca2)) Some(1d)
 		else {
-			val b = bigrams(ca1, ca2)
-			val ms = scoreMatches(b)
+			val ca1bg = NGramAlgorithm.compute(ca1)(2).get
+			val ca2bg = NGramAlgorithm.compute(ca2)(2).get
+			val ms = scoreMatches((ca1bg.map(_.mkString), ca2bg.map(_.mkString)))
 
-			Some((2d * ms) / (b._1.length + b._2.length))
+			Some((2d * ms) / (ca1bg.length + ca2bg.length))
 		}
 	}
 
@@ -25,16 +27,5 @@ object DiceSorensenMetric extends StringMetric with FilterableStringMetric {
 			stringFilter.filter(string2.toCharArray)
 		)(new StringFilterDelegate)
 
-	private[this] def bigrams(ct: CompareTuple[Char]): MatchTuple[String] = {
-		@tailrec
-		def set(ca: Array[Char], sa: Array[String]): Array[String] = {
-			if (ca.length <= 1) sa
-			else
-				set(ca.tail, sa :+ "" + ca.head + ca(1))
-		}
-
-		(set(ct._1, Array.empty[String]), set(ct._2, Array.empty[String]))
-	}
-
 	private[this] def scoreMatches(mt: MatchTuple[String]) = mt._1.intersect(mt._2).length
 }
\ No newline at end of file
diff --git a/core/source/core/scala/org/hashtree/stringmetric/similarity/NGramAlgorithm.scala b/core/source/core/scala/org/hashtree/stringmetric/similarity/NGramAlgorithm.scala
new file mode 100755
index 0000000..89a6d68
--- /dev/null
+++ b/core/source/core/scala/org/hashtree/stringmetric/similarity/NGramAlgorithm.scala
@@ -0,0 +1,31 @@
+package org.hashtree.stringmetric.similarity
+
+import org.hashtree.stringmetric.{ FilterableConfigurableStringAlgorithm, StringAlgorithm, StringFilter, StringFilterDelegate }
+import scala.annotation.tailrec
+
+/** An implementation of the N-Gram [[org.hashtree.stringmetric.StringAlgorithm]]. */
+object NGramAlgorithm extends StringAlgorithm with FilterableConfigurableStringAlgorithm[Int] {
+	override def compute(charArray: Array[Char])(n: Int)(implicit stringFilter: StringFilter): Option[Array[Array[Char]]] = {
+		if (n <= 0)
+			throw new IllegalArgumentException("Expected valid n.")
+
+		val ca = stringFilter.filter(charArray)
+
+		if (ca.length == 0) None
+		else
+			Some(sequence(ca, Array.empty[Array[Char]], n))
+	}
+
+	override def compute(string: String)(n: Int)(implicit stringFilter: StringFilter): Option[Array[String]] =
+		compute(stringFilter.filter(string.toCharArray))(n)(new StringFilterDelegate) match {
+			case Some(mp) => Some(mp.map(_.mkString))
+			case None => None
+		}
+
+	@tailrec
+	private[this] def sequence(i: Array[Char], o: Array[Array[Char]], n: Int): Array[Array[Char]] = {
+		if (i.length <= n) o :+ i
+		else
+			sequence(i.tail, o :+ i.take(n), n)
+	}
+}
\ No newline at end of file
diff --git a/core/source/test/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetricSpec.scala b/core/source/test/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetricSpec.scala
index 70d2c25..d121ea0 100755
--- a/core/source/test/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetricSpec.scala
+++ b/core/source/test/scala/org/hashtree/stringmetric/similarity/DiceSorensenMetricSpec.scala
@@ -25,9 +25,17 @@ final class DiceSorensenMetricSpec extends ScalaTest {
 					DiceSorensenMetric.compare("abc", "xyz").get should be (0)
 				}
 			}
+			"invalid arguments" should returns {
+				"Double indicating distance" in {
+					DiceSorensenMetric.compare("n", "naght").get should be (0)
+					DiceSorensenMetric.compare("night", "n").get should be (0)
+				}
+			}
 			"valid arguments" should returns {
 				"Double indicating distance" in {
 					DiceSorensenMetric.compare("night", "nacht").get should be (0.25)
+					DiceSorensenMetric.compare("night", "naght").get should be (0.5)
+					DiceSorensenMetric.compare("context", "contact").get should be (0.5)
 				}
 			}
 		}
diff --git a/core/source/test/scala/org/hashtree/stringmetric/similarity/NGramAlgorithmSpec.scala b/core/source/test/scala/org/hashtree/stringmetric/similarity/NGramAlgorithmSpec.scala
new file mode 100755
index 0000000..f76a01e
--- /dev/null
+++ b/core/source/test/scala/org/hashtree/stringmetric/similarity/NGramAlgorithmSpec.scala
@@ -0,0 +1,53 @@
+package org.hashtree.stringmetric.similarity
+
+import org.hashtree.stringmetric.ScalaTest
+import org.junit.runner.RunWith
+import org.scalatest.junit.JUnitRunner
+
+@RunWith(classOf[JUnitRunner])
+final class NGramAlgorithmSpec extends ScalaTest {
+	"NGramAlgorithm" should provide {
+		"compute method" when passed {
+			"empty argument" should returns {
+				"None" in {
+					NGramAlgorithm.compute("")(1).isDefined should be (false)
+				}
+			}
+			"invalid n argument" should throws {
+				"IllegalArgumentException" in {
+					evaluating {
+						NGramAlgorithm.compute("")(0).isDefined should be (false)
+					} should produce [IllegalArgumentException]
+
+					evaluating {
+						NGramAlgorithm.compute("")(-1).isDefined should be (false)
+					} should produce [IllegalArgumentException]
+				}
+			}
+			"valid argument" should returns {
+				"Array[String]" in {
+					NGramAlgorithm.compute("abcdefghijklmnopqrstuvwxyz")(1).get should equal (
+						Array(
+							"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
+							"s", "t", "u", "v", "w", "x", "y", "z"
+						)
+					)
+
+					NGramAlgorithm.compute("abcdefghijklmnopqrstuvwxyz")(2).get should equal (
+						Array(
+							"ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl", "lm", "mn", "no", "op",
+							"pq", "qr", "rs", "st", "tu", "uv", "vw", "wx", "xy", "yz"
+						)
+					)
+
+					NGramAlgorithm.compute("abcdefghijklmnopqrstuvwxyz")(3).get should equal (
+						Array(
+							"abc", "bcd", "cde", "def", "efg", "fgh", "ghi", "hij", "ijk", "jkl", "klm", "lmn", "mno",
+							"nop", "opq", "pqr", "qrs", "rst", "stu", "tuv", "uvw", "vwx", "wxy", "xyz"
+						)
+					)
+				}
+			}
+		}
+	}
+}
\ No newline at end of file