文本文件去除重复行的程序要怎么做才高效？

Question

本帖最后由 ynduanlian 于 2013-02-16 15:48:41 编辑

Answer 1

方法很多，基本思想就是做Hash。

Answer 2

本帖最后由 bcrun 于 2013-02-22 14:41:15 编辑

  

Answer 3

http://www.vbgood.com/thread-90704-2-1.html
15楼，效果非常理想，希望能带给你帮助。

Answer 4

仙剑他自己估计都没测试过，用dictionary要比他那个快的多

Answer 5

为什么这个需求不适合排序和可能不适合 Hash 方案：首先注意，这个需求的数据处理是一次性的。1 排序包含了比较和顺序排列两个操作。而对于这个需求，比较已经足够。因为知道是否已有相同记录，就可以决定当前记录的去留。附加的排列顺序是不必要的。2 Hash 的做法，是付出一次大运算量，来换取多次比较时的效率。也就是对所有待比较的数据对象计算出 Hash 值，作为比较的基准。对于这里一次性数据处理，计算 Hash 再比较相比直接比较付出的代价可能还要大。这与文本中的行数相关。行数少时，就不划算。极端的例子，如果只有 2 行，计算出 Hash 值来进行比较，显然不如直接比较。比较的计算量是随行数非线性增加的，当行数达到一个临界值时，Hash 的计算加比较计算量就会与直接比较更少。因此，需要做一个设定某些边界条件的评估（例如预期的重复率，极端的情况是所有行都相同，这样永远是 2 行之间的比较，因为从第二行起直至当前行的上一行，都被抛弃，不需要比较）。

Answer 6

此外，Hash 方案还有一个碰撞率问题。也就是说，有极小的概率，将不同的内容误判为相同，而错误地丢弃。

Answer 7

不知道这个项目肯投入多少？
如果是不重视，随便写写就算了。不要纠结什么算法。
我说说我的思路：
如果每一行字符很多，又有巨多行，可以考虑这个方案：
每行按字符生成一个Hash码，并将Hash码存储为B-树+索引表结构便于检索，
下一行生成Hash码后，先到B-树中检索Hash码值是否重复，如果重复，删掉本行，否则存储Hash码。
至于删除操作，还可以进一步优化。
至于为什么要用B-树+索引表，是因为巨量信息检索最快。
至于和dictionary比谁快，这个要看情况。

Answer 8

如果行数很多，各行相似度很高（长度相同，只有个别字符不同），重复率很低，则最适合用 Hash 方案。否则，就不一定。例如，如果是自然文本，各行长度不一，文字各式各样。则采用先比长度，再逐字符比较的方式，部分比较在长度上不匹配，另外的大多数行，只比了几个字符就不同了。这种情况下，直接比较，比计算 Hash 再比可能更快。

Answer 9

生成Hash码的算法也很讲究。不是调用一些开源的方法就完了。
话说也快十年没接触过所谓的算法了，现在都忘了当年学的东西了。
好了，不展开具体算法了，深怕误人子弟。

Answer 10

记得当年Google编程大赛还是什么大赛上好像有道类似的题目，我只记得大概，不记得获胜算法了。
坛子上的老人有知道的，请拿出来讲讲。
在此，替众小菜们谢过了！

Answer 11

仅供参考//文件1中的内容排序并去重,结果保存到文件2中
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCHARS 128      //能处理的最大行宽,包括行尾的\n和字符串尾的\0
int MAXLINES=10000,MAXLINES2;
char *buf,*buf2;
int c,n,hh,i,L;
FILE *f;
char ln[MAXCHARS];
int ignore_case=0;
int icompare(const void *arg1,const void *arg2) {
   return stricmp((char *)arg1,(char *)arg2);
}
int compare(const void *arg1,const void *arg2) {
   return strcmp((char *)arg1,(char *)arg2);
}
int main(int argc,char **argv) {
    if (argc<3) {
        printf("Unique line. Designed by [email protected]. 2012-08-20\n");
        printf("Usage: %s src.txt uniqued.txt [-i]\n",argv[0]);
        return 1;
    }
    if (argc>3) ignore_case=1;//若存在命令行参数3，忽略大小写
    f=fopen(argv[1],"r");
    if (NULL==f) {
        printf("Can not find file %s!\n",argv[1]);
        return 1;
    }
    buf=(char *)malloc(MAXLINES*MAXCHARS);
    if (NULL==buf) {
        fclose(f);
        printf("Can not malloc(%d LINES*%d CHARS)!\n",MAXLINES,MAXCHARS);
        return 2;
    }
    n=0;
    hh=0;
    i=0;
    while (1) {
        if (NULL==fgets(ln,MAXCHARS,f)) break;//
        hh++;
        L=strlen(ln)-1;
        if ('\n'!=ln[L]) {//超长行忽略后面内容
            printf("%s Line %d too long(>%d),spilth ignored.\n",argv[1],hh,MAXCHARS);
            while (1) {
                c=fgetc(f);
                if ('\n'==c || EOF==c) break;//
            }
        }
        while (1) {//去掉行尾的'\n'和空格
            if ('\n'==ln[L] || ' '==ln[L]) {
                ln[L]=0;
                L--;
                if (L<0) break;//
            } else break;//
        }
        if (L>=0) {
            strcpy(buf+i,ln);i+=MAXCHARS;
            n++;
            if (n>=MAXLINES) {
                MAXLINES2=MAXLINES*2;
                if (MAXLINES2==1280000) MAXLINES2=2500000;
                buf2=(char *)realloc(buf,MAXLINES2*MAXCHARS);
                if (NULL==buf2) {
                    printf("Can not malloc(%d LINES*%d CHARS)!\n",MAXLINES2,MAXCHARS);
                    printf("WARNING: Lines >%d ignored.\n",MAXLINES);
                    break;//
                }
                buf=buf2;
                MAXLINES=MAXLINES2;
            }
        }
    }
    fclose(f);
    if (n>1) {
        if (ignore_case) qsort(buf,n,MAXCHARS,icompare);
        else qsort(buf,n,MAXCHARS,compare);
    }
    f=fopen(argv[2],"w");
    if (NULL==f) {
        free(buf);
        printf("Can not create file %s!\n",argv[2]);
        return 2;
    }
    fprintf(f,"%s\n",buf);
    if (n>1) {
        if (ignore_case) {
            hh=0;
            L=MAXCHARS;
            for (i=1;i<n;i++) {
                if (stricmp((const char *)buf+hh,(const char *)buf+L)) {
                    fprintf(f,"%s\n",buf+L);
                }
                hh=L;
                L+=MAXCHARS;
            }
        } else {
            hh=0;
            L=MAXCHARS;
            for (i=1;i<n;i++) {
                if ( strcmp((const char *)buf+hh,(const char *)buf+L)) {
                    fprintf(f,"%s\n",buf+L);
                }
                hh=L;
                L+=MAXCHARS;
            }
        }
    }
    fclose(f);
    free(buf);
    return 0;
}