Ефективно извличане на 1-5 грама с питон

Имам огромни файлове от 3 000 000 реда и всеки ред има 20-40 думи. Трябва да извлека 1 до 5 ngram от корпуса. Моите входни файлове са токенизиран обикновен текст, напр.:

This is a foo bar sentence .
There is a comma , in this sentence .
Such is an example text .

В момента го правя както е показано по-долу, но това не изглежда е ефективен начин за извличане на 1-5 грама:

#!/usr/bin/env python -*- coding: utf-8 -*-

import io, os
from collections import Counter
import sys; reload(sys); sys.setdefaultencoding('utf-8')

with io.open('train-1.tok.en', 'r', encoding='utf8') as srcfin, \
io.open('train-1.tok.jp', 'r', encoding='utf8') as trgfin:
    # Extract words from file. 
    src_words = ['<s>'] + srcfin.read().replace('\n', ' </s> <s> ').split()
    del src_words[-1] # Removes the final '<s>'
    trg_words = ['<s>'] + trgfin.read().replace('\n', ' </s> <s> ').split()
    del trg_words[-1] # Removes the final '<s>'

    # Unigrams count.
    src_unigrams = Counter(src_words) 
    trg_unigrams = Counter(trg_words) 
    # Sum of unigram counts.
    src_sum_unigrams = sum(src_unigrams.values())
    trg_sum_unigrams = sum(trg_unigrams.values())

    # Bigrams count.
    src_bigrams = Counter(zip(src_words,src_words[1:]))
    trg_bigrams = Counter(zip(trg_words,trg_words[1:]))
    # Sum of bigram counts.
    src_sum_bigrams = sum(src_bigrams.values())
    trg_sum_bigrams = sum(trg_bigrams.values())

    # Trigrams count.
    src_trigrams = Counter(zip(src_words,src_words[1:], src_words[2:]))
    trg_trigrams = Counter(zip(trg_words,trg_words[1:], trg_words[2:]))
    # Sum of trigram counts.
    src_sum_trigrams = sum(src_bigrams.values())
    trg_sum_trigrams = sum(trg_bigrams.values())

Има ли друг начин да направите това по-ефективно?

Как да извлечете оптимално различни N nграма едновременно?

От Fast/Optimize N-gram реализации в python, по същество това:

zip(*[words[i:] for i in range(n)])

когато е твърдо кодирано това е за биграми, n=2:

zip(src_words,src_words[1:])

и това за триграми ли е, n=3:

zip(src_words,src_words[1:],src_words[2:])

python nlp nltk n-gram information-retrieval
person alvas    schedule 13.10.2014    source източник
comment
Какъв е форматът на входните файлове?   -  person mbatchkarov    schedule 15.10.2014

Отговори (3)


arrow_upward
7
arrow_downward

Ако се интересувате само от най-често срещаните (чести) 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, ако се използва правилно хеширане). Освен това, ако имате достатъчно RAM (за вашия корпус, много GB), можете изключително да ускорите функцията за заявка. За всеки 1-грам съхранете хеш-набор от индекси на редове, съдържащ дадения 1-грам. Когато комбинирате два n-грама в (n+1)-грам, използвайте пресичане на двата съответни комплекта, за да получите набор от линии, където може да се съдържа (n+1)-грам.

Сложността на времето нараства с намаляване на s_min. Красотата е, че редките (и следователно безинтересни) n-грама са напълно филтрирани, докато алгоритъмът работи, спестявайки изчислително време само за честите.

person Tregoreg    schedule 22.10.2014

arrow_upward
2
arrow_downward

Давам ви куп насоки относно общите проблеми, които се опитвате да разрешите. Един или повече от тях трябва да са ви полезни и да ви помогнат да разберете това.

За това, което правите (предполагам, че това е някакъв експеримент за машинен превод), всъщност не е необходимо да зареждате двата файла srcfin и trgfin в паметта едновременно (поне не за примерния код, който сте предоставили). Отделната им обработка ще бъде по-евтина от гледна точка на количеството неща, които трябва да съхранявате в паметта в даден момент.

Вие четете много данни в паметта, обработвате ги (което отнема още повече памет) и след това държите резултатите в някои структури от данни в паметта. Вместо да правите това, трябва да се стремите да бъдете по-мързеливи. Научете за генераторите на Python и напишете генератор, който извежда всички ngrams от даден текст, без да е необходимо да държите целия текст в паметта във всеки даден момент от време. Пакетът itertools python вероятно ще бъде полезен, докато пишете това.

След една точка вече няма да е възможно да съхранявате всички тези данни в паметта. Трябва да разгледате map-reduce, за да ви помогне да разбиете това. Вижте пакета mrjob python, който ви позволява да пишете задачи за намаляване на картите в python. В стъпката на картографиране ще разбиете текста на неговите ngrams, а в етапа на редуциране ще преброите колко пъти виждате всеки ngram, за да получите общия му брой. mrjob може да се изпълнява и локално, което очевидно няма да ви даде никакви ползи от паралелизиране, но ще бъде хубаво, защото mrjob все пак ще свърши много тежка работа вместо вас.

Ако сте принудени да държите всички преброявания в паметта едновременно (за огромно количество текст), тогава или приложете някаква стратегия за изрязване, за да изрежете много редки ngrams, или обмислете използването на някаква постоянна файлово-базирана справочна таблица като sqlite за съхранява всички данни за вас.

person Aditya Mukherji    schedule 16.10.2014

arrow_upward
2
arrow_downward

Ако приемем, че не искате да броите 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

Облекчаването на предположението за заменяемост би изисквало нещо като отговора на Tregoreg за ефективно подрязване, но в повечето случаи заменяемостта трябва да се запази.

Що се отнася до необработената скорост, мисля, че zip (като оригиналния код) срещу deque е основният въпрос. zip премахва най-вътрешния цикъл, така че вероятно вече е много бърз. deque изисква най-вътрешния цикъл, но също така консумира данните итеративно, така че неговият отпечатък на работната памет трябва да бъде много по-малък. Кое е по-добро вероятно ще зависи от вашата машина, но бих си представил, че за големи машини/малки данни zip ще бъде по-бърз. След като започне да ви липсва памет (особено ако започнете да говорите за подрязване), обаче, deque получава още няколко предимства.

person metaperture    schedule 21.10.2014
comment
Той добавя тези тагове, защото е полезно да има допълнителни думи, представляващи началото и края на изречението. Това може да бъде полезно, например, за езикови модели. Вижте раздела за езиково моделиране в този курс на Coursera, ако искате повече информация. - person HerrKaputt; 22.10.2014
comment
Това има смисъл, предполагам, че ще го считам за модифицирана n-грама. - person metaperture; 22.10.2014