2

次のようなキー/値を含む巨大なテキスト ファイル (50 MB) があります。

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

基本的に、それは多くの単語であり、値はフィクション小説全体を含む別のファイル内のその単語の位置へのポインターです。

課題は、すべての文字の組み合わせ AAA ～ ZZZ のハッシュ テーブル インデックスを作成し、それをファイルに格納することによって、非常に高速な検索アルゴリズムを作成することです。ハッシュ値は、その 3 文字で始まる単語の最初の出現を指す必要があります。組み合わせ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;
}
4

2 に答える 2

1

こんにちはを探している理想的なアルゴリズムは3つすべてのこんにちはを返す必要があるため、それは困難です

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 に答える