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

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，赋值建议执行二进制搜索。

实际上，我设法解决了这个问题，但是这个解决方案很难看，很大程度上是由于上面描述的文本文件。

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

任何建议都要感谢！

编辑

很抱歉有个问题没有说明。我只想从社区里得到一些信息.也许是一些关于如何解决这个问题的最佳实践建议。

下面是构建我的hashTable的代码：

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的

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翻转的值.

Answer 2

解决非常不明确的问题的方法是:使用数据库(mySQL f.e.)。它拥有你所需要的一切，拥有超过40年的数据库管理系统设计和构建的知识。