Есть ли более эффективный способ найти наиболее распространенные n-граммы?

Я пытаюсь найти k самых распространенных n-грамм из большого корпуса. Я видел много мест, предлагающих наивный подход — простое сканирование всего корпуса и ведение словаря с подсчетом всех n-грамм. Есть лучший способ сделать это?


nlp algorithm n-gram
person bendl    schedule 21.02.2017    source источник
comment
Возможный дубликат cs.stackexchange.com/questions/8972/   -  person pltrdy    schedule 21.02.2017
comment
С чем вы сравниваете? Насколько большой корпус? Я думаю, что вы можете легко подсчитать количество ngrams в C++ довольно быстро для огромного корпуса, и даже в Python это довольно быстро =)   -  person alvas    schedule 22.02.2017
comment
Вы имеете в виду символьные ngrams или словесные ngrams?   -  person alvas    schedule 22.02.2017
comment
Я использую словесные ngrams, но я полагаю, что ngrams символов будут обобщать. Что касается корпуса, он должен иметь возможность масштабироваться до корпуса размером до 20 ГБ или около того, работающего на кластере Hadoop.   -  person bendl    schedule 23.02.2017

Ответы (1)


arrow_upward
11
arrow_downward

В Python с использованием NLTK:

$ wget http://norvig.com/big.txt
$ python
>>> from collections import Counter
>>> from nltk import ngrams
>>> bigtxt = open('big.txt').read()
>>> ngram_counts = Counter(ngrams(bigtxt.split(), 2))
>>> ngram_counts.most_common(10)
[(('of', 'the'), 12422), (('in', 'the'), 5741), (('to', 'the'), 4333), (('and', 'the'), 3065), (('on', 'the'), 2214), (('at', 'the'), 1915), (('by', 'the'), 1863), (('from', 'the'), 1754), (('of', 'a'), 1700), (('with', 'the'), 1656)]

В Python встроенный (см. Быстрая/оптимизация реализации N-грамм в python):

>>> import collections
>>> def ngrams(text, n=2):
...     return zip(*[text[i:] for i in range(n)])
>>> ngram_counts = collections.Counter(ngrams(bigtxt.split(), 2))
>>> ngram_counts.most_common(10)
    [(('of', 'the'), 12422), (('in', 'the'), 5741), (('to', 'the'), 4333), (('and', 'the'), 3065), (('on', 'the'), 2214), (('at', 'the'), 1915), (('by', 'the'), 1863), (('from', 'the'), 1754), (('of', 'a'), 1700), (('with', 'the'), 1656)]

В Julia см. раздел Создание ngrams с помощью Julia.

import StatsBase: countmap
import Iterators: partition
bigtxt = readstring(open("big.txt"))
ngram_counts = countmap(collect(partition(split(bigtxt), 2, 1)))

Грубый тайминг:

$ time python ngram-test.py # With NLTK.

real    0m3.166s
user    0m2.274s
sys 0m0.528s

$ time python ngram-native-test.py 

real    0m1.521s
user    0m1.317s
sys 0m0.145s

$ time julia ngram-test.jl 

real    0m3.573s
user    0m3.188s
sys 0m0.306s
person alvas    schedule 22.02.2017