java - 更有效地存储(字符串，整数)元组并应用二分搜索

Question

简介

我们将元组(string,int)存储在二进制文件中。该字符串代表一个单词(没有空格或数字)。为了找到一个单词，我们应用二分搜索算法，因为我们知道所有元组都是根据该单词排序的。

为了存储它，我们使用 writeUTF 作为字符串，使用 writeInt 作为整数。除此之外，我们假设现在没有办法区分元组的开始和结束，除非我们提前知道它们。

问题

When we apply binary search, we get a position (i.e. (a+b)/2) in the file, which we can read using methods in Random Access File, i.e. we can read the byte at that place. However, since we can be in the middle of the word, we cannot know where this words starts or finishes.

解决方案

我们提出了两种可能的解决方案，但是，我们正在尝试确定哪一种更节省空间/更快。

• 方法 1: 我们没有将整数存储为数字，而是将其存储为字符串(例如使用 writeChars 或 writeUTF )，因为在这种情况下，我们可以在元组的末尾插入一个空字符。也就是说，我们可以确定用于序列化数据的任何方法都不会使用空字符，因为我们存储的信息(数字和数字)具有更高的 ASCII 值表示形式。

• 方法 2:我们保持相同的结构，但我们用 6-8(或更少)字节的随机噪声(在整个文件中相同)分隔每个元组。在这种情况下，我们假设单词的熵较低，因此它们不太可能有任何随机性迹象。即使整数可能获得与随机噪声中完全相同的4个字节，后面的额外两个字节也不会(很有可能)。

您会推荐以下哪种方法？有没有更好的方法来存储此类信息。请注意，我们无法序列化整个文件，然后将其反序列化到内存中，因为它非常大(而且我们不允许这样做)。

Answer 1

我假设您正在尝试优化速度和空间(按顺序)。

我会使用不同的布局，由 2 个文件构建:

1. 整数+索引文件
   每个“记录”正好是 8 个字节长，下面 4 个字节是该记录的整数值，上面 4 个字节是表示该记录在另一个文件中的偏移量的整数(>字 rune 件)。
2. 角色文件
   连续的字 rune 件(UTF-8 编码或您选择的任何编码)。 “记录”没有分隔，没有以任何方式终止，简单的1×1字符。例如，记录 Good、Hello、Morning 将类似于 GoodHelloMorning。

要迭代数据集，可以直接访问整数/索引文件(recordNum * 8 是记录的字节偏移量)，读取整数和字符偏移量，加上字符偏移量下一条记录的值(即 recordNum * 8 + 12 处的 4 字节整数)，然后从字 rune 件中从索引文件读取的偏移量之间读取字符串。完成!