Package com.irurueta.commons

Class EditDistance

  • public class EditDistance
extends java.lang.Object
    Utility class to compute Levenshtein distance (number of substitutions/modifications) between two arrays or strings. Levenshtein distance is an approximate comparison measure that has into account the number of modifications, added or removed elements required to make two collections equal. Thus, this distance measure is appropriate to compare similar but not exactly equal Strings (to take into account typographic errors, etc).

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected static interface  EditDistance.ArrayWrapper<T>
      Interface used as a wrapper for arrays of type T used to generalized efficient access to elements of an array of a generic data type T.
      protected static class  EditDistance.GenericArrayWrapper<T>
      Implementation of ArrayWrapper for generic objects of type T.
      protected static class  EditDistance.StringArrayWrapper
      Specific implementation of ArrayWrapper for Strings.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected EditDistance()
      Constructor.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static <T> int distance​(EditDistance.ArrayWrapper<T> x, EditDistance.ArrayWrapper<T> y)
      Computes Levenshtein distance between two arrays of type T.
      static <T> int distance​(T[] x, T[] y)
      Computes Levenshtein distance between two arrays of objects of type T.
      static int stringDistance​(java.lang.String x, java.lang.String y)
      Computes Levenshtein distance between two Strings.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • EditDistance

        protected EditDistance()
        Constructor.

    • Method Detail

      • stringDistance

        public static int stringDistance​(java.lang.String x,
                                 java.lang.String y)
        Computes Levenshtein distance between two Strings.
        Parameters:
        x - 1st String.
        y - 2nd String.
        Returns:
        Levenshtein distance.

      • distance

        public static <T> int distance​(T[] x,
                               T[] y)
        Computes Levenshtein distance between two arrays of objects of type T. NOTE: this method cannot be used with arrays of primitive types, instead an array of wrappers of primitive objects must be used or this class must be extended to add implementations of ArrayWrappers for all primitive types that must be supported.
        Type Parameters:
        T - type of arrays.
        Parameters:
        x - 1st array of objects of type T.
        y - 2nd array of objects of type T.
        Returns:
        Levenshtein distance.

      • distance

        private static <T> int distance​(EditDistance.ArrayWrapper<T> x,
                                EditDistance.ArrayWrapper<T> y)
        Computes Levenshtein distance between two arrays of type T. To compute this distance an ArrayWrapper is used to make a more efficient access to primitive datatypes or strings.
        Type Parameters:
        T - type of arrays.
        Parameters:
        x - 1st array of objects of type T.
        y - 2nd array of objects of type T.
        Returns:
        Levenshtein distance.