Удаление повторяющихся строк в файле с использованием Java

Question

Как часть проекта, над которым я работаю, я бы хотел очистить файл, который я генерирую, от повторяющихся записей строк. Однако эти дубликаты часто не встречаются рядом друг с другом. Я придумал способ сделать это в Java (который в основном делал копию файла, а затем использовал вложенный оператор while для сравнения каждой строки в одном файле с остальной частью другого). Проблема в том, что мой сгенерированный файл довольно большой и тяжелый (около 225 тыс. Строк текста и около 40 мегабайт). Я считаю, что мой текущий процесс занимает 63 часа! Это определенно не приемлемо.

Однако для этого мне нужно интегрированное решение. Желательно на Яве. Есть идеи? Спасибо!

Answer 1

Хм ... 40 мегабайт кажется достаточно маленьким, чтобы вы могли построить Set из линий и затем распечатать их все обратно. Это было бы намного быстрее, чем работа O (n ² ).

Было бы что-то вроде этого (игнорируя исключения):

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();
}

Если порядок важен, вы можете использовать LinkedHashSet вместо HashSet. Поскольку элементы хранятся по ссылке, накладные расходы дополнительного связанного списка должны быть незначительными по сравнению с фактическим объемом данных.

Редактировать: Как отметил Алекс Семинар, если вы не возражаете против создания временного файла, вы можете просто распечатать строки по мере их чтения. Это позволяет вам использовать простой HashSet вместо LinkedHashSet. Но я сомневаюсь, что вы заметите разницу в операции ввода-вывода, подобной этой.

Answer 2

Хорошо, большинство ответов немного глупые и медленные, так как они включают добавление строк в некоторый хэш-набор или что-то в этом роде, а затем перемещение его обратно из этого набора снова. Позвольте мне показать наиболее оптимальное решение в псевдокоде:

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.

Пожалуйста, ребята, не усложняйте, чем нужно. :-) Даже не сортируйте, вам не нужно.

Answer 3

Аналогичный подход

public void stripDuplicatesFromFile(String filename) {
    IOUtils.writeLines(
        new LinkedHashSet<String>(IOUtils.readLines(new FileInputStream(filename)),
        "\n", new FileOutputStream(filename + ".uniq"));
}

Answer 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, который (хотя и немного быстрее для поиска / вставки) переупорядочивает все строки.

Answer 5

Если порядок не имеет значения, самый простой способ - это сценарии оболочки :

<infile sort | uniq > outfile

Answer 6

Вы можете использовать Set в библиотеке Collections для хранения уникальных видимых значений при чтении файла.

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);
}

Answer 7

• Прочитать в файле, сохранив номер строки и строку: O (n)
• Сортировка в алфавитном порядке: O (n log n)
• Удалить дубликаты: O (n)
• Сортировка в исходном порядке номеров строк: O (n log n)

Answer 8

Попробуйте простой HashSet, в котором хранятся строки, которые вы уже прочитали. Затем переберите файл. Если вы встречаете дубликаты, они просто игнорируются (поскольку набор может содержать каждый элемент только один раз).

Answer 9

Подход Hash Set в порядке, но вы можете настроить его так, чтобы не нужно было хранить все строки в памяти, а иметь логический указатель на местоположение в файле, чтобы вы могли вернуться к чтению действительного значения только в том случае, если вы нужно это.

Другой творческий подход - добавить к каждой строке номер строки, затем отсортировать все строки, удалить дубликаты (игнорируя последний токен, который должен быть номером), а затем снова отсортировать файл по последнему токену и чередуя его на выходе.

Answer 10

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");
}