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

Question

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

Для этого мне нужно комплексное решение. Предпочтительно в Java. Есть идеи? Благодаря!

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

Вы можете использовать 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 3

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

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

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

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

Answer 6

Если бы вы могли использовать UNIX команды оболочки вы могли бы сделать что-то вроде следующего:

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

Это перебирать весь файл и только пройти каждый уникальный случай раз в SED вызова. Таким образом, вы не делаете кучу поисков, которые вы делали раньше.

Answer 7

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

Answer 8

Есть два масштабируемые решения, в которых с помощью масштабируемого я имею в виду диска, а не памяти на основе, в зависимости должна ли процедура быть стабильной или нет, где по стабильному я имею в виду, что порядок после удаления дубликатов тоже самое. если масштабируемость не является проблемой, просто используйте память для такого же метода.

Для нестабильного решения сначала отсортируйте файл на диске. Это делается путем разделения файла на более мелкие файлы, сортировки меньших фрагментов в памяти и последующего объединения файлов в отсортированном порядке, где слияние игнорирует дубликаты.

Слияние может быть выполнено с использованием почти без памяти, сравнивая только текущую строку в каждом файле, поскольку следующая строка гарантированно будет больше.

Устойчивое решение немного сложнее. Сначала соберите файл в кусках по-прежнему, но в каждой строке укажите исходный номер строки. Затем во время «слияния» не нужно записывать результат , просто номера строк, которые нужно удалить.

Затем скопируйте исходный файл по строкам, игнорируя номера строк, которые вы сохранили выше.

Answer 9

Если заказ не имеет значения, то simplest way is shell scripting:

<infile sort | uniq > outfile 

Answer 10

Имеет ли значение, в каком порядке линия приходит, и сколько дубликатов вы рассчитываете увидеть?

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

Answer 11

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

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 12

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

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

Answer 13

Я сделал два предположения для этого эффективного решения:

1. Существует Капля эквивалент линии или мы можем обработать его как двоичный
2. Мы можем сохранить смещение или указатель на начало каждой строки.

Основываясь на этих предположениях решения является: 1.read линии, сохранить длину в HashMap, как ключ, так что у нас есть более легкий HashMap.Сохраните список как запись в hashmap для всех строк, имеющих указанную длину в ключе. Построение этого хэшмапа - O (n). При сопоставлении смещений для каждой строки в хэш-карте сравните строки blob со всеми существующими записями в списке строк (смещения) для этой длины ключа, за исключением записи -1 как offset.if, найденный дубликат, удаляет обе строки и сохраняет смещение -1 в тех местах в списке.

Так считает сложность и использование памяти:

Hashmap памяти, пространство сложности = O (п), где п число строк

Время Сложности - если нет дубликатов, но все ровные линии длины не считая длину каждая строка = m, рассмотрим no из строк = n, то это будет O (n). Поскольку мы предполагаем, что мы можем сравнить blob, m не имеет значения. Это был худший случай.

В других случаях мы сохраняем при сравнении, хотя у нас будет мало дополнительного места в хэшмапе.

Кроме того, мы можем использовать mapreduce на стороне сервера для разделения набора и последующего объединения результатов. И используя длину или начало строки в качестве ключевого ключа.

Answer 14

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