c# - 如何检查字节数组是否包含另一个数组

Question

我有一个很长的字节数组，例如:

Byte[] bytes = {90, 80, 63, 65, 70 ...};

将近 20-30 Mb(理论上)。有没有一种快速的方法来检查这个数组是否包含另一个数组，例如:

Byte[] small = {63, 80, 75, 77};

首先，我需要按照在小数组中定义的顺序查找字节。其次，我需要在另一个数组中找到数组而不是小数组的任何字节。 感谢大家的进步。

Answer 1

为了提高性能，您需要像 Boyer-Moore string search algorithm 这样的东西.虽然它是为字符串设计的，但它应该同样适用于字节数组，并且比蛮力解决方案的性能好得多。

Wikipedia 文章提供了几种实现，包括一种用 Java 和一种用 C 实现，因此创建 C# 实现应该相当轻松。

---

事实证明，将维基百科文章的 Boyer-Moore 的 Java 实现转换为 C#(并将 char 转换为 byte)确实很轻松。在这里:

public static class BoyerMoore
{
    public static int IndexOf(byte[] haystack, byte[] needle)
    {
        if (needle.Length == 0)
        {
            return 0;
        }

        int[] charTable = MakeCharTable(needle);
        int[] offsetTable = MakeOffsetTable(needle);
        for (int i = needle.Length - 1; i < haystack.Length;)
        {
            int j;
            for (j = needle.Length - 1; needle[j] == haystack[i]; --i, --j)
            {
                if (j == 0)
                {
                    return i;
                }
            }

            i += Math.Max(offsetTable[needle.Length - 1 - j], charTable[haystack[i]]);
        }

        return -1;
    }

    private static int[] MakeCharTable(byte[] needle)
    {
        const int ALPHABET_SIZE = 256;
        int[] table = new int[ALPHABET_SIZE];
        for (int i = 0; i < table.Length; ++i)
        {
            table[i] = needle.Length;
        }

        for (int i = 0; i < needle.Length - 1; ++i)
        {
            table[needle[i]] = needle.Length - 1 - i;
        }

        return table;
    }

    private static int[] MakeOffsetTable(byte[] needle)
    {
        int[] table = new int[needle.Length];
        int lastPrefixPosition = needle.Length;
        for (int i = needle.Length - 1; i >= 0; --i)
        {
            if (IsPrefix(needle, i + 1))
            {
                lastPrefixPosition = i + 1;
            }

            table[needle.Length - 1 - i] = lastPrefixPosition - i + needle.Length - 1;
        }

        for (int i = 0; i < needle.Length - 1; ++i)
        {
            int slen = SuffixLength(needle, i);
            table[slen] = needle.Length - 1 - i + slen;
        }

        return table;
    }

    private static bool IsPrefix(byte[] needle, int p)
    {
        for (int i = p, j = 0; i < needle.Length; ++i, ++j)
        {
            if (needle[i] != needle[j])
            {
                return false;
            }
        }

        return true;
    }

    private static int SuffixLength(byte[] needle, int p)
    {
        int len = 0;
        for (int i = p, j = needle.Length - 1; i >= 0 && needle[i] == needle[j]; --i, --j)
        {
            len += 1;
        }

        return len;
    }
}

该算法在开始时花费线性时间来构建它的表；从那时起，速度快得惊人。