c - 解决快速搜索算法分配的技巧

Question

我有一个巨大的文本文件 (50 MB)，其中的键/值看起来像这样:

...
ham 2348239
hehe 1233493
hello 1234213
hello 1812394
hello 1923943
help 2038484
helping 2342394
hesitate 1298389
...

基本上它是很多单词，值是指向该单词在另一个文件中的位置的指针，该文件包含一整本小说。

作业是编写一个非常快速的搜索算法，方法是创建所有字母组合 AAA-ZZZ 的哈希表索引并将其存储在文件中。散列值应指向以这三个字母开头的单词的第一次出现，例如。组合HEH应该指向hehe，HEL应该指向第一个hello等。

因此，如果我搜索 help，HEL 将被散列，我将收到指向第一个 hello 的指针，并通过查找我的哈希表中的下一个索引，我将得到一个指向 hesitate 的指针，从而可以访问以 HEL 开头的整个单词范围。

要在范围内找到单词 help，作业建议进行二分查找。

我实际上设法解决了这个问题，但解决方案非常丑陋，很大程度上是由于上述文本文件。

我在想一定有一种更优雅的方式来构建键/值文本文件。也许是二进制的。

感谢任何建议!

编辑

抱歉未指定的问题。我只是想从社区获得一些意见……也许是关于如何解决此问题的一些最佳实践建议。

这是构建我的哈希表的代码:

while ((fscanf(indexFile, "%s %lu\n%n", buf, &bookPos, &rowLength)) != EOF){
    newHash = calcHashIndex(buf);
    if (curHash < newHash){
        curHash++;
        indexPos = ftell(indexFile) - rowLength;
        for (;curHash <= newHash; curHash++){
            hashTable[curHash] = indexPos;
        }
        curHash = newHash;
    }
}
fwrite(hashTable, sizeof(hashTable), 1, hashTableFile);

下面是在 indexFile 中进行二分查找的代码。实际上它并没有真正起作用...一些只出现 1 次的随机词不会作为匹配项返回。

int binarySearch(unsigned char *searchWord, FILE * file, long firstIndex, long lastIndex){
    unsigned char buf[WORD_LEN];
    long bookPos, middle;
    int cmpVal, rowLength;

    while (firstIndex < lastIndex){
        middle = (firstIndex + lastIndex)/2;
        fseek(file, middle, SEEK_SET);
        goBackToLastNewLine(file, 0);
        fscanf(file, "%s %lu\n%n", buf, &bookPos, &rowLength);
        if (strcmp(searchWord, buf) <= 0){
            lastIndex = ftell(file) - rowLength;
        } else {
            firstIndex = ftell(file);
        }
    }

    fseek(file, -rowLength, SEEK_CUR);
    return (strcmp(searchWord, buf) == 0) ? 1 : 0;
}

Answer 1

这很困难，因为寻找 hello 的理想算法应该返回所有三个 hello

void binary_search(int index1, int index2, char* value, int* range){
    int range_size = (index2 - index1);

    if( range_size == 0 ){
         range[0] = range[1] = -1;
         return;
    }

    int middle_index = (range_size / 2) + index1;
    char* current_line = get_file_line(middle_index);

    int str_compare = strcmp(current_line,value);

    if(str_compare > 0 ) { 
        binary_search(index1, middle_index-1, value, range);
    } else if (str_compare < 0 ) { 
        binary_search(middle_index+1, index2, value, range);
    } else {
        find_whole_range(middle_index, value);
    }
} 

void find_whole_range(int index, char* value, int* range){

    range[0] = index;
    range[1] = index; 


    while( strcmp( get_file_line( range_top - 1 ), value) == 0 )
        range[0]--;

    while( strcmp( get_file_line( range_top + 1 ), value) == 0 )
        range[1]++;
}

编辑:这是未经测试的，我确​​定某些引用/取消引用是错误的，您可能需要仔细检查我没有翻转 strcmp 的值...