c - 使用c检测文件上的重复行

Question

我有一个包含大约 (15000-25000) 行（固定大小）的 csv 文件，我想知道如何使用 c 语言检测重复的行。

输出示例如下：

0123456789;CUST098WZAX;35

我没有记忆或时间限制，所以我想要最简单的解决方案。

谢谢你的帮助。

Answer 1

#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;

while (fgets(buffer, sizeof buffer, stdin)) {
        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);
                *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 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;
}

Answer 2

我不确定这是否是最简单的解决方案，但是...

如果每个条目看起来像这样：

0123456789;CUST098WZAX;35

...并且最后两个字符始终是来自00-的值99，您可以使用此值来索引存储桶。这个桶是 100 个数组中的一项（即 0-99，就像值一样），每个都指向存储属于该桶的字符串的结构的链表。

将字符串分类到桶中后，识别重复项所需的完整字符串比较的数量（希望）大大减少 - 只需比较同一桶中的字符串。

如果所有条目具有相同的值，这会将所有条目放在同一个桶中，仅在比较步骤中将此方法降级为 O(n^2)。但是假设值的分布不同，这种方法在实践中会更快。

（当然，我刚刚描述了一个哈希表，但它具有比通常使用的更天真的哈希函数。）

Answer 3

最简单的算法：

1. 将原始文件作为行数组 A 加载到内存中。
2. 创建一个相同大小的单独数组 B。
3. 遍历 A。对 B 中的当前行进行线性搜索。如果不存在，将其添加到 B 和输出文件中。

这是非常简单、残酷、低效的 O(n^2) 解决方案。假设你有基本的 C 技能，实现起来非常简单。

顺便说一句，如果顺序无关紧要，您可以对文件进行排序，然后任务就更简单了。您只需首先对文件进行排序，然后为最后一行设置变量，您可以根据该变量检查当前，如果它等于最后一个则跳过当前。