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</code>'s <code>left</code> and <code>right</code> respectively, the runtime of the 028 * algorithm is <i>O(m*n)</i>. 029 * </p> 030 * 031 * <p> 032 * This implementation is based on the Longest Commons Substring algorithm 033 * from <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem"> 034 * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem</a>. 035 * </p> 036 * 037 * <p>For further reading see:</p> 038 * 039 * <p>Lothaire, M. <i>Applied combinatorics on words</i>. New York: Cambridge U Press, 2005. <b>12-13</b></p> 040 * 041 * @since 1.0 042 */ 043public class LongestCommonSubsequence implements SimilarityScore<Integer> { 044 045 /** 046 * Calculates longestCommonSubsequence similarity score of two <code>CharSequence</code>'s passed as 047 * input. 048 * 049 * @param left first character sequence 050 * @param right second character sequence 051 * @return longestCommonSubsequenceLength 052 * @throws IllegalArgumentException 053 * if either String input {@code null} 054 */ 055 @Override 056 public Integer apply(final CharSequence left, final CharSequence right) { 057 // Quick return for invalid inputs 058 if (left == null || right == null) { 059 throw new IllegalArgumentException("Inputs must not be null"); 060 } 061 return logestCommonSubsequence(left, right).length(); 062 } 063 064 /** 065 * 066 * Computes the longestCommonSubsequence between the two <code>CharSequence</code>'s passed as 067 * input. 068 * 069 * <p> 070 * Note, a substring and 071 * subsequence are not necessarily the same thing. Indeed, <code>abcxyzqrs</code> and 072 * <code>xyzghfm</code> have both the same common substring and subsequence, namely <code>xyz</code>. However, 073 * <code>axbyczqrs</code> and <code>abcxyzqtv</code> have the longest common subsequence <code>xyzq</code> because a 074 * subsequence need not have adjacent characters. 075 * </p> 076 * 077 * <p> 078 * For reference, we give the definition of a subsequence for the reader: a <i>subsequence</i> is a sequence that 079 * can be derived from another sequence by deleting some elements without changing the order of the remaining 080 * elements. 081 * </p> 082 * 083 * @param left first character sequence 084 * @param right second character sequence 085 * @return lcsLengthArray 086 * @throws IllegalArgumentException 087 * if either String input {@code null} 088 */ 089 public CharSequence logestCommonSubsequence(final CharSequence left, final CharSequence right) { 090 // Quick return 091 if (left == null || right == null) { 092 throw new IllegalArgumentException("Inputs must not be null"); 093 } 094 StringBuilder longestCommonSubstringArray = new StringBuilder(Math.max(left.length(), right.length())); 095 int[][] lcsLengthArray = longestCommonSubstringLengthArray(left, right); 096 int i = left.length() - 1; 097 int j = right.length() - 1; 098 int k = lcsLengthArray[left.length()][right.length()] - 1; 099 while (k >= 0) { 100 if (left.charAt(i) == right.charAt(j)) { 101 longestCommonSubstringArray.append(left.charAt(i)); 102 i = i - 1; 103 j = j - 1; 104 k = k - 1; 105 } else if (lcsLengthArray[i + 1][j] < lcsLengthArray[i][j + 1]) { 106 i = i - 1; 107 } else { 108 j = j - 1; 109 } 110 } 111 return longestCommonSubstringArray.reverse().toString(); 112 } 113 114 /** 115 * 116 * Computes the lcsLengthArray for the sake of doing the actual lcs calculation. This is the 117 * dynamic programming portion of the algorithm, and is the reason for the runtime complexity being 118 * O(m*n), where m=left.length() and n=right.length(). 119 * 120 * @param left first character sequence 121 * @param right second character sequence 122 * @return lcsLengthArray 123 */ 124 public int[][] longestCommonSubstringLengthArray(final CharSequence left, final CharSequence right) { 125 int[][] lcsLengthArray = new int[left.length() + 1][right.length() + 1]; 126 for (int i = 0; i < left.length(); i++) { 127 for (int j = 0; j < right.length(); j++) { 128 if (i == 0) { 129 lcsLengthArray[i][j] = 0; 130 } 131 if (j == 0) { 132 lcsLengthArray[i][j] = 0; 133 } 134 if (left.charAt(i) == right.charAt(j)) { 135 lcsLengthArray[i + 1][j + 1] = lcsLengthArray[i][j] + 1; 136 } else { 137 lcsLengthArray[i + 1][j + 1] = Math.max(lcsLengthArray[i + 1][j], lcsLengthArray[i][j + 1]); 138 } 139 } 140 } 141 return lcsLengthArray; 142 } 143 144}