C# .NET の一般的な Boyer–Moore–Horspool アルゴリズム

今年の初めに、アルゴリズムとデータ構造の知識をブラッシュアップすることにしました. Robert Horvick による PluralSight で、これらの 2 つのコース ( 1 、 2 ) を受講しました.
このコースで学んだことを実践するために、さまざまなアルゴリズムとデータ構造の汎用バージョンを作成することにしました.

ジェネリック バージョンとはどういう意味ですか?これらのタイプのコースでは、常に整数または文字列を使用してアルゴリズムを示します.これらのプリミティブ データ型を使用する代わりに、C# の generic type parameters を使用してアルゴリズムとデータ構造を再実装しています.

次に示すのは、T のシーケンスを探す Boyer-Moore-Horspool アルゴリズム検索を実行する汎用メソッド BoyerMooreHorspoolSearchSequence を使用したコンソール アプリケーションです.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var numbers = Enumerable.Range(250, 750).ToArray();

        var index = BoyerMooreHorspoolSearchSequence(numbers.AsEnumerable(), new int[] { 500, 501, 502 });
        Console.WriteLine("Boyer-Moore-Horspool Search Sequence:");
        Console.WriteLine(index);
        Console.ReadKey();
        Console.Clear();
    }

    private static int BoyerMooreHorspoolSearchSequence<T>(IEnumerable<T> list, IEnumerable<T> needle) where T : IComparable
    {
        var items = list.ToArray();
        var itemsLength = items.Length;
        var needleArray = needle.ToArray();
        var needleLength = needleArray.Length;

        int shiftAmountIfMissing = needleLength;
        Dictionary<T, int> badMatchTable = new Dictionary<T, int>();
        for (int i = 0; i < needleLength - 1; i++)
        {
            badMatchTable[needleArray[i]] = needleLength - i - 1;
        }

        int listIndex = 0;
        while (listIndex <= itemsLength - needleLength)
        {
            int matchIndex = needleLength - 1;
            while (true)
            {
                if (items[listIndex + matchIndex].CompareTo(needleArray[matchIndex]) == 0)
                {
                    matchIndex--;
                }
                else
                {
                    break;
                }

                if (matchIndex <= 0)
                {
                    return listIndex;
                }
            }

            if (badMatchTable.TryGetValue(items[listIndex + needleLength - 1], out int amountToShift))
            {
                listIndex += amountToShift;
            }
            else
            {
                listIndex += shiftAmountIfMissing;
            }
        }

        return -1;
    }
}

型が IComparable インターフェイスを実装する必要があるという制約と共にジェネリック型パラメーターを使用することで、作業している正確な型を知らなくても、Boyer–Moore–Horspool アルゴリズムを実行できます.

Boyer–Moore–Horspool アルゴリズムの背後にあるロジックを理解したい場合は、前述のコースをチェックすることをお勧めします.オンラインには他にもたくさんの優れたリソースがあります.

免責事項: このコードは動作しますが、練習のためにのみ開発されています.自己責任で使用するか、並べ替えライブラリを使用してください.改善の余地がある場合は、おそらく、私はすべての耳です〜