-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 回答