-2

在这个问题中： Detecting duplicate lines on file using 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：澄清：目的是在输入文件中查找所有重复项。当输入中有不止一个行的实例时，该行根本不应该出现在输出中。目的不仅是删除该行的重复项，因此每个仅出现一次，而且如果该行在输入中重复，则删除该行的所有实例。

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，那么如果数据非常重要，那么发生冲突的可能性可能比我乐意接受的要高。

我可能应该提到另一种可能性：另一种可能性是使用一些混合 - 存储类似 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 回答