首页 文章

二进制搜索文件与不同的行长度

提问于
浏览 次
2

我有一些代码在每行上对带有排序十六进制值（SHA1哈希）的文件进行二进制搜索 . 这用于搜索HaveIBeenPwned数据库 . 最新版本包含每个密码哈希的查找次数，因此某些行末尾有额外的字符，格式为':###'

这个附加检查的长度不固定，并不总是存在 . 这会导致缓冲区读取不正确的值，并且无法找到实际存在的值 .

当前代码：

static bool Check(string asHex, string filename)
{
    const int LINELENGTH = 40;  //SHA1 hash length

    var buffer = new byte[LINELENGTH];
    using (var sr = File.OpenRead(filename))
    {
        //Number of lines
        var high = (sr.Length / (LINELENGTH + 2)) - 1;
        var low = 0L;

        while (low <= high)
        {
            var middle = (low + high + 1) / 2;
            sr.Seek((LINELENGTH + 2) * ((long)middle), SeekOrigin.Begin);
            sr.Read(buffer, 0, LINELENGTH);
            var readLine = Encoding.ASCII.GetString(buffer);
            switch (readLine.CompareTo(asHex))
            {
                case 0:
                    return true;

                case 1:
                    high = middle - 1;
                    break;

                case -1:
                    low = middle + 1;
                    break;

                default:
                    break;
            }
        }
    }
    return false;
}

我的想法是从中间向前寻找直到找到换行符，然后向后寻找相同的点，这应该给我一个完整的行，我可以通过'：'分隔符分割 . 然后我比较分裂字符串数组的第一部分，它应该只是一个SHA1哈希 .

我认为这仍然应该以正确的 Value 为中心，但我想知道是否有更简洁的方法来做到这一点？如果中点不是行尾字符之间的实际中点，是否应该在高值和低值之前进行调整？

c# binary-search

1 回答

  • 2

    我认为这可能是一个更简单（更快）的解决方案，没有回溯到线的开头 . 我认为你可以使用字节文件索引，而不是尝试使用完整的“记录/行 . 因为中间索引不会总是在行/记录的开头，”readline“可以返回部分行/记录如果你要立即做第二个“readline”，你会得到一个完整的行/记录 . 这不是最佳的，因为你实际上会比中间索引略微一点 .

    我下载了pwned-passwords-update-1并在开始，结束和中间提取了大约30条记录，它似乎找到了所有记录 . 你怎么看？

    const int HASHLENGTH = 40;

static bool Check(string asHex, string filename)
{
    using (var fs = File.OpenRead(filename))
    {
        var low = 0L;
        // We don't need to start at the very end
        var high = fs.Length - (HASHLENGTH - 1); // EOF - 1 HASHLENGTH

        StreamReader sr = new StreamReader(fs);

        while (low <= high)
        {
            var middle = (low + high + 1) / 2;
            fs.Seek(middle, SeekOrigin.Begin);

            // Resync with base stream after seek
            sr.DiscardBufferedData();

            var readLine = sr.ReadLine();

            // 1) If we are NOT at the beginning of the file, we may have only read a partial line so
            //    Read again to make sure we get a full line.
            // 2) No sense reading again if we are at the EOF
            if ((middle > 0) && (!sr.EndOfStream)) readLine = sr.ReadLine() ?? "";

            string[] parts = readLine.Split(':');
            string hash = parts[0];

            // By default string compare does a culture-sensitive comparison we may not be what we want?
            // Do an ordinal compare (0-9 < A-Z < a-z)
            int compare = String.Compare(asHex, hash, StringComparison.Ordinal);

            if (compare < 0)
            {
                high = middle - 1;
            }
            else if (compare > 0)
            {
                low = middle + 1;
            }
            else
            {
                return true;
            }
        }
    }
    return false;
}
    回复于

相关问题