Как убрать дубликаты строк в двух больших текстовых файлах по количеству появлений?

Question

У меня есть два больших текстовых файла с одинаковым количеством строк (9 миллионов строк, около 12 ГБ каждый файл). Поэтому они не могут быть загружены в память.

Строки в этих текстовых файлах, представленные в таблице, выглядят так:

Мне нужно удалите дубликаты в A.txt и B.txt и оставьте только наиболее частые комбинации для каждой строки из a.txt . В случае двух наиболее часто встречающихся строк с одинаковым количеством повторений программа должна выбрать строку, которая впервые появилась в тексте, и удалить все остальные.

В реальных файлах строки не просто (A, B, C, D , ... 1,6,7, ..) и каждая строка содержит около 2000 символов.

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

Answer 1

Как можно избежать одновременного считывания 2 × 12 ГБ в память, но при этом обрабатывать все данные?

Загружая эти 24 ГБ по частям и отбрасывая данные, которые вам больше не нужны, так как вы go. Поскольку ваши файлы основаны на строках, чтение и обработка построчно кажется разумным. Наличие 4000-и sh символов в памяти одновременно не должно создавать проблем на современных персональных компьютерах.

Объединение файлов

Требуется упорядочить конечный результат (или, возможно, даже отсортировать) по содержанию строки A.txt. Чтобы не потерять связь между строками в A.txt и B.txt при изменении их порядка, нам нужно сначала объединить их содержимое.

Сделать это путем

• , открыв оба файла пока не прочитав их
• открывая новый файл AB.txt для записи
• , повторяя следующее до тех пор, пока все A.txt и B.txt не будут обработаны:
  • чтение a строка A.txt
  • , читающая строку B.txt
  • , добавьте объединенное содержимое в качестве новой строки к AB.txt
  • , чтобы отменить то, что мы прочитали до сих пор. из памяти

Если вы знаете, что определенный символ (скажем, '\t') не может встречаться в A.txt, вы можете использовать его в качестве разделителя:

with \
        open("A.txt") as a_file, \
        open("B.txt") as b_file, \
        open("AB.txt", "w") as ab_file:
    for a_line, b_line in zip(a_file, b_file):
        # get rid of the line endings, whatever they are
        a_line, = a_line.splitlines()
        b_line, = b_line.splitlines()

        # output the combined content to AB.txt
        print(f"{a_line}\t{b_line}", file=ab_file)

(Обратите внимание, что это zip ведет себя "лениво" и возвращает генератор, а не читает файлы полностью и возвращает огромный список, как это было бы в Python 2.)

Если все строки в A.txt имеют одинаковую фиксированную длину, вам вообще не нужен разделитель. (Для сохранения вашего здравомыслия во время отладки вы все равно можете использовать его.) Если вы не знаете ни одного персонажа, который не может появиться в A.txt, вы можете создать csv.writer и используйте его writerow метод , чтобы записать строки в AB.txt. Он позаботится о необходимом экранировании или цитировании для вас.

Вы можете задаться вопросом, где шаг

отбрасывает то, что мы прочли из памяти

реализовано. Это происходит здесь неявно, потому что единственные переменные, которые содержат данные из файлов, a_line и b_line перезаписываются для каждой итерации.

Упорядочение объединенного файла

Для упорядочения всего файла мы должны полностью загрузить его в память, верно?

Нет. Ну, на самом деле да, но, опять же, не все сразу. Мы можем использовать внешнюю сортировку . Вы можете попробовать реализовать это самостоятельно в Python, или вы можете просто использовать UNIX инструмент командной строки sort ( справочная страница ), который делает именно это. В системе Linux или macOS она уже доступна. На Windows он должен быть включен в любой эмулятор UNIX, такой как Cygwin или MinGW. Если у вас уже установлена ​​Git с установщиком Git по умолчанию для Windows, вы можете использовать UNIX sort из включенного «Git Bash».

Обратите внимание, что из-за По порядку нашего содержимого в каждой строке файл будет отсортирован сначала по содержимому, полученному с A.txt, а затем (если он такой же) по содержимому, полученному с B.txt.

Подсчет

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

Что мы хочу сделать это:

• Для каждого блока последующих строк с одинаковым A-содержимым:
  • в пределах этого, для каждого блока последующих строк с таким же B-содержимым:
  • считать его строки
  • следить за тем, у какого B-контента, который еще просматривался (в блоке A-контента), было наибольшее количество строк
  • в конце блока A-контента: вывести строку с A-контентом и наиболее частым B-контентом для этого A-контента

Поскольку мы можем положиться на порядок, который мы установили выше, это приведет к желаемому результату.

Примерно так должно работать:

• читать строку
• разделить его на A-контент и B-контент
• , если A-контент такой же, как в предыдущей строке *:
  • если B-контент такой же, как в предыдущей строке *:
    • увеличить счетчик для текущей комбинации ab-контента
  • else (т. Е. если B-контент отличается от предыдущей строки):
    • запоминает, какой B-контент наиболее часто встречается на данный момент, и его подсчет
      • (это либо наиболее часто встречающийся ранее B-контент или тот, что в предыдущей строке)
    • сбросить счетчик для текущей комбинации ab-content
    • увеличить этот счетчик на единицу (для текущей строки)
    • где-то хранит B-контент, так что мы можем сравнить его с содержимым следующей строки в следующей итерации
• else (т. Е. Если A -content отличается от предыдущей строки) **:
  • выводит A-контент предыдущей строки и наиболее заметный B-контент из предыдущей строки
  • сбрасывает счетчик для текущая комбинация ab-content
  • сбросить информацию о том, что наиболее часто встречается в B-контенте t и его подсчет
  • хранят A-контент и B-контент текущей строки, поэтому их можно сравнить с данными следующей строки в следующей итерации
• повторять до тех пор, пока весь файл не будет обработан

* для первой строки, это неявно false

** также сделайте это, когда вы достигнете конца файл

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

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

Answer 2

Опираясь на ответ das-g , считая объединенные и отсортированные строки с вложенными groupby:

from itertools import groupby
from operator import itemgetter

# Combine and sort, in reality done like das-g described.
A = 'ABCDACADAEF'
B = '16781918216'
combined_and_sorted = sorted(zip(A, B))

# Count and produce the results
for a, agroup in groupby(combined_and_sorted, itemgetter(0)):
    bcounts = ((b, sum(1 for _ in group))
               for b, group in groupby(agroup, itemgetter(1)))
    print(a, max(bcounts, key=itemgetter(1))[0])

Вывод :

A 1
B 6
C 7
D 8
E 1
F 6

Answer 3

Эта опция не потребует всего файла в памяти, но должна будет содержать словарь с A в качестве ключей и несколько диктовок с B в качестве ключей. Это можно упростить, если вы могли бы иметь sh или классифицировать значения (присваивая значение int каждому уникальному A и каждому уникальному B).

Edit: словари были изменены для использования хешированных ключей для уменьшения памяти занимаемая площадь за счет использования ЦП и измененного вывода для отображения строк, которые нужно сохранить (поскольку исходные значения A и B скрыты)

Предполагается, что мой файл:

Lines,A.txt,B.txt
1,A,1
2,A,1
3,A,2
4,B,1
5,B,2

from collections import Counter
from csv import DictReader
_ = {}
_file = DictReader(open('abc.txt', 'r'), delimiter=',')

hash_to_line = {}
for row in _file:
    a = hash(row['A.txt'])
    b = hash(row['B.txt'])
    if a not in _:
        _[a] = Counter()
    if b not in _[a]:
        hash_to_line[(a, b)] = row['Lines']
    _[a][b] += 1

output = []
for A in _:
    _vals = list(_[A].values())
    _keys = list(_[A].keys())
    _max = max(_vals)

    _vals.index(_max)
    A, _[A][_keys[_vals.index(_max)]]
    output.append(hash_to_line[A, _keys[_vals.index(_max)]])
print('lines to keep:', output)

Замените печать с соответствующим запоминанием результатов.

Answer 4

Как я уже упоминал в комментариях, я думаю, что использование модуля shelve позволит вам делать то, что вы хотите.

Вот пример реализации и ее вывод. Обратите внимание , что я добавил четыре строки в конце A.txt и B.txt, чтобы убедиться, что было выбрано правильное значение, когда оно не было первым. Также обратите внимание на , который я оставил в коде разработки и отладки, так как вы определенно захотите удалить или отключить его перед запуском действительно больших входных файлов.

В виде таблицы два входных файла выглядят так:

 1 A 1
 2 B 6
 3 C 7
 4 D 8
 5 A 1
 6 C 9
 7 A 1
 8 D 8
 9 A 2
10 E 1
11 F 6
12 G 5
13 G 7
15 G 7
16 G 7

И, опять же, в виде таблицы, вот каковы будут два выходных файла, если они будут переписаны:

1 A 1
2 B 6
3 C 7
4 D 8
5 E 1
6 F 6
7 G 7

---

import glob
from operator import itemgetter, methodcaller
import os
import shelve


shelf_name = 'temp_shelf'
file_a_name = 'A.txt'
file_b_name = 'B.txt'


with open(file_a_name) as file_a, \
     open(file_b_name) as file_b, \
     shelve.open(shelf_name, flag='n', writeback=False) as shelf:

    for line, items in enumerate(zip(file_a, file_b)):
        x, fx = map(methodcaller('rstrip'), items)  # Remove line endings.
        d = shelf.setdefault(x, {})      # Each shelf entry is a regular dict.
        d[fx] = d.setdefault(fx, 0) + 1  # Update its value.
        shelf[x] = d                     # Update shelf.

        print('{!r} -> {!r}'.format(x, shelf[x]))

    # Show what ended up in shelf during development.
    print('\nFinal contents of shelf:')
    for k, d in shelf.items():
        print('  {!r}: {!r}'.format(k, d))

# Change file names to prevent overwriting originals during development.
file_a_name = 'A_updated.txt'
file_b_name = 'B_updated.txt'
comp_name = 'composite.txt'  # Used for development only.

# Update files leaving only most frequent combination.
with open(file_a_name, 'w') as file_a, \
     open(file_b_name, 'w') as file_b, \
     open(comp_name, 'w') as file_c, \
     shelve.open(shelf_name, flag='r') as shelf:

    for line, (k, d) in enumerate(shelf.items(), 1):
        file_a.write(k + '\n')
        fx = sorted(d.items(),  # Rev sort by number of occurrences.
                    key=itemgetter(1), reverse=True)[0][0]  # Most common fx.
        file_b.write(fx + '\n')
        file_c.write('{} {} {}\n'.format(line, k, fx))  # For development only.

# CLean up by removing shelf files.
for filename in glob.glob(shelf_name + '.*'):
    print('removing', filename)
    os.remove(filename)

print('\nDone')