BMPartialPatternSearch.cs

Boyer Moore Partial Pattern Search

using System;
using System.Collections.Generic;
public class BMPartialPatternSearch
{
    public int MinimumSearchLength;
    public BMPartialPatternSearch(int min = 5)
    {
        MinimumSearchLength = min;
    }
    public (byte[] partialPattern, int idx) SearchPartial(byte[] pattern, byte[] searchArray)
    {
        var bm   = new BoyerMoore(pattern);
        var len  = pattern.Length;
        var tree = new List<byte[]>();
        if (len < MinimumSearchLength)
            throw new Exception("Search Pattern less than minimum search length.");
        var offset = 0;
        var wl     = MinimumSearchLength;
        do
        {
            var tpat = new byte[wl];
            Array.Copy(pattern, offset, tpat, 0, wl);
            tree.Add(tpat);
            bm.SetPattern(tpat);
            var idx = bm.Search(searchArray);
            if (idx != -1)
                return (tpat, idx);
            if (offset + wl >= len)
            {
                offset = 0;
                wl++;
                continue;
            }
            offset++;
        } while (wl != len + 1);
        return (pattern, -1);
    }
    public List<(byte[] partialPattern, int idx)> SearchPartialFirst(byte[] pattern, byte[] searchArray)
    {
        var bm   = new BoyerMoore(pattern);
        var len  = pattern.Length;
        var lst  = new List<(byte[] partialPattern, int idx)>();
        var tree = new List<byte[]>();
        if (len < MinimumSearchLength)
            throw new Exception("Search Pattern less than minimum search length.");
        var offset = 0;
        var wl     = MinimumSearchLength;
        do
        {
            var tpat = new byte[wl];
            Array.Copy(pattern, offset, tpat, 0, wl);
            tree.Add(tpat);
            bm.SetPattern(tpat);
            var idx = bm.Search(searchArray);
            if (idx != -1)
                lst.Add((tpat, idx));
            if (offset + wl >= len)
            {
                offset = 0;
                wl++;
                continue;
            }
            offset++;
        } while (wl != len + 1);
        return new List<(byte[] partialPattern, int idx)> {(pattern, -1)};
    }
    public List<(byte[] partialPattern, int idx)> SearchPartialAll(byte[] pattern, byte[] searchArray)
    {
        var bm   = new BoyerMoore(pattern);
        var len  = pattern.Length;
        var lst  = new List<(byte[] partialPattern, int idx)>();
        var tree = new List<byte[]>();
        if (len < MinimumSearchLength)
            throw new Exception("Search Pattern less than minimum search length.");
        var offset = 0;
        var wl     = MinimumSearchLength;
        do
        {
            var tpat = new byte[wl];
            Array.Copy(pattern, offset, tpat, 0, wl);
            tree.Add(tpat);
            bm.SetPattern(tpat);
            var idxl = bm.SearchAll(searchArray);
            if (idxl.Item1.Count > 0)
                foreach (var idx in idxl.Item1)
                    lst.Add((tpat, idx));
            if (offset + wl >= len)
            {
                offset = 0;
                wl++;
                continue;
            }
            offset++;
        } while (wl != len + 1);
        return lst;
    }
    public static Dictionary<string, int> SearchPartialSubSet(byte[] searchArray, int startLength, int endLength)
    {
        var pattern = (byte[]) searchArray.Clone();
        var bm      = new BoyerMoore(pattern);
        var pLen    = pattern.Length;
        var lst     = new Dictionary<string, int>();
        var tree    = new List<byte[]>();
        if (pLen < endLength)
            throw new Exception("Search Pattern less than minimum search length.");
        var offset = 0;
        var wl     = startLength;
        do
        {
            var tpat = new byte[wl];
            Array.Copy(pattern, offset, tpat, 0, wl);
            tree.Add(tpat);
            bm.SetPattern(tpat);
            var idxl = bm.SearchAll(searchArray);
            if (idxl.Item1.Count > 1)
            {
                var sapat = tpat.ToHexString();
                if (!lst.ContainsKey(sapat))
                    lst.Add(sapat, idxl.Item1.Count);
            }
            if (offset + wl >= pLen)
            {
                offset = 0;
                wl++;
                if (wl > endLength)
                    break;
                continue;
            }
            offset++;
        } while (wl != pLen + 1);
        return lst;
    }
    public static Dictionary<string, int> SearchPartialSubSet(byte[] searchArray1, byte[] searchArray2, int startLength, int endLength)
    {
        var bm   = new BoyerMoore(searchArray2);
        var pLen = searchArray2.Length;
        var lst  = new Dictionary<string, int>();
        var tree = new List<byte[]>();
        if (pLen < endLength)
            throw new Exception("Search Pattern less than minimum search length.");
        var offset = 0;
        var wl     = startLength;
        do
        {
            var tpat = new byte[wl];
            Array.Copy(searchArray2, offset, tpat, 0, wl);
            tree.Add(tpat);
            bm.SetPattern(tpat);
            var idxl = bm.SearchAll(searchArray1);
            if (idxl.Item1.Count > 1)
            {
                var sapat = tpat.ToHexString();
                if (!lst.ContainsKey(sapat))
                    lst.Add(sapat, idxl.Item1.Count);
            }
            if (offset + wl >= pLen)
            {
                offset = 0;
                wl++;
                if (wl > endLength)
                    break;
                continue;
            }
            offset++;
        } while (wl != pLen + 1);
        return lst;
    }
}