ITPub博客

首页 > 应用开发 > IT综合 > 一个文件,内含一千万行字符串,每个字符串在1K以内,要求找出所有相反的串对

一个文件,内含一千万行字符串,每个字符串在1K以内,要求找出所有相反的串对

原创 IT综合 作者:dongyu2013 时间:2014-05-17 09:58:57 0 删除 编辑

一个文件,内含一千万行字符串,每个字符串在1K以内,要求找出所有相反的串对


一个文件,内含一千万行字符串,每个字符串在1K以内,要求找出所有相反的串对,如abc和cba。

当时怎么想的忘记了,现在重新思考一下,文件的大小上限是10G,不可能在内存操作了。考虑设计一种hash使得如果两个字符串维相反串能得出相同的hash值,然后用该hash将文件中的字符串散列到不同的文件中,再在各文件中进行匹配。比如这样的hash函数对字符串上所有字符的ascii求和,因为长度在1K以内,因此范围在int之内。更进一步,可以在上面那个hash后面再加一个字符串长度,可以得到更好的散列效果。(例如,a2b1c5,统计按照每个字母出现的次数进行一步的hash)

在各个单独文件中匹配时,如果采用的是第二种hash函数,那么该文件中的所有字符串都有相同的长度。如果hash效果好,那么这个文件应该小到可以在内存中进行操作了。将文件拷贝为两份,分别按照不同规则hash:第一份按前k位哈希,第二份将字符串的头尾进行颠倒后按前k位哈希(只是对于排序算法颠倒,不必实际颠倒)。这里的按前k位哈希只需要前k位相同能得到相同结果就好,比如第i位的ascii乘以2^i。两份拷贝中hash值相同的就很可能是要求的相反串对了,再进行实际匹配,工作量应该就可以接受了。

第二步,将第一份字符串放入hash_set中,然后将第二份的字符串以颠倒的字符串求hash_set,查看是否在hash_set中,注意字符串中字母完全相同的情况


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29012686/viewspace-1163147/,如需转载,请注明出处,否则将追究法律责任。

下一篇: binlog_format
请登录后发表评论 登录
全部评论

注册时间:2013-12-25

  • 博文量
    263
  • 访问量
    209208