如何找出两个大文件中的数据不同部分
问题描述:对比两个大于4G的日志文件A和B,如何高效的找出A和B中的数据不同部分。
整体思路:
第一步:文件分割;将大文件分割成多个小文件。本文采用哈希函数来分割大文件,扫描文件A,对每行字符求hash(url) % M,url是文件中的一行字符串,本文中的hash函数取JDK自带的hashCode方法,M表示分解的文件数目。根据所得的值,将url写入到对应的小文件中,如hash(url) % M = 4,则写入第四个文件中。如此,大文件A可以分为<a(0),a(1),a(2),...a(M-1)>,同理,大文件B可以分为<b(0),b(1),...b(M-1)>。可能相同的url必然都在对应的小文件中,也就是说,我们只需要寻找对应的小文件中的不同部分,然后归并所有的不同部分就是整个两个大文件的数据不同部分。
第二步:证明:可能相同的url必然都在对应的小文件中
假设X为文件A中的某行字符串,Y为文件B中的某行字符串,X.equals(Y) == true,则hash(X) == hash(Y), hash(X) % M == hash(Y) % M,则令k = hash(X) % M,则X必然在a(k)中,Y必然在b(k)中。
第三步:hash统计。统计小文件a(i)和b(i)中的不同部分,最后归并。代码如下:
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Set; public class TestBigData { // 分割的文件数 private static final int CUTTED_FILE_NUM = 30; //文件后缀名 private static final String FILE_EXTENSIONS = ".log"; //回车换行 private static final String NEWLINE ="\r\n"; /** * 输入大文件的路径,根据Hash函数讲大文件分割成若干个小文件 * * @param sourceFilePath * @param destinationFilePath */ public static void hashCutFile(String sourceFilePath, String destinationDirPath) { File fr = new File(sourceFilePath); BufferedReader br = null; BufferedWriter bw = null; String[] filePath = new String[CUTTED_FILE_NUM]; for (int i = 0; i < filePath.length; i++) { filePath[i] = destinationDirPath + i + FILE_EXTENSIONS; } String[] split = new String[2]; try { br = new BufferedReader(new FileReader(fr)); String line = br.readLine(); while (line != null) { // 数据格式为00001016114116820131725061748117041361&4580337030|||112050 // 规范化数据 split = line.split("\\|\\|\\|"); String url = split[0]; // 采用字符串自带的hashCode作为Hash函数 int hashcode = new Integer(url.hashCode()); int hashResult = hashcode % CUTTED_FILE_NUM; if (hashResult < 0) { hashResult = hashResult + CUTTED_FILE_NUM; } bw = new BufferedWriter(new FileWriter(new File( filePath[hashResult]), true)); bw.write(url); bw.write(NEWLINE); bw.close(); line = br.readLine(); } } catch (Exception e) { e.printStackTrace(); } finally { try { br.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } } /** * 查找两个文件中不同的内容 * * @param fileA * @param fileB */ public static List<String> findDifference(String fileA, String fileB) { List<String> partialResult = new ArrayList<String>(); File frA = new File(fileA); File frB = new File(fileB); BufferedReader brA = null; BufferedReader brB = null; List<String> listA = new ArrayList<String>(); List<String> listB = new ArrayList<String>(); Set<String> hashset = new HashSet<String>(); try { brA = new BufferedReader(new FileReader(frA)); brB = new BufferedReader(new FileReader(frB)); // 把fileA的内容读入到listA中 String line = brA.readLine(); while (line != null) { listA.add(line); line = brA.readLine(); } line = null; // 把fileB的内容读入到listB中 line = brB.readLine(); while (line != null) { listB.add(line); line = brB.readLine(); } } catch (IOException e) { e.printStackTrace(); } finally { try { brA.close(); brB.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } hashset.addAll(listB); for (int i = 0; i < listA.size(); i++) { String elemA = listA.get(i); if (!hashset.contains(elemA)) { partialResult.add(elemA); } } hashset.clear(); hashset.addAll(listA); for (int i = 0; i < listB.size(); i++) { String elemB = listB.get(i); if (!hashset.contains(elemB)) { partialResult.add(elemB); } } return partialResult; } /** * * @param file * @return */ public static List<String> findDifference(String file) { List<String> partialResult = new ArrayList<String>(); File fr = new File(file); BufferedReader br = null; try { br = new BufferedReader(new FileReader(fr)); // 把file的内容读入到list中 String line = br.readLine(); while (line != null) { partialResult.add(line); line = br.readLine(); } } catch (IOException e) { e.printStackTrace(); } finally { try { br.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } return partialResult; } /** * list1和list2求交集 * * @param list1 * @param list2 * @return */ public static List<String> Intersection(List<String> list1, List<String> list2) { List<String> list = new ArrayList<String>(); Set<String> hashSet = new HashSet<String>(); hashSet.addAll(list2); for (int i = 0; i < list1.size(); i++) { String temp = list1.get(i); if (hashSet.contains(list1.get(i))) { list.add(temp); } } return list; } /** * 求List1与List2的差集 list1 - list2 * * @param list1 * @param list2 * @return */ public static List<String> Complement(List<String> list1, List<String> list2) { List<String> list = new ArrayList<String>(); Set<String> hashSet = new HashSet<String>(); hashSet.addAll(list2); for (int i = 0; i < list1.size(); i++) { String temp = list1.get(i); if (!hashSet.contains(temp)) { list.add(temp); } } return list; } /** * 归并所有小文件中所有不相同的内容 * * @param dirAPath * 大文件A对应的分割后的小文件目录 * @param dirBPath * 大文件B对应的分割后的小文件目录 * @return */ public static Set<String> mergeDifferenceList(String dirAPath, String dirBPath) { Set<String> resultSet = new HashSet<String>(); File dirA = new File(dirAPath); File dirB = new File(dirBPath); File[] Afiles = dirA.listFiles(); File[] Bfiles = dirB.listFiles(); String Afiletemp = dirA.getAbsolutePath(); String Bfiletemp = dirB.getAbsolutePath(); List<String> AfilesPath = new ArrayList<String>(); List<String> BfilesPath = new ArrayList<String>(); //存放A和B的交集结果 List<String> intersectionList = new ArrayList<String>(); //存放A - A与B的交集 List<String> complementListA = new ArrayList<String>(); //存放B - A与B的交集 List<String> complementListB = new ArrayList<String>(); for (int i = 0; i < Afiles.length; i++) { AfilesPath.add(Afiles[i].getName()); } for (int i = 0; i < Bfiles.length; i++) { BfilesPath.add(Bfiles[i].getName()); } intersectionList = Intersection(AfilesPath, BfilesPath); for (int i = 0; i < intersectionList.size(); i++) { resultSet.addAll(findDifference(Afiletemp + "\\" + intersectionList.get(i), Bfiletemp + "\\" + intersectionList.get(i))); } complementListA = Complement(AfilesPath, intersectionList); complementListB = Complement(BfilesPath, intersectionList); for (int i = 0; i < complementListA.size(); i++) { resultSet.addAll(findDifference(Afiletemp + "\\" + complementListA.get(i))); } for (int i = 0; i < complementListB.size(); i++) { resultSet.addAll(findDifference(Bfiletemp + "\\" + complementListB.get(i))); } return resultSet; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub long t1 = System.currentTimeMillis(); String fileA = "C:/Users/jim/Desktop/big data/sourceFile1.log"; String fileB = "C:/Users/jim/Desktop/big data/sourceFile2.log"; // String fileA = "C:/Users/jim/Desktop/big data/新建文本文档.txt"; // String fileB = "C:/Users/jim/Desktop/big data/新建文本文档 (2).txt"; String destinationA = "C:/Users/jim/Desktop/big data/destinationA/"; String destinationB = "C:/Users/jim/Desktop/big data/destinationB/"; Set<String> hashset = new HashSet<String>(); hashCutFile(fileA, destinationA); hashCutFile(fileB, destinationB); hashset = mergeDifferenceList(destinationA, destinationB); for (Iterator<String> it = hashset.iterator(); it.hasNext();) { System.out.println(it.next()); } long t2 = System.currentTimeMillis(); System.out.println("时间t= " + (t2 - t1) + "ms"); } }
相关推荐
hadoop2面试题 - 迅速在两个含有大量数据的文件中寻找相同的数据.pdf
给出两个以行为单位文本文件的差集的命令行工具。 功能为输出当前目录下在文本文件prog中且不在文本文件list中的行。 可以用重定向将结果输出到文件中,比如: lackof >result 注意文件无后缀名 比如文件prog中有4行...
有一个问题就是,如果两个文件排序不一样的话,会出问题 第二种:grep命令法 命令如下:grep -vwf file1 file2 统计file1中没有,file2中有的行 具体使用环境以后再补充,今天先记录到这里。 您可能感兴趣的文章:...
利用VC6.0开发的小程序,比对两个不同的EXCEL中相同项中的不同内容并罗列出来,可以用来查看某EXCEL文件相对于原来的版本是否有未知的修改
适合初学数据结构 ...设计学校的平面图,至少包括10个以上景点(场所),每两个景点间可以有不同道路,且路长也可能不同,找出在游人所在景点到其他景点的最短路径,或游人输入的任意两个景点的最短路径。
大家都知道shell在文本处理上确有极大优势,比如多文本合并、去重等,但是最近遇到了一个难搞的问题,即两个大数据量文件去重。下面来看看详细的介绍吧。 要求 有txt文件A.txt和B.txt。 其中A为关键词和搜索量,以...
两个文件对比重复号码,对比不重复号码,单个文件找出重复的号码,找出不重复的号码,数据去重,发短信的号码整理助手 具体使用技巧参考博客:https://blog.csdn.net/bbyn1314/article/details/89788189
对比excel表格的两列数据之间的差异,找出他们的不同的数据输出结果。
对比出两个文本文件不同之处和相同之处(用一个TXT文件列出),MD5对比 批量文件加解密功能如下: 用任意字符数字对任意文件加解密 批量文件打包释放功能如下: 将多个文件打包成一个并且可以释放出来,可对打包...
1. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 2. 有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你...
这两个步骤主要的操作有两个,一个是从一个数组中找出另一个数组的位置,类似于 String 类中的 indexOf 的功能,另一个是从一个数组中提取出另一个数组, 类似于 String 类中的 substring 的功能,为此我们可以专门...
本软件提供了45大类共几百种针对txt文本文件的全文或者每一行的批量处理或者批量替换...43.找出两个txt文档中内容相同的部分并提取出来顺序保存 44.批量随机位置随机插入内容 45.剔除列表文件中重复数据 ……………
7.8找出一个二维数组中的鞍点,即该位置上的元素在该行上最大,在该列上最小。也可能没有鞍点。 38 7.9有15个数按从小到大的顺序存放在一个数组中。输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。...
excel VBA实现两个excel文件所有worksheet单元格做对比,并找出差异,将差异进行着重显示,对于数据量非常在和对数据要求高的场景将会大大缩减人工对比的时间
数据库原理实验指导书 实验名称:试验一:SQL语言嵌套查询和数据更新操作 所属课程:数据库原理 ...40. 选做:将数据插入SPJ数据库中的四个表S,P,J,SPJ中,并以.SQL文件和.txt文件的形式保存在磁盘
数据指纹就是一个文件内容的特征,理论上是没有重复的,出现重复就只有一种可能,就是文件复制前、后的两个文件,数据指纹会相同。数据指纹与文件名没有关系。 操作前准备: 无需要准备 操作步骤: 数据扫描 在...
>比较合并两个文件 >在文件比较窗口中直接编辑文件 >当文件内容改变时文件比较窗口自动更新比较结果 >在文件比较窗口中查找/替换 >查找上一个/下一个不同的文本块 >将所有相同/不同的行拷贝到剪贴...
这个软件能够比较两个文件夹中有哪些文件不同,还能将另一个文件夹中的不同文件导入进来,也可使两个文件夹完全相同(只改变部分文件就可办到,而不用复制,花费的时间短),也可以做为备份文件夹更新软件。...
简单来说,这个模式提供两个功能:执行Python代码,接受文件上传下载。 为什么是这两个功能的组合? 可以看目前最火的一条测试结果,和数据科学相关: 作者首先上传一个CSV格式数据集,然后问ChatGPT都能怎么分析或...