加快字节数组中模式的查找速度

Question

我有一个大约 70MB 的大型二进制文件。在我的程序中，我有一个方法可以根据文件查找byte[]数组模式，以查看它们是否存在于文件中。我有大约 1-1000 万个模式要针对该文件运行。我看到的选项如下：

1. 将文件读入内存，然后byte[] file = File.ReadAllBytes(path)针对文件字节执行 byte[] 模式的 byte[] 查找。我已经使用了多种方法来执行此操作，例如： byte[] 数组模式搜索 在另一个数组中查找数组 (byte[])？ 检查一个 byte[] 是否包含在另一个 byte[] 中的最佳方法尽管如此，当源大小很大时，查找速度非常慢byte[]。byte[]在普通计算机上运行 100 万个模式需要数周时间。
2. 将文件和模式转换为十六进制字符串，然后使用contains()执行查找的方法进行比较。这比byte[]查找更快，但将字节转换为十六进制会导致文件在内存中变大，从而导致更多的处理时间。
3. Encoding.GetEncoding(1252).GetBytes()使用并执行查找将文件和模式转换为字符串。contains()然后，通过运行与执行查找的另一种方法的匹配来补偿二进制到字符串转换的限制（我知道它们不兼容）byte[]（建议第一个选项）。这对我来说是最快的选择。

使用第三种方法（最快），100 万个模式将需要 2/3 天到一天的时间，具体取决于 CPU。我需要有关如何加快查找速度的信息。

谢谢。

编辑：感谢@MySkullCaveIsADarkPlace，我现在有了第四种方法，它比上述三种方法更快。我曾经使用有限的 byte[] 查找算法，现在我使用MemoryExtensions.IndexOf()byte[] 查找方法，该方法比上述三种方法稍快。尽管这种方法速度更快，但查找速度仍然很慢。1000 个模式查找需要 1 分钟。

每个模式为 12-20 字节。

Answer 1

我假设您正在查找一种又一种模式。即，您正在文件中的每个位置执行 1 到 1000 万次模式搜索！

考虑反过来做。循环一次文件字节并确定当前位置是否是模式的开始。

为了有效地做到这一点，我建议将模式组织在模式列表数组中。每个模式都存储在数组索引处的列表中256 * byte[0] + byte[1]。对于 1000 万个模式，每个数组位置的列表中平均有 152 个模式。这允许快速查找。

您还可以使用前 3 个字节 ( 256 * (256 * byte[0] + byte[1]) + byte[2]) 生成长度为 256^3 ~ 1600 万的数组（我使用更长的数组；对于 C# 来说没有问题）。那么平均每个数组位置的模式将少于一个。这将导致O(n)相对于文件长度的搜索时间几乎呈线性。O(num_of_patterns * file_length)与直接算法的二次方程相比，这是一个巨大的改进。

我们可以使用简单的逐字节比较来比较模式，因为我们可以从已知位置开始进行比较。（博耶摩尔在这里没有用。）

2 字节索引（模式必须至少有 2 字节长）

byte[] file = { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125 };
byte[][] patterns = {
    new byte[]{ 12, 3, 5, 76, 8, 0, 6, 125, 11 },
    new byte[]{ 211, 122, 22, 4 },
    new byte[]{ 17, 211, 5, 8 },
    new byte[]{ 22, 4, 7, 89, 76, 64 },
};
var patternMatrix = new List<byte[]>[256 * 256];

// Add patterns to matrix.
// We assume pattern.Length >= 2.
foreach (byte[] pattern in patterns) {
    int index = 256 * pattern[0] + pattern[1];
    patternMatrix[index] ??= new List<byte[]>(); // Ensure we have a list.
    patternMatrix[index].Add(pattern);
}

// The search. Loop through the file
for (int fileIndex = 0; fileIndex < file.Length - 1; fileIndex++) { // Length - 1 because we need 2 bytes.
    int patternIndex = 256 * file[fileIndex] + file[fileIndex + 1];
    List<byte[]> candiatePatterns = patternMatrix[patternIndex];
    if (candiatePatterns != null) {
        foreach (byte[] candidate in candiatePatterns) {
            if (fileIndex + candidate.Length <= file.Length) {
                bool found = true;
                // We know that the 2 first bytes are matching,
                // so let's start at the 3rd
                for (int i = 2; i < candidate.Length; i++) {
                    if (candidate[i] != file[fileIndex + i]) {                             
                        found = false;
                        break;
                    }
                }
                if (found) {
                    Console.WriteLine($"pattern {{{candidate[0]}, {candidate[1]} ..}} found at file index {fileIndex}");
                }
            }
        }
    }
}

具有 3 个字节的相同算法（甚至更快！）

3 字节索引（模式必须至少有 3 字节长）

var patternMatrix = new List<byte[]>[256 * 256 * 256];

// Add patterns to matrix.
// We assume pattern.Length >= 3.
foreach (byte[] pattern in patterns) {
    int index = 256 * 256 * pattern[0] + 256 * pattern[1] + pattern[2];
    patternMatrix[index] ??= new List<byte[]>(); // Ensure we have a list.
    patternMatrix[index].Add(pattern);
}

// The search. Loop through the file
for (int fileIndex = 0; fileIndex < file.Length - 2; fileIndex++) { // Length - 2 because we need 3 bytes.
    int patternIndex = 256 * 256 * file[fileIndex] + 256 * file[fileIndex + 1] + file[fileIndex + 2];
    List<byte[]> candiatePatterns = patternMatrix[patternIndex];
    if (candiatePatterns != null) {
        foreach (byte[] candidate in candiatePatterns) {
            if (fileIndex + candidate.Length <= file.Length) {
                bool found = true;
                // We know that the 3 first bytes are matching,
                // so let's start at the 4th
                for (int i = 3; i < candidate.Length; i++) {
                    if (candidate[i] != file[fileIndex + i]) {
                        found = false;
                        break;
                    }
                }
                if (found) {
                    Console.WriteLine($"pattern {{{candidate[0]}, {candidate[1]} ..}} found at file index {fileIndex}");
                }
            }
        }
    }
}

为什么更快？

一个简单的嵌套循环算法可比较多达约 70 ⁶ * 10 ⁶ = 7 * 10 ¹⁴（700 万亿）个模式！70 ⁶是文件的长度。10 ⁶是模式的数量。

我的算法使用 2 字节索引进行 ~ 70 ⁶ * 152 = 10 ¹⁰次模式比较。数字 152 来自这样的事实：对于给定的 2 字节索引~ 10 ⁶ /(256 * 256)平均有 152 个模式。这快了 65,536 倍。

使用 3 个字节，您可以获得大约 70 ^{6 个}模式比较。这快了超过 1000 万倍。出现这种情况是因为我们将所有模式存储在一个数组中，该数组的长度（1600 万）大于模式数量（1000 万或更少）。因此，在文件中的任何字节位置加上随后的 2 个位置，我们只能拾取以相同 3 个字节开头的模式。平均而言，这种模式少于一种。有时可能有 0 或 1 个模式，有时可能有 2 或 3 个模式，但在任何数组位置很少有更多模式。

尝试一下。该转变是从O(n ² )到接近O(n)。初始化时间为O(n)。假设模式的前 2 个或 3 个字节或多或少是随机分布的。如果不是这种情况，我的算法在最坏的情况下将降级为O(n ² ) 。

好吧，这就是理论。由于 3 字节索引版本在初始化时速度较慢，因此它可能只在处理大量数据集时具有优势。使用 可以进行其他改进Span<byte>。

请参阅：大 O 表示法 - 维基百科。