-2

この質問の場合： c iを使用してファイル上の重複行を検出すると、重複行を検出できますが、ファイルからこの行を削除するにはどうすればよいですか？

ありがとう。

編集：私のコードを追加するには：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct somehash {
    struct somehash *next;
        unsigned hash;
        char *mem;
};

#define THE_SIZE 100000

struct somehash *table[THE_SIZE] = { NULL,};

struct somehash **some_find(char *str, unsigned len);
static unsigned some_hash(char *str, unsigned len);

int main (void)
{
    char buffer[100];
    struct somehash **pp;
    size_t len;
    FILE * pFileIn;
    FILE * pFileOut;

    pFileIn  = fopen("in.csv", "r");
    pFileOut  = fopen("out.csv", "w+");

    if (pFileIn==NULL) perror ("Error opening input file");
    if (pFileOut==NULL) perror ("Error opening output file");

    while (fgets(buffer, sizeof buffer, pFileIn)) {
            len = strlen(buffer);
            pp = some_find(buffer, len);
            if (*pp) { /* found */
                fprintf(stderr, "Duplicate:%s\n", buffer);
                }
            else    
        {       /* not found: create one */
                    fprintf(stdout, "%s", buffer);
                    fprintf(pFileOut, "%s", buffer);
                    *pp = malloc(sizeof **pp);
                    (*pp)->next = NULL;
                    (*pp)->hash = some_hash(buffer,len);
                    (*pp)->mem = malloc(1+len);
                    memcpy((*pp)->mem , buffer,  1+len);
                }
        }

return 0;
}

struct somehash **some_find(char *str, unsigned len)
{
    unsigned hash;
    unsigned short slot;
    struct somehash **hnd;

    hash = some_hash(str,len);
    slot = hash % THE_SIZE;
    for (hnd = &table[slot]; *hnd ; hnd = &(*hnd)->next ) {
        if ( (*hnd)->hash != hash) continue;
            if ( strcmp((*hnd)->mem , str) ) continue;
                break;
        }

    return hnd;
}

static unsigned some_hash(char *str, unsigned len)
{
    unsigned val;
    unsigned idx;

    if (!len) len = strlen(str);

    val = 0;
    for(idx=0; idx < len; idx++ )   {
            val ^= (val >> 2) ^ (val << 5) ^ (val << 13) ^ str[idx] ^ 0x80001801;
    }

    return val;
}

しかし、出力ファイルでは、常に最初のオカレンスを取得しました。

編集2：明確にするために：目的は、入力ファイル内のすべての重複を見つけることです。入力に複数の行のインスタンスがある場合、その行は出力にまったく表示されないはずです。その目的は、その行の重複を削除してそれぞれが1回だけ発生するようにするだけでなく、その行が入力で重複している場合にその行のすべてのインスタンスを削除することです。

4

1 に答える 1

3

基本的に、テキストファイルから行を削除する唯一の方法は、コピーにそれらの行がない状態でファイルをコピーすることです。通常はこの順序で何かになります：

while (fgets(buffer, size, infile))
    if (search(your_hashtable, buffer) == NOT_FOUND) {
        fputs(line, outfile);
        insert(your_hashtable, buffer);
    }

いくつかのストレージスペースを節約したい場合は、完全な行の代わりにハッシュを保存することができます。理論的には、ハッシュの衝突が原因で失敗する可能性がありますが、SHA-256のような暗号化ハッシュを使用する場合、衝突の可能性は、CPUエラーが原因で文字列の比較が間違って行われる可能性よりもおそらく遅くなります。その上、SHA-256との衝突を見つけた場合、それだけで少なくとも少しの名声を得ることができます（幸運ではないにしても）。

編集：@Zackがほのめかしたように、ハッシュサイズの状況は基本的に、衝突の可能性を受け入れるかどうかを決定することです。暗号化された256ビットハッシュを使用すると、可能性は非常に低く、検討する価値はほとんどありません。これをたとえば128ビットハッシュに減らすと、可能性はかなり高くなりますが、ほとんどの実用的な目的にはまだ十分に小さいです。一方、たとえば32ビットCRCに減らすと、データが重要である場合に受け入れられるよりも、衝突の可能性が高くなる可能性があります。

もう1つの可能性について言及する必要があります。別の可能性は、ハイブリッドのビットを使用することです。32ビットCRC（計算が非常に高速です）のようなものを、ファイル内のその行が始まるオフセットとともに格納します。ファイルが4Gを超えない場合は、両方を8バイトで保存できます。

この場合、作業方法は少し異なります。まずCRCを計算し、ほとんどの場合、ファイルにない場合は、ファイルを出力にコピーして、それらの値をハッシュテーブルに挿入します。それがすでにテーブルにある場合は、おそらく同一の行に戻ってそれを読み戻し、現在の行と比較します。それらが一致する場合は、元の場所に戻り、次の行に進みます。それらが一致しない場合は、現在の行を出力にコピーし、そのオフセットをハッシュテーブルに追加します。

編集2：今のところ、ファイルが十分に小さいので、すべてをメモリに合理的に収めることができると仮定しましょう。その場合、行とそれが発生した行番号を保存できます。行がすでに保存されている場合は、その行番号を-1に変更して、重複していて出力に表示されないようにすることができます。

C ++では（関連するデータ構造を定義しているため）、次のようになります。

std::string line;

typedef std::map<std::string, int> line_record;

line_record lines;
int line_number = 1;

while (std::getline(line, infile)) {
    line_record::iterator existing = lines.find(line);
    if (existing != lines.end()) // if it was already in the map
        existing->second = -1;    // indicate that it's duplicated
    else
        lines.insert(std::make_pair(line, line_number); // otherwise, add it to map
    ++line_number;
}

さて、それは行を読み取り、各行について、それがすでにマップにあるかどうかをチェックします。そうである場合は、line_numberを-1に設定して、出力に表示されないことを示します。そうでない場合は、行番号とともにマップに挿入されます。

line_record::iterator pos;

std::vector<line_record::iterator> sortable_lines;

for (pos=lines.begin(); pos != lines.end(); ++pos)
    if (pos->second != -1)
        sortable_lines.push_back(pos);

これは、マップへのイテレータのベクトルとして設定さsortable_linesれるため、行全体をコピーする代わりに、イテレータ（基本的にはポインタのような）をそれらの行にコピーします。次に、イテレータをそこにコピーしますが、行番号が-1でない行に対してのみです。

std::sort(sortable_lines.begin(), sortable_lines.end(), by_line_number());

struct by_line_number {
     bool operator()(line_record::iterator a, line_record::iterator b) { 
         return a->second < b->second;
     }
};

次に、これらのイテレータを行番号で並べ替えます。

for (int i=0; i<sortable_lines.size(); i++)
     outfile << sortable_lines[i]->first << "\n";

最後に、各行を元の行番号順にコピーして出力ファイルにコピーします。

于 2012-04-17T23:02:07.970 に答える