Way to check if a byte array contains another byte Array

Question

I'm checking if an byte array contains a another Byte Array with this Code:

private int IndexOf(int index, byte[] AllBytes, byte[] searchByteArray)
{
    for (int i = index; i <= AllBytes.Length - 1 - searchByteArray.Length - 1; i++)
    {

        for (int j = 0; j <= searchByteArray.Length - 1; j++)
        {
            if (AllBytes[i + j] == searchByteArray[j])
            {
                if (j + 1 == searchByteArray.Length)
                    return i;
            }
            else
                break;
        }
    }
    return -1;
}

That works perfect and I get the index of the first byte back.

But the problem is I want to check very large Data.

My "big" Array contains around 900000000 Bytes and my searchArray about 10-20 Bytes. In that way my function is very very slow. Is there a way to make a better performance?

I need the Index of every found match so I do it into a loop:

for (int i = (IndexOf(0, allData, suchBytes) - 1); i < allData.Length; i++)
{
    Debug.WriteLine(i);
    tmpIndex = IndexOf(i, allData, suchBytes);

    if (tmpIndex > -1)
    {

        Byte1_Index.Add(tmpIndex + suchBytes.Length);
        Debug.WriteLine("Counter: " + Byte_Index_Counter);
        i = tmpIndex;
        Byte_Index_Counter++;

    }
}

And it takes a way too much time...

Answer 1

The biggest improvement would be to keep track of potential matches while you are finding if the current match is valid. As Raymond mentioned, in his comment, you could look at KMP or Boyer Moore algorithms but you trade performance for complexity.

Searching though 900000000 Byte will just take some time. There is no magic answer for that but I did a couple of test one with just searching while keeping track of potential matches and one using producer/consumer pattern so I could use the TPL and not block the main threads. Neither one of these was actually faster than the other - in the end it was a wash and both ran anywhere between 7.5 seconds to 8 seconds to run on my machine. The async version was a little better as it didn't just "hang" the system while it ran but I don't know if you can use Task in your solution. I did try to bench your code on my machine but it had index out of bound issues. I fixed them with what I thought would be correct but never got a bench mark because I got tired of waiting for the result.

Here is a example of searching that keeps track of potential matches. There is more optimization that could happen. Like not checking rest of source if no matches found and it is past the length of the search. Also could do a pattern match but I'm just checking the first character.

Word of warning I did not do extensive testing on this

public class ByteSearch
{
    public static IEnumerable<int> Search(byte[] source, byte[] searchByteArray)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source));
        }
        if (searchByteArray == null)
        {
            throw new ArgumentNullException(nameof(searchByteArray));
        }

        var searchLength = searchByteArray.Length;
        var sourceLength = source.Length;
        if (searchLength > sourceLength || searchLength == 0)
        {
            yield break;
        }

        var matches = new List<ByteSearchStore>(searchLength);
        for (var i = 0; i < sourceLength - 1; i++)
        {
            var currentByte = source[i];

            // found a potential match
            if (currentByte == searchByteArray[0])
            {
                if (searchByteArray.Length == 1)
                {
                    yield return i;
                }
                else
                {
                    matches.Add(new ByteSearchStore
                    {
                        StartingIndex = i,
                        Index = -1
                    });
                }
            }

            // check matches
            var count = matches.Count;
            var m = 0;
            while (m < count)
            {
                var potentalMatch = matches[m];
                if (searchByteArray[potentalMatch.Index + 1] == currentByte)
                {
                    potentalMatch.Index++;
                    if (potentalMatch.Index == searchLength - 1)
                    {
                        yield return potentalMatch.StartingIndex;
                        count = 0;
                        matches = new List<ByteSearchStore>(searchLength);
                    }
                    else
                    {
                        m++;
                    }
                }
                else
                {
                    matches.RemoveAt(m);
                    count--;
                }
            }
        }
    }

    private class ByteSearchStore
    {
        public int Index { get; set; }
        public int StartingIndex { get; set; }
    }
}

The program builds up a list of matches each time it hits the first character of the search string then ejects them once they stop matching the search string. We only check the top match to see if it's the search string because it would be the longest and if it matches we wipe the list as we don't want matches inside our current match.

Example how I ran the program

var random = new Random();
var source = Enumerable.Range(0, 900000000).Select(_ => (byte)random.Next(byte.MinValue, byte.MaxValue)).ToArray();
var search = Enumerable.Range(0, 9000).Select(_ => (byte)random.Next(byte.MinValue, byte.MaxValue)).ToArray();
var test = ByteSearch.Search(source, search).ToArray();

If you want the TPL Producer/Consumer one I can post that but again it will be As Is