26

作为我正在处理的项目的一部分，我想清理我生成的重复行条目的文件。然而，这些重复通常不会彼此靠近。我想出了一种在 Java 中这样做的方法（基本上是复制文件，然后使用嵌套的 while 语句将一个文件中的每一行与另一个文件中的每一行进行比较）。问题是我生成的文件非常大并且文本很重（大约 225k 行文本，大约 40 兆）。我估计我目前的流程需要 63 个小时！这绝对不能接受。

但是，我需要一个集成的解决方案。最好用Java。有任何想法吗？谢谢！

4

15 回答 15

39

嗯... 40 兆似乎足够小，您可以构建一条Set线，然后将它们全部打印出来。这将比执行 O(n 2 ) I/O 工作快得多。

它会是这样的（忽略异常）：

public void stripDuplicatesFromFile(String filename) {
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    Set<String> lines = new HashSet<String>(10000); // maybe should be bigger
    String line;
    while ((line = reader.readLine()) != null) {
        lines.add(line);
    }
    reader.close();
    BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
    for (String unique : lines) {
        writer.write(unique);
        writer.newLine();
    }
    writer.close();
}

如果顺序很重要，您可以使用 aLinkedHashSet而不是 a HashSet。由于元素是通过引用存储的，因此与实际数据量相比，额外链表的开销应该是微不足道的。

编辑：正如 Workshop Alex 指出的，如果您不介意制作一个临时文件，您可以在阅读时简单地打印出这些行。这允许您使用简单HashSet的而不是LinkedHashSet. 但我怀疑你会注意到像这样的 I/O 绑定操作的区别。

于 2009-06-15T13:18:08.817 回答
16

好的，大多数答案有点愚蠢和缓慢，因为它涉及向某些哈希集或其他内容添加行，然后再次将其从该集中移回。让我用伪代码展示一下最优解：

Create a hashset for just strings.
Open the input file.
Open the output file.
while not EOF(input)
  Read Line.
  If not(Line in hashSet)
    Add Line to hashset.
    Write Line to output.
  End If.
End While.
Free hashset.
Close input.
Close output.

请各位，不要让它变得比需要的更困难。:-) 甚至不用担心排序，你不需要。

于 2009-06-15T13:52:24.650 回答
10

类似的方法

public void stripDuplicatesFromFile(String filename) {
    IOUtils.writeLines(
        new LinkedHashSet<String>(IOUtils.readLines(new FileInputStream(filename)),
        "\n", new FileOutputStream(filename + ".uniq"));
}
于 2009-06-16T20:30:07.057 回答
4

像这样的东西，也许：

BufferedReader in = ...;
Set<String> lines = new LinkedHashSet();
for (String line; (line = in.readLine()) != null;)
    lines.add(line); // does nothing if duplicate is already added
PrintWriter out = ...;
for (String line : lines)
    out.println(line);

LinkedHashSet保持插入顺序，而不是HashSet（虽然查找/插入速度稍快）将重新排序所有行。

于 2009-06-15T13:20:46.877 回答
3

您可以在 Collections 库中使用 Set 在您阅读文件时存储唯一的、可见的值。

Set<String> uniqueStrings = new HashSet<String>();

// read your file, looping on newline, putting each line into variable 'thisLine'

    uniqueStrings.add(thisLine);

// finish read

for (String uniqueString:uniqueStrings) {
  // do your processing for each unique String
  // i.e. System.out.println(uniqueString);
}
于 2009-06-15T13:18:23.857 回答
3

如果顺序无关紧要，最简单的方法是 shell 脚本：

<infile sort | uniq > outfile
于 2009-06-15T13:26:08.377 回答
2

尝试一个简单的 HashSet 来存储您已经阅读的行。然后遍历文件。如果您遇到重复项，它们将被忽略（因为 Set 只能包含每个元素一次）。

于 2009-06-15T13:19:18.863 回答
2
  • 读入文件，存储行号和行：O(n)
  • 按字母顺序排序：O(n log n)
  • 删除重复项：O(n)
  • 将其排序为其原始行号顺序：O(n log n)
于 2009-06-15T13:23:35.810 回答
1

哈希集方法是可以的，但是您可以对其进行调整，使其不必将所有字符串存储在内存中，而是一个指向文件中位置的逻辑指针，这样您就可以在需要时返回读取实际值。

另一种创造性的方法是在每行附加行号，然后对所有行进行排序，删除重复项（忽略应该是数字的最后一个标记），然后按最后一个标记再次对文件进行排序并将其删除在输出中。

于 2009-06-15T13:21:39.713 回答
0

如果您可以使用 UNIX shell 命令，您可以执行以下操作：

for(i = line 0 to end)
{
    sed 's/\$i//2g' ; deletes all repeats
}

这将遍历您的整个文件，并且每次 sed 调用仅传递每个唯一事件一次。这样，您就不会进行以前做过的大量搜索。

于 2009-06-15T13:21:39.713 回答
0

有两种可扩展的解决方案，其中可扩展的意思是磁盘而不是基于内存的，这取决于过程是否应该稳定，其中稳定的意思是删除重复项后的顺序是相同的。如果可伸缩性不是问题，那么只需将内存用于相同的方法。

对于不稳定的解决方案，首先对磁盘上的文件进行排序。这是通过将文件拆分为较小的文件，对内存中的较小块进行排序，然后按排序顺序合并文件来完成的，其中合并忽略重复项。

合并本身可以通过仅比较每个文件中的当前行来完成，几乎不使用内存，因为保证下一行更大。

稳定的解决方案稍微复杂一些。首先，像以前一样按块对文件进行排序，但在每行中注明原始行号。然后，在“合并”期间不要费心存储结果，只需删除要删除的行号。

然后逐行复制原始文件，忽略上面存储的行号。

于 2009-06-15T13:25:17.663 回答
0

行的顺序是否重要，您希望看到多少重复？

如果不是这样，并且如果您指望很多骗子（即阅读多于写作），我还会考虑并行化哈希集解决方案，将哈希集作为共享资源。

于 2009-06-15T13:45:28.253 回答
0

我对这个有效的解决方案做了两个假设：

  1. 有一个 Blob 等价于 line 或者我们可以将它处理为二进制
  2. 我们可以保存偏移量或指向每行开头的指针。

基于这些假设的解决方案是： 1.读取一行，将hashmap中的长度保存为key，这样我们就有了更轻量的hashmap。将列表保存为哈希图中的条目，用于键中提到的所有具有该长度的行。构建这个哈希图是 O(n)。在映射哈希图中每一行的偏移量时，将行 blob 与行列表中的所有现有条目（偏移量）进行比较，以获取此键长度，但条目 -1 作为偏移量除外。如果发现重复，则删除两行并保存偏移量 - 1 在列表中的那些地方。

所以考虑复杂性和内存使用：

Hashmap 内存，空间复杂度 = O(n) 其中 n 是行数

时间复杂度 - 如果没有重复但所有等长的线都考虑到每条线的长度 = m，则考虑线数 =n，那么这将是 O(n)。因为我们假设我们可以比较 blob ，所以 m 无关紧要。那是最坏的情况。

在其他情况下，我们节省了比较，尽管我们在 hashmap 中需要很少的额外空间。

此外，我们可以在服务器端使用 mapreduce 来拆分集合并稍后合并结果。并使用长度或行首作为映射器键。

于 2015-05-16T00:00:01.230 回答
0 
void deleteDuplicates(File filename) throws IOException{
    @SuppressWarnings("resource")
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    Set<String> lines = new LinkedHashSet<String>();
    String line;
    String delims = " ";
    System.out.println("Read the duplicate contents now and writing to file");
    while((line=reader.readLine())!=null){
        line = line.trim(); 
        StringTokenizer str = new StringTokenizer(line, delims);
        while (str.hasMoreElements()) {
            line = (String) str.nextElement();
            lines.add(line);
            BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
            for(String unique: lines){
                writer.write(unique+" ");               
            }
            writer.close();
        }
    }
    System.out.println(lines);
    System.out.println("Duplicate removal successful");
}
于 2015-09-02T19:00:52.850 回答
0

这些答案都依赖于文件足够小以存储在内存中。

如果可以对文件进行排序，这是一种可用于任何大小文件的算法。

你需要这个库：https ://github.com/lemire/externalsortinginjava

我假设你从一个文件开始fileDumpCsvFileUnsorted，你最终会得到一个fileDumpCsvFileSorted经过排序且没有重复的新文件。

ExternalSort.sort(fileDumpCsvFileUnsorted, fileDumpCsvFileSorted);
int numDupes = 0;
File dupesRemoved = new File(fileDumpCsvFileSorted.getAbsolutePath() + ".nodupes");
String previousLine = null;
try (FileWriter fw = new FileWriter(dupesRemoved);
     BufferedWriter bw = new BufferedWriter(fw);
     FileReader fr = new FileReader(fileDumpCsvFileSorted);
     LineIterator lineIterator = new LineIterator(fr)
) {
  while (lineIterator.hasNext()) {
    String nextLine = lineIterator.nextLine();
    if (StringUtils.equals(nextLine, previousLine)) {
      ++numDupes;
      continue;
    }
    bw.write(String.format("%s%n", nextLine));
    previousLine = nextLine;
  }
}
logger.info("Removed {} dupes from {}", numDupes, fileDumpCsvFileSorted.getAbsolutePath());
FileUtils.deleteQuietly(fileDumpCsvFileSorted);
FileUtils.moveFile(dupesRemoved, fileDumpCsvFileSorted);

fileDumpCsvFileSorted现在创建的文件已排序，没有重复。

于 2021-02-05T02:35:07.303 回答