logo标签列表

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

c#arraysalgorithm
6

我有一个非常长的字节数组，例如：

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

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

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

首先，我需要按照小数组中定义的顺序查找字节。其次，我需要在另一个数组中查找小数组，而不是任何小数组中的字节。 提前感谢所有人。
1
你能具体一些吗？你是指确切的顺序还是这些数字，以任何顺序放置在任何位置？ - II ARROWS
1
可能是检查一个数组是否为另一个数组的子集的重复问题。 - Farhad Jabiyev
你是否在寻找序列，即这四个字节必须按照特定的顺序出现？如果是这样，通常被称为子字符串搜索(即使在你所使用的任何语言中都不涉及字符串)，你应该能够查找到很多相关算法。 - Damien_The_Unbeliever
你希望它们以相同的顺序呈现吗？如果顺序不重要，那么您可以对初始数组进行排序，然后二进制搜索候选对象。如果顺序很重要，那么有各种算法可帮助您解决问题。我能想到的最快的可能是Aho Corasick算法。 - user932887
你可以尝试使用IsSubsetOf方法，如此答案所述。 - Farhad Jabiyev
小数组的大小是固定的吗？ - xyz
6个回答
5

对于性能，您希望使用类似Boyer-Moore字符串搜索算法的东西。虽然它是为字符串设计的，但在字节数组上应该同样有效，并且比暴力解决方案要快得多。

维基百科文章提供了几种实现方式，包括Java和C中的一种，因此创建一个C#实现应该相当轻松。

事实证明，将维基百科文章中的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;
    }
}

算法在开始时花费线性位时间来构建其表格；从那时起，它的速度极快。
3
static int search(byte[] haystack, byte[] needle)
{
    for (int i = 0; i <= haystack.Length - needle.Length; i++)
    {
        if (match(haystack, needle, i))
        {
            return i;
        }
    }
    return -1;
}

static bool match(byte[] haystack, byte[] needle, int start)
{
    if (needle.Length + start > haystack.Length)
    {
        return false;
    }
    else
    {
        for (int i = 0; i < needle.Length; i++)
        {
            if (needle[i] != haystack[i + start])
            {
                return false;
            }
        }
        return true;
    }
}
3
OP并没有将数组视为集合，而是作为序列来处理。 - Damien_The_Unbeliever
它并没有解决问题。它没有按照小数组中定义的字节顺序，在大数组中定位小数组。 - kate
0

如果你有数百万个字节元素，我建议：

  1. 排序字节
  2. 在小范围内使用foreach，如果找不到元素则返回false

因此

bytes.Sort(); // only need to do this once.
bool smallContained = ContainsAll(bytes, small);

并且

static bool ContainsAll(int[] src, int [] subset)
{ 
    foreach(var i in subset)
       if (src.BinarySearch(i) < 0)
               return false;
    return true;
}
我需要按照小数组中定义的顺序查找字节。 - kate
0

如果我理解正确，您想要判断small是否为bytes的子序列。您可以通过循环遍历bytes来实现。由于处理器缓存的优势，它应该运行非常快。

  for (int i = 0, index = 0; i < bytes.Length; ++i) 
    if (bytes[i] == small[index]) {
      if (++index >= small.Length) {
        return true; 
      }
    }
  return false;
@PetterHesselberg，你的意思是它不能正确检测子序列，还是它没有解决顶部混淆的问题？ - Sorin
它甚至不能编译；代码包含一个左大括号和两个右大括号。但这只是小问题，很容易解决。问题在于它会产生误报——如果“small”的字节存在于“bytes”中，但是它们之间有其他值，你的算法仍然会返回“true”。我相信OP想要一个连续的字节序列。 - Petter Hesselberg
@PetterHesselberg 感谢您找到了这个笔误。那些不是假阳性，而是子序列的定义。OP说“首先，我需要按照小数组中定义的顺序查找字节”，我理解为子序列。上面的代码实现了这一点。我无法理解第二个问题。希望OP回来澄清一下。 - Sorin
0

您可以使用此函数，来自Reddit帖子：

public static bool CheckSequence<T>(IEnumerable<T> containingArray, IEnumerable<T> containedArray)
{
    bool result = false;
    for (int i = 0; i <= containingArray.Count(); i++)
    {
        if (containedArray.SequenceEqual(containingArray.Skip(i).Take(containedArray.Count())))
            result = true;
    }
    return result;
}

喜欢：

var result = CheckSequence(bytes, small);
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接