Come calcolare skipgram in python?

Question

A k skipgram è un ngram che è un superset di tutti gli ngram e ciascuno (k-i) skipgram till (k-i) == 0 (che include 0 salta grammi). Quindi, come calcolare in modo efficiente questi skipgram in python?

seguito riporta il codice ho provato, ma non sta facendo come previsto:

<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> 

Il codice di cui sopra non è il rendering in modo corretto, ma la stampa find_skipgrams(['all', 'this', 'happened', 'more', 'or', 'less'],2,1) dà seguente output

[[ 'questo' , "successo", "altro"], ["successo", "altro", "o"], ["altro", "o", "meno"], ["o", "meno"], [ 'less'], ['happened', 'more', 'or'], ['more', 'or', 'less'], ['or', 'less'], ['less'], ['less']]

Il codice qui elencato anche non dà uscita corretta: https://github.com/heaven00/skipgram/blob/master/skipgram.py

stampa skipgram_ndarray ("Qual è il tuo nome") dà: [ 'Che cosa, è', 'è, il tuo', 'la tua , nome ',' nome, ',' Cosa, tuo ',' è, nome ']

nome è un unigram!

Answer 1

Dal paper che i collegamenti OP, la seguente stringa:

insorti uccisi in combattimenti in corso

Rese:

2-saltare-bi-grammi = {insorti uccisi, i ribelli in, gli insorti in corso, ucciso in, ucciso in corso, combattimenti ucciso, in corso, in combattimenti, combattimenti in corso}

2-salto -tri-grammi = {insorti uccisi, ribelli uccisi in corso, ribelli in rivolta, insorti in combattimento , ribelli in corso, combattimenti in corso, uccisi in combattimento , combattimenti in corso, combattimenti in corso}.

Con lieve modifica al codice del NLTK ngrams (https://github.com/nltk/nltk/blob/develop/nltk/util.py#L383):

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 

Facciamo un po doctest per abbinare l'esempio nella carta:

>>> 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')] 

Ma si noti che se n+k > len(sequence), produrrà gli stessi effetti di skipgrams(sequence, n, k-1) (questo non è un bug, è una funzionalità di sicurezza), ad es.

>>> 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')] 

Questo permette n == k ma non consentire n > k secondo le indicazioni delle linee:

if n < k: 
     raise Exception("Degree of Ngrams (n) needs to be bigger than skip (k)")  

---

Per capire bene, cerchiamo di capire la linea di "mistica":

for idx in list(combinations(range(len(history)), n-1)): 
    pass # Do something 

Dato un elenco di elementi unici, le combinazioni producono questo:

>>> 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)] 

E poiché gli indici di un elenco di token sono sempre univoci, ad es.

>>> sent = ['this', 'is', 'a', 'foo', 'bar'] 
>>> current_token = sent.pop(0) # i.e. 'this' 
>>> range(len(sent)) 
[0,1,2,3] 

E 'possibile calcolare la possibile combinations (without replacement) della gamma:

>>> n = 3 
>>> list(combinations(range(len(sent)), n-1)) 
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] 

Se tracciamo gli indici torna alla lista di token:

>>> [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')] 

Poi abbiamo concatenare con l'current_token , otteniamo gli skipgram per il token corrente e il contesto + finestra di salto:

>>> [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')] 

Quindi passiamo alla parola successiva.

Answer 2

ne dite di usare qualcun altro implementazione https://github.com/heaven00/skipgram/blob/master/skipgram.py, dove k = skip_size e 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 

Answer 3

CURA

L'ultima NLTK versione 3.2.5 ha la skipgrams implementato.

Ecco un'implementazione più pulito dal @jnothman dalla repo NLTK: https://github.com/nltk/nltk/blob/develop/nltk/util.py#L538

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 

[out]:

>>> 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')] 

Answer 4

Anche se questo sarebbe separarsi del tutto dal codice e rinviare ad una libreria esterna ; è possibile utilizzare Colibri Core (https://proycon.github.io/colibri-core) per l'estrazione skipgram. È una libreria scritta appositamente per l'estrazione efficiente di n-grammi e skipgram da grandi corpora testuali. Il codice base è in C++ (per velocità/efficienza), ma è disponibile un collegamento Python.

Hai giustamente menzionato l'efficienza, poiché l'estrazione di skipgram mostra rapidamente una complessità esponenziale, che potrebbe non essere un grosso problema se si passa una frase come nel tuo input_list, ma diventa problematica se la si rilascia su grandi dati corpus. Per mitigare ciò è possibile impostare parametri come una soglia di occorrenza o richiedere che ogni salto di uno skipgram sia compilabile di almeno x n-gram distinti.

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)) 

C'è un tutorial Python più completo su tutto questo sul sito web.

Disclaimer: io sono l'autore di Colibri Nucleo

Answer 5

consultare this per informazioni complete.

L'esempio seguente è già stato menzionato in esso in merito al suo utilizzo e funziona come un incantesimo!

>>>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')]