免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2320 | 回复: 5

请教文本处理的一个算法。 [复制链接]

论坛徽章:
0
发表于 2008-10-16 09:33 |显示全部楼层
有个文件里包含了几十万行的数据。现在需要找出这些行的最大公共子串,并且这个子串在每一行的起始位要求在同一位。
举个例子。
abda1234asdkj;fjdf;dsa
adab1234hjksniurfmdl;r
ruda1234urojasdfkljf;lasfklasj
rkaj1234rujfdljrjeljsdlajf
12381234urqjflajlfkjasd;fklja

这堆数据中的最大公共子串就是substr($line,5,4)

没办法,只会用c++来写啦:

int main(int argc,char** argv)
{
    if(argc != 2)
    {
        cout << "usage : " << argv[0] << " filename" << endl;
        exit(-1);
    }

    string filename(argv[1]);
    FILE *fp = fopen(filename.c_str(),"r");
    if(fp == NULL)
    {
        cout << filename << " open error!" << endl;
        exit(-1);
    }

    vector<string> v;
    char * line = NULL;
    size_t len = 0;
    ssize_t readlen = 0;
    while((readlen = getline(&line, &len, fp)) != -1)
    {
        v.push_back(string(line,readlen - 1));
    }
    fclose(fp);

    string public_str;
    for(long row = 0,col=0; row<v.size()&&col<20; ++row)
    {
        if( (row != 0) && (v[row][col] != v[row - 1][col]) )
        {
            public_str += ".";
            row = 0;
            col ++;
            continue;
        }
        if(row == v.size() - 1)
        {
            if(v[row][col] == v[row - 1][col])
            {
                public_str += v[row][col];
            }
            row = 0;
            col ++;
            continue;
        }
    }

    cout << public_str << endl;
    if(line != NULL)
    {
        free( line );
    }

}


我只匹配每行的前20位,最后的结果大概是:
....1234.............



[ 本帖最后由 lemboyz 于 2008-10-16 12:49 编辑 ]

论坛徽章:
23
15-16赛季CBA联赛之吉林
日期:2017-12-21 16:39:27白羊座
日期:2014-10-27 11:14:37申猴
日期:2014-10-23 08:36:23金牛座
日期:2014-09-30 08:26:49午马
日期:2014-09-29 09:40:16射手座
日期:2014-11-25 08:56:112015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:0315-16赛季CBA联赛之山东
日期:2017-12-21 16:39:1915-16赛季CBA联赛之广东
日期:2016-01-19 13:33:372015亚冠之山东鲁能
日期:2015-10-13 09:39:062015亚冠之西悉尼流浪者
日期:2015-09-21 08:27:57
发表于 2008-10-16 09:37 |显示全部楼层
原帖由 lemboyz 于 2008-10-16 09:33 发表
有个文件里包含了几十万行的数据。现在需要找出这些行的最大公共子串,并且这个子串在每一行的起始位要求在同一位。
举个例子。
abda1234asdkj;fjdf;dsa
adab1234hjksniurfmdl;r
rufda1234urojasdfkljf;las ...


rufda1234urojasdfkljf;lasfklasj
rukaj1234rujfdljrjeljsdlajf

这2行不是从第6位开始的么?

论坛徽章:
0
发表于 2008-10-16 09:37 |显示全部楼层
用shell有点悬......

论坛徽章:
9
2015亚冠之阿尔纳斯尔
日期:2015-09-10 16:21:162015亚冠之塔什干火车头
日期:2015-07-01 16:23:022015年亚洲杯之巴勒斯坦
日期:2015-04-20 17:19:46子鼠
日期:2014-11-13 09:51:26未羊
日期:2014-08-28 18:13:36技术图书徽章
日期:2014-02-21 09:30:15酉鸡
日期:2014-01-14 11:12:49天蝎座
日期:2013-12-09 17:56:53平安夜徽章
日期:2015-12-26 00:06:30
发表于 2008-10-16 09:51 |显示全部楼层
梯形逐次半分不知道怎么样

论坛徽章:
23
15-16赛季CBA联赛之吉林
日期:2017-12-21 16:39:27白羊座
日期:2014-10-27 11:14:37申猴
日期:2014-10-23 08:36:23金牛座
日期:2014-09-30 08:26:49午马
日期:2014-09-29 09:40:16射手座
日期:2014-11-25 08:56:112015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:0315-16赛季CBA联赛之山东
日期:2017-12-21 16:39:1915-16赛季CBA联赛之广东
日期:2016-01-19 13:33:372015亚冠之山东鲁能
日期:2015-10-13 09:39:062015亚冠之西悉尼流浪者
日期:2015-09-21 08:27:57
发表于 2008-10-16 11:08 |显示全部楼层

回复 #1 lemboyz 的帖子

try:

test.awk
  1. #! /usr/bin/awk
  2. NR == 1 {
  3.         s = $0
  4.         getline
  5.         l = length(s) < length($0) ? length(s) : length($0)
  6.         for(i = 1; i <= l; i ++)
  7.                 if ( substr(s, i, 1) == substr($0, i, 1) )
  8.                         a[i] = substr(s, i, 1)
  9.                 else
  10.                         a[i] = ""
  11.         next
  12. }
  13. {
  14.         s = l
  15.         l = length($0) < l ? length($0) : l
  16.         if ( l < s )
  17.                 for(i = l + 1; i <= s; i ++)
  18.                         delete a[i]
  19.         for(i = 1; i <= l; i ++)
  20.                 if ( a[i] != "" && substr($0, i, 1) != a[i] )
  21.                         a[i] = ""
  22. }
  23. END {
  24.         for(i = 1; i<=l; i ++)
  25.                 if ( a[i] != "" )
  26.                 {
  27.                         k = i
  28.                         for(j = i; a[j] != ""; j ++ )
  29.                                 b[k] = b[k] "" a[j]
  30.                         m = m < length(b[k]) ? length(b[k]) : m
  31.                         i = j
  32.                 }
  33.         for( i in b )
  34.                 if ( length(b[i]) == m )
  35.                         print "substr($line ,"i" ,"m") = "b[i]
  36. }
复制代码


awk -f test.awk urfile

论坛徽章:
0
发表于 2008-10-16 11:09 |显示全部楼层
有个想法:

先读取前两行,然后获取它的所有公共子串和起始位置,然后向下读取,并用这些公共子 串来匹配,如果有不匹配的子串,那么就删除这个公共子串

这样,到最后的时候,找出这些公共子串的最长的就可以了。

找前两行的公共子串的大概方法就是

  1. for(i=0;i<length(line1)-1;i++){
  2.   j=1;
  3.   while(substr(line2,i,j)==substr(line1,i,j)) j++;
  4.   if(j==1) continue;
  5.   j--;
  6.   a[i,j]=substr(line1,i,j)  #a是hash数组,其key是i,j的组合,即起始位置和长度的组合
  7. }
复制代码



匹配其他行的时候,先遍历数组a,取出子串的起始位置和长度,然后取出当前行的子串,比较一下,看看是不是匹配,如果不匹配,就从hash数组中删除这个子串的记录

不过,不知道这样效能是不是很差
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP