c - 如何进行百万级词典搜索**(非英语)**

Question

有字典csv文件，百万级数据&非英文(如中文或日文)，最大单词可达32bytes

每次我想在文件中搜索单词。

现在我的解决方案是阻止搜索:

1. 首先对数据进行排序
2. 然后，我将 N 个数据分成 Sqrt(N) 个 block ，并使用 ftell in C 获取每个 block 中第一个数据的文件偏移量，然后将它们存储在一个以这种方式索引文件:(word),(dict中的offset)
3. 每次收到一个词搜索请求时，我打开索引文件并逐行读取，直到我发现这个词在这个 block 中，然后我使用fseek 重新定位到字典文件中该 block 的第一个数据，然后逐行读取，直到在字典中找到数据。

这个解决方案是否合适或者是否有改进的空间？或者还有其他解决方案吗？我不知道如何使用散列或树来搜索文件中的数据。我必须按要求重新制作它们吗？谢谢!!!!!!

Answer 1

我的第一个想法是，对于这种数据集大小，一百万并不是一个大数字。使用基本的平衡二分搜索应该是 log2(million) 次比较，或者每次搜索大约 20 次比较。为了尽可能简单，我会将 32 字节的键读入一个包含(键，文件偏移量)的结构数组:

struct record {
  uint8_t key[32];
  uint8_t key_length;
  uint64_t file_offset;
};

#define MAX_RECORDS 1000000

struct record my_index[MAX_RECORDS];

然后确保“my_index”数组按键排序，这可以使用标准库 qsort() 函数 (https://linux.die.net/man/3/qsort) 简单地完成。完成后，您可以按照此处列出的算法实现分而治之的二进制数组搜索 https://en.wikipedia.org/wiki/Binary_search_algorithm ... 该算法由标准 C 库的 bsearch() 函数 ( https://linux.die.net/man/3/bsearch ) 实现。