<jupyter_start><jupyter_text>Information Retrieval This notebook demonstrates how to put together a simple retrieval engine in python. We'll focus on *ranked retrieval*, using a TFxIDF vector space model. We won't bother about any optimisations, and just use python dicts, sets etc.Our dataset is the *Cranfield collection*, an early resource which has been widely used in IR research. You may need to call `nltk.download()` to install the stopwords corpus.<jupyter_code>import nltk
from math import log
from collections import defaultdict, Counter
import requests, tarfile<jupyter_output><empty_output><jupyter_text>First, download the cranfield files, using the code below. Or you can do this manually by downloading http://ir.dcs.gla.ac.uk/resources/test_collections/cran/cran.tar.gz and extracting the files into the current directory.<jupyter_code># download
fname = 'cran.tar.gz'
url = 'http://ir.dcs.gla.ac.uk/resources/test_collections/cran/' + fname
r = requests.get(url)
# write to disk
open(fname , 'wb').write(r.content)
# extract files from archive
tar = tarfile.open(fname, "r:")
tar.extractall()
tar.close()<jupyter_output><empty_output><jupyter_text>We'll need to extract the document details---the document ids and text content---from the cranfield files.<jupyter_code>def parse_cranfield_documents(fname):
    SKIP, READ = range(2)
    state = SKIP
    identifier = body = None
    with open(fname) as infile:
        for line in infile:
            line = line.strip()
            parts = line.split()
            first = parts[0]
            if first[0] == ".":
                if first[1] == "I":
                    if state != None and identifier:
                        yield (identifier, body)
                    identifier = int(parts[1])
                    state = SKIP
                elif first[1] == "W":
                    state = READ
                    body = ''
                else:
                    state = SKIP
            elif state == READ:
                body += line + ' '
        if state == READ:
            yield (identifier, body)
docfname = 'cran.all.1400'
raw_docs = list(parse_cranfield_documents(docfname))
len(raw_docs)
raw_docs[0]
print(raw_docs[-1])<jupyter_output>(1400, 'the buckling shear stress of simply-supported infinitely long plates with transverse stiffeners . this report is an extension of previous theoretical investigations of the elastic buckling in shear of flat plates reinforced by transverse stiffeners . the plates are treated as infinitely long and simply-supported along the long sides . stiffeners are spaced at regular intervals, dividing the plate into a number of panels of uniform size . the effect ob bending and torsional stiffnesses of the stiffener upon the buckling shear stress is calculated for the complete range of stiffnesses, for panels with ratios of width to stiffener spacing of graphical forms . ')<jupyter_text>We'll need to tokenise the documents, remove stop-words and stem the words to form our bag-of-words representation. Here we'll use the PorterStemmer (there are others in NLTK).<jupyter_code>stopwords = set(nltk.corpus.stopwords.words('english')) # wrap in a set() (see below)
stemmer = nltk.stem.PorterStemmer() 

def extract_terms(doc):
    terms = set()
    for token in nltk.word_tokenize(doc):
        if token not in stopwords: # 'in' and 'not in' operations are much faster over sets that lists
            terms.add(stemmer.stem(token.lower()))
    return terms<jupyter_output><empty_output><jupyter_text>Let's test the method using the first document.<jupyter_code>print(list(sorted(extract_terms(raw_docs[0][1]))))<jupyter_output>[',', '.', '/destalling/', 'aerodynam', 'agre', 'angl', 'attack', 'basi', 'boundary-layer-control', 'compar', 'configur', 'curv', 'destal', 'determin', 'differ', 'distribut', 'due', 'effect', 'empir', 'evalu', 'evid', 'experi', 'experiment', 'flow', 'found', 'free', 'increas', 'increment', 'integr', 'intend', 'investig', 'lift', 'load', 'made', 'order', 'part', 'potenti', 'problem', 'produc', 'propel', 'ratio', 'remain', 'result', 'show', 'slipstream', 'span', 'spanwis', 'specif', 'stream', 'studi', 'substanti', 'subtract', 'support', 'theoret', 'theori', 'togeth', 'treatment', 'veloc', 'well', 'wing']<jupyter_text>We probably want to remove numbers and punctuation, which aren't being caught by the stop list. We may want to be a bit more agressive with tokenising hyphenated words (although take care, as some might be important.) Have a go yourself and see if you can improve the preprocessing to correct for these issues. Now we can apply the term extraction method to all documents in our corpus. (This may take a minute.)<jupyter_code>docs = {}
for docid, text in raw_docs:
    terms = extract_terms(text)
    docs[docid] = terms<jupyter_output><empty_output><jupyter_text>To build a _vector space model_ we must define a scoring function capable of relating a query to a document, then use this to retrieve the top *k* scoring documents for a given query. The scoring function we use is the cosine similarity measure over a _TF*IDF_ vector representation of the document and the query. This requires us to process the data to compute:1. term frequencies within each document (a *bag* of words, rather than a *set* as for boolean retrieval)2. document frequencies for each term, counting how many documents they occur in3. normlised _tf*idf_ vectors for each document 4. an inverted index to allow for efficient lookup by termThe first step is to collect term frequencies for each document, which is only a slight change from the code above for creating the binary index.<jupyter_code>def extract_term_freqs(doc):
    tfs = Counter()
    for token in doc:
        if token not in stopwords: # 'in' and 'not in' operations are much faster over sets that lists
            tfs[stemmer.stem(token.lower())] += 1
    return tfs<jupyter_output><empty_output><jupyter_text>We'll also need to compute the document frequencies, for the *idf* factors in the scoring function.<jupyter_code>def compute_doc_freqs(doc_term_freqs):
    dfs = Counter()
    for tfs in doc_term_freqs.values():
        for term in tfs.keys():
            dfs[term] += 1
    return dfs<jupyter_output><empty_output><jupyter_text>Using the above two functions, process the corpus into term frequencies and document frequencies.<jupyter_code>doc_term_freqs = {}
for docid, terms in docs.items():
    term_freqs = extract_term_freqs(terms)
    doc_term_freqs[docid] = term_freqs
M = len(doc_term_freqs)
doc_freqs = compute_doc_freqs(doc_term_freqs)<jupyter_output><empty_output><jupyter_text>As a sanity check, let's check some of the *df* values:<jupyter_code>for term in "flux viscous magnet".split():
    stem = stemmer.stem(term.lower())
    print("term", term, "df", doc_freqs[stem], 'idf', log(M / float(doc_freqs[stem])))<jupyter_output>term flux df 16 idf 4.471638793363569
term viscous df 117 idf 2.482053580805594
term magnet df 37 idf 3.6333096029591254<jupyter_text>Now to create the inverted index. For this we need to include the scoring function to compute the *tf* and *idf* values, then normalise each document vector to be unit length. For this we process each document in the corpus, compute a vector with one entry per term, normalise for length and store in the inverted index.Note that this a fairly inefficient inverted index. Many optimisations are possible, and are indeed necessary for this to scale to more realistic sized datasets. The approach below, though, is fine for small collections like this one.<jupyter_code>vsm_inverted_index = defaultdict(list)
for docid, term_freqs in doc_term_freqs.items():
    N = sum(term_freqs.values())
    length = 0
    
    # find tf*idf values and accumulate sum of squares 
    tfidf_values = []
    for term, count in term_freqs.items():
        tfidf = float(count) * log(M / float(doc_freqs[term]))
        tfidf_values.append((term, tfidf))
        length += tfidf ** 2

    # normalise documents by length and insert into index
    length = length ** 0.5
    for term, tfidf in tfidf_values:
        # note the inversion of the indexing, to be term -> (doc_id, score)
        vsm_inverted_index[term].append([docid, tfidf / length])
        
# ensure posting lists are in sorted order (less important here cf above)
for term, docids in vsm_inverted_index.items():
    docids.sort()<jupyter_output><empty_output><jupyter_text>For querying this index, we use the algorithm from the lecture. This just sums up the weights for each document using the posting lists for all query terms, then returns the ranked list of results. (Again, there are more efficient algorithms for doing ranked retrieval in the VSM, such as [WAND](http://lucene.472066.n3.nabble.com/attachment/577044/0/p426-broder.pdf).)<jupyter_code>def query_vsm(query, index, k=10):
    accumulator = Counter()
    for term in query:
        postings = index[term]
        for docid, weight in postings:
            accumulator[docid] += weight
    return accumulator.most_common(k)

results = query_vsm([stemmer.stem(term.lower()) for term in "flux viscous magnet".split()], vsm_inverted_index)
results<jupyter_output><empty_output><jupyter_text>It's worth taking a look at the top scoring document(s), e.g.<jupyter_code>print(raw_docs[results[0][0]-1])<jupyter_output>(298, 'incompressible wedge flows of an electrically conducting viscous fluid in the presence of a magnetic field . the purpose of this note is to discuss the two-dimensional flow of an electrically conducting viscous fluid past a wedge in the presence of a magnetic field .  the governing differential equations and boundary conditions are given and analyzed . ')
{'fraction_non_alphanumeric': 0.09318626945675704, 'fraction_numerical': 0.011235955056179775, 'mean_word_length': 4.1197889182058045, 'pattern_counts': {'":': 3, '<': 49, '<?xml version=': 0, '>': 50, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '13', 'dir': 'jupyter-structured-clean-dedup', 'id': '282740', 'license': 'BSD-4-Clause-UC', 'n_tokens_mistral': 2980, 'n_tokens_neox': 2789, 'n_words': 1092, 'path': 'notebooks/WSTA_N2_information_retrieval.ipynb', 'repo_name': 'trevorcohn/comp90042', 'size': '9701'}