我有一个字节数组,希望找到一些字节的"出现次数"。
例如,00 69 73 6F 6D
在非常大的字节数组(> 50/100 兆字节)中
或
更好的反向操作:在不知道的情况下搜索最常见的模式,代码应该能够从文件中读取和找到它。
您可以使用 Boyer-Moore 算法有效地搜索字节数组中的字节序列。
这是我从 Boyer-Moore 上的维基百科条目中转换而来的 Java 版本的 C# 版本。
public sealed class BoyerMoore
{
readonly byte[] needle;
readonly int[] charTable;
readonly int[] offsetTable;
public BoyerMoore(byte[] needle)
{
this.needle = needle;
this.charTable = makeByteTable(needle);
this.offsetTable = makeOffsetTable(needle);
}
public IEnumerable<int> Search(byte[] haystack)
{
if (needle.Length == 0)
yield break;
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)
continue;
yield return i;
i += needle.Length - 1;
break;
}
i += Math.Max(offsetTable[needle.Length - 1 - j], charTable[haystack[i]]);
}
}
static int[] makeByteTable(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;
}
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;
}
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;
}
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;
return len;
}
}
下面是它的一些控制台应用测试代码:
public static void Main()
{
byte[] haystack = new byte[10000];
byte[] needle = { 0x00, 0x69, 0x73, 0x6F, 0x6D };
// Put a few copies of the needle into the haystack.
for (int i = 1000; i <= 9000; i += 1000)
Array.Copy(needle, 0, haystack, i, needle.Length);
var searcher = new BoyerMoore(needle);
foreach (int index in searcher.Search(haystack))
Console.WriteLine(index);
}
请注意 Search()
方法如何返回 haystack
内needle
开始的所有位置的索引。
如果你只是想要计数,你可以做:
int count = new BoyerMoore(needle).Search(haystack).Count();
对于您的第二个问题:我假设您正在询问如何找到最长的重复字节序列?
这是一个更加复杂和非常不同的问题。如果你想要一个答案,你应该问一个单独的问题,但你应该阅读维基百科关于"最长重复子字符串问题"的条目。