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:澄清一下:目的是查找输入文件中的所有重复项。当输入中一行有多个实例时，该行根本不应出现在输出中。。其目的不仅仅是删除该行的重复项，以便每个行仅出现一次，而是删除该行的所有实例(如果该行在输入中重复)。 p>

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，并且绝大多数情况下，当它不在文件中时，您将文件复制到输出并将这些值插入到哈希中 table 。当它已经在表中时，您将查找可能相同的行，将其读回并与当前行进行比较。如果它们匹配，您将返回到原来的位置并前进到下一行。如果它们不匹配，则将当前行复制到输出，并将其偏移量添加到哈希表中。

编辑 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;
}

好的，读取行，对于每一行，它检查它是否已经在 map 中。如果是，它将 line_number 设置为 -1，以指示它不会出现在输出中。如果不是，则将其及其行号插入到 map 中。

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 设置为映射中的迭代器 vector ，因此我们只需将迭代器(本质上类似于指针)复制到这些行，而不是复制整行。然后它将迭代器复制到那里，但仅限于行号不是 -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";

最后，我们按照原始行号的顺序将每一行复制到输出文件。