java - 捕获文件的高效搜索算法

Question

我目前正在用 Java 开发一个工具，它可以帮助跟踪和解释通过以太网连接发送的数据。我已经成功开发了数据包嗅探器和数据包数据解释器。

我在尝试导航到跟踪文件中的特定数据包时遇到了问题。每个数据包都有一个关联的时间戳，我希望能够导航到特定的时间窗口。我目前执行此操作的方法如下。

public ArrayList<Packet> getTimeWindow(double time, int window) {
    ArrayList<Packet> packets = new ArrayList<Packet>();
    double start = time - window;
    double end = time + window;

    JpcapCaptor captor = null;
    try {
        captor = JpcapCaptor.openFile(this.traceFile); 
    } catch (IOException e) {e.printStackTrace();}

    Packet p = captor.getPacket();
    while(packet != null) {
        if(f.timestamp > end) return packets;
        if(p.timestamp >= start) packets.add(p);    
        packet=captor.getPacket();
    }
    return packets;
}

这适用于小跟踪，但当我们处理数百万数据包时会变得非常慢。我想实现某种形式的二进制搜索算法，但我想不出一种方法来导航到数据包的中间而不对它们进行预处理。数据包没有按行整齐地组织，即使我跳到文件中的随机点，我也不能保证我在数据包的开头。

总结:我希望开发一种有效的方法来在捕获(.pcap 或 .cap)文件中搜索特定数据包。我已经在网上搜索过了，但我没能找到任何可以完全满足我要求的东西。

如果有人有任何想法/解决方案可以建议，我们将不胜感激。

谢谢!

Answer 1

一个简单的小型解决方案是为相关文件构建一个简单的索引。例如，您可以在文件中记录每第 1000 个数据包开始的偏移量。将此信息(只是原始跟踪文件中的一系列 64 位索引)存储在一个小索引文件中。然后当你进行二进制搜索时，你可以使用这个索引，连同原始文件，找到(在 1000 个数据包内)开始读取的正确点。

当然，这需要对跟踪文件进行预处理(或边生成边处理)。