edu.illinois.cs.cogcomp.core.algorithms

Class LongestCommonSubsequence<T extends Comparable<T>>

java.lang.Object

edu.illinois.cs.cogcomp.core.algorithms.LongestCommonSubsequence<T>

Type Parameters:

T - It is assumed that this implements equals().

public class LongestCommonSubsequence<T extends Comparable<T>>
extends Object

Identify the longest common substrings between two lists.

NOTE: This implements a naive dynamic program and can be improved in terms of memory usage by maintaining only the current row of the dynamic programming table and by using a hash table to store only non-zero values of that row.

Author:

Vivek Srikumar

Jul 7, 2009

Constructor Summary

Constructors

Constructor and Description
LongestCommonSubsequence()

Method Summary

Modifier and Type	Method and Description
protected double	compareTokens(T tok1, T tok2)
static List<IntPair>	getCharacterLCS(String s1, String s2)
static Map<Integer,Integer>	getCharacterLCSMap(String s1, String s2)
List<IntPair>	getLCSMatch(List<T> seq1, List<T> seq2)
List<IntPair>	getLCSMatch(T[] seq1, T[] seq2)
Map<Integer,Integer>	getLCSMatchMap(List<T> seq1, List<T> seq2)
Map<Integer,Integer>	getLCSMatchMap(T[] seq1, T[] seq2)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LongestCommonSubsequence

public LongestCommonSubsequence()

Method Detail

compareTokens

protected double compareTokens(T tok1,
                               T tok2)

getLCSMatch

public List<IntPair> getLCSMatch(List<T> seq1,
                                 List<T> seq2)

getLCSMatch

public List<IntPair> getLCSMatch(T[] seq1,
                                 T[] seq2)

getLCSMatchMap

public Map<Integer,Integer> getLCSMatchMap(List<T> seq1,
                                           List<T> seq2)

getLCSMatchMap

public Map<Integer,Integer> getLCSMatchMap(T[] seq1,
                                           T[] seq2)

getCharacterLCSMap

public static Map<Integer,Integer> getCharacterLCSMap(String s1,
                                                      String s2)

getCharacterLCS

public static List<IntPair> getCharacterLCS(String s1,
                                            String s2)