2

我有一个视频文件，它由许多连续的二进制数据帧组成。每帧也有一个唯一的时间戳（不是它在文件中的序号，而是一个值，由相机在录制时提供）。另一方面，我有一个 API 函数，它根据该帧的序号检索该帧。让事情变得更复杂一些 - 我有一个玩家，他提供了时间戳，并且应该获取该帧的二进制数据。

另一个可悲的事情是：时间戳不是连续的。它们可以是连续的，但不能保证，因为围绕最大无符号短大小可能会发生回绕。所以时间戳序列可以是 54567, 54568, ... , 65535, 65536 , ... 或
54567, 54568, ..., 65535, 0, 1, ...

所以它可能如下所示：

Frame 0
timestamp 54567
binary data
........
Frame 1
timestamp 54569
binary data
........
Frame 2
timestamp 54579
binary data
.
.
.
Frame n
timestamp m
binary data

0 <= n <= 65536 (MAX_UNSIGNED_SHORT)
0 <= m <= MAX_UNSIGNED_INT

剪辑播放器 API 应该能够通过时间戳获取二进制帧。但是，在内部，我只能通过帧序号来获取帧。因此，如果我被要求输入时间戳m，我需要遍历n帧，以找到带有时间戳的帧m。

为了优化它，我选择创建一个索引文件，它可以让我在时间戳和帧序号之间进行匹配。这是我的问题：

目前我的索引文件由 size 的二进制对组成2*sizeof(unsigned int)，其中包含时间戳和帧序号。播放器稍后会从该文件中stl map创建key==timestamp, value==frame sequential number。

有什么方法可以更有效地做到这一点吗？我是否应该将索引文件创建为某些数据结构的转储，以便稍后在打开剪辑时由剪辑播放器将其加载到内存中，这样我就可以 O(1) 访问帧？您还有其他建议吗？

升级版：

我已经更新了名称和要求（时间戳不一定是连续的，并且帧数由 MAX_UNSIGNED_SHORT 值限制）。还要感谢所有已经抽出时间并给出答案的人。插值搜索是一个有趣的想法，尽管我自己从未尝试过。我想问题将是运行时之间O(1)和O(log log N)运行时的增量。

4

3 回答 3

1

看起来我们应该能够做出以下假设：a）视频文件本身在创建后不会被修改 b）播放器可能想要找到连续的帧，即当它进行正常播放时 c）播放器可能想要找到随机帧，即当它正在执行 FF、REW 或跳过或跳过章节时

鉴于此，为什么不做一个 HashMap 关联 Frame Id 和 Frame Index 呢？您可以创建一次，玩家可以阅读它，然后可以对请求的帧进行简单且有时间限制的查找。

于 2013-03-07T16:08:55.430 回答
0

这里有一系列的权衡。

您的索引文件已经是一个数据结构的转储：一个数组。如果您不打算经常插入或删除帧，并将此数组保持在排序顺序，则可以轻松地std::binary_search对数组进行二进制搜索（使用 ）。插入和删除需要 O(N)，但查找仍然是 O(log N)。该数组将占用更少的内存空间，并且可以更快地从索引文件中读取和写入。

如果您正在执行大量插入和删除帧，那么转换为std::map结构将为您提供更好的性能。如果帧的数量很大，或者你想用它们存储更多的元数据，你可能想看看B-tree structure ，或者只是使用像Sqlite或BerkeleyDB这样的嵌入式数据库。这两个都实现了 B-tree 索引并且是经过良好测试的代码片段。

于 2013-03-07T16:03:05.767 回答
0

只需将帧数据存储在一个数组中，其中索引表示帧号。然后创建一个从相机索引到帧号的哈希映射。您可以获得属于 O(1) 中的帧号或相机索引的帧，而几乎不使用比当前方法更多的内存。

或者，您可以维护一个按帧号索引的数组，该数组存储（相机索引，数据）对，并在您需要通过相机索引访问它时对其执行 O(log n) 二进制搜索。这利用了相机索引已排序的事实。

在 C++ 的标准库中，哈希映射可用作std::unordered_map（如果您的编译器/STL 支持它们，情况可能并非如此，因为它们最近才被添加到 C++ 标准中），尽管基于树的std::map（使用 O(log n)查找）可能足以达到此目的。

二进制搜索实现可作为std::binary_search.

于 2013-03-07T16:28:46.037 回答