Как избавиться от MemoryError при работе с большим словарем?

Question

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

for t in arrayOfTrigrams: 
    if t in trigrams: 
     trigrams[t] += 1 
    else: 
     trigrams[t] = 1 

Но данные очень большой - более 500 МБ сырых текстов, и я не знаю, как справиться с MemoryError. И в отличие от Python memoryerror creating large dictionary Я не создаю никаких неуместных вещей, каждая триграмма важна.

Answer 1

Дальнейшее редактирование - код включен Если вы в состоянии удерживать arrayOfTrigrams в памяти, см. Исходное решение внизу. Но, если вы не смогли создать arrayOfTrigrams (и я несколько скептически отношусь к тому, что вы получили такой далекий размер данных), вы все равно можете стрелять для создания словаря повторяющихся триграмм. Повторные биграммы всегда содержат повторяющиеся слова, а повторяющиеся триграммы содержат повторяющиеся биграммы. Обрабатывайте 500 МБ данных поэтапно. Сначала создайте набор повторяющихся слов. Используя это, создайте словарь повторных биграмм. Сначала сделайте необработанное частотное число биграмм, содержащих одно из повторяющихся слов, а затем отбросьте все, чей счет равен 1. Затем обработайте данные в третий раз, создав словарь повторяющихся триграмм. Опять же, сделайте необработанную частоту подсчета триграмм, которые содержат повторяющийся bigram (который должен быть небольшим подмножеством всех возможных триграмм), а затем отбросить те из словаря, окончательный счет которого равен 1. Таким образом, вы можете создать словарь без когда-либо, чтобы сохранить все триграммы в памяти сразу.

Доказательство концепции:

from collections import defaultdict 

chars = set('ABCDEFGHIJKLMNOPQRSTUVWXYZ') 

def cleanWord(s): 
    return ''.join(c for c in s if c in chars) 

f = open('moby dick.txt') #downloaded from Project Gutenberg: http://www.gutenberg.org/ebooks/2701 -- Thanks! 
words = f.read().split() 
f.close() 

words = [cleanWord(w.upper()) for w in words] 
words = [w for w in words if len(w) > 1 and not(w in set('AIOY'))] 

repeatedWords = defaultdict(int) 
for w in words: 
    repeatedWords[w] += 1 

repeatedWords = set(w for w in repeatedWords if repeatedWords[w] > 1) 

repeatedBigrams = defaultdict(int) 
for i in range(len(words) - 1): 
    x,y = words[i:i+2] 
    if x in repeatedWords or y in repeatedWords: 
     repeatedBigrams[x + ' ' + y] +=1 

repeatedBigrams = set(b for b in repeatedBigrams if repeatedBigrams[b] > 1) 

repeatedTrigrams = defaultdict(int) 

for i in range(len(words) - 2): 
    x,y,z = words[i:i+3] 
    if x + ' ' + y in repeatedBigrams and y + ' ' + z in repeatedBigrams: 
     repeatedTrigrams[x + ' ' + y + ' ' + z] +=1 

repeatedTrigrams = {t:c for t,c in repeatedTrigrams.items() if c > 1} 

Этот код поворачивает вверх 10016 триграмм, которые появляются более одного раза. В отличии от этого, когда я оцениваю

len(set(' '.join(words[i:i+3]) for i in range(len(words)-2))) 

Я получаю 188285, так что в этом несколько значительных естественном языке, например, только 10016/188285 = 5,3% от возможных триграмм повторяются триграммами. Предполагая, что для ваших данных справедливо соотношение, я считаю, что размер частотного словаря для повторяющихся триграмм будет составлять около 100 МБ.

---

оригинальное решение:

---

Ваш код и Ваш вопрос предполагает, что вы в состоянии держать arrayOfTrigrams в памяти, но не может создать словарь. Одним из возможных способов заключается в первый сортировать этот массив и создать счетчик частоты повторил триграмм:

arrayOfTrigrams.sort() 
repeatedTrigrams = {} 

for i,t in enumerate(arrayOfTrigrams): 
    if i > 0 and arrayOfTrigrams[i-1] == t: 
     if t in repeatedTrigrams: 
      repeatedTrigrams[t] += 1 
     else: 
      repeatedTrigrams[t] = 2 

После построения repeatedTrigrams вы могли бы использовать набор понимание:

uniques = {t for t in arrayOfTrigrams if not t in repeatedTrigrams} 

Затем t in uniques бы передать информацию что число t равно 1, что я бы заподозрил в истинности для подавляющего большинства триграмм. На этом этапе у вас есть все соответствующей информации частоты и может отбросить список триграмм, чтобы освободить часть памяти, что вы потребленный:

arrayOfTrigrams = None 

Answer 2

Мое первое предложение было бы не держать arrayOfTrigrams в памяти полностью , но используйте потоковое вещание.Вы читаете его откуда-то, так что вы можете контролировать, как вы его читаете. Здесь очень удобны генераторы Python. Давайте представим, что вы читаете из файла:

def read_trigrams(fobj): 
    unique = {} 
    def make_unique(w): 
     w = w.strip("\"'`!?,.():-;{}").lower() 
     return unique.setdefault(w, w) 
    fobj.seek(0, 2) 
    total_size = fobj.tell() 
    fobj.seek(0, 0) 

    read = 0 
    prev_words = [] 
    for idx, line in enumerate(fobj): 
     read += len(line) 
     words = prev_words 
     words.extend(filter(None, (make_unique(w) for w in line.split()))) 
     if len(words) > 3: 
      for i in range(len(words) - 3): 
       yield tuple(words[i:i+3]) 
     prev_words = words[-2:] 

Две вещи здесь:

1. Мы используем генератор так вместо чтения во всем файле и возвращает список триграмм, мы возвращать триграмму триграммой. Это немного медленнее, но сохраняет память.
2. Мы следим за тем, чтобы в конце концов было прочитано не более одной копии каждой строки, которую мы читаем, имея в своем распоряжении строку строк. Хотя сначала это может показаться странным, чтение одной и той же последовательности байтов S из файла N занимает время N*len(S) байтов. Используя словарь, мы удостоверяемся, что на входе есть одна уникальная копия каждого слова. Конечно, это потребляет некоторую память.

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

Это уже экономит немного памяти, но не слишком много.

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

LIMIT = 5e6 
def flush(counts, idx): 
    with open('counts-%d' % (idx,), 'wb') as fobj: 
     p = pickle.Pickler(fobj) 
     for item in sorted(counts.items()): 
      p.dump(item) 

import sys 
import pickle 
from collections import defaultdict 

counts = defaultdict(int) 
caches = 0 
with open(sys.argv[1], 'r') as fobj: 
    for t in read_trigrams(fobj): 
     counts[t] += 1 
     if len(counts) > LIMIT: 
      flush(counts, caches) 
      caches += 1 
      counts.clear() 
flush(counts, caches) 

На этом шаге вы можете настроить LIMIT, чтобы не использовать слишком много памяти, то есть просто сократить его до тех пор, пока вы не испытаете MemoryError больше.

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

import sys 
import pickle 

def merger(inputs): 
    unpicklers = [pickle.Unpickler(open(f, 'rb')) for f in inputs] 
    DONE = (object(),) 
    NEXT = (object(),) 

    peek = [NEXT] * len(unpicklers) 

    while True: 
     for idx in range(len(unpicklers)): 
      if peek[idx] is NEXT: 
       try: 
        peek[idx] = unpicklers[idx].load() 
       except EOFError: 
        peek[idx] = DONE 

     if all(v is DONE for v in peek): 
      return 
     min_key = min(v[0] for v in peek if v is not DONE) 
     yield min_key, sum(v[1] for v in peek if v[0] == min_key) 
     peek = [NEXT if (v[0] == min_key) else v for v in peek] 


for trigram, count in merger(sys.argv[1:]): 
    print(trigram, count) 

Если у вас есть 4 Гб на память, вы можете на самом деле нужно использовать функцию разделения. С 8 гигабайтами вы должны иметь возможность хранить все в ОЗУ.