2

我有一个巨大的文本文件（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;
}
4

2 回答 2

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

于 2012-09-04T16:49:10.523 回答
0

解决您非常不具体的问题的想法：使用数据库（mySQL fe）。凭借超过 40 年的 DBMS 设计和构建的工程知识，这拥有您所需的一切。

于 2012-09-04T15:48:07.513 回答