Как вычислить скипграммы в python?
K skipgram - это ngram, который является надмножеством всех ngram и каждой (ki) скипграммы до (ki)==0 (которая включает в себя 0 пропущенных грамм) Итак, как эффективно вычислить эти скипграммы в python?
Ниже приведен код, который я пробовал, но он не работает, как ожидалось:
<pre>
input_list = ['all', 'this', 'happened', 'more', 'or', 'less']
def find_skipgrams(input_list, N,K):
bigram_list = []
nlist=[]
K=1
for k in range(K+1):
for i in range(len(input_list)-1):
if i+k+1<len(input_list):
nlist=[]
for j in range(N+1):
if i+k+j+1<len(input_list):
nlist.append(input_list[i+k+j+1])
bigram_list.append(nlist)
return bigram_list
</pre>
Приведенный выше код не отображает правильно, но печатать find_skipgrams(['all', 'this', 'happened', 'more', 'or', 'less'],2,1) дает следующий вывод
[['this', 'случилось', 'больше'], ['произошло', 'больше', 'или'], ['больше', 'или', 'меньше'], ['или', 'меньше '], [' меньше '], [' произошло ',' больше ',' или '], [' больше ',' или ',' меньше '], [' или ',' меньше '], [' меньше '], ['Меньше']]
Код, указанный здесь, также не дает правильного вывода: https://github.com/heaven00/skipgram/blob/master/skipgram.py
print skipgram_ndarray ("Как тебя зовут") дает: ["Что, есть", "есть, твое", "ваше, имя", "имя", "Что, ваше", "есть, имя"]
зовут униграмма!
5 ответов
Из бумаги, на которую ссылается OP, следующая строка:
Повстанцы убиты в продолжающихся боевых действиях
Урожайность:
2-skip-bi-grams = {убиты повстанцы, повстанцы внутри, повстанцы продолжаются, убиты, убиты продолжаются, убиты сражаются, продолжаются, находятся в бою, продолжаются боевые действия}
2-skip-tri-grams = {повстанцы убиты в ходе, повстанцы убиты продолжаются, повстанцы убиты в бою, повстанцы в бою, повстанцы продолжаются в бою, убиты в продолжающемся, убиты в бою, убиты в продолжающемся бою, в продолжающемся бою}.
С небольшими изменениями в НЛТК ngrams код ( https://github.com/nltk/nltk/blob/develop/nltk/util.py):
from itertools import chain, combinations
import copy
from nltk.util import ngrams
def pad_sequence(sequence, n, pad_left=False, pad_right=False, pad_symbol=None):
if pad_left:
sequence = chain((pad_symbol,) * (n-1), sequence)
if pad_right:
sequence = chain(sequence, (pad_symbol,) * (n-1))
return sequence
def skipgrams(sequence, n, k, pad_left=False, pad_right=False, pad_symbol=None):
sequence_length = len(sequence)
sequence = iter(sequence)
sequence = pad_sequence(sequence, n, pad_left, pad_right, pad_symbol)
if sequence_length + pad_left + pad_right < k:
raise Exception("The length of sentence + padding(s) < skip")
if n < k:
raise Exception("Degree of Ngrams (n) needs to be bigger than skip (k)")
history = []
nk = n+k
# Return point for recursion.
if nk < 1:
return
# If n+k longer than sequence, reduce k by 1 and recur
elif nk > sequence_length:
for ng in skipgrams(list(sequence), n, k-1):
yield ng
while nk > 1: # Collects the first instance of n+k length history
history.append(next(sequence))
nk -= 1
# Iterative drop first item in history and picks up the next
# while yielding skipgrams for each iteration.
for item in sequence:
history.append(item)
current_token = history.pop(0)
# Iterates through the rest of the history and
# pick out all combinations the n-1grams
for idx in list(combinations(range(len(history)), n-1)):
ng = [current_token]
for _id in idx:
ng.append(history[_id])
yield tuple(ng)
# Recursively yield the skigrams for the rest of seqeunce where
# len(sequence) < n+k
for ng in list(skipgrams(history, n, k-1)):
yield ng
Давайте сделаем несколько тестов, чтобы соответствовать примеру в статье:
>>> two_skip_bigrams = list(skipgrams(text, n=2, k=2))
[('Insurgents', 'killed'), ('Insurgents', 'in'), ('Insurgents', 'ongoing'), ('killed', 'in'), ('killed', 'ongoing'), ('killed', 'fighting'), ('in', 'ongoing'), ('in', 'fighting'), ('ongoing', 'fighting')]
>>> two_skip_trigrams = list(skipgrams(text, n=3, k=2))
[('Insurgents', 'killed', 'in'), ('Insurgents', 'killed', 'ongoing'), ('Insurgents', 'killed', 'fighting'), ('Insurgents', 'in', 'ongoing'), ('Insurgents', 'in', 'fighting'), ('Insurgents', 'ongoing', 'fighting'), ('killed', 'in', 'ongoing'), ('killed', 'in', 'fighting'), ('killed', 'ongoing', 'fighting'), ('in', 'ongoing', 'fighting')]
Но обратите внимание, что если n+k > len(sequence), это даст тот же эффект, что и skipgrams(sequence, n, k-1) (это не ошибка, это отказоустойчивая функция), например
>>> three_skip_trigrams = list(skipgrams(text, n=3, k=3))
>>> three_skip_fourgrams = list(skipgrams(text, n=4, k=3))
>>> four_skip_fourgrams = list(skipgrams(text, n=4, k=4))
>>> four_skip_fivegrams = list(skipgrams(text, n=5, k=4))
>>>
>>> print len(three_skip_trigrams), three_skip_trigrams
10 [('Insurgents', 'killed', 'in'), ('Insurgents', 'killed', 'ongoing'), ('Insurgents', 'killed', 'fighting'), ('Insurgents', 'in', 'ongoing'), ('Insurgents', 'in', 'fighting'), ('Insurgents', 'ongoing', 'fighting'), ('killed', 'in', 'ongoing'), ('killed', 'in', 'fighting'), ('killed', 'ongoing', 'fighting'), ('in', 'ongoing', 'fighting')]
>>> print len(three_skip_fourgrams), three_skip_fourgrams
5 [('Insurgents', 'killed', 'in', 'ongoing'), ('Insurgents', 'killed', 'in', 'fighting'), ('Insurgents', 'killed', 'ongoing', 'fighting'), ('Insurgents', 'in', 'ongoing', 'fighting'), ('killed', 'in', 'ongoing', 'fighting')]
>>> print len(four_skip_fourgrams), four_skip_fourgrams
5 [('Insurgents', 'killed', 'in', 'ongoing'), ('Insurgents', 'killed', 'in', 'fighting'), ('Insurgents', 'killed', 'ongoing', 'fighting'), ('Insurgents', 'in', 'ongoing', 'fighting'), ('killed', 'in', 'ongoing', 'fighting')]
>>> print len(four_skip_fivegrams), four_skip_fivegrams
1 [('Insurgents', 'killed', 'in', 'ongoing', 'fighting')]
Это позволяет n == k но это запрещено n > k как показано в строках:
if n < k:
raise Exception("Degree of Ngrams (n) needs to be bigger than skip (k)")
Для понимания давайте попробуем понять "мистическую" строчку:
for idx in list(combinations(range(len(history)), n-1)):
pass # Do something
Учитывая список уникальных предметов, комбинации производят это:
>>> from itertools import combinations
>>> x = [0,1,2,3,4,5]
>>> list(combinations(x,2))
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
А так как индексы списка токенов всегда уникальны, например
>>> sent = ['this', 'is', 'a', 'foo', 'bar']
>>> current_token = sent.pop(0) # i.e. 'this'
>>> range(len(sent))
[0,1,2,3]
Можно рассчитать возможные комбинации (без замены) диапазона:
>>> n = 3
>>> list(combinations(range(len(sent)), n-1))
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
Если мы отобразим индексы обратно в список токенов:
>>> [tuple(sent[id] for id in idx) for idx in combinations(range(len(sent)), 2)
[('is', 'a'), ('is', 'foo'), ('is', 'bar'), ('a', 'foo'), ('a', 'bar'), ('foo', 'bar')]
Затем мы объединяем с current_tokenмы получаем skipgrams для текущего токена и окна context+skip:
>>> [tuple([current_token]) + tuple(sent[id] for id in idx) for idx in combinations(range(len(sent)), 2)]
[('this', 'is', 'a'), ('this', 'is', 'foo'), ('this', 'is', 'bar'), ('this', 'a', 'foo'), ('this', 'a', 'bar'), ('this', 'foo', 'bar')]
Итак, после этого мы переходим к следующему слову.
РЕДАКТИРОВАНИЕ
Последняя версия 3.2.5 NLTK имеет skipgrams реализованы.
Вот более чистая реализация от @jnothman из репозитория NLTK: https://github.com/nltk/nltk/blob/develop/nltk/util.py
def skipgrams(sequence, n, k, **kwargs):
"""
Returns all possible skipgrams generated from a sequence of items, as an iterator.
Skipgrams are ngrams that allows tokens to be skipped.
Refer to http://homepages.inf.ed.ac.uk/ballison/pdf/lrec_skipgrams.pdf
:param sequence: the source data to be converted into trigrams
:type sequence: sequence or iter
:param n: the degree of the ngrams
:type n: int
:param k: the skip distance
:type k: int
:rtype: iter(tuple)
"""
# Pads the sequence as desired by **kwargs.
if 'pad_left' in kwargs or 'pad_right' in kwargs:
sequence = pad_sequence(sequence, n, **kwargs)
# Note when iterating through the ngrams, the pad_right here is not
# the **kwargs padding, it's for the algorithm to detect the SENTINEL
# object on the right pad to stop inner loop.
SENTINEL = object()
for ngram in ngrams(sequence, n + k, pad_right=True, right_pad_symbol=SENTINEL):
head = ngram[:1]
tail = ngram[1:]
for skip_tail in combinations(tail, n - 1):
if skip_tail[-1] is SENTINEL:
continue
yield head + skip_tail
[из]:
>>> from nltk.util import skipgrams
>>> sent = "Insurgents killed in ongoing fighting".split()
>>> list(skipgrams(sent, 2, 2))
[('Insurgents', 'killed'), ('Insurgents', 'in'), ('Insurgents', 'ongoing'), ('killed', 'in'), ('killed', 'ongoing'), ('killed', 'fighting'), ('in', 'ongoing'), ('in', 'fighting'), ('ongoing', 'fighting')]
>>> list(skipgrams(sent, 3, 2))
[('Insurgents', 'killed', 'in'), ('Insurgents', 'killed', 'ongoing'), ('Insurgents', 'killed', 'fighting'), ('Insurgents', 'in', 'ongoing'), ('Insurgents', 'in', 'fighting'), ('Insurgents', 'ongoing', 'fighting'), ('killed', 'in', 'ongoing'), ('killed', 'in', 'fighting'), ('killed', 'ongoing', 'fighting'), ('in', 'ongoing', 'fighting')]
Хотя это будет полностью разделять ваш код и переносить его во внешнюю библиотеку; вы можете использовать Colibri Core ( https://proycon.github.io/colibri-core) для извлечения скипграмм. Это библиотека, написанная специально для эффективного извлечения n-грамм и скипграмм из больших текстовых корпусов. База кода находится в C++ (для скорости / эффективности), но доступна привязка Python.
Вы справедливо упомянули эффективность, так как извлечение скипграмм быстро показывает экспоненциальную сложность, которая не может быть большой проблемой, если вы только выносите предложение, как вы это делали в своем input_list, но становится проблематичным, если вы отпустите его на больших данных корпуса. Чтобы смягчить это, вы можете установить такие параметры, как порог вхождения, или потребовать, чтобы каждый пропуск скипграммы заполнялся как минимум на x различных n-грамм.
import colibricore
#Prepare corpus data (will be encoded for efficiency)
corpusfile_plaintext = "somecorpus.txt" #input, one sentence per line
encoder = colibricore.ClassEncoder()
encoder.build(corpusfile_plaintext)
corpusfile = "somecorpus.colibri.dat" #corpus output
classfile = "somecorpus.colibri.cls" #class encoding output
encoder.encodefile(corpusfile_plaintext,corpusfile)
encoder.save(classfile)
#Set options for skipgram extraction (mintokens is the occurrence threshold, maxlength maximum ngram/skipgram length)
colibricore.PatternModelOptions(mintokens=2,maxlength=8,doskipgrams=True)
#Instantiate an empty pattern model
model = colibricore.UnindexedPatternModel()
#Train the model on the encoded corpus file (this does the skipgram extraction)
model.train(corpusfile, options)
#Load a decoder so we can view the output
decoder = colibricore.ClassDecoder(classfile)
#Output all skipgrams
for pattern in model:
if pattern.category() == colibricore.Category.SKIPGRAM:
print(pattern.tostring(decoder))
На этом сайте есть более обширное руководство по Python.
Отказ от ответственности: я автор Colibri Core
Обратитесь к этому для полной информации.
В приведенном ниже примере уже упоминалось о его использовании и работает как шарм!
>>>sent = "Insurgents killed in ongoing fighting".split()
>>>list(skipgrams(sent, 2, 2))
[('Insurgents', 'killed'), ('Insurgents', 'in'), ('Insurgents', 'ongoing'), ('killed', 'in'), ('killed', 'ongoing'), ('killed', 'fighting'), ('in', 'ongoing'), ('in', 'fighting'), ('ongoing', 'fighting')]
Как насчет использования чужой реализации https://github.com/heaven00/skipgram/blob/master/skipgram.py, где k = skip_size а также n=ngram_order:
def skipgram_ndarray(sent, k=1, n=2):
"""
This is not exactly a vectorized version, because we are still
using a for loop
"""
tokens = sent.split()
if len(tokens) < k + 2:
raise Exception("REQ: length of sentence > skip + 2")
matrix = np.zeros((len(tokens), k + 2), dtype=object)
matrix[:, 0] = tokens
matrix[:, 1] = tokens[1:] + ['']
result = []
for skip in range(1, k + 1):
matrix[:, skip + 1] = tokens[skip + 1:] + [''] * (skip + 1)
for index in range(1, k + 2):
temp = matrix[:, 0] + ',' + matrix[:, index]
map(result.append, temp.tolist())
limit = (((k + 1) * (k + 2)) / 6) * ((3 * n) - (2 * k) - 6)
return result[:limit]
def skipgram_list(sent, k=1, n=2):
"""
Form skipgram features using list comprehensions
"""
tokens = sent.split()
tokens_n = ['''tokens[index + j + {0}]'''.format(index)
for index in range(n - 1)]
x = '(tokens[index], ' + ', '.join(tokens_n) + ')'
query_part1 = 'result = [' + x + ' for index in range(len(tokens))'
query_part2 = ' for j in range(1, k+2) if index + j + n < len(tokens)]'
exec(query_part1 + query_part2)
return result