Эффективное извлечение 1-5 граммов с помощью python

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

Предполагая, что вы не хотите считать 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)]

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

Результирующий объект данных, я считаю, настолько редким, насколько это возможно. Строки длиной 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

Расслабление предположения об обмене потребует что-то вроде ответа Tregoreg для эффективной обрезки, но в большинстве случаев обмен должен быть.

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