IR - 11 - Lab I

Le librerie utilizzate sono le seguenti

 from nltk.corpus import stopwords
 from nltk.tokenize import word_tokenize
 from nltk.stem import PorterStemmer

 import nltk
 import os
 import string
 import numpy as np
 import copy
 import pandas as pd
 import pickle

Il dataset utilizzato è il 20 NewsGroup, che rappresenta una collezione di quasi \(20.000\) articoli di news partizionati in modo uniforme rispetto a \(20\) diverse categorie. Per scaricarlo è possibile eseguire il seguente codice bash

curl http://qwone.com/~jason/20Newsgroups/20news-19997.tar.gz -o 20_newsgroups
tar -xvf 20_newsgroups

Il codice python che segue deve essere eseguito all'interno della stessa cartella in cui è stato scaricato il dataset. Si assume inoltre che la cartella contenente il dataset è chiamata 20_newsgroups . Tale codice non fa altro che inserire in una lista le paths di tutti i documenti da indicizzare.

title = "20_newsgroups"
paths = []
for (dirpath, dirnames, filenames) in os.walk(str(os.getcwd()) + '/' + title + '/'):
    for i in filenames:
        paths.append(str(dirpath)+str("/") + i)

Una volta eseguito nella lista paths abbiamo quindi tutte le paths salvate nella lista paths .

print(paths[0]) 
# home/leo/repos/ir/private/code/lab_1/20_newsgroups/comp.graphics/38704
print(paths[1]) 
# /home/leo/repos/ir/private/code/lab_1/20_newsgroups/comp.graphics/38352

Andiamo adesso a definire la catena di preprocessamento che vogliamo applicare al contenuto di ciascun documento prima di andarlo ad indicizzare.

def preprocess(data, query):
    if not query:
        data = remove_header(data)
        data = convert_lower_case(data)
        data = convert_numbers(data)
        data = remove_punctuation(data) # remove comma seperately
        data = remove_stop_words(data)
        data = remove_apostrophe(data)
        data = remove_single_characters(data)
        data = stemming(data)
    return data

Notiamo come l'ordine in cui effettuiamo questi steps è importante. Segue quindi l'implementazione di ciascun modulo.

Per quanto riguarda la costruzione dell'indice, l'idea è quella di utilizzare i data frame offerti dalla libreria pandas . Per meggiori informazioni è possibile utilizzare il seguente link Pandas DataFrame

Il codice che si occupa della creazione della struttura dati principale è il seguente

doc = 0
postings = pd.DataFrame()

for path in paths:
    # open file, get text, close  file
    file = open(path, 'r', encoding='cp1250')
    text = file.read().strip()
    file.close()
    
    # preprocess text
    preprocessed_text = preprocess(text, False)

    # Index each token in the document in our data structure.
    tokens = word_tokenize(str(preprocessed_text))
    for token in tokens: 
        if token in postings:
            p = postings[token][0] # get posting list associated with token 
            p.add(doc)             # add docID to posting list
            postings[token][0] = p # update posting list associated with token
        else:
            # create new posting list for token with a single docID
            postings.insert(value=[{doc}], loc=0, column=token)

    # increment docID variable
    doc += 1

La struttura creata è quella descritta in una delle prime lezioni. Per analizzarla meglio possiamo eseguire i seguenti comandi python

print(postings.info(verbose=True))
#    class pandas.core.frame.DataFrame
#    RangeIndex: 1 entries, 0 to 0
#    Data columns (total 485 columns):
#    #   Column           Dtype 
#    ---  ------           ----- 
#    0   license          object
#    1   privat           object
#    2   other            object
#    3   news             object
#    4   keep             object
#    5   dont             object
#    6   apparantli       object
#    7   success          object
#    8   determin         object
#    9   sell             object
#    10  softwar          object
#    11  concept          object
#    ...

Ogni riga della tabella è poi formata da una lista di docIDs nel seguente modo

print(postings['zero'])
# 0    {0, 2, 3, 6, 7, 8, 9}
# Name: zero, dtype: object

Per salvare sul disco la struttura dati in modo da mantenere un certo livello di persistenza possiamo utilizzare la libreria python pickle nel seguente modo

#  write to file
postings.to_pickle(title + "_unigram_postings")
# read from file
postings = pd.read_pickle(title + "_unigram_postings")

Infine, per interagire con la struttura dati definiamo le seguenti due funzioni:

• La funzione get_posting(word) non fa altro che ritornare la posting list associata alla parola word :

  def get_posting(word):
      if word in postings:
          return postings[word][0]
      else:
          return []
  

• La funzione print_word_postings(word) stampa la posting list associata alla parola word :

  def print_word_postings(word):
      preprocessed_word = str(preprocess(word, True))
      print(preprocessed_word)
      postings = get_posting(preprocessed_word)
      print("Document Frequency:",len(postings))
      print("Postings List:",postings)    
  

Andiamo adesso ad implementare la nostra query language. Le query che vogliamo eseguire sono semplici query booleane. Segue qualche esempio

• \(\text{place}\)

• \(\text{authority}\)

• \(\text{place AND NOT authority}\)

• \(\text{place OR authority}\)

• \(\text{place OR authority AND NOT welcome}\)

La funzione principale che si occupa dell'esecuzione delle nostre query è la seguente.

def execute_query(query):
    command_tokens, query_tokens = generate_query_tokens(query)
    tup = generate_not_tuple(query_tokens, command_tokens)
    
    print("\nCommands:", command_tokens)
    print("\nQuery Words:", query_tokens)
    print("\nNot Tup:", len(tup))
    
    final_set = binary_operations(query_tokens, command_tokens, tup)
    final_set = sorted(final_set)
    
    print("\nFinal Set:",final_set)
    print("-----------------------------------------")
    return final_set

ed è così descritta:

• La chiamata alla funzione generate_query_tokens() serve per leggere la query e spezzarla in due sequenze di tokens: i command_tokens , che sono i token relativi ai comandi tipo \(\text{AND, OR, NOT}\), e i query_tokens , che sono i termini presenti nella query tipo \(\text{place, authority}\). Tale funzione è implementata nel seguente modo

  def generate_query_tokens(query):
      query = query.lower()
      tokens = word_tokenize(query)
      
      command_tokens = []
      query_tokens = []
      
      for t in tokens:
          if t not in ['and', 'or', 'not']:
              processed_token = preprocess([t], True)
              query_tokens.append(str(processed_token))
          else:
              command_tokens.append(t)
              
      return command_tokens, query_tokens
  

• La funzione get_not_tuple() invece esegue tutti i comandi della forma \(\text{NOT} \langle \text{token} \rangle\) e ritorna in un insieme i risultati dei comandi eseguiti indicizzati in base alla posizione del comando rispetto a tutti i comandi. Tale funzione è implementata nel seguente modo

  def generate_not_tuple(query_tokens, command_tokens):
      tup = set()
      # as long as there are NOT command to execute
      while 'not' in commands:
          i = command_tokens.index('not')
          word = query_tokens[i]
          word_postings = get_not(word) # get result of NOT <word> 
          tup.update(word_postings)
          command_tokens.pop(i) # remove command
          # Replace the word with an ID to signal that it has been
          # processed 
          # 
          # NOTE: numbers have been already removed in the preprocessing
          # stage.
          query_words[i] = i
          print("\nAfter Not Processing:",commands, query_words)
      return tup
  

  Tale funzione esegue a sua volta la funzione get_not(word), che non fa altro che calcolare la posting list contenente il \(\text{docID}\) di tutti i documenti che non contengono la parola \(\text{word}\). Tale funzione è implementata come segue

  def get_not(word):
      a = get_posting(word)
      b = set(range(len(paths)))
      return b.difference(a)
  

  dove paths era la lista che ci eravamo calcolati inizialmente e che conteneva le paths di tutti i documenti che abbiamo indicizzato.

• Infine, la funzione binary_operations() viene utilizzata per eseguire i restanti comandi e calcolare il risultato finale. Tale funzione è implementata come segue

  def binary_operations(query_tokens, command_tokens, tup):
      if not query_tokens[0]:
          return tup
  
      a = get_posting(query_tokens[0])
      query_tokens.pop(0)
  
      for i in range(len(command_tokens)):
          if type(query_tokens[i])==int:
              b = tup
          else:
              b = get_posting(query_tokens[i])
  
          if command_tokens[i] == 'and':
              a = a.intersection(b)
          elif command_tokens[i] == 'or':
              a = a.union(b)
          else:
              print("Invalid Command")
  
      return a
  

Seguono alcuni possibili esercizi che consistono nel modificare il codice appena descritto:

• Cambiare l'implementazione del codice che costruire le varie posting lists in modo tale da avere delle posting lists ordinate rispetto ai vari \(\text{docIDs}\).

• Ottimizzare l'implementazione dell'operazione \(\text{NOT}\).

• Implementare un concetto di priorità tra le operazioni utilizzando le parentesi.

La costruzione dell'indice questa volta viene nel seguente modo

postings = pd.DataFrame()
frequency = pd.DataFrame()
doc = 0

for path in paths:
    file = open(path, 'r', encoding='cp1250')
    text = file.read().strip()
    file.close()
    preprocessed_text = preprocess(text, False)
    tokens = word_tokenize(str(preprocessed_text))

    pos = 0
    for token in tokens:
        if token in postings:
            p = postings[token][0]            
            k = [a[0] for a in p]  # get all docIDs
            if doc in k:
                for a in p:
                    if a[0] == doc:
                        a[1].add(pos)
                else:
                    p.append([doc,{pos}])
                    frequency[token][0] += 1
        else:
            postings.insert(value=[[[doc, {pos}]]], loc=0, column=token)
            frequency.insert(value=[1], loc=0, column=token)

        pos += 1
    doc += 1

Per quanto riguarda l'interazione con la struttura dati abbiamo le seguenti funzioni utili

def get_word_postings(word):
    preprocessed_word = str(preprocess(word, True))
    term_frequency = frequency[preprocessed_word][0]
    term_postings = postings[preprocessed_word][0]
    return term_frequency, term_postings

def get_posting(word):
    if word in postings:
        return postings[word][0]
    else:
        return []

def get_positions(posting_values, doc):
    for value in posting_values:
        if value[0] == doc:
            return posting_value[1]
    return {}

In questo esempio siamo interessati ad implementare un linguaggio di query che ci permette di rispondere a query del tipo

• \(\text{Los Angeles}\)

• \(\text{Tor Vergata}\)

• \(\text{Mountain View}\)

Per fare questo utilizziamo la seguente funzione

def run_query(query):
    processed_query = preprocess(query, True)
    query_tokens = word_tokenize(str(processed_query))
    
    if len(query_tokens) == 1:
        query_postings = get_posting(query_tokens[0])
        result = [a[0] for a in query_postings]
        return result
    
    init_word = query_tokens[0]
    init_matches = gen_init_set_matchings(init_word)
    query_tokens.pop(0)
    total_matched_docs = match_positional_index(init_matches, query_tokens)
    total_matched_docs = sorted(total_matched_docs)    
    return total_matched_docs

tale funziona controlla se la query ha un solo termine. In quel caso calcola tramite la funzione get_posting() quali sono i \(\text{docIDs}\) che contengono tale termine e gli ritorna come risultato. Altrimenti, se la funzione ha più una parola, calcola tutti i \(\text{docIDs}\) che contengono almeno il primo termine tramite la funzione gen_init_set_matchings() , che è implementata come segue

def gen_init_set_matchings(word):
    init = []
    word_postings = get_posting(word)
    for word_posting in word_postings:
        for positions in word_posting[1]:
            init.append((word_posting[0], positions))
    return init

tale funzione non fa altro che ritornare una lista di coppie di elementi della forma (docID, pos) .

Per finire viene poi chiamata la funzione match_positional_index , che utilizza la lista di coppie init_matches e i restanti query_tokens per calcolare quali sono i \(\text{docIDs}\) che contengono esattamente tutti i token della query nel giusto ordine. Una possibile implementazione per tale funzione è la seguente

def match_positional_index(init, query_tokens):
    matched_docs = []
    for p in init:
        doc, pos = p[0], p[1]
        count = 0
        
        for query_token in query_tokens:
            pos = pos+1
            query_token_pos = get_posting(query_token)
            docs_list = [z[0] for z in query_token_pos]
            if doc in docs_list:
                doc_positions = get_positions(query_token_pos, doc)
                if pos in doc_positions:
                    count += 1
                else:
                    count += 1
                    break

            if count == len(query_tokens):
                matched_docs.append(p[0])
                
    return set(matched_docs)

Seguono alcuni possibili esercizi che consistono nel modificare il codice appena descritto:

• Cambiare l'implementazione del codice che costruire le varie posting lists in modo tale da avere delle posting lists ordinate rispetto ai vari \(\text{docIDs}\).

• Ottimizzare l'implementazione dell'operazione merge che viene effettuata all'interno della funzione match_positional_index() .

• Integrare gli indici posizinali con il linguaggio di query utilizzato nel precedente esempio.