提问人： 提问时间：2/1/2011 最后编辑：MPelletier 更新时间：8/18/2023 访问量：16359
在另一个数组中查找一个数组 （byte[]）？
Find an array (byte[]) inside another array?
问：
在另一个 byte[] 中查找一个 byte[] 的最简单方法是什么？我有一种感觉，我可以用 LINQ 做到这一点，但我不知道该怎么做。
注意：我用搜索了一下，没有找到任何东西，我很惊讶。[c#]
答：
-2赞
Aaron Anodide
2/1/2011
#1
你可能已经想到了这一点，但有时我喜欢做简单的事情。
bool found = false;
int i = 0;
for(; i < byteArray.Length || found; i++)
{
if(byteArray[i] == lookingFor)
{
found = true;
}
}
评论
2赞
jason
2/1/2011
我想你误解了这个问题。把问题想象成在字符串中找到一个单词，但单词是 a，字符串是另一个。byte[]byte[]
0赞
Aaron Anodide
2/1/2011
是的，我将其读取为字节数组中的字节。我的错。如果你有 ASCII，你可以使用 ASCIIEncoding.ASCII.GetString 从你的 byte[] 创建一个字符串
9赞
Ergwun
2/1/2011
#2
这里有一个简单（幼稚？）的方法：
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;
}
}
评论
0赞
2/1/2011
完美，正如我需要的那样。糟糕的是，我不能用 linq 或内置的东西来做到这一点。你现在刚写这个吗？还是从某个地方复制/粘贴？
0赞
jason
2/1/2011
请注意，根据输入的不同，这可能会非常慢。
0赞
Ergwun
2/1/2011
@acidzombie - 刚刚写好了。@Jason - 是的，可能很慢，但很简单。
0赞
2/1/2011
@jason：为什么？我看不出有什么“慢”的？
0赞
jason
2/1/2011
@acidzombie24：很容易想出速度慢得离谱的例子。你可以让它通过算法的匹配部分反复开始长时间的搜索，然后几乎不失败，然后不得不重新开始。
0赞
Alex Klaus
12/14/2012
#3
尝试使用 lambda 表达式：
private bool CheckPatternInArray(byte[] array, byte[] pattern)
{
int fidx = 0;
int result = Array.FindIndex(array, 0, array.Length, (byte b) =>
{
fidx = (b == pattern[fidx]) ? fidx + 1 : 0;
return (fidx == pattern.Length);
});
return (result >= pattern.Length - 1);
}
如果您追求最快的，请在此处查看解决方案。
28赞
Michael Geary
11/12/2014
#4
以下是 Ergwun 优秀答案的更快版本：
static int SearchBytes( byte[] haystack, byte[] needle ) {
var len = needle.Length;
var limit = haystack.Length - len;
for( var i = 0; i <= limit; i++ ) {
var k = 0;
for( ; k < len; k++ ) {
if( needle[k] != haystack[i+k] ) break;
}
if( k == len ) return i;
}
return -1;
}
在使用 11MB 干草堆和 9 字节指针的简短测试中，这大约快了三倍。
优化包括：
- 每次都不通过外部循环调用函数。
- 针长度和搜索限制被缓存。
- 删除了开始时的冗余长度测试。
match()
当然，对于长字节数组，你会希望使用像Boyer-Moore搜索这样的东西，但对于许多目的来说，像这样的简单算法已经足够好了，而且它具有简短且易于理解和验证的优点。
评论
0赞
Askar Rayapov
11/2/2018
为什么是否使用 BM 的决定取决于输入的大小而不是字母集？
1赞
Michael Geary
11/3/2018
好点子！我只是笼统地说：如果你的数据很小（无论从哪个角度来看），或者运行多长时间真的不那么重要，那么一个缓慢但简单易懂的算法就足够好了。例如，我有一个案例，我必须在构建过程中执行类似的字节数组搜索。使用像上面这样的简单算法，搜索大约需要一秒钟。显然，在许多情况下，这将是一个交易破坏者，但这是发布版本的一部分，需要几分钟的时间，并且只是偶尔运行。如此简单和缓慢是足够好的！
0赞
Goku
2/25/2020
这怎么更快？它不是在做同样幼稚的搜索吗？
0赞
Michael Geary
2/26/2020
@Goku 是的，它是相同的算法，但由于我在答案中列出的三个优化，实现速度更快。
0赞
stoj
4/13/2023
#5
这是一个老问题，但由于 LINQ 中仍然没有它，尽管这是一个常见的方案，因此我根据 Michael 的回答在下面添加了一个 LINQ 扩展方法。本着 string/byte[] IndexOf 的精神编写。
它还显式处理一个空的针集，而以前的解决方案返回匹配项（索引 0），现在返回为缺失 （索引 -1）。
public static class LinqExtensions
{
public static int IndexOf(this IEnumerable<byte> haystack, IEnumerable<byte> needle)
{
var needleArray = needle as byte[] ?? needle.ToArray();
var haystackArray = haystack as byte[] ?? haystack.ToArray();
var needleLength = needleArray.Length;
var haystackLengthLimit = haystackArray.Length - needleLength;
if (needleLength > 0)
{
for (var i = 0; i <= haystackLengthLimit; i++)
{
var j = 0;
for (; j < needleLength; j++)
{
if (needleArray[j] != haystackArray[i + j])
break;
}
if (j == needleLength)
return i;
}
}
return -1;
}
}
加上一些测试来展示它的实际效果。
[Test]
[TestCase(new byte[] { 1, 2, 3}, new byte[] {1, 3}, -1)]
[TestCase(new byte[] { 1, 2, 3}, new byte[] {}, -1)]
[TestCase(new byte[] { 1, 2, 3}, new byte[] {1}, 0)]
[TestCase(new byte[] { 1, 2, 3}, new byte[] {2, 3}, 1)]
[TestCase(new byte[] { 1, 2, 3, 20, 30, 40}, new byte[] {20, 30, 40}, 3)]
[TestCase(new byte[] { 1, 2}, new byte[] {1, 2, 3}, -1)]
[TestCase(new byte[] { }, new byte[] {1, 2, 3}, -1)]
[TestCase(new byte[] { }, new byte[] {}, -1)]
public void TestIndexOf(byte[] haystack, byte[] needle, int expectedIndex)
{
Assert.That(haystack.IndexOf(needle), Is.EqualTo(expectedIndex));
}
0赞
拉拉姬
8/18/2023
#6
byte[] any = { 0xff, 0x14, 0x1f, 0x13, 0x12, 0x2f, 0x3f, 0x4f, 0x5f, 0x6f, 0x11, 0x22, 0x23 };
byte[] pattern = { 0x4f, 0x5f, 0x6f };
string anyHexString = BitConverter.ToString(any).Replace("-", "");
string patternHexString = BitConverter.ToString(pattern).Replace("-", "");
int findIndex = anyHexString.IndexOf(patternHexString) / 2;
Console.WriteLine(findIndex);
如果你不关心性能，你可以使用这种方法，它几乎是最简洁明了的
将字节数组转换为 hexString 并查找
评论