Эффективная экстракция 1-5 грамм с помощью питона

Если вас интересуют только наиболее распространенные (частые) n-граммы (что, я полагаю, относится к вашему случаю), вы можете повторно использовать центральную идею Априорный алгоритм. Учитывая s_min, минимальную поддержку, которую можно рассматривать как количество строк, в которых содержится данная n-грамма, он эффективно ищет все такие n-граммы.

Идея такова: написать функцию запроса, которая берет n-грамму и проверяет, сколько раз она содержится в корпусе. После того, как вы подготовили такую ​​функцию (может быть оптимизирована, как будет рассмотрено позже), просканируйте весь корпус и получите все 1-граммы, т.е. голые токены, и выберите те, которые содержатся не менее s_min раз. Это дает вам подмножество F1 частых 1 граммов. Затем проверьте все возможные 2-граммы, объединив все 1-граммы из F1. Опять же, выберите те, которые соответствуют критерию s_min, и вы получите F2. Объединив все 2-граммы из F2 и выбрав наиболее часто встречающиеся 3-граммы, вы получите F3. Повторяйте до тех пор, пока Fn не пусто.

Здесь можно сделать множество оптимизаций. При объединении n-граммов из Fn вы можете использовать тот факт, что n-граммы x и y могут быть объединены в (n+1)-грамм только тогда и только тогда, когда x[1:] == y[:-1] (можно проверить в постоянное время для любого n, если используется правильное хеширование). Более того, если у вас достаточно оперативной памяти (для вашего корпуса много ГБ), вы можете чрезвычайно ускорить функцию запроса. Для каждой 1-граммы сохраните хэш-набор индексов строк, содержащих данную 1-грамму. При объединении двух n-грамм в (n+1)-грамму используйте пересечение двух соответствующих наборов, получая набор строк, в которых может содержаться (n+1)-грамма.

Временная сложность растет по мере уменьшения s_min. Прелесть в том, что нечастые (и, следовательно, неинтересные) n-граммы полностью фильтруются во время работы алгоритма, экономя время вычислений только для частых.

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

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

Вы читаете тонны данных в память, обрабатываете их (что занимает еще больше памяти), а затем сохраняете результаты в некоторых структурах данных в памяти. Вместо этого вы должны стремиться быть ленивее. Узнайте о генераторах Python и напишите генератор, который выдает все энграммы из заданного текста без необходимости хранить весь текст в памяти в любой заданный момент времени. Пакет itertools python, вероятно, пригодится при написании этого.

В какой-то момент вы больше не сможете хранить все эти данные в памяти. Вы должны подумать о том, чтобы посмотреть на map-reduce, чтобы помочь вам сломать это. Ознакомьтесь с пакетом mrjob python, который позволяет вам писать задания по уменьшению карты на python. На этапе сопоставления вы разбиваете текст на его энграммы, а на этапе редуктора вы подсчитываете, сколько раз вы видите каждый энграмм, чтобы получить его общее количество. mrjob также можно запускать локально, что, очевидно, не даст вам никаких преимуществ распараллеливания, но будет приятно, потому что mrjob по-прежнему будет делать за вас много тяжелой работы.

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

Предполагая, что вы не хотите считать ngrams между строками, и предполагая наивную токенизацию:

def ngrams(n, f):
    deque = collections.deque(maxlen=n)
    for line in f:
        deque.clear()
        words = ["<s>"] + line.split() + ["</s>"]
        deque.extend(words[:n-1]) # pre-seed so 5-gram counter doesn't count incomplete 5-grams
        for word in words[n-1:]:
            deque.append(word)
            yield tuple(str(w) for w in deque) # n-gram tokenization
counters = [collections.Counter(ngrams(i, open('somefile.txt'))) for i in range(5)]

изменить: добавлены маркеры начала/конца строки

Результирующий объект данных, я считаю, максимально разреженным. 3 миллиона строк с 40 словами — это примерно 120 миллионов токенов. С примерно 1 миллионом слов на английском языке (хотя и менее часто используемым), вы, вероятно, получите довольно длинный хвост. Если вы можете представить, что ваши данные могут быть заменены / iid, вы можете добавить некоторую обрезку посередине:

def ngrams(n, f, prune_after=10000):
    counter = collections.Counter()
    deque = collections.deque(maxlen=n)
    for i, line in enumerate(f):
        deque.clear()
        words = ["<s>"] + line.split() + ["</s>"]
        deque.extend(words[:n-1])
        for word in words[n-1:]:
            deque.append(word)
            ngram = tuple(str(w) for w in deque)
            if i < prune_after or ngram in counter:
                counter[ngram] += 1
    return counter

Ослабление допущения о заменяемости потребует чего-то вроде ответа Трегорега для эффективного сокращения, но в большинстве случаев заменяемость должна сохраняться.

Что касается сырой скорости, я думаю, что zip (как и исходный код) против deque - это фундаментальный вопрос. zip удаляет самый внутренний цикл, поэтому, вероятно, он уже очень быстрый. deque требует самого внутреннего цикла, но также использует данные итеративно, поэтому его объем рабочей памяти должен быть намного меньше. Что лучше, скорее всего, зависит от вашей машины, но я полагаю, что для больших машин / небольших данных zip будет быстрее. Однако, как только у вас начинает заканчиваться память (особенно если вы начинаете говорить об отсечении), deque получает еще несколько преимуществ.