最快搜索二进制文件的算法

Question

我正在寻找最快和最好的算法来搜索一些值到一个非常大的二进制文件(一种2 GB的AFP文件)，这意味着在内存中加载整个数据必须是不可想象的。我正在使用c#，我不知道是否有任何其他编程语言(C/c++…)会真的快得多，否则我会继续使用c#。谢谢你的建议。

Answer 1

Boyer-Moore在性能和复杂性之间提供了一个很好的折衷(并且链接的文章有指向其他方法的链接)。

用C实现(源代码链接)将明显比c#快，尽管在实践中您可能会发现磁盘I/o是最大的障碍。

Answer 2

在评论之后，我决定提供一个可能的解决方案。
注意:这个解决方案不是最好的，也不是优雅的。
用它作为起始点:

string SEARCH = @"X'D3A8AF";
int BUFFER = 1024;
int tot = 0;
using (FileStream fs = new FileStream(filename, FileMode.Open))
{
    using (StreamReader sr = new StreamReader(fs))
    {
        char[] buffer = new char[BUFFER];
        int pos = 0;
        while (fs.Position < fs.Length)
        {
            sr.ReadBlock(buffer, 0, BUFFER);
            string s = new string(buffer);
            int i = 0;
            do
            {
                i = s.IndexOf(SEARCH, i);
                if (i >= 0) { tot++; i++; }
            }
            while (i >= 0);
            pos += BUFFER;
            if (!s.EndsWith(SEARCH)) pos -= SEARCH.Length;
            fs.Position = pos;
        }
        sr.Close();
    }
    fs.Close();
}

BUFFER可以根据您的需要修改(增加)。

Answer 3

必须加载整个文件才能搜索对象。如果可能的话，根据唯一的id拆分文件。例如，基于唯一id或其他参数，为每100条记录(1- 100,101 - 200,201 -300等)拆分文件。它类似于索引二进制文件

Answer 4

你可以使用TextReader。ReadBlock方法。逐块读取文件并查找所请求的值。或者使用BinaryReader更好。ReadBytes方法。