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:我们不将integer存储为数字，而是将其存储为字符串（使用例如writeChars或writeUTF），因为在这种情况下，我们可以在元组末尾插入一个空字符。也就是说，我们可以确保用于序列化数据的任何方法都不会使用空字符，因为我们存储的信息（数字和数字）具有更高的ASCII值表示形式

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

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

Answer 1

it's less than 200MB. Max 20 chars for a word.

那为什么要麻烦呢？除非您在一些严格限制的系统上工作，否则将所有内容加载到Map<String, Integer>中并获得几个数量级的速度

但是，让我们说，我忽略了一些东西，让我们继续

---

Method 1: Instead of storing the integer as a number, we thought to store it as a string (using eg. writeChars or writeUTF), because in that case, we can insert a null character

你不必像你说的那样，你的单词里没有数字。因此，您总是可以唯一地解析0124some456word789之类的内容

效率取决于分配。您可能会赢4倍（一位数）或输2.5倍（10位数）。你可以通过使用更高的基数来节省一些东西。但是这里有存储字符串的空间，它可能占主导地位

Method 2: We keep the same structure, but instead we separate each tuple with 6-8 (or less) bytes of random noise (same across the file).

这太浪费了。在数据字节之间使用四个零可以：

• 找到至少四个零的序列
• 找到最后一个零
• 这是最后一个分隔符字节

方法3:使用一些技巧，可以确保数字不包含零字节（假设它不使用整个范围，或者用五个字节表示）。然后一个零字节就可以了

方法4:由于磁盘是按块组织的，您可能应该将数据拆分为4 KiB块。然后，您可以添加一些时间头，允许您快速访问数据（第8、16条等数据的开始索引）。第8块和第16块之间的范围应按顺序扫描，因为它比二进制搜索更简单、更快

Answer 2

我假设您正在尝试优化速度和性能；空格（按那个顺序）

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

1. 集成+索引文件
   每个“记录”的长度正好是8个字节，下面的4个字节是记录的整数值，上面的4个字节是表示另一个文件（字符文件）中记录偏移量的整数
2. 字符文件
   字符的连续文件（UTF-8编码或您选择的任何内容）。“记录”不以任何方式分隔，也不以简单的1×1字符终止。例如，记录Good、Hello、Morning看起来像GoodHelloMorning

要迭代数据集，您可以通过直接访问来迭代整数/索引文件（recordNum * 8是记录的字节偏移量），读取整数和字符偏移量，再加上下一条记录的字符偏移量（即recordNum * 8 + 12处的4字节整数），然后在从索引文件读取的偏移量之间从字符文件读取字符串。完成了