001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.text.similarity; 018 019/** 020 * A similarity algorithm indicating the length of the longest common subsequence between two strings. 021 * 022 * <p> 023 * The Longest common subsequence algorithm returns the length of the longest subsequence that two strings have in 024 * common. Two strings that are entirely different, return a value of 0, and two strings that return a value 025 * of the commonly shared length implies that the strings are completely the same in value and position. 026 * <i>Note.</i> Generally this algorithm is fairly inefficient, as for length <i>m</i>, <i>n</i> of the input 027 * {@code CharSequence}'s {@code left} and {@code right} respectively, the runtime of the 028 * algorithm is <i>O(m*n)</i>. 029 * </p> 030 * 031 * <p> 032 * As of version 1.10, a more space-efficient of the algorithm is implemented. The new algorithm has linear space 033 * complexity instead of quadratic. However, time complexity is still quadratic in the size of input strings. 034 * </p> 035 * 036 * <p> 037 * The implementation is based on Hirschberg's Longest Commons Substring algorithm (cited below). 038 * </p> 039 * 040 * <p>For further reading see:</p> 041 * <ul> 042 * <li> 043 * Lothaire, M. <i>Applied combinatorics on words</i>. New York: Cambridge U Press, 2005. <b>12-13</b> 044 * </li> 045 * <li> 046 * D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences," CACM, 1975, pp. 341--343. 047 * </li> 048 * </ul> 049 * 050 * @since 1.0 051 */ 052public class LongestCommonSubsequence implements SimilarityScore<Integer> { 053 054 /** 055 * An implementation of "ALG B" from Hirschberg's CACM '71 paper. 056 * Assuming the first input sequence is of size <code>m</code> and the second input sequence is of size 057 * <code>n</code>, this method returns the last row of the dynamic programming (DP) table when calculating 058 * the LCS of the two sequences in <i>O(m*n)</i> time and <i>O(n)</i> space. 059 * The last element of the returned array, is the size of the LCS of the two input sequences. 060 * 061 * @param left first input sequence. 062 * @param right second input sequence. 063 * @return last row of the dynamic-programming (DP) table for calculating the LCS of <code>left</code> and <code>right</code> 064 * @since 1.10.0 065 */ 066 private static int[] algorithmB(final CharSequence left, final CharSequence right) { 067 final int m = left.length(); 068 final int n = right.length(); 069 070 // Creating an array for storing two rows of DP table 071 final int[][] dpRows = new int[2][1 + n]; 072 073 for (int i = 1; i <= m; i++) { 074 // K(0, j) <- K(1, j) [j = 0...n], as per the paper: 075 // Since we have references in Java, we can swap references instead of literal copying. 076 // We could also use a "binary index" using modulus operator, but directly swapping the 077 // two rows helps readability and keeps the code consistent with the algorithm description 078 // in the paper. 079 final int[] temp = dpRows[0]; 080 dpRows[0] = dpRows[1]; 081 dpRows[1] = temp; 082 083 for (int j = 1; j <= n; j++) { 084 if (left.charAt(i - 1) == right.charAt(j - 1)) { 085 dpRows[1][j] = dpRows[0][j - 1] + 1; 086 } else { 087 dpRows[1][j] = Math.max(dpRows[1][j - 1], dpRows[0][j]); 088 } 089 } 090 } 091 092 // LL(j) <- K(1, j) [j=0...n], as per the paper: 093 // We don't need literal copying of the array, we can just return the reference 094 return dpRows[1]; 095 } 096 097 /** 098 * An implementation of "ALG C" from Hirschberg's CACM '71 paper. 099 * Assuming the first input sequence is of size <code>m</code> and the second input sequence is of size 100 * <code>n</code>, this method returns the Longest Common Subsequence (LCS) of the two sequences in 101 * <i>O(m*n)</i> time and <i>O(m+n)</i> space. 102 * 103 * @param left first input sequence. 104 * @param right second input sequence. 105 * @return the LCS of <code>left</code> and <code>right</code> 106 * @since 1.10.0 107 */ 108 private static String algorithmC(final CharSequence left, final CharSequence right) { 109 final int m = left.length(); 110 final int n = right.length(); 111 112 final StringBuilder out = new StringBuilder(); 113 114 if (m == 1) { // Handle trivial cases, as per the paper 115 final char leftCh = left.charAt(0); 116 for (int j = 0; j < n; j++) { 117 if (leftCh == right.charAt(j)) { 118 out.append(leftCh); 119 break; 120 } 121 } 122 } else if (n > 0 && m > 1) { 123 final int mid = m / 2; // Find the middle point 124 125 final CharSequence leftFirstPart = left.subSequence(0, mid); 126 final CharSequence leftSecondPart = left.subSequence(mid, m); 127 128 // Step 3 of the algorithm: two calls to Algorithm B 129 final int[] l1 = algorithmB(leftFirstPart, right); 130 final int[] l2 = algorithmB(reverse(leftSecondPart), reverse(right)); 131 132 // Find k, as per the Step 4 of the algorithm 133 int k = 0; 134 int t = 0; 135 for (int j = 0; j <= n; j++) { 136 final int s = l1[j] + l2[n - j]; 137 if (t < s) { 138 t = s; 139 k = j; 140 } 141 } 142 143 // Step 5: solve simpler problems, recursively 144 out.append(algorithmC(leftFirstPart, right.subSequence(0, k))); 145 out.append(algorithmC(leftSecondPart, right.subSequence(k, n))); 146 } 147 148 return out.toString(); 149 } 150 151 // An auxiliary method for CharSequence reversal 152 private static String reverse(final CharSequence s) { 153 return new StringBuilder(s).reverse().toString(); 154 } 155 156 /** 157 * Calculates the longest common subsequence similarity score of two {@code CharSequence}'s passed as 158 * input. 159 * 160 * <p> 161 * This method implements a more efficient version of LCS algorithm which has quadratic time and 162 * linear space complexity. 163 * </p> 164 * 165 * <p> 166 * This method is based on newly implemented {@link #algorithmB(CharSequence, CharSequence)}. 167 * An evaluation using JMH revealed that this method is almost two times faster than its previous version. 168 * </p> 169 * 170 * @param left first character sequence 171 * @param right second character sequence 172 * @return length of the longest common subsequence of <code>left</code> and <code>right</code> 173 * @throws IllegalArgumentException if either String input {@code null} 174 */ 175 @Override 176 public Integer apply(final CharSequence left, final CharSequence right) { 177 // Quick return for invalid inputs 178 if (left == null || right == null) { 179 throw new IllegalArgumentException("Inputs must not be null"); 180 } 181 // Find lengths of two strings 182 final int leftSz = left.length(); 183 final int rightSz = right.length(); 184 185 // Check if we can avoid calling algorithmB which involves heap space allocation 186 if (leftSz == 0 || rightSz == 0) { 187 return 0; 188 } 189 190 // Check if we can save even more space 191 if (leftSz < rightSz) { 192 return algorithmB(right, left)[leftSz]; 193 } 194 return algorithmB(left, right)[rightSz]; 195 } 196 197 /** 198 * Computes the longest common subsequence between the two {@code CharSequence}'s passed as input. 199 * 200 * <p> 201 * Note, a substring and subsequence are not necessarily the same thing. Indeed, {@code abcxyzqrs} and 202 * {@code xyzghfm} have both the same common substring and subsequence, namely {@code xyz}. However, 203 * {@code axbyczqrs} and {@code abcxyzqtv} have the longest common subsequence {@code xyzq} because a 204 * subsequence need not have adjacent characters. 205 * </p> 206 * 207 * <p> 208 * For reference, we give the definition of a subsequence for the reader: a <i>subsequence</i> is a sequence that 209 * can be derived from another sequence by deleting some elements without changing the order of the remaining 210 * elements. 211 * </p> 212 * 213 * @param left first character sequence 214 * @param right second character sequence 215 * @return the longest common subsequence found 216 * @throws IllegalArgumentException if either String input {@code null} 217 * @deprecated Deprecated as of 1.2 due to a typo in the method name. 218 * Use {@link #longestCommonSubsequence(CharSequence, CharSequence)} instead. 219 * This method will be removed in 2.0. 220 */ 221 @Deprecated 222 public CharSequence logestCommonSubsequence(final CharSequence left, final CharSequence right) { 223 return longestCommonSubsequence(left, right); 224 } 225 226 /** 227 * Computes the longest common subsequence between the two {@code CharSequence}'s passed as 228 * input. 229 * 230 * <p> 231 * This method implements a more efficient version of LCS algorithm which although has quadratic time, it 232 * has linear space complexity. 233 * </p> 234 * 235 * 236 * <p> 237 * Note, a substring and subsequence are not necessarily the same thing. Indeed, {@code abcxyzqrs} and 238 * {@code xyzghfm} have both the same common substring and subsequence, namely {@code xyz}. However, 239 * {@code axbyczqrs} and {@code abcxyzqtv} have the longest common subsequence {@code xyzq} because a 240 * subsequence need not have adjacent characters. 241 * </p> 242 * 243 * <p> 244 * For reference, we give the definition of a subsequence for the reader: a <i>subsequence</i> is a sequence that 245 * can be derived from another sequence by deleting some elements without changing the order of the remaining 246 * elements. 247 * </p> 248 * 249 * @param left first character sequence 250 * @param right second character sequence 251 * @return the longest common subsequence found 252 * @throws IllegalArgumentException if either String input {@code null} 253 * @since 1.2 254 */ 255 public CharSequence longestCommonSubsequence(final CharSequence left, final CharSequence right) { 256 // Quick return 257 if (left == null || right == null) { 258 throw new IllegalArgumentException("Inputs must not be null"); 259 } 260 // Find lengths of two strings 261 final int leftSz = left.length(); 262 final int rightSz = right.length(); 263 264 // Check if we can avoid calling algorithmC which involves heap space allocation 265 if (leftSz == 0 || rightSz == 0) { 266 return ""; 267 } 268 269 // Check if we can save even more space 270 if (leftSz < rightSz) { 271 return algorithmC(right, left); 272 } 273 return algorithmC(left, right); 274 } 275 276 /** 277 * Computes the lcsLengthArray for the sake of doing the actual lcs calculation. This is the 278 * dynamic programming portion of the algorithm, and is the reason for the runtime complexity being 279 * O(m*n), where m=left.length() and n=right.length(). 280 * 281 * @param left first character sequence 282 * @param right second character sequence 283 * @return lcsLengthArray 284 * @deprecated Deprecated as of 1.10. A more efficient implementation for calculating LCS is now available. 285 * Use {@link #longestCommonSubsequence(CharSequence, CharSequence)} instead to directly calculate the LCS. 286 * This method will be removed in 2.0. 287 */ 288 @Deprecated 289 public int[][] longestCommonSubstringLengthArray(final CharSequence left, final CharSequence right) { 290 final int[][] lcsLengthArray = new int[left.length() + 1][right.length() + 1]; 291 for (int i = 0; i < left.length(); i++) { 292 for (int j = 0; j < right.length(); j++) { 293 if (i == 0) { 294 lcsLengthArray[i][j] = 0; 295 } 296 if (j == 0) { 297 lcsLengthArray[i][j] = 0; 298 } 299 if (left.charAt(i) == right.charAt(j)) { 300 lcsLengthArray[i + 1][j + 1] = lcsLengthArray[i][j] + 1; 301 } else { 302 lcsLengthArray[i + 1][j + 1] = Math.max(lcsLengthArray[i + 1][j], lcsLengthArray[i][j + 1]); 303 } 304 } 305 } 306 return lcsLengthArray; 307 } 308 309}