edu.northwestern.at.morphadorner.corpuslinguistics.stringsimilarity

## Class LCS

- java.lang.Object
- - edu.northwestern.at.morphadorner.corpuslinguistics.stringsimilarity.LCS

- All Implemented Interfaces:
    StringSimilarity

      public class LCS
      extends java.lang.Object
      implements StringSimilarity

  Implementation of the Longest Common Subsequence algorithm.

  That is, given two strings A and B, this program will find the longest sequence of letters that are common and ordered in A and B.

  There are only two reasons you are reading this:

  - you don't care what the algorithm is but you need a piece of code to do it
  - you're trying to understand the algorithm, and a piece of code might help

  In either case, you should either read an entire chapter of an algorithms textbook on the subject of dynamic programming, or you should consult a webpage that describes this particular algorithm. It is important, for example, that we use arrays of size |A|+1 x |B|+1.

  This code is provided AS-IS. You may use this code in any way you see fit, EXCEPT as the answer to a homework problem or as part of a term project in which you were expected to arrive at this code yourself.

  Copyright (C) 2005 Neil Jones.

  Similarity computation added by Phiip R. Burns. 2007/10/24.

- - ### Constructor Summary

    Constructors
    Constructor and Description
    `LCS()` Create LCS instance.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `static java.lang.String` | `LCSAlgorithm(java.lang.String a, java.lang.String b)`
    `static double` | `lcsSimilarity(java.lang.String s1, java.lang.String s2)` Compute similarity of two strings using longest common subsequence.
    `double` | `similarity(java.lang.String s1, java.lang.String s2)` Compute similarity of two strings using longest common subsequence.

    - ### Methods inherited from class java.lang.Object

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

- - ### Constructor Detail

    - #### LCS

          public LCS()

      Create LCS instance.

  - ### Method Detail

    - #### LCSAlgorithm

          public static java.lang.String LCSAlgorithm(java.lang.String a,
                                      java.lang.String b)

    - #### lcsSimilarity

          public static double lcsSimilarity(java.lang.String s1,
                             java.lang.String s2)

      Compute similarity of two strings using longest common subsequence.
      Parameters:
        `s1` - First string.
        `s2` - Second string.
      Returns:
        Similarity measure in the range [0,1] .

    - #### similarity

          public double similarity(java.lang.String s1,
                          java.lang.String s2)

      Compute similarity of two strings using longest common subsequence.
      Specified by:
        `similarity` in interface `StringSimilarity`
      Parameters:
        `s1` - First string.
        `s2` - Second string.
      Returns:
        Similarity measure in the range [0,1] .