使用C刪除文件中的所有重複行C

Question

在這個問題中： Detecting duplicate lines on file using c 我可以檢測到重複的行，但我們如何從我們的文件中刪除此行？

謝謝。

編輯：要添加我的代碼：

#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：澄清：目的是在輸入文件中查找所有重複項。當輸入中有多條線的實例時，該線不應出現在輸出的所有處。意圖不僅僅是刪除的重複的行，因此每行只出現一次，而是刪除全部行的實例（如果該行在輸入中重複）。

Answer 1

基本上，從文本文件中刪除行的唯一方法是在副本中複製沒有這些行的文件。通常是這樣的順序：

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，那麼碰撞的機率可能會高於我很樂意接受數據非常重要的機率。我應該再提一個可能性：另一種可能性是使用一點混合存儲器，就像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"; 

最後，我們將每行復制到輸出文件中，按照其原始行號順序排列。