5
\$\begingroup\$

Please review my generic implementation of the Knuth-Morris-Pratt algorithm. Its modified to search a source of indeterminate length in a memory efficient fashion.

namespace Code
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// A generic implementation of the Knuth-Morris-Pratt algorithm that searches,
    /// in a memory efficient way, over a given <see cref="IEnumerator"/>.
    /// </summary>
    public static class KMP
    {
        /// <summary>
        /// Determines whether the Enumerator contains the specified pattern.
        /// </summary>
        /// <typeparam name="T">The type of an item.</typeparam>
        /// <param name="source">
        ///     The source, the <see cref="IEnumerator"/> must yield 
        ///     objects of <typeparamref name="T"/>.
        /// </param>
        /// <param name="pattern">The pattern.</param>
        /// <param name="equalityComparer">The equality comparer.</param>
        /// <returns>
        ///   <c>true</c> if the source contains the specified pattern;
        ///   otherwise, <c>false</c>.
        /// </returns>
        /// <exception cref="ArgumentNullException">pattern</exception>
        public static bool Contains<T>(
                this IEnumerator source,
                IEnumerable<T> pattern,
                IEqualityComparer<T> equalityComparer = null)
        {
            if (pattern == null)
            {
                throw new ArgumentNullException(nameof(pattern));
            }

            equalityComparer = equalityComparer ?? EqualityComparer<T>.Default;

            return SearchImplementation(pattern, source, equalityComparer).Any();
        }

        /// <summary>
        /// Identifies indices of a pattern string in source.
        /// </summary>
        /// <typeparam name="T">The type of an item.</typeparam>
        /// <param name="patternString">The pattern string.</param>
        /// <param name="source">
        ///     The source, the <see cref="IEnumerator"/> must yield
        ///     objects of <typeparamref name="T"/>.
        /// </param>
        /// <param name="equalityComparer">The equality comparer.</param>
        /// <returns>
        ///     A sequence of indices where the pattern can be found
        ///     in the source.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">
        ///     patternSequence - The pattern must contain 1 or more elements.
        /// </exception>
        private static IEnumerable<long> SearchImplementation<T>(
            IEnumerable<T> patternString,
            IEnumerator source,
            IEqualityComparer<T> equalityComparer)
        {
            // Pre-process the pattern
            var preResult = GetSlide(patternString, equalityComparer);
            var pattern = preResult.Pattern;
            var slide = preResult.Slide;
            var patternLength = pattern.Count;

            if (pattern.Count == 0)
            {
                throw new ArgumentOutOfRangeException(
                    nameof(patternString),
                    "The pattern must contain 1 or more elements.");
            }

            var buffer = new Dictionary<long, T>(patternLength);
            var more = true;

            long i = 0; // index for source
            int j = 0; // index for pattern

            while (more)
            {
                more = FillBuffer(
                        buffer,
                        source, 
                        i,
                        patternLength,
                        out T t);

                if (equalityComparer.Equals(pattern[j], t))
                {
                    j++;
                    i++;
                }

                more = FillBuffer(
                        buffer,
                        source,
                        i,
                        patternLength,
                        out t);

                if (j == patternLength)
                {
                    yield return i - j;
                    j = slide[j - 1];
                }
                else if (more && !equalityComparer.Equals(pattern[j], t))
                {
                    if (j != 0)
                    {
                        j = slide[j - 1];
                    }
                    else
                    {
                        i = i + 1;
                    }
                }
            }
        }

        /// <summary>
        /// Fills the buffer.
        /// </summary>
        /// <remarks>
        ///     The buffer is used so that it is not necessary to hold the
        ///     entire source in memory.
        /// </remarks>
        /// <typeparam name="T">The type of an item.</typeparam>
        /// <param name="buffer">The buffer.</param>
        /// <param name="s">The source enumerator.</param>
        /// <param name="i">The current index.</param>
        /// <param name="patternLength">Length of the pattern.</param>
        /// <param name="value">The value retrieved from the source.</param>
        /// <returns>
        ///     <c>true</c> if there is potentially more data to process; 
        ///     otherwise <c>false</c>.
        /// </returns>
        private static bool FillBuffer<T>(
            IDictionary<long, T> buffer,
            IEnumerator s,
            long i,
            int patternLength,
            out T value)
        {
            bool more = true;
            if (!buffer.TryGetValue(i, out value))
            {
                more = s.MoveNext();
                if (more)
                {
                    value = (T)s.Current;
                    buffer.Remove(i - patternLength);
                    buffer.Add(i, value);
                }
            }

            return more;
        }

        /// <summary>
        /// Gets the offset array which acts as a slide rule for the KMP algorithm.
        /// </summary>
        /// <typeparam name="T">The type of an item.</typeparam>
        /// <param name="pattern">The pattern.</param>
        /// <param name="equalityComparer">The equality comparer.</param>
        /// <returns>A tuple of the offsets and the enumerated pattern.</returns>
        private static (IReadOnlyList<int> Slide, IReadOnlyList<T> Pattern) GetSlide<T>(
                IEnumerable<T> pattern, 
                IEqualityComparer<T> equalityComparer)
        {
            var patternList = pattern.ToList();
            var slide = new int[patternList.Count];

            int length = 0;
            int i = 1;

            while (i < patternList.Count)
            {
                if (equalityComparer.Equals(patternList[i], patternList[length]))
                {
                    length++;
                    slide[i] = length;
                    i++;
                }
                else
                {
                    if (length != 0)
                    {
                        length = slide[length - 1];
                    }
                    else
                    {
                        slide[i] = length;
                        i++;
                    }
                }
            }

            return (slide, patternList);
        }
    }
}

I've used the non-generic IEnumerator for representing the source as it allows a wider breadth of enumerators to represent data, including the TextElementEnumerator. This enables the generic implementation to be used trivially to search Unicode strings with different normalizations, e.g.

namespace Code
{
    using System;
    using System.Collections.Generic;
    using System.Globalization;
    using System.Linq;

    class Program
    {
        static void Main(string[] args)
        {

            var testData = new List<(string Source, string Pattern)>
                {
                    (string.Empty, "x"),
                    ("y", "x"),
                    ("x", "x"),
                    ("yx", "x"),
                    ("xy", "x"),
                    ("aababccba", "abc"),
                    ("1x2x3x4", "x"),
                    ("x1x2x3x4x", "x"),
                    ("1aababcabcd2aababcabcd3aababcabcd4", "aababcabcd"),
                    ("ssstring", "sstring")
                };

            foreach(var d in testData)
            {
                var contains = Ext.Contains(d.Source, d.Pattern);
                Console.WriteLine(
                 $"Source:\"{d.Source}\", Pattern:\"{d.Pattern}\", Contains:{contains}");
            }

            Console.ReadKey();
        }
    }

    public static class Ext
    {
        public static bool Contains(
            this string source,
            string value,
            CultureInfo culture = null,
            StringComparer comparer = null)
        {
            comparer = comparer ?? StringComparer.Ordinal;

            var sourceEnumerator = StringInfo.GetTextElementEnumerator(source);
            var sequenceEnumerator = StringInfo.GetTextElementEnumerator(value);

            var pattern = new List<string>();
            while (sequenceEnumerator.MoveNext())
            {
                pattern.Add((string)sequenceEnumerator.Current);
            }

            return sourceEnumerator.Contains(pattern, comparer);
        }
    }
}

This question was improved following the answer here.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ You may want to fix that typo in KMP.Contains (pattern != null) before an answer comes in. \$\endgroup\$ Jan 16, 2019 at 14:20
  • \$\begingroup\$ @PieterWitvoet, sorry being really dense, I do see what you mean!!! \$\endgroup\$
    – Jodrell
    Jan 16, 2019 at 15:02
  • 1
    \$\begingroup\$ I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Heslacher
    Jan 17, 2019 at 8:00

2 Answers 2

4
\$\begingroup\$

Using an IEnumerator as first argument is quite unexpected, and makes this method more cumbersome to use than it needs to be. I'd stick to IEnumerable<T>.

It looks like StringInfo.GetTextElementEnumerator was an important motivation for this decision, but that's an old method that predates the introduction of generics. Why not write a wrapper method for that instead, one that returns IEnumerable<string>?


A few other points:

  • You can use tuple deconstruction when calling Slide: var (slide, pattern) = GetSlide(patternString, equalityComparer);.
  • It's good to see documentation, but some of it isn't very useful. If parameter documentation is just a repetition of the (already properly descriptive) parameter name then I would leave it out.
  • I'd rename i to sourceIndex and j to patternIndex. Those comments already indicate that those names aren't sufficiently descriptive.
  • The culture parameter in Ext.Contains is not used.
  • TextElementEnumerator has a GetTextElement method, which gives you Current as a string.
\$\endgroup\$
5
\$\begingroup\$

I'm looking at this block of code

while (more)
{
    more = FillBuffer(buffer, source, i, patternLength, out T t);

    if (equalityComparer.Equals(pattern[j], t))
    {
        j++;
        i++;
    }

    more = FillBuffer(buffer, source, i, patternLength, out T t);

    ...
}

I'm not convinced that it is correct...
Based how I read it, in the scenario that your if statement is false, then FillBuffer will return the same result, therefore it is a redundant call.

I would consider changing the code to something like this...

while (more)
{
    more = FillBuffer(buffer, source, i, patternLength, out T t);

    if (equalityComparer.Equals(pattern[j], t))
    {
        j++;
        i++;

        // now inside the if statement
        more = FillBuffer(buffer, source, i, patternLength, out T t);
    }

    ...
}
\$\endgroup\$
2
  • \$\begingroup\$ this makes logical sense to me and, it works in my testing. \$\endgroup\$
    – Jodrell
    Jan 17, 2019 at 7:27
  • \$\begingroup\$ I've updated my question to incorporate these changes. In lieu of a more substantial update in the near future, I'll mark this as the answer. \$\endgroup\$
    – Jodrell
    Jan 17, 2019 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.