A Generic Text Comparison Tool Implementation with LCS Approach

Detecting and showing differences of two texts (especially having hundreds or thousands of lines) is a common problem. Using pure java.lang.String class methods may be a solution, but the most important issue for that kind of operations, "performance" will not be satisfactory. We want an efficient solution which may have a view as below: 

Text Difference Tool Example

The problem contains two parts: 

• Detecting differences of two texts: For detecting differences, an efficient dynamic algorithm of LCS (Longest Common Subsequence) used in this solution. This solution has O(text1WordCount * text2WordCount) complexity and coded as "longestCommonSubsequence" method below.
• Visualizing the differences: For visualizing, an HTML tag based approach is used, which marks new words of text2 with green color and old words of text1 with red color. This solution has O(changedWordsCount * (text1WordCount+text2WordCount)) complexity and coded as "markTextDifferences" method below.

Note1: For simplicity, "normalizeText" method is used for removing \n, \t and multiple space characters. 

Note2: This class was created as a Vaadin component. But "longestCommonSubsequence" is pure generic and "markTextDifferences" method is generic on HTML based visual components, so they can also be used with different frameworks.

1. import java.util.ArrayList;
2. import com.vaadin.ui.CustomComponent;
3. import com.vaadin.ui.Label;
4. import com.vaadin.ui.Layout;
5. import com.vaadin.ui.VerticalLayout;
7. /**
8.  * Text comparison component which marks differences of two texts with colors.
9.  *
10.  * @author cb
11.  */
12. public class TextCompareComponent extends CustomComponent {
14.     private Layout mainLayout = new VerticalLayout();
15.     private ArrayList<String> longestCommonSubsequenceList;
16.     private static final String INSERT_COLOR = "#99FFCC";
17.     private static final String DELETE_COLOR = "#CB6D6D";
19.     public TextCompareComponent(String text1, String text2) {
20.        
21.         text1 = normalizeText(text1);
22.         text2 = normalizeText(text2);
24.         this.longestCommonSubsequenceList = longestCommonSubsequence(text1, text2);
25.         String result = markTextDifferences(text1, text2,
26.             longestCommonSubsequenceList, INSERT_COLOR, DELETE_COLOR);
27.        
28.         Label label = new Label(result, Label.CONTENT_XHTML);
29.         mainLayout.addComponent(label);
30.         setCompositionRoot(mainLayout);
31.     }
33.     /**
34.      * Finds a list of longest common subsequences (lcs) of given two texts.
35.      *
36.      * @param text1
37.      * @param text2
38.      * @return - longest common subsequence list
39.      */
40.     private ArrayList<String> longestCommonSubsequence(String text1, String text2) {
42.         String[] text1Words = text1.split(" ");
43.         String[] text2Words = text2.split(" ");
45.         int text1WordCount = text1Words.length;
46.         int text2WordCount = text2Words.length;
47.        
48.         int[][] solutionMatrix = new int[text1WordCount + 1][text2WordCount + 1];
49.        
50.         for (int i = text1WordCount - 1; i >= 0; i--) {
51.             for (int j = text2WordCount - 1; j >= 0; j--) {
52.                 if (text1Words[i].equals(text2Words[j])) {
53.                     solutionMatrix[i][j] = solutionMatrix[i + 1][j + 1] + 1;
54.                 }
55.                 else {
56.                     solutionMatrix[i][j] = Math.max(solutionMatrix[i + 1][j],
57.                         solutionMatrix[i][j + 1]);
58.                 }
59.             }
60.         }
61.        
62.         int i = 0, j = 0;
63.         ArrayList<String> lcsResultList = new ArrayList<String>();
65.         while (i < text1WordCount && j < text2WordCount) {
66.             if (text1Words[i].equals(text2Words[j])) {
67.                 lcsResultList.add(text2Words[j]);
68.                 i++;
69.                 j++;
70.             }
71.             else if (solutionMatrix[i + 1][j] >= solutionMatrix[i][j + 1]) {
72.                 i++;
73.             }
74.             else {
75.                 j++;
76.             }
77.         }
78.         return lcsResultList;
79.     }
80.    
81.     /**
82.      * Normalizes given string by deleting \n, \t and extra spaces.
83.      *
84.      * @param text - initial string
85.      * @return - normalized string
86.      */
87.     private String normalizeText(String text) {
88.        
89.         text = text.trim();
90.         text = text.replace("\n", " ");
91.         text = text.replace("\t", " ");
92.        
93.         while (text.contains("  ")) {
94.             text = text.replace("  ", " ");
95.         }
96.         return text;
97.     }
99.     /**
100.      * Returns colored inserted/deleted text representation of given two texts.
101.      * Uses longestCommonSubsequenceList to determine colored sections.
102.      *
103.      * @param text1
104.      * @param text2
105.      * @param lcsList
106.      * @param insertColor
107.      * @param deleteColor
108.      * @return - colored result text
109.      */
110.     private String markTextDifferences(String text1, String text2,
111.         ArrayList<String> lcsList, String insertColor, String deleteColor) {
113.         StringBuffer stringBuffer = new StringBuffer();
115.         if (text1 != null && lcsList != null) {
117.             String[] text1Words = text1.split(" ");
118.             String[] text2Words = text2.split(" ");
119.             int i = 0, j = 0, word1LastIndex = 0, word2LastIndex = 0;
121.             for (int k = 0; k < lcsList.size(); k++) {
122.                 for (i = word1LastIndex, j = word2LastIndex;
123.                     i < text1Words.length && j < text2Words.length;) {
124.                     if (text1Words[i].equals(lcsList.get(k)) &&
125.                         text2Words[j].equals(lcsList.get(k))) {
126.                         stringBuffer.append("<SPAN>" + lcsList.get(k) + " </SPAN>");
127.                         word1LastIndex = i + 1;
128.                         word2LastIndex = j + 1;
129.                         i = text1Words.length;
130.                         j = text2Words.length;
131.                     }
132.                     else if (!text1Words[i].equals(lcsList.get(k))) {
133.                         for (; i < text1Words.length &&
134.                             !text1Words[i].equals(lcsList.get(k)); i++) {
135.                             stringBuffer.append("<SPAN style='BACKGROUND-COLOR:" +
136.                                 deleteColor + "'>" + text1Words[i] + " </SPAN>");
137.                         }
138.                     } else if (!text2Words[j].equals(lcsList.get(k))) {
139.                         for (; j < text2Words.length &&
140.                             !text2Words[j].equals(lcsList.get(k)), j++) {
141.                             stringBuffer.append("<SPAN style='BACKGROUND-COLOR:" +
142.                                 insertColor + "'>" + text2Words[j] + " </SPAN>");
143.                         }
144.                     }
145.                 }
146.             }
147.             for (; word1LastIndex < text1Words.length; word1LastIndex++) {
148.                 stringBuffer.append("<SPAN style='BACKGROUND-COLOR:" +
149.                     deleteColor + "'>" + text1Words[word1LastIndex] + " </SPAN>");
150.             }
151.             for (; word2LastIndex < text2Words.length; word2LastIndex++) {
152.                 stringBuffer.append("<SPAN style='BACKGROUND-COLOR:" +
153.                     insertColor + "'>" + text2Words[word2LastIndex] + " </SPAN>");
154.             }
155.         }
156.         return stringBuffer.toString();
157.     }
158. }