You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ch...@apache.org on 2016/12/23 14:11:57 UTC
[1/8] [text] TEXT-32: finishing LCS similarity
Repository: commons-text
Updated Branches:
refs/heads/master 4c29a73b0 -> 8bda46197
TEXT-32: finishing LCS similarity
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/46bb20ab
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/46bb20ab
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/46bb20ab
Branch: refs/heads/master
Commit: 46bb20abc4bd2dd2afbf92eb5005158a281f0ba7
Parents: 676a1a7
Author: Rob Tompkins <ch...@gmail.com>
Authored: Thu Dec 22 15:30:49 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Thu Dec 22 15:34:14 2016 -0500
----------------------------------------------------------------------
.../similarity/LongestCommonSubsequence.java | 48 ++++-------
.../LongestCommonSubsequenceTest.java | 89 +++++++++++++++-----
2 files changed, 83 insertions(+), 54 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/46bb20ab/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
index 4e809c2..fd2b5bb 100644
--- a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
+++ b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
@@ -42,12 +42,23 @@ package org.apache.commons.text.similarity;
*/
public class LongestCommonSubsequence implements SimilarityScore<Integer> {
+ /**
+ * Calculates longestCommonSubsequence similarity scoreof two set character sequence passed as
+ * input.
+ *
+ * @param left first character sequence
+ * @param right second character sequence
+ * @return longestCommonSubsequenceLength
+ * @throws IllegalArgumentException
+ * if either String input {@code null}
+ */
+ @Override
public Integer apply(final CharSequence left, final CharSequence right) {
// Quick return for invalid inputs
if (left == null || right == null) {
throw new IllegalArgumentException("Inputs must not be null");
}
- return longestCommonSubstringLengthArray(left,right)[left.length()][right.length()];
+ return logestCommonSubsequence(left, right).length();
}
/**
@@ -70,6 +81,8 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> {
* @param left
* @param right
* @return lcsLengthArray
+ * @throws IllegalArgumentException
+ * if either String input {@code null}
*/
public CharSequence logestCommonSubsequence(final CharSequence left, final CharSequence right) {
// Quick return
@@ -93,7 +106,7 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> {
j = j - 1;
}
}
- return longestCommonSubstringArray;
+ return longestCommonSubstringArray.reverse().toString();
}
/**
@@ -126,35 +139,4 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> {
return lcsLengthArray;
}
-
- public int wikiLcs(CharSequence left, CharSequence right) {
- int m = left.length();
- int n = right.length();
- char[] x = left.toString().toCharArray();
- char[] y = right.toString().toCharArray();
-
- int[][] c = new int[m + 1][n + 1];
-
- for (int i = 0; i <= m; i++) {
- c[i][0] = 0;
- }
-
- for (int j = 0; j <= n; j++) {
- c[0][j] = 0;
- }
-
- for (int i = 1; i <= m; i++) {
- for (int j = 1; j <= n; j++) {
- if (x[i - 1] == y[j - 1]) {
- c[i][j] = c[i - 1][j - 1] + 1;
-
- } else {
- c[i][j] = Math.max(c[i][j - 1], c[i - 1][j]);
- }
- }
- }
-
- return c[m][n];
- }
-
}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/46bb20ab/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
index 9c50412..e852884 100644
--- a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
+++ b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
@@ -1,36 +1,83 @@
package org.apache.commons.text.similarity;
+import org.junit.Before;
import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+
/**
* Created by tompkicr on 12/20/16.
*/
public class LongestCommonSubsequenceTest {
+ private LongestCommonSubsequence subject;
+
+ @Before
+ public void setup() {
+ subject = new LongestCommonSubsequence();
+ }
+
@Test
- public void testLongestCommonSubsequence() {
- LongestCommonSubsequence lcs = new LongestCommonSubsequence();
- CharSequence retVal = lcs.logestCommonSubsequence("abab","abba");
- System.out.println("testLongestCommonSubstring:");
- System.out.println("retVal: " + retVal);
- for (int n=0; n < retVal.length(); n++){
- System.out.print("isISOControl: " + Character.isISOControl(retVal.charAt(n)) + " ");
- System.out.println(retVal.charAt(n));
- }
+ public void testLongestCommonSubsequenceApply() {
+ assertEquals(Integer.valueOf(0), subject.apply("", ""));
+ assertEquals(Integer.valueOf(0), subject.apply("left", ""));
+ assertEquals(Integer.valueOf(0), subject.apply("", "right"));
+ assertEquals(Integer.valueOf(3), subject.apply("frog", "fog"));
+ assertEquals(Integer.valueOf(0), subject.apply("fly", "ant"));
+ assertEquals(Integer.valueOf(1), subject.apply("elephant", "hippo"));
+ assertEquals(Integer.valueOf(8), subject.apply("ABC Corporation", "ABC Corp"));
+ assertEquals(Integer.valueOf(20), subject.apply("D N H Enterprises Inc", "D & H Enterprises, Inc."));
+ assertEquals(Integer.valueOf(24), subject.apply("My Gym Children's Fitness Center", "My Gym. Childrens Fitness"));
+ assertEquals(Integer.valueOf(11), subject.apply("PENNSYLVANIA", "PENNCISYLVNIA"));
+ assertEquals(Integer.valueOf(1), subject.apply("left", "right"));
+ assertEquals(Integer.valueOf(4), subject.apply("leettteft", "ritttght"));
+ assertEquals(Integer.valueOf(15), subject.apply("the same string", "the same string"));
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceApplyNullNull() throws Exception {
+ subject.apply(null, null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceApplyStringNull() throws Exception {
+ subject.apply(" ", null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceApplyNullString() throws Exception {
+ subject.apply(null, "right");
}
@Test
- public void testLcsLengthArray() {
- LongestCommonSubsequence lcs = new LongestCommonSubsequence();
- String left = "abab";
- String right = "abba";
- int[][] retVal = lcs.longestCommonSubstringLengthArray(left, right);
- System.out.println("testLcsLengthArray:");
- for (int i=0; i <= left.length(); i++){
- for (int j=0; j <= right.length(); j++){
- System.out.print(retVal[i][j] + " ");
- }
- System.out.print("\n");
- }
+ public void testLongestCommonSubsequence() {
+ assertEquals("", subject.logestCommonSubsequence("", ""));
+ assertEquals("", subject.logestCommonSubsequence("left", ""));
+ assertEquals("", subject.logestCommonSubsequence("", "right"));
+ assertEquals("fog", subject.logestCommonSubsequence("frog", "fog"));
+ assertEquals("", subject.logestCommonSubsequence("fly", "ant"));
+ assertEquals("h", subject.logestCommonSubsequence("elephant", "hippo"));
+ assertEquals("ABC Corp", subject.logestCommonSubsequence("ABC Corporation", "ABC Corp"));
+ assertEquals("D H Enterprises Inc", subject.logestCommonSubsequence("D N H Enterprises Inc", "D & H Enterprises, Inc."));
+ assertEquals("My Gym Childrens Fitness", subject.logestCommonSubsequence("My Gym Children's Fitness Center", "My Gym. Childrens Fitness"));
+ assertEquals("PENNSYLVNIA", subject.logestCommonSubsequence("PENNSYLVANIA", "PENNCISYLVNIA"));
+ assertEquals("t", subject.logestCommonSubsequence("left", "right"));
+ assertEquals("tttt", subject.logestCommonSubsequence("leettteft", "ritttght"));
+ assertEquals("the same string", subject.logestCommonSubsequence("the same string", "the same string"));
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceNullNull() throws Exception {
+ subject.logestCommonSubsequence(null, null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceStringNull() throws Exception {
+ subject.logestCommonSubsequence(" ", null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceNullString() throws Exception {
+ subject.logestCommonSubsequence(null, "right");
}
}
[5/8] [text] TEXT-32: Adding Bruno's edits to javadoc
Posted by ch...@apache.org.
TEXT-32: Adding Bruno's edits to javadoc
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/f6dd7156
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/f6dd7156
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/f6dd7156
Branch: refs/heads/master
Commit: f6dd7156d9e718f13a05fc3069aa0e5acfa8306f
Parents: b239ae4
Author: Rob Tompkins <ch...@gmail.com>
Authored: Fri Dec 23 08:56:43 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Fri Dec 23 08:56:43 2016 -0500
----------------------------------------------------------------------
.../commons/text/similarity/LongestCommonSubsequence.java | 9 +++++----
1 file changed, 5 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/f6dd7156/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
index fd2b5bb..1f132ef 100644
--- a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
+++ b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
@@ -17,7 +17,7 @@
package org.apache.commons.text.similarity;
/**
- * A similarity algorithm indicating the length of the longest common subsequence between two strings..
+ * A similarity algorithm indicating the length of the longest common subsequence between two strings.
*
* <p>
* The Longest common subsequence algorithm returns the length of the longest subsequence that two strings have in
@@ -25,7 +25,7 @@ package org.apache.commons.text.similarity;
* of the commonly shared length implies that the strings are completely the same in value and position.
* <i>Note.</i> Generally this algorithm is fairly inefficient, as for length <i>m</i>, <i>n</i> of the input
* <code>CharSequence</code>'s <code>left</code> and <code>right</code> respectively, the runtime of the
- * algoirthm is <i>O(m*n)</i>.
+ * algorithm is <i>O(m*n)</i>.
* </p>
*
* <p>
@@ -43,7 +43,7 @@ package org.apache.commons.text.similarity;
public class LongestCommonSubsequence implements SimilarityScore<Integer> {
/**
- * Calculates longestCommonSubsequence similarity scoreof two set character sequence passed as
+ * Calculates longestCommonSubsequence similarity score of two <code>CharSequence</code>'s passed as
* input.
*
* @param left first character sequence
@@ -63,7 +63,8 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> {
/**
*
- * Computes the longestCommonSubsequence between the two strings given.
+ * Computes the longestCommonSubsequence between the two <code>CharSequence</code>'s passed as
+ * input.
*
* <p>
* Note, a substring and
[4/8] [text] TEXT-32: changes.xml addition
Posted by ch...@apache.org.
TEXT-32: changes.xml addition
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/b239ae45
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/b239ae45
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/b239ae45
Branch: refs/heads/master
Commit: b239ae454da408a884d9d662b9109202e3bbe8bd
Parents: 288781e
Author: Rob Tompkins <ch...@gmail.com>
Authored: Thu Dec 22 15:57:33 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Thu Dec 22 15:57:33 2016 -0500
----------------------------------------------------------------------
src/changes/changes.xml | 1 +
1 file changed, 1 insertion(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/b239ae45/src/changes/changes.xml
----------------------------------------------------------------------
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index ec4d183..3502637 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -22,6 +22,7 @@
<body>
<release version="1.0" date="tba" description="tba">
+ <action issue="TEXT-32" type="add" dev="chtompki">Add LCS similarity and distance</action>
<action issue="TEXT-34" type="add" dev="djones">Add class to generate random strings</action>
<action issue="TEXT-35" type="fix" dev="kinow">Unfinished class Javadoc for CosineDistance</action>
<action issue="TEXT-33" type="update" dev="chtompki">Consolidating since tags at 1.0, removing deprecated methods</action>
[3/8] [text] TEXT-32: LCS distance calculation
Posted by ch...@apache.org.
TEXT-32: LCS distance calculation
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/288781ef
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/288781ef
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/288781ef
Branch: refs/heads/master
Commit: 288781eff3725fd55c1ddece95be9f22fddfd324
Parents: 46bb20a
Author: Rob Tompkins <ch...@gmail.com>
Authored: Thu Dec 22 15:55:27 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Thu Dec 22 15:55:27 2016 -0500
----------------------------------------------------------------------
.../LongestCommonSubsequenceDistance.java | 61 ++++++++++++++++++
.../LongestCommonSubsequenceDistanceTest.java | 68 ++++++++++++++++++++
.../LongestCommonSubsequenceTest.java | 26 ++++++--
3 files changed, 150 insertions(+), 5 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/288781ef/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistance.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistance.java b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistance.java
new file mode 100644
index 0000000..bac02de
--- /dev/null
+++ b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistance.java
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.text.similarity;
+
+/**
+ * An edit distance algorithm based on the length of the longest common subsequence between two strings.
+ *
+ * <p>
+ * This code is directly based upon the implementation in {@link LongestCommonSubsequence}.
+ * </p>
+ *
+ * <p>
+ * For reference see: <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem">
+ * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem</a>.
+ * </p>
+ *
+ * <p>For further reading see:</p>
+ *
+ * <p>Lothaire, M. <i>Applied combinatorics on words</i>. New York: Cambridge U Press, 2005. <b>12-13</b></p>
+ *
+ * @since 1.0
+ */
+public class LongestCommonSubsequenceDistance implements EditDistance<Integer> {
+
+ private final LongestCommonSubsequence longestCommonSubsequence = new LongestCommonSubsequence();
+
+ /**
+ * Calculates an edit distance between two <code>CharSequence</code>'s <code>left</code> and
+ * <code>right</code> as: <code>left.length() + right.length() - 2 * LCS(left, right)</code>, where
+ * <code>LCS</code> is given in {@link LongestCommonSubsequence#apply(CharSequence, CharSequence)}.
+ *
+ * @param left first character sequence
+ * @param right second character sequence
+ * @return distance
+ * @throws IllegalArgumentException
+ * if either String input {@code null}
+ */
+ @Override
+ public Integer apply(final CharSequence left, final CharSequence right) {
+ // Quick return for invalid inputs
+ if (left == null || right == null) {
+ throw new IllegalArgumentException("Inputs must not be null");
+ }
+ return left.length() + right.length() - 2 * longestCommonSubsequence.apply(left, right);
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/288781ef/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistanceTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistanceTest.java b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistanceTest.java
new file mode 100644
index 0000000..a107b47
--- /dev/null
+++ b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceDistanceTest.java
@@ -0,0 +1,68 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.text.similarity;
+
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Unit tests for {@link org.apache.commons.text.similarity.LongestCommonSubsequenceDistance}.
+ */
+public class LongestCommonSubsequenceDistanceTest {
+
+ private static LongestCommonSubsequenceDistance subject;
+
+ @BeforeClass
+ public static void setup() {
+ subject = new LongestCommonSubsequenceDistance();
+ }
+
+ @Test
+ public void testGettingLogestCommonSubsequenceDistacne() {
+ assertEquals(Integer.valueOf(0), subject.apply("", ""));
+ assertEquals(Integer.valueOf(4), subject.apply("left", ""));
+ assertEquals(Integer.valueOf(5), subject.apply("", "right"));
+ assertEquals(Integer.valueOf(1), subject.apply("frog", "fog"));
+ assertEquals(Integer.valueOf(6), subject.apply("fly", "ant"));
+ assertEquals(Integer.valueOf(11), subject.apply("elephant", "hippo"));
+ assertEquals(Integer.valueOf(7), subject.apply("ABC Corporation", "ABC Corp"));
+ assertEquals(Integer.valueOf(4), subject.apply("D N H Enterprises Inc", "D & H Enterprises, Inc."));
+ assertEquals(Integer.valueOf(9), subject.apply("My Gym Children's Fitness Center", "My Gym. Childrens Fitness"));
+ assertEquals(Integer.valueOf(3), subject.apply("PENNSYLVANIA", "PENNCISYLVNIA"));
+ assertEquals(Integer.valueOf(7), subject.apply("left", "right"));
+ assertEquals(Integer.valueOf(9), subject.apply("leettteft", "ritttght"));
+ assertEquals(Integer.valueOf(0), subject.apply("the same string", "the same string"));
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceDistanceNullNull() throws Exception {
+ subject.apply(null, null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceDistanceStringNull() throws Exception {
+ subject.apply(" ", null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGettingLongestCommonSubsequenceDistanceNullString() throws Exception {
+ subject.apply(null, "right");
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/288781ef/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
index e852884..c5f43ba 100644
--- a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
+++ b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
@@ -1,19 +1,35 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
package org.apache.commons.text.similarity;
-import org.junit.Before;
+import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
/**
- * Created by tompkicr on 12/20/16.
+ * Unit tests for {@link org.apache.commons.text.similarity.LongestCommonSubsequence}.
*/
public class LongestCommonSubsequenceTest {
- private LongestCommonSubsequence subject;
+ private static LongestCommonSubsequence subject;
- @Before
- public void setup() {
+ @BeforeClass
+ public static void setup() {
subject = new LongestCommonSubsequence();
}
[2/8] [text] TEXT-32: Initial pass as LCS, needs better tests
Posted by ch...@apache.org.
TEXT-32: Initial pass as LCS, needs better tests
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/676a1a70
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/676a1a70
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/676a1a70
Branch: refs/heads/master
Commit: 676a1a70557b60e849bef86ccf565faff49b45e9
Parents: 4c29a73
Author: Rob Tompkins <ch...@gmail.com>
Authored: Tue Dec 20 20:35:40 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Thu Dec 22 15:34:14 2016 -0500
----------------------------------------------------------------------
.../similarity/LongestCommonSubsequence.java | 160 +++++++++++++++++++
.../LongestCommonSubsequenceTest.java | 36 +++++
2 files changed, 196 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/676a1a70/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
new file mode 100644
index 0000000..4e809c2
--- /dev/null
+++ b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
@@ -0,0 +1,160 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.text.similarity;
+
+/**
+ * A similarity algorithm indicating the length of the longest common subsequence between two strings..
+ *
+ * <p>
+ * The Longest common subsequence algorithm returns the length of the longest subsequence that two strings have in
+ * common. Two strings that are entirely different, return a value of 0, and two strings that return a value
+ * of the commonly shared length implies that the strings are completely the same in value and position.
+ * <i>Note.</i> Generally this algorithm is fairly inefficient, as for length <i>m</i>, <i>n</i> of the input
+ * <code>CharSequence</code>'s <code>left</code> and <code>right</code> respectively, the runtime of the
+ * algoirthm is <i>O(m*n)</i>.
+ * </p>
+ *
+ * <p>
+ * This implementation is based on the Longest Commons Substring algorithm
+ * from <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem">
+ * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem</a>.
+ * </p>
+ *
+ * <p>For further reading see:</p>
+ *
+ * <p>Lothaire, M. <i>Applied combinatorics on words</i>. New York: Cambridge U Press, 2005. <b>12-13</b></p>
+ *
+ * @since 1.0
+ */
+public class LongestCommonSubsequence implements SimilarityScore<Integer> {
+
+ public Integer apply(final CharSequence left, final CharSequence right) {
+ // Quick return for invalid inputs
+ if (left == null || right == null) {
+ throw new IllegalArgumentException("Inputs must not be null");
+ }
+ return longestCommonSubstringLengthArray(left,right)[left.length()][right.length()];
+ }
+
+ /**
+ *
+ * Computes the longestCommonSubsequence between the two strings given.
+ *
+ * <p>
+ * Note, a substring and
+ * subsequence are not necessarily the same thing. Indeed, <code>abcxyzqrs</code> and
+ * <code>xyzghfm</code> have both the same common substring and subsequence, namely <code>xyz</code>. However,
+ * <code>axbyczqrs</code> and <code>abcxyzqtv</code> have the longest common subsequence <code>xyzq</code> because a
+ * subsequence need not have adjacent characters.
+ * </p>
+ *
+ * <p>
+ * For reference, we give the definition of a subsequence for the reader: a <i>subsequence</i> is a sequence that can be
+ * derived from another sequence by deleting some elements without changing the order of the remaining elements.
+ * </p>
+ *
+ * @param left
+ * @param right
+ * @return lcsLengthArray
+ */
+ public CharSequence logestCommonSubsequence(final CharSequence left, final CharSequence right) {
+ // Quick return
+ if (left == null || right == null) {
+ throw new IllegalArgumentException("Inputs must not be null");
+ }
+ StringBuffer longestCommonSubstringArray = new StringBuffer(Math.max(left.length(), right.length()));
+ int[][] lcsLengthArray = longestCommonSubstringLengthArray(left, right);
+ int i = left.length() - 1;
+ int j = right.length() - 1;
+ int k = lcsLengthArray[left.length()][right.length()] - 1;
+ while (k >= 0) {
+ if (left.charAt(i) == right.charAt(j)) {
+ longestCommonSubstringArray.append(left.charAt(i));
+ i = i - 1;
+ j = j - 1;
+ k = k - 1;
+ } else if (lcsLengthArray[i + 1][j] < lcsLengthArray[i][j + 1]) {
+ i = i - 1;
+ } else {
+ j = j - 1;
+ }
+ }
+ return longestCommonSubstringArray;
+ }
+
+ /**
+ *
+ * Computes the lcsLengthArray for the sake of doing the actual lcs calculation. This is the
+ * dynamic programming portion of the algorithm, and is the reason for the runtime complexity being
+ * O(m*n), where m=left.length() and n=right.length().
+ *
+ * @param left
+ * @param right
+ * @return lcsLengthArray
+ */
+ public int[][] longestCommonSubstringLengthArray(final CharSequence left, final CharSequence right) {
+ int[][] lcsLengthArray = new int[left.length() + 1][right.length() + 1];
+ for (int i=0; i < left.length(); i++) {
+ for (int j=0; j < right.length(); j++) {
+ if (i == 0) {
+ lcsLengthArray[i][j] = 0;
+ }
+ if (j == 0) {
+ lcsLengthArray[i][j] = 0;
+ }
+ if (left.charAt(i) == right.charAt(j)) {
+ lcsLengthArray[i + 1][j + 1] = lcsLengthArray[i][j] + 1;
+ } else {
+ lcsLengthArray[i + 1][j + 1] = Math.max(lcsLengthArray[i + 1][j], lcsLengthArray[i][j + 1]);
+ }
+ }
+ }
+ return lcsLengthArray;
+ }
+
+
+ public int wikiLcs(CharSequence left, CharSequence right) {
+ int m = left.length();
+ int n = right.length();
+ char[] x = left.toString().toCharArray();
+ char[] y = right.toString().toCharArray();
+
+ int[][] c = new int[m + 1][n + 1];
+
+ for (int i = 0; i <= m; i++) {
+ c[i][0] = 0;
+ }
+
+ for (int j = 0; j <= n; j++) {
+ c[0][j] = 0;
+ }
+
+ for (int i = 1; i <= m; i++) {
+ for (int j = 1; j <= n; j++) {
+ if (x[i - 1] == y[j - 1]) {
+ c[i][j] = c[i - 1][j - 1] + 1;
+
+ } else {
+ c[i][j] = Math.max(c[i][j - 1], c[i - 1][j]);
+ }
+ }
+ }
+
+ return c[m][n];
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/676a1a70/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
new file mode 100644
index 0000000..9c50412
--- /dev/null
+++ b/src/test/java/org/apache/commons/text/similarity/LongestCommonSubsequenceTest.java
@@ -0,0 +1,36 @@
+package org.apache.commons.text.similarity;
+
+import org.junit.Test;
+
+/**
+ * Created by tompkicr on 12/20/16.
+ */
+public class LongestCommonSubsequenceTest {
+
+ @Test
+ public void testLongestCommonSubsequence() {
+ LongestCommonSubsequence lcs = new LongestCommonSubsequence();
+ CharSequence retVal = lcs.logestCommonSubsequence("abab","abba");
+ System.out.println("testLongestCommonSubstring:");
+ System.out.println("retVal: " + retVal);
+ for (int n=0; n < retVal.length(); n++){
+ System.out.print("isISOControl: " + Character.isISOControl(retVal.charAt(n)) + " ");
+ System.out.println(retVal.charAt(n));
+ }
+ }
+
+ @Test
+ public void testLcsLengthArray() {
+ LongestCommonSubsequence lcs = new LongestCommonSubsequence();
+ String left = "abab";
+ String right = "abba";
+ int[][] retVal = lcs.longestCommonSubstringLengthArray(left, right);
+ System.out.println("testLcsLengthArray:");
+ for (int i=0; i <= left.length(); i++){
+ for (int j=0; j <= right.length(); j++){
+ System.out.print(retVal[i][j] + " ");
+ }
+ System.out.print("\n");
+ }
+ }
+}
[8/8] [text] RandomStringBuilder: slight javadoc fix
Posted by ch...@apache.org.
RandomStringBuilder: slight javadoc fix
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/8bda4619
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/8bda4619
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/8bda4619
Branch: refs/heads/master
Commit: 8bda4619742739e75ac2951558d019abc6a6c930
Parents: ecda776
Author: Rob Tompkins <ch...@gmail.com>
Authored: Fri Dec 23 09:08:16 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Fri Dec 23 09:08:16 2016 -0500
----------------------------------------------------------------------
src/main/java/org/apache/commons/text/RandomStringBuilder.java | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/8bda4619/src/main/java/org/apache/commons/text/RandomStringBuilder.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/RandomStringBuilder.java b/src/main/java/org/apache/commons/text/RandomStringBuilder.java
index 8f4253d..38ba974 100644
--- a/src/main/java/org/apache/commons/text/RandomStringBuilder.java
+++ b/src/main/java/org/apache/commons/text/RandomStringBuilder.java
@@ -103,6 +103,8 @@ public class RandomStringBuilder implements Builder<String> {
/**
* <p>
* Constructs a builder with default properties:
+ * </p>
+ *
* <ul>
* <li>Length: {@value #DEFAULT_LENGTH}</li>
* <li>Minimum code point: {@value #DEFAULT_MINIMUM_CODE_POINT}</li>
@@ -110,7 +112,6 @@ public class RandomStringBuilder implements Builder<String> {
* <li>Default source of randomness</li>
* <li>No character filters</li>
* </ul>
- * </p>
*
* @since 1.0
*/
[7/8] [text] TEXT-32: Fixes to javadoc compilation errors
Posted by ch...@apache.org.
TEXT-32: Fixes to javadoc compilation errors
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/ecda7763
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/ecda7763
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/ecda7763
Branch: refs/heads/master
Commit: ecda7763441660a4984f20a8f11a035591e28969
Parents: 4263ce3
Author: Rob Tompkins <ch...@gmail.com>
Authored: Fri Dec 23 09:01:57 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Fri Dec 23 09:01:57 2016 -0500
----------------------------------------------------------------------
.../commons/text/similarity/LongestCommonSubsequence.java | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/ecda7763/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
index 5c063bf..83bf46a 100644
--- a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
+++ b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
@@ -79,8 +79,8 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> {
* derived from another sequence by deleting some elements without changing the order of the remaining elements.
* </p>
*
- * @param left
- * @param right
+ * @param left first character sequence
+ * @param right second character sequence
* @return lcsLengthArray
* @throws IllegalArgumentException
* if either String input {@code null}
@@ -116,8 +116,8 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> {
* dynamic programming portion of the algorithm, and is the reason for the runtime complexity being
* O(m*n), where m=left.length() and n=right.length().
*
- * @param left
- * @param right
+ * @param left first character sequence
+ * @param right second character sequence
* @return lcsLengthArray
*/
public int[][] longestCommonSubstringLengthArray(final CharSequence left, final CharSequence right) {
[6/8] [text] TEXT-32: Switching StringBuffer to StringBuilder
Posted by ch...@apache.org.
TEXT-32: Switching StringBuffer to StringBuilder
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/4263ce38
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/4263ce38
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/4263ce38
Branch: refs/heads/master
Commit: 4263ce38d789622ec107f2d666586c8a8de219aa
Parents: f6dd715
Author: Rob Tompkins <ch...@gmail.com>
Authored: Fri Dec 23 08:57:52 2016 -0500
Committer: Rob Tompkins <ch...@gmail.com>
Committed: Fri Dec 23 08:57:52 2016 -0500
----------------------------------------------------------------------
.../apache/commons/text/similarity/LongestCommonSubsequence.java | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/4263ce38/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
index 1f132ef..5c063bf 100644
--- a/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
+++ b/src/main/java/org/apache/commons/text/similarity/LongestCommonSubsequence.java
@@ -90,7 +90,7 @@ public class LongestCommonSubsequence implements SimilarityScore<Integer> {
if (left == null || right == null) {
throw new IllegalArgumentException("Inputs must not be null");
}
- StringBuffer longestCommonSubstringArray = new StringBuffer(Math.max(left.length(), right.length()));
+ StringBuilder longestCommonSubstringArray = new StringBuilder(Math.max(left.length(), right.length()));
int[][] lcsLengthArray = longestCommonSubstringLengthArray(left, right);
int i = left.length() - 1;
int j = right.length() - 1;