使用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"; 

最后，我们将每行复制到输出文件中，按照其原始行号顺序排列。