Mini_search_engine.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KvWgp6zfgTHk"
      },
      "source": [
        "# Imports"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "SuD8m2KhGC1Q",
        "outputId": "ef4b47ee-c953-4a07-f7fc-60bd5cae6a1e"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import re\n",
        "import nltk\n",
        "import math\n",
        "import json\n",
        "import statistics\n",
        "import os\n",
        "from nltk import FreqDist\n",
        "from nltk.corpus import stopwords\n",
        "from nltk.stem.porter import PorterStemmer"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {},
      "outputs": [],
      "source": [
        "current_directory=os.getcwd()\n",
        "corpus_path = os.path.join(current_directory, 'files\\CACM\\cacm.txt')\n",
        "stoplist_path = os.path.join(current_directory, 'files\\CACM\\common_words.txt')\n",
        "query_path = os.path.join(current_directory, 'files\\CACM\\query.txt')\n",
        "qrels_path = os.path.join(current_directory, 'files\\CACM\\qrels.txt')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QFNiWrRqKIgD"
      },
      "source": [
        "# Data preparation"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "id": "-WCGavIrHYd-"
      },
      "outputs": [],
      "source": [
        "def apply_regex(regex , string):\n",
        "  #Apply a regex to the input string\n",
        "  matches = list(re.finditer(regex, string))\n",
        "  if (len(matches) != 0):\n",
        "    for match in matches:\n",
        "      result = match.groups()[0]\n",
        "  else:\n",
        "    result = ''\n",
        "  return result\n",
        "\n",
        "\n",
        "def make_corpus(pathfile):\n",
        "  #Construct a list in which each element contains the title, author, and abstract of the corpus documents\n",
        "  f = open(pathfile , 'r')\n",
        "  text = f.read()\n",
        "  tab = re.split(pattern=\"\\.I [0-9]+\\n\", string=text)\n",
        "  tab.remove('')\n",
        "  regex_title =  r\"\\.T\\n((.|\\n)*?)\\.[WBAKCNX]\\n\"\n",
        "  regex_author = r\"\\.A\\n((.|\\n)*?)\\.[WBTKCNX]\\n\"\n",
        "  regex_abstract = r\"\\.W\\n((.|\\n)*?)\\.[ABTKCNX]\\n\"\n",
        "  result = []\n",
        "  for string in tab:\n",
        "    title = apply_regex(regex_title , string)\n",
        "    author = apply_regex(regex_author , string)\n",
        "    abstract = apply_regex(regex_abstract , string)\n",
        "    concat = title + ' ' + author + ' ' + abstract\n",
        "    result.append(concat)\n",
        "  return result\n",
        "\n",
        "\n",
        "def vec2dict(tab):\n",
        "  #Transform the list of documents into a dictionary\n",
        "  keys = ['doc_'+str(i) for i in range(1, len(tab)+1)]\n",
        "  dico = {k : v for k,v in zip(keys , tab)}\n",
        "  return dico\n",
        "\n",
        "\n",
        "def preprocessing(string, path_stoplist):\n",
        "  #Romove commun words from sentences and transform the words into their stem form\n",
        "  f = open(path_stoplist , 'r')\n",
        "  local_stoplist = f.read().splitlines()\n",
        "  string = re.sub(\"[\\W]\", ' ', string)\n",
        "  string = string.lower()\n",
        "  string = string.split()\n",
        "  ps = PorterStemmer()\n",
        "  string = [ps.stem(word) for word in string if (not word in set(stopwords.words('english'))) & (not word in set(local_stoplist))]\n",
        "  string = ' '.join(string)\n",
        "  return string\n",
        "\n",
        "\n",
        "def count_freq(string):\n",
        "  # Return the words contained in a sentence with their frequence in a dictinary format\n",
        "  string = string.split()\n",
        "  freqs = dict(FreqDist(string))\n",
        "  return freqs\n",
        "\n",
        "\n",
        "def treat_dataset(path_corpus, path_stoplist):\n",
        "  #Transform the input corpus into a dictionary of documents IDs and content, in which each elemnt consists of the words contained in the document and their frequency of aparition\n",
        "  result = make_corpus(path_corpus)\n",
        "  dico = vec2dict(result)\n",
        "  for key in dico:\n",
        "    val = dico.get(key)\n",
        "    val = preprocessing(val , path_stoplist)\n",
        "    val = count_freq(val)\n",
        "    dico[key] = val\n",
        "  return dico"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2AMb8jpyP462",
        "outputId": "ddf2d1ee-3db1-4b4f-d7c7-e66bd21a6d4f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Number of documents:  3204\n",
            "{'secant': 2, 'method': 2, 'simultan': 2, 'nonlinear': 1, 'equat': 2, 'wolf': 1, 'procedur': 1, 'solut': 1, 'system': 1, 'necessarili': 1, 'linear': 1, 'gener': 1, 'singl': 1, 'function': 1, 'variabl': 1}\n"
          ]
        }
      ],
      "source": [
        "Data = treat_dataset(corpus_path , stoplist_path)\n",
        "\n",
        "#Save data in a json file\n",
        "json.dump( Data, open( \"files\\Data.json\", 'w' ) )\n",
        "\n",
        "#Data = json.load( open( os.path.join(current_directory, \"files\\Data.json\") ) )\n",
        "\n",
        "print('Number of documents: ',len(Data))\n",
        "print(Data['doc_39'])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wScLLS9Aclae"
      },
      "source": [
        "# Boolean Model"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "collapsed": true,
        "id": "Zbn95vyiUJNw"
      },
      "outputs": [],
      "source": [
        "def inverse_doc_freq(dictio):\n",
        "  dictio_inverse = {}\n",
        "  for doc in dictio.keys():\n",
        "    info = dictio.get(doc)\n",
        "    for word in info.keys():\n",
        "      freq = info.get(word)\n",
        "      dictio_inverse[(word , doc)] = freq\n",
        "  return dictio_inverse\n",
        "\n",
        "\n",
        "def inverted_index(dictio_inverse):\n",
        "  access = {}\n",
        "  for item in dictio_inverse:\n",
        "    word = item[0]\n",
        "    doc = item[1]\n",
        "    freq = dictio_inverse.get(item)\n",
        "    if not word in access:\n",
        "      access[word] = {doc : freq}\n",
        "    else:\n",
        "      dictio_tmp = access.get(word)\n",
        "      dictio_tmp[doc] = freq\n",
        "      access[word] = dictio_tmp\n",
        "  return access"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {
        "id": "6vIs2qiXzVsg"
      },
      "outputs": [],
      "source": [
        "def space(query,ch1,ch2):\n",
        "  #Add space in the input query\n",
        "  result=\"\"\n",
        "  lenght=len(query)\n",
        "  t=0\n",
        "  for ch in query:\n",
        "    if t==lenght-1: result = result + ch; break\n",
        "    else:\n",
        "      if ch==ch1:\n",
        "        result = result + ch + ' '\n",
        "      else:\n",
        "        if query[t+1]==ch2:\n",
        "          result = result + ch + ' '\n",
        "        else:\n",
        "          result = result + ch\n",
        "    t=t+1\n",
        "  return(result)\n",
        "\n",
        "def treat_query(query):\n",
        "  query=space(query,\"∨\",\"∨\")\n",
        "  query=space(query,\"∧\",\"∧\")\n",
        "  query=space(query,\"¬\",\"¬\")\n",
        "  query=query.replace(\"∨\",\"or\")\n",
        "  query=query.replace(\"∧\",\"and\")\n",
        "  query=query.replace(\"¬\",\"not\")\n",
        "  query=space(query,\"(\",\")\")\n",
        "  query = query.lower()\n",
        "  query = query.split()\n",
        "  ps = PorterStemmer()\n",
        "  boolquery = [ps.stem(word) for word in query]\n",
        "  return(boolquery)\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YQ8PMSvyF7TI",
        "outputId": "7911fd3d-ef06-495e-c4ea-fdfd28c41254"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['doc_1', 'doc_637', 'doc_2050', 'doc_2380', 'doc_2556', 'doc_2584', 'doc_2911', 'doc_2929', 'doc_2970', 'doc_2972', 'doc_3001']\n"
          ]
        }
      ],
      "source": [
        "query= \"(preliminary∨(report∧time)) ∧ ¬computer \"\n",
        "#query=input (\"Enter your boolean query :\")\n",
        "boolquery=treat_query(query)\n",
        "\n",
        "words=[]\n",
        "for m in boolquery:\n",
        "  if m!=\"or\" and m!=\"and\" and m!=\"not\" and m!=\"(\" and m!=\")\" :\n",
        "    words.append(m)\n",
        "\n",
        "corpusbool=inverse_doc_freq(Data)\n",
        "corpusbool=inverted_index(corpusbool)\n",
        "\n",
        "querydictionary={\"doc_1\":{}}                  #Initialize a dictionary representing the presence or absence of each word from the query in each document.\n",
        "for i in range (1,len(Data)+1):\n",
        "  querydictionary[\"doc_\"+str(i)] = list()\n",
        "\n",
        "for word in words:\n",
        "  listedocs=[]\n",
        "  if word in corpusbool.keys():\n",
        "    for n in corpusbool[word].keys():\n",
        "       listedocs.append(n)\n",
        "\n",
        "  for doc in querydictionary:\n",
        "    if doc in listedocs:\n",
        "      querydictionary[doc].append(1)\n",
        "    else:\n",
        "      querydictionary[doc].append(0)\n",
        "\n",
        "#print (querydictionary)\n",
        "\n",
        "result=[]\n",
        "for i in range (1,len(Data)):\n",
        "  boolquery2=boolquery\n",
        "  k=0; c=0\n",
        "  for j in  boolquery2:\n",
        "    if j!=\"or\" and j!=\"and\" and j!=\"not\"and j!=\"(\"and j!=\")\":\n",
        "      boolquery2[c]=querydictionary[\"doc_\"+str(i)][k]\n",
        "      k=k+1\n",
        "    c=c+1\n",
        "\n",
        "  boolquery2=' '.join(map(str,boolquery2))\n",
        "  res=eval(boolquery2)\n",
        "  if res== True:\n",
        "    res=1\n",
        "  if res == False:\n",
        "    res=0\n",
        "  result.append(res)\n",
        "\n",
        "#Display the pertinant documents\n",
        "cnt=0\n",
        "listdocsol=[]\n",
        "for r in result:\n",
        "  cnt=cnt+1\n",
        "  if r==1:\n",
        "    listdocsol.append(\"doc_\"+str(cnt))\n",
        "print(listdocsol)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c-6mtEeu43Zc"
      },
      "source": [
        "# Vectorial Model"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "id": "DDqgxoLPZAvo"
      },
      "outputs": [],
      "source": [
        "def freq(term , doc , data):\n",
        "  return (data.get(doc)).get(term)\n",
        "\n",
        "\n",
        "def max_freq(doc , data):\n",
        "  dictio_terme = data.get(doc)\n",
        "  values = dictio_terme.values()\n",
        "  return max(values)\n",
        "\n",
        "\n",
        "def get_nb_docs_contains_term(term , inv_index):\n",
        "  return len(inv_index.get(term))\n",
        "\n",
        "\n",
        "def compute_tf_idf(term, doc , data , inv_index):\n",
        "  N = len(data)\n",
        "  frequence = freq(term , doc , data)\n",
        "  max_frequence = max_freq(doc , data)\n",
        "  ni = get_nb_docs_contains_term(term , inv_index)\n",
        "  weight = (frequence / max_frequence) * math.log((N / ni) + 1)\n",
        "  return weight\n",
        "\n",
        "\n",
        "def compute_ponderation_dataset(data):\n",
        "  N = len(data)\n",
        "  inv_index = inverted_index(inverse_doc_freq(data))\n",
        "  for term in inv_index:\n",
        "    dico = inv_index.get(term)\n",
        "    for doc in dico :\n",
        "      dico[doc] = compute_tf_idf(term , doc , data , inv_index)\n",
        "  return inv_index"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "id": "PF1WunPk175L"
      },
      "outputs": [],
      "source": [
        "def query_terms_list(query , list_terms):\n",
        "  #Return a list of all the termn with their frequency in the query\n",
        "  query_dictio = {}\n",
        "  query = query.split()\n",
        "  tab_req = [word for word in query]\n",
        "  for term in list_terms:\n",
        "    if term in tab_req:\n",
        "      query_dictio[term] = 1\n",
        "    else:\n",
        "      query_dictio[term] = 0\n",
        "  return query_dictio\n",
        "\n",
        "\n",
        "def inner_product_similarity(dict_query, dict_term):\n",
        "  result = 0\n",
        "  dict_query_values = list(dict_query.values())\n",
        "  dict_term_values = list(dict_term.values())\n",
        "  for i in range(len(dict_query.values())):\n",
        "    result = result + dict_query_values[i] * dict_term_values[i]\n",
        "  return result\n",
        "\n",
        "\n",
        "def dice_similarity(dict_query, dict_term):\n",
        "  tmp1 = 0; tmp2 = 0; tmp3 = 0\n",
        "  dict_query_values = list(dict_query.values())\n",
        "  dict_term_values = list(dict_term.values())\n",
        "  for i in range(len(dict_query.values())):\n",
        "    tmp1 = tmp1 + dict_query_values[i] * dict_term_values[i]\n",
        "    tmp2 = tmp2 + dict_query_values[i]**2\n",
        "    tmp3 = tmp3 + dict_term_values[i]**2\n",
        "  return (2 * tmp1) / (tmp2 + tmp3)\n",
        "\n",
        "\n",
        "def cosine_similarity(dict_query, dict_term):\n",
        "  tmp1 = 0; tmp2 = 0; tmp3 = 0\n",
        "  dict_query_values = list(dict_query.values())\n",
        "  dict_term_values = list(dict_term.values())\n",
        "  for i in range(len(dict_query.values())):\n",
        "    tmp1 = tmp1 + dict_query_values[i] * dict_term_values[i]\n",
        "    tmp2 = tmp2 + dict_query_values[i]**2\n",
        "    tmp3 = tmp3 + dict_term_values[i]**2\n",
        "  return (tmp1) / (math.sqrt(tmp2 * tmp3))\n",
        "\n",
        "\n",
        "def jaccard(dict_query, dict_term):\n",
        "  tmp1 = 0; tmp2 = 0; tmp3 = 0\n",
        "  dict_query_values = list(dict_query.values())\n",
        "  dict_term_values = list(dict_term.values())\n",
        "  for i in range(len(dict_query.values())):\n",
        "    tmp1 = tmp1 + dict_query_values[i] * dict_term_values[i]\n",
        "    tmp2 = tmp2 + dict_query_values[i]**2\n",
        "    tmp3 = tmp3 + dict_term_values[i]**2\n",
        "  return (tmp1) / (tmp2 + tmp3 - tmp1)\n",
        "\n",
        "\n",
        "def compute_simiralite(doc , req_dico , sim_fonction , inv_index , data):\n",
        "  #Compute the similarity between the query and a document\n",
        "  N = len(data)\n",
        "  dico_word_term_pondere = {}\n",
        "  for word in inv_index:\n",
        "    dico_word_term_pondere[word] = 0\n",
        "    if doc in inv_index.get(word):\n",
        "      dico_word_term_pondere[word] = (inv_index.get(word)).get(doc)\n",
        "  if sim_fonction == 'product':\n",
        "    sim = inner_product_similarity(req_dico , dico_word_term_pondere)\n",
        "  elif sim_fonction == 'cosine':\n",
        "    sim = cosine_similarity(req_dico , dico_word_term_pondere)\n",
        "  elif sim_fonction == 'dice':\n",
        "    sim = dice_similarity(req_dico , dico_word_term_pondere)\n",
        "  elif sim_fonction == 'jaccard':\n",
        "    sim = jaccard(req_dico , dico_word_term_pondere)\n",
        "  else:\n",
        "    raise ValueError(\"Choose between: 'product', 'dice', 'cosine', 'jaccard'\")\n",
        "  return sim"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "c7d-OFiW_nqL",
        "outputId": "3959b1b3-077b-44d0-ea30-40fd4b515222"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "0.11376074532489822"
            ]
          },
          "execution_count": 19,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "inv_index=compute_ponderation_dataset(Data)\n",
        "#Test\n",
        "compute_simiralite('doc_7' , query_terms_list(preprocessing('computer report',stoplist_path) , list(inv_index.keys())) ,'cosine' ,inv_index ,Data)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 20,
      "metadata": {
        "id": "rebN0j3A17vF"
      },
      "outputs": [],
      "source": [
        "def get_result(query , list_doc , sim_fonction , data , inv_index , max_doc):\n",
        "  # Treat the input query and return the most pertinent document, the number of returned documents is max_doc\n",
        "  N = len(data)\n",
        "  dico_doc_sim = {}\n",
        "  query=preprocessing(query,stoplist_path)\n",
        "  query_dico = query_terms_list(query , list(inv_index.keys()))\n",
        "  inv_index = compute_ponderation_dataset(data)\n",
        "  for doc in list_doc:\n",
        "    dico_doc_sim[doc] = compute_simiralite(doc , query_dico , sim_fonction , inv_index , data)\n",
        "\n",
        "  dico_doc_sim = sorted(dico_doc_sim.items() , key = lambda x : x[1] , reverse=True)\n",
        "  return dico_doc_sim[0:max_doc]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 21,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4Hj2fBkdM4dP",
        "outputId": "901fa348-d00a-4e7d-bf51-9cf2733d71d4"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[('doc_1071', 0.3785051570818026),\n",
              " ('doc_1938', 0.3594777416220278),\n",
              " ('doc_1572', 0.30978738955327717),\n",
              " ('doc_2371', 0.3066996837368273),\n",
              " ('doc_2319', 0.2711126145055777),\n",
              " ('doc_971', 0.2689840210947489),\n",
              " ('doc_1908', 0.25536641514904174),\n",
              " ('doc_2151', 0.2371598807532838),\n",
              " ('doc_1680', 0.23493782943921554),\n",
              " ('doc_1657', 0.2339894061534857)]"
            ]
          },
          "execution_count": 21,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# req = 'computer report'\n",
        "req = 'What articles exist which deal with TSS (Time Sharing System), an operating system for IBM computers?'\n",
        "get_result(req , list(Data.keys()) , 'cosine' , Data , inv_index , 10)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ppibz7Hehdmc"
      },
      "source": [
        "## Vectorial Model Evaluation\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 22,
      "metadata": {
        "id": "B-TJC17vYsCh"
      },
      "outputs": [],
      "source": [
        "def make_query_corpus(pathfile):\n",
        "  f = open(pathfile , 'r')\n",
        "  text = f.read()\n",
        "  tab = re.split(pattern=\"\\.I [0-9]+\\n\", string=text)\n",
        "  tab.remove('')\n",
        "  regex_abstract = r\"\\.W\\n((.|\\n)*?)\\.[AN]\\n\"\n",
        "  regex_author = r\"\\.A\\n((.|\\n)*?)\\.N\\n\"\n",
        "  result = []\n",
        "  for string in tab:\n",
        "    author = apply_regex(regex_author , string)\n",
        "    abstract = apply_regex(regex_abstract , string)\n",
        "    concat =  abstract + ' ' + author\n",
        "    result.append(concat)\n",
        "  return result"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 23,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Zk1yaLOzhlUa",
        "outputId": "131edc66-4c93-4567-d781-2ea163420681"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['What articles exist which deal with TSS (Time Sharing System), an operating system for IBM computers?', 'I am interested in articles written either by Prieve or Udo Pooch  Prieve, B. Pooch, U.', 'Intermediate languages used in construction of multi-targeted compilers; TCOLL', \"I'm interested in mechanisms for communicating between disjoint processes, possibly, but not exclusively, in a distributed environment.  I would rather see descriptions of complete mechanisms, with or without implementations, as opposed to theoretical work on the abstract problem.  Remote procedure calls and message-passing are examples of my interests.\", \"I'd like papers on design and implementation of editing interfaces, window-managers, command interpreters, etc.  The essential issues are human interface design, with views on improvements to user efficiency, effectiveness and satisfaction.\", 'Interested in articles on robotics, motion planning particularly the geometric and combinatorial aspects.  We are not interested in the dynamics of arm motion.', 'I am interested in distributed algorithms - concurrent programs in which processes communicate and synchronize by using message passing. Areas of particular interest include fault-tolerance and techniques for understanding the correctness of these algorithms.', 'Addressing schemes for resources in networks; resource addressing in network operating systems', 'Security considerations in local networks, network operating systems, and distributed systems.', 'Parallel languages; languages for parallel computation', 'SETL, Very High Level Languages', 'portable operating systems', 'code optimization for space efficiency', 'find all discussions of optimal implementations of sort algorithms for database management applications', 'Find all discussions of horizontal microcode optimization with special emphasis on optimization of loops and global optimization.', 'find all descriptions of file handling in operating systems based on multiple processes and message passing.', 'Optimization of intermediate and machine code', 'Languages and compilers for parallel processors, especially highly horizontal microcoded machines; code compaction', 'Parallel algorithms', 'Graph theoretic algorithms applicable to sparse matrices', 'computational complexity, intractability, class-complete reductions, algorithms and efficiency', 'I am interested in hidden-line and hidden-surface algorithms for cylinders, toroids, spheres, and cones.  This is a rather specialized topic in computer graphics.', 'Distributed computing structures and algorithms', 'Applied stochastic processes', 'Performance evaluation and modelling of computer systems', 'Concurrency control mechanisms in operating systems', 'Memory management aspects of operating systems', 'Any information on packet radio networks.  Of particular interest are algorithms for packet routing, and for dealing with changes in network topography.  I am not interested in the hardware used in the network.', 'Number-theoretic algorithms, especially involving prime number series, sieves, and Chinese Remainder theorem.', 'Articles on text formatting systems, including \"what you see is what you get\" systems.  Examples: t/nroff, scribe, bravo.', 'I\\'d like to find articles describing the use of singular value decomposition in digital image processing.  Applications include finding approximations to the original image and restoring images that are subject to noise. An article on the subject is H.C. Andrews and C.L. Patterson \"Outer product expansions and their uses in digital image processing\", American Mathematical Monthly, vol. 82.  Andrews, H.C. Patterson, C.L.', \"I'd like to find articles describing graph algorithms that are based on the eigenvalue decomposition (or singular value decomposition) of the ajacency matrix for the graph.  I'm especially interested in any heuristic algorithms for graph coloring and graph isomorphism using this method.\", 'Articles about the sensitivity of the eigenvalue decomposition of real matrices, in particular, zero-one matrices.  I\\'m especially interested in the separation of eigenspaces corresponding to distinct eigenvalues. Articles on the subject: C. Davis and W.M. Kahn, \"The rotation of eigenvectors by a permutation:, SIAM J. Numerical Analysis, vol. 7, no. 1 (1970); G.W. Stewart, \"Error bounds for approximate invariant subspaces of closed linear operators\", SIAM J. Numerical Analysis., Vol. 8, no. 4 (1971).  Davis, C. Kahn, W.M. Stewart, G.W.', 'Currently interested in isolation of root of polynomial; there is an old article by Heindel, L.E. in J. ACM, Vol. 18, 533-548.  I would like to find more recent material.  Heindel, L.E.', 'Probabilistic algorithms especially those dealing with algebraic and symbolic manipulation.  Some examples: Rabiin, \"Probabilistic algorithm on finite field\", SIAM Waztch, \"Probabilistic testing of polynomial identities\", SIAM  Rabin,M.', 'Fast algorithm for context-free language recognition or parsing', 'Articles describing the relationship between data types and concurrency (e.g. what is the type of a process?  when is a synchronization attempt  between two processes \"type correct\"?  in a message-passing system is there any notion of the types of messages?--i.e. any way to check that the sender of the message and the receiver are both treating the bit stream as some particular type)', 'What is the type of a module?\\t(I don\\'t want the entire literature on Abstract Data Types here, but I\\'m not sure how to phrase this to avoid it. I\\'m interested in questions about how one can check that a module \"matches\" contexts in which it is used.)', 'What does type compatibility mean in languages that allow programmer defined types?  (You might want to restrict this to \"extensible\" languages that allow definition of abstract data types or programmer-supplied definitions of operators like *, +.)', 'List all articles dealing with data types in the following languages: Pascal, CLU, Alphard, Russell, Ada, ALGOL 68, EL1.  List any other languages that are referenced frequently in papers on the above languages (e.g. catch any languages with interesting type structures that I might have missed).', 'Theory of distributed systems and databases.  Subtopics of special interest include reliability and fault-tolerance in distributed systems, atomicity, distributed transactions, synchronization algorithms,  resource allocation; lower bounds and models for asynchronous parallel systems.  Also theory of communicating processes and protocols.', 'Computer performance evaluation techniques using pattern recognition and clustering.', 'Analysis and perception of shape by humans and computers.  Shape descriptions, shape recognition by computer.  Two-dimensional shapes. Measures of circularity.  Shape matching.', 'Texture analysis by computer.\\tDigitized texture analysis.  Texture synthesis. Perception of texture.', 'The use of operations research models to optimize information system performance.  This includes fine tuning decisions such as secondary index selection, file reorganization, and distributed databases.', 'The application of fuzzy subset theory to clustering and information retrieval problems.  This includes performance evaluation and automatic indexing considerations.', 'The use of Bayesian decision models to optimize information retrieval system performance.  This includes stopping rules to determine when a user should cease scanning the output of a retrieval search.', 'The use of computer science principles (e.g. data structures,  numerical methods) in generating optimization (e.g. linear programming) algorithms.  This includes issues of the Khachian (Russian, ellipsoidal) algorithm and complexity of such algorithms.', 'The role of information retrieval in knowledge based systems (i.e., expert systems).', 'Parallel processors in information retrieval', 'Parallel processors and paging algorithms', 'Modelling and simulation in agricultural ecosystems.', 'mathematical induction, group theory, integers modulo m, probability, binomial coefficients, binomial theorem, homomorphism, morphism, transitivity, relations, relation matrix.', 'Semantics of programming languages, including abstract specifications of data types, denotational semantics, and proofs of correctness.  Hoare, A. Dijkstra, E.', 'Anything dealing with star height of regular languages or regular expressions or regular events.', 'Articles relation the algebraic theory of semigroups and monoids to the study of automata and regular languages.', 'Abstracts of articles:     J. Backus, \"Can programming be liberated from the Von Neumann style?                A functional style and its algebra of programs\", CACM 21                (1978), 613-641.     R.A.De Millo, R.J. Lipton, A.J. Perlis, letter to ACM Forum, CACM 22 \\t       (1979), 629-630  Backus, J. De Millo, R.A. Lipton, R.J. Perlis, A.J.', \"Algorithms or statistical packages for ANOVA, regression using least squares or generalized linear models.  System design, capabilities, statistical formula are of interest.  Student's t test, Wilcoxon and sign tests, multivariate and univariate components can be included.\", 'Dictionary construction and accessing methods for fast retrieval of words or lexical items or morphologically related information. Hashing or indexing methods are usually applied to English spelling or natural language problems.', 'Hardware and software relating to database management systems. Database packages, back end computers, special associative hardware with microcomputers attached to disk heads or things like RAP,  relational or network (CODASYL) or hierarchical models, systems like SYSTEM R, IMS, ADABAS, TOTAL, etc.', 'Information retrieval articles by Gerard Salton or others about clustering, bibliographic coupling, use of citations or co-citations, the vector space model, Boolean search methods using inverted files, feedback, etc.  Salton, G.', \"Results relating parallel complexity theory (both for PRAM's and uniform circuits).\", 'Algorithms for parallel computation, and especially comparisons between parallel and sequential algorithms.', \"List all articles on EL1 and ECL (EL1 may be given as EL/1; I don't remember how they did it.\"]\n",
            "['01 1410  0 0', '01 1572  0 0', '01 1605  0 0', '01 2020  0 0', '01 2358  0 0', '02 2434  0 0', '02 2863  0 0', '02 3078  0 0', '03 1134  0 0', '03 1613  0 0', '03 1807  0 0', '03 1947  0 0', '03 2290  0 0', '03 2923  0 0', '04 1749  0 0', '04 1811  0 0', '04 2256  0 0', '04 2371  0 0', '04 2597  0 0', '04 2796  0 0', '04 2912  0 0', '04 3043  0 0', '04 3073  0 0', '04 3082  0 0', '04 3127  0 0', '04 3128  0 0', '05 0756  0 0', '05 1307  0 0', '05 1502  0 0', '05 2035 0 0', '05 2299  0 0', '05 2399  0 0', '05 2501 0 0', '05 2820 0 0', '06 1543  0 0', '06 2078  0 0', '06 2828  0 0', '07 1198  0 0', '07 1338  0 0', '07 1877  0 0', '07 1960  0 0', '07 2150  0 0', '07 2228  0 0', '07 2256  0 0', '07 2280  0 0', '07 2320  0 0', '07 2342  0 0', '07 2376  0 0', '07 2482  0 0', '07 2578  0 0', '07 2597  0 0', '07 2618  0 0', '07 2685  0 0', '07 2700  0 0', '07 2777  0 0', '07 2865  0 0', '07 2866  0 0', '07 2895  0 0', '07 2912  0 0', '07 2941  0 0', '07 3043  0 0', '07 3082  0 0', '07 3128  0 0', '07 3141  0 0', '07 3148  0 0', '08 2625  0 0', '08 2849 0 0', '08 3032 0 0', '09 2372  0 0', '09 2632 0 0', '09 2870  0 0', '09 2876 0 0', '09 3068  0 0', '09 3111  0 0', '09 3128 0 0', '09 3158  0 0', '09 3177 0 0', '10 0046  0 0', '10 0141  0 0', '10 0392  0 0', '10 0950  0 0', '10 1158  0 0', '10 1198  0 0', '10 1262  0 0', '10 1380  0 0', '10 1471  0 0', '10 1601  0 0', '10 1613  0 0', '10 1747  0 0', '10 1795  0 0', '10 1811  0 0', '10 2060  0 0', '10 2150  0 0', '10 2256  0 0', '10 2289  0 0', '10 2342  0 0', '10 2376  0 0', '10 2433  0 0', '10 2618  0 0', '10 2664  0 0', '10 2685  0 0', '10 2700  0 0', '10 2714  0 0', '10 2777  0 0', '10 2785  0 0', '10 2851  0 0', '10 2895  0 0', '10 2896  0 0', '10 2912  0 0', '10 3039  0 0', '10 3075  0 0', '10 3156  0 0', '11 1043  0 0', '11 1188  0 0', '11 1306  0 0', '11 1358  0 0', '11 1396  0 0', '11 1491  0 0', '11 1923  0 0', '11 2246  0 0', '11 2316  0 0', '11 2527  0 0', '11 2699  0 0', '11 2710  0 0', '11 2715  0 0', '11 2716  0 0', '11 2906  0 0', '11 2923  0 0', '11 2956  0 0', '11 3073  0 0', '11 3150  0 0', '12 1523  0 0', '12 2080  0 0', '12 2246  0 0', '12 2629  0 0', '12 3127  0 0', '13 0115  0 0', '13 1223  0 0', '13 1231  0 0', '13 1551  0 0', '13 1625  0 0', '13 1795  0 0', '13 1807  0 0', '13 1947  0 0', '13 2495  0 0', '13 2579  0 0', '13 2897  0 0', '14 0074  0 0', '14 0117  0 0', '14 0232  0 0', '14 0776 0 0', '14 0827  0 0', '14 0850 0 0', '14 0851 0 0', '14 0852  0 0', '14 0854  0 0', '14 0855 0 0', '14 0856  0 0', '14 0857 0 0', '14 0858 0 0', '14 0860 0 0', '14 0861 0 0', '14 0862 0 0', '14 0864  0 0', '14 0865 0 0', '14 0866  0 0', '14 1175 0 0', '14 1724  0 0', '14 1919  0 0', '14 1956 0 0', '14 1969 0 0', '14 1980 0 0', '14 1997 0 0', '14 2017  0 0', '14 2041 0 0', '14 2108  0 0', '14 2118  0 0', '14 2146 0 0', '14 2176 0 0', '14 2191  0 0', '14 2272  0 0', '14 2337  0 0', '14 2348  0 0', '14 2397  0 0', '14 2563 0 0', '14 2664 0 0', '14 2679 0 0', '14 2714 0 0', '14 2716 0 0', '14 3075  0 0', '14 3187 0 0', '15 1231 0 0', '15 1551 0 0', '15 1613 0 0', '15 1947  0 0', '15 2263  0 0', '15 2495 0 0', '15 2598  0 0', '15 2685  0 0', '15 2701  0 0', '15 2880  0 0', '16 1746 0 0', '16 1749 0 0', '16 1828 0 0', '16 1854 0 0', '16 1960 0 0', '16 2070  0 0', '16 2114  0 0', '16 2342 0 0', '16 2376  0 0', '16 2378 0 0', '16 2500 0 0', '16 2632 0 0', '16 2817 0 0', '16 2912 0 0', '16 3073 0 0', '16 3105 0 0', '16 3148  0 0', '17 0115  0 0', '17 0405  0 0', '17 1134  0 0', '17 1223  0 0', '17 1231  0 0', '17 1535  0 0', '17 1551  0 0', '17 1613  0 0', '17 1807  0 0', '17 1934  0 0', '17 1947  0 0', '17 2290  0 0', '17 2495  0 0', '17 2579  0 0', '17 2586  0 0', '17 2923  0 0', '18 1158  0 0', '18 1215  0 0', '18 1262  0 0', '18 1471  0 0', '18 1613  0 0', '18 1811  0 0', '18 2060  0 0', '18 2175  0 0', '18 2413  0 0', '18 2433  0 0', '18 2685  0 0', '19 0141 0 0', '19 0863 0 0', '19 0950 0 0', '19 1601 0 0', '19 2266 0 0', '19 2664 0 0', '19 2714 0 0', '19 2973 0 0', '19 3075 0 0', '19 3156 0 0', '19 3175 0 0', '20 1563 0 0', '20 2695 0 0', '20 2986 0 0', '21 1429  0 0', '21 1847  0 0', '21 2189  0 0', '21 2490  0 0', '21 2603  0 0', '21 2701  0 0', '21 2702  0 0', '21 2703  0 0', '21 2932  0 0', '21 3018  0 0', '21 3139  0 0', '22 2369 0 0', '22 2384  0 0', '22 2441  0 0', '22 2473  0 0', '22 2564  0 0', '22 2637  0 0', '22 2638  0 0', '22 2678 0 0', '22 2692 0 0', '22 2751  0 0', '22 2760  0 0', '22 2761  0 0', '22 2827  0 0', '22 2828 0 0', '22 2829 0 0', '22 3116 0 0', '22 3149 0 0', '23 2578  0 0', '23 2849  0 0', '23 3137  0 0', '23 3148  0 0', '24 0268  0 0', '24 1696  0 0', '24 1892  0 0', '24 2069  0 0', '24 2123  0 0', '24 2297  0 0', '24 2373  0 0', '24 2667  0 0', '24 2862  0 0', '24 2970  0 0', '24 2996  0 0', '24 3078  0 0', '24 3098  0 0', '25 0268  0 0', '25 0757  0 0', '25 0963  0 0', '25 1408  0 0', '25 1518  0 0', '25 1526  0 0', '25 1533  0 0', '25 1572  0 0', '25 1653  0 0', '25 1698  0 0', '25 1719  0 0', '25 1805  0 0', '25 1892  0 0', '25 1901  0 0', '25 2085  0 0', '25 2095  0 0', '25 2218  0 0', '25 2277  0 0', '25 2318  0 0', '25 2319  0 0', '25 2358  0 0', '25 2373  0 0', '25 2434  0 0', '25 2452  0 0', '25 2535  0 0', '25 2582  0 0', '25 2667  0 0', '25 2668  0 0', '25 2669  0 0', '25 2681  0 0', '25 2741  0 0', '25 2765  0 0', '25 2798  0 0', '25 2818  0 0', '25 2831  0 0', '25 2859  0 0', '25 2862  0 0', '25 2863  0 0', '25 2881  0 0', '25 2918  0 0', '25 2928  0 0', '25 2984  0 0', '25 2988  0 0', '25 2996  0 0', '25 3006  0 0', '25 3048  0 0', '25 3059  0 0', '25 3067  0 0', '25 3088  0 0', '25 3089  0 0', '25 3119  0 0', '26 1071  0 0', '26 1198  0 0', '26 1338  0 0', '26 1749  0 0', '26 1828  0 0', '26 1854  0 0', '26 1960  0 0', '26 2080  0 0', '26 2150  0 0', '26 2256  0 0', '26 2320  0 0', '26 2342  0 0', '26 2376  0 0', '26 2379  0 0', '26 2541  0 0', '26 2597  0 0', '26 2618  0 0', '26 2632  0 0', '26 2700  0 0', '26 2740  0 0', '26 2777  0 0', '26 2851  0 0', '26 2866  0 0', '26 2912  0 0', '26 2938  0 0', '26 3039  0 0', '26 3043  0 0', '26 3048  0 0', '26 3082  0 0', '26 3128  0 0', '27 1641  0 0', '27 1642  0 0', '27 1750  0 0', '27 1752  0 0', '27 1879  0 0', '27 1884  0 0', '27 1901  0 0', '27 2095  0 0', '27 2297  0 0', '27 2435  0 0', '27 2481  0 0', '27 2498  0 0', '27 2560  0 0', '27 2596  0 0', '27 2669  0 0', '27 2734  0 0', '27 2747  0 0', '27 2768  0 0', '27 2798  0 0', '27 2818  0 0', '27 2859  0 0', '27 2864  0 0', '27 2902  0 0', '27 2918  0 0', '27 2955  0 0', '27 2983  0 0', '27 2988  0 0', '27 3000  0 0', '27 3052  0 0', '28 2578 0 0', '28 2849  0 0', '28 2890  0 0', '28 2949  0 0', '28 3032  0 0', '29 0377  0 0', '29 0513  0 0', '29 0610  0 0', '29 0935  0 0', '29 1094  0 0', '29 1420  0 0', '29 1537  0 0', '29 1538  0 0', '29 1539  0 0', '29 1840  0 0', '29 1841  0 0', '29 1967  0 0', '29 2028  0 0', '29 2089  0 0', '29 2120  0 0', '29 2462  0 0', '29 2927  0 0', '29 2932  0 0', '29 3037  0 0', '30 1926  0 0', '30 2486  0 0', '30 2786  0 0', '30 2917  0 0', '31 2125  0 0', '31 3047  0 0', '32 0366  0 0', '32 1145  0 0', '32 3139  0 0', '33 2805  0 0', '36 1265  0 0', '36 1350  0 0', '36 1683  0 0', '36 1768  0 0', '36 1787  0 0', '36 1825  0 0', '36 1836  0 0', '36 2015  0 0', '36 2084  0 0', '36 2110  0 0', '36 2179  0 0', '36 2340  0 0', '36 2423  0 0', '36 2702  0 0', '36 2708  0 0', '36 2733  0 0', '36 2824  0 0', '36 2836  0 0', '36 2986  0 0', '36 3094  0 0', '37 2265 0 0', '37 2377 0 0', '37 2558 0 0', '37 2625 0 0', '37 2632 0 0', '37 2651 0 0', '37 2738 0 0', '37 2840 0 0', '37 2939 0 0', '37 2941 0 0', '37 3144 0 0', '37 3148 0 0', '38 2265 0 0', '38 2558 0 0', '38 2625 0 0', '38 2632 0 0', '38 2651 0 0', '38 2868 0 0', '38 2939 0 0', '38 2940 0 0', '38 2941 0 0', '38 2956 0 0', '38 2957 0 0', '38 2958 0 0', '38 2960 0 0', '38 3031 0 0', '38 3103 0 0', '38 3150 0 0', '39 1693 0 0', '39 1861 0 0', '39 2126 0 0', '39 2265 0 0', '39 2317 0 0', '39 2558 0 0', '39 2625 0 0', '39 2632 0 0', '39 2651 0 0', '39 2939 0 0', '39 2941 0 0', '39 3031 0 0', '40 1614 0 0', '40 2126 0 0', '40 2148 0 0', '40 2265 0 0', '40 2651 0 0', '40 2939 0 0', '40 2940 0 0', '40 2941 0 0', '40 2956 0 0', '40 2958 0 0', '42 0963 0 0', '42 1069 0 0', '42 1518 0 0', '42 1572 0 0', '42 1653 0 0', '42 1805 0 0', '42 1827 0 0', '42 1884 0 0', '42 2022 0 0', '42 2085 0 0', '42 2151 0 0', '42 2247 0 0', '42 2318 0 0', '42 2344 0 0', '42 2522 0 0', '42 2542 0 0', '42 2749 0 0', '42 2951 0 0', '42 2984 0 0', '42 3048 0 0', '42 3072 0 0', '43 0122 0 0', '43 0266 0 0', '43 0297 0 0', '43 0462 0 0', '43 1113 0 0', '43 1325 0 0', '43 1528 0 0', '43 1554 0 0', '43 1686 0 0', '43 1697 0 0', '43 2004 0 0', '43 2195 0 0', '43 2201 0 0', '43 2211 0 0', '43 2382 0 0', '43 2400 0 0', '43 2421 0 0', '43 2514 0 0', '43 2523 0 0', '43 2655 0 0', '43 2687 0 0', '43 2751 0 0', '43 2754 0 0', '43 2771 0 0', '43 2788 0 0', '43 2811 0 0', '43 2826 0 0', '43 2827 0 0', '43 2828 0 0', '43 2829 0 0', '43 2841 0 0', '43 2883 0 0', '43 2910 0 0', '43 2913 0 0', '43 2924 0 0', '43 2994 0 0', '43 3047 0 0', '43 3062 0 0', '43 3116 0 0', '43 3149 0 0', '43 3172 0 0', '44 1804 0 0', '44 1891 0 0', '44 2004 0 0', '44 2382 0 0', '44 2514 0 0', '44 2523 0 0', '44 2547 0 0', '44 2687 0 0', '44 2751 0 0', '44 2771 0 0', '44 2827 0 0', '44 2829 0 0', '44 2910 0 0', '44 2913 0 0', '44 2924 0 0', '44 3013 0 0', '44 3047 0 0', '45 0268 0 0', '45 1831 0 0', '45 1935 0 0', '45 2140 0 0', '45 2257 0 0', '45 2359 0 0', '45 2360 0 0', '45 2452 0 0', '45 2493 0 0', '45 2669 0 0', '45 2680 0 0', '45 2716 0 0', '45 2765 0 0', '45 2816 0 0', '45 2878 0 0', '45 2882 0 0', '45 2900 0 0', '45 2964 0 0', '45 2965 0 0', '45 2969 0 0', '45 3002 0 0', '45 3058 0 0', '45 3129 0 0', '45 3137 0 0', '45 3152 0 0', '45 3168 0 0', '48 0149 0 0', '48 1353 0 0', '48 1666 0 0', '48 1729 0 0', '48 1797 0 0', '48 1863 0 0', '48 2073 0 0', '48 2223 0 0', '48 2226 0 0', '48 2285 0 0', '48 2325 0 0', '48 2589 0 0', '49 1152 0 0', '49 1515 0 0', '49 1681 0 0', '49 2127 0 0', '49 2390 0 0', '49 2561 0 0', '49 2795 0 0', '49 2832 0 0', '57 3077 0 0', '58 0432 0 0', '58 0536 0 0', '58 1293 0 0', '58 1344 0 0', '58 1398 0 0', '58 1411 0 0', '58 1420 0 0', '58 1445 0 0', '58 1619 0 0', '58 1629 0 0', '58 1631 0 0', '58 1691 0 0', '58 1709 0 0', '58 1812 0 0', '58 1944 0 0', '58 2098 0 0', '58 2115 0 0', '58 2122 0 0', '58 2123 0 0', '58 2249 0 0', '58 2349 0 0', '58 2395 0 0', '58 2634 0 0', '58 2636 0 0', '58 2719 0 0', '58 2731 0 0', '58 2825 0 0', '58 3159 0 0', '58 3166 0 0', '58 3167 0 0', '59 0440 0 0', '59 0944 0 0', '59 1112 0 0', '59 1170 0 0', '59 1235 0 0', '59 1314 0 0', '59 1324 0 0', '59 1456 0 0', '59 1457 0 0', '59 1700 0 0', '59 1785 0 0', '59 1786 0 0', '59 1855 0 0', '59 1860 0 0', '59 1885 0 0', '59 1973 0 0', '59 2018 0 0', '59 2032 0 0', '59 2033 0 0', '59 2092 0 0', '59 2107 0 0', '59 2111 0 0', '59 2127 0 0', '59 2203 0 0', '59 2251 0 0', '59 2274 0 0', '59 2359 0 0', '59 2412 0 0', '59 2524 0 0', '59 2530 0 0', '59 2532 0 0', '59 2537 0 0', '59 2543 0 0', '59 2552 0 0', '59 2559 0 0', '59 2631 0 0', '59 2673 0 0', '59 2905 0 0', '59 2974 0 0', '59 2991 0 0', '59 3053 0 0', '59 3083 0 0', '59 3126 0 0', '60 2023 0 0', '60 2046 0 0', '60 2198 0 0', '60 2377 0 0', '60 2406 0 0', '60 2452 0 0', '60 2493 0 0', '60 2516 0 0', '60 2526 0 0', '60 2593 0 0', '60 2710 0 0', '60 2715 0 0', '60 2716 0 0', '60 2717 0 0', '60 2718 0 0', '60 2765 0 0', '60 2816 0 0', '60 2817 0 0', '60 2882 0 0', '60 2957 0 0', '60 2959 0 0', '60 2960 0 0', '60 2964 0 0', '60 2976 0 0', '60 3087 0 0', '60 3137 0 0', '60 3147 0 0', '61 0239 0 0', '61 0440 0 0', '61 0634 0 0', '61 1032 0 0', '61 1236 0 0', '61 1457 0 0', '61 1514 0 0', '61 1675 0 0', '61 1830 0 0', '61 1927 0 0', '61 1976 0 0', '61 2160 0 0', '61 2307 0 0', '61 2363 0 0', '61 2451 0 0', '61 2452 0 0', '61 2524 0 0', '61 2575 0 0', '61 2631 0 0', '61 2641 0 0', '61 2711 0 0', '61 2765 0 0', '61 2965 0 0', '61 2966 0 0', '61 2976 0 0', '61 2990 0 0', '61 3001 0 0', '61 3012 0 0', '61 3134 0 0', '61 3168 0 0', '61 3169 0 0', '62 0950 0 0', '62 1601 0 0', '62 1811 0 0', '62 2289 0 0', '62 2664 0 0', '62 2714 0 0', '62 3075 0 0', '62 3156 0 0', '63 0950 0 0', '63 1601 0 0', '63 1795 0 0', '63 1811 0 0', '63 2266 0 0', '63 2289 0 0', '63 2557 0 0', '63 2664 0 0', '63 2714 0 0', '63 2973 0 0', '63 3075 0 0', '63 3156 0 0', '64 2651 0 0']\n",
            "{1: ['doc_1410', 'doc_1572', 'doc_1605', 'doc_2020', 'doc_2358'], 2: ['doc_2434', 'doc_2863', 'doc_3078'], 3: ['doc_1134', 'doc_1613', 'doc_1807', 'doc_1947', 'doc_2290', 'doc_2923'], 4: ['doc_1749', 'doc_1811', 'doc_2256', 'doc_2371', 'doc_2597', 'doc_2796', 'doc_2912', 'doc_3043', 'doc_3073', 'doc_3082', 'doc_3127', 'doc_3128'], 5: ['doc_756', 'doc_1307', 'doc_1502', 'doc_2035', 'doc_2299', 'doc_2399', 'doc_2501', 'doc_2820'], 6: ['doc_1543', 'doc_2078', 'doc_2828'], 7: ['doc_1198', 'doc_1338', 'doc_1877', 'doc_1960', 'doc_2150', 'doc_2228', 'doc_2256', 'doc_2280', 'doc_2320', 'doc_2342', 'doc_2376', 'doc_2482', 'doc_2578', 'doc_2597', 'doc_2618', 'doc_2685', 'doc_2700', 'doc_2777', 'doc_2865', 'doc_2866', 'doc_2895', 'doc_2912', 'doc_2941', 'doc_3043', 'doc_3082', 'doc_3128', 'doc_3141', 'doc_3148'], 8: ['doc_2625', 'doc_2849', 'doc_3032'], 9: ['doc_2372', 'doc_2632', 'doc_2870', 'doc_2876', 'doc_3068', 'doc_3111', 'doc_3128', 'doc_3158', 'doc_3177'], 10: ['doc_46', 'doc_141', 'doc_392', 'doc_950', 'doc_1158', 'doc_1198', 'doc_1262', 'doc_1380', 'doc_1471', 'doc_1601', 'doc_1613', 'doc_1747', 'doc_1795', 'doc_1811', 'doc_2060', 'doc_2150', 'doc_2256', 'doc_2289', 'doc_2342', 'doc_2376', 'doc_2433', 'doc_2618', 'doc_2664', 'doc_2685', 'doc_2700', 'doc_2714', 'doc_2777', 'doc_2785', 'doc_2851', 'doc_2895', 'doc_2896', 'doc_2912', 'doc_3039', 'doc_3075', 'doc_3156'], 11: ['doc_1043', 'doc_1188', 'doc_1306', 'doc_1358', 'doc_1396', 'doc_1491', 'doc_1923', 'doc_2246', 'doc_2316', 'doc_2527', 'doc_2699', 'doc_2710', 'doc_2715', 'doc_2716', 'doc_2906', 'doc_2923', 'doc_2956', 'doc_3073', 'doc_3150'], 12: ['doc_1523', 'doc_2080', 'doc_2246', 'doc_2629', 'doc_3127'], 13: ['doc_115', 'doc_1223', 'doc_1231', 'doc_1551', 'doc_1625', 'doc_1795', 'doc_1807', 'doc_1947', 'doc_2495', 'doc_2579', 'doc_2897'], 14: ['doc_74', 'doc_117', 'doc_232', 'doc_776', 'doc_827', 'doc_850', 'doc_851', 'doc_852', 'doc_854', 'doc_855', 'doc_856', 'doc_857', 'doc_858', 'doc_860', 'doc_861', 'doc_862', 'doc_864', 'doc_865', 'doc_866', 'doc_1175', 'doc_1724', 'doc_1919', 'doc_1956', 'doc_1969', 'doc_1980', 'doc_1997', 'doc_2017', 'doc_2041', 'doc_2108', 'doc_2118', 'doc_2146', 'doc_2176', 'doc_2191', 'doc_2272', 'doc_2337', 'doc_2348', 'doc_2397', 'doc_2563', 'doc_2664', 'doc_2679', 'doc_2714', 'doc_2716', 'doc_3075', 'doc_3187'], 15: ['doc_1231', 'doc_1551', 'doc_1613', 'doc_1947', 'doc_2263', 'doc_2495', 'doc_2598', 'doc_2685', 'doc_2701', 'doc_2880'], 16: ['doc_1746', 'doc_1749', 'doc_1828', 'doc_1854', 'doc_1960', 'doc_2070', 'doc_2114', 'doc_2342', 'doc_2376', 'doc_2378', 'doc_2500', 'doc_2632', 'doc_2817', 'doc_2912', 'doc_3073', 'doc_3105', 'doc_3148'], 17: ['doc_115', 'doc_405', 'doc_1134', 'doc_1223', 'doc_1231', 'doc_1535', 'doc_1551', 'doc_1613', 'doc_1807', 'doc_1934', 'doc_1947', 'doc_2290', 'doc_2495', 'doc_2579', 'doc_2586', 'doc_2923'], 18: ['doc_1158', 'doc_1215', 'doc_1262', 'doc_1471', 'doc_1613', 'doc_1811', 'doc_2060', 'doc_2175', 'doc_2413', 'doc_2433', 'doc_2685'], 19: ['doc_141', 'doc_863', 'doc_950', 'doc_1601', 'doc_2266', 'doc_2664', 'doc_2714', 'doc_2973', 'doc_3075', 'doc_3156', 'doc_3175'], 20: ['doc_1563', 'doc_2695', 'doc_2986'], 21: ['doc_1429', 'doc_1847', 'doc_2189', 'doc_2490', 'doc_2603', 'doc_2701', 'doc_2702', 'doc_2703', 'doc_2932', 'doc_3018', 'doc_3139'], 22: ['doc_2369', 'doc_2384', 'doc_2441', 'doc_2473', 'doc_2564', 'doc_2637', 'doc_2638', 'doc_2678', 'doc_2692', 'doc_2751', 'doc_2760', 'doc_2761', 'doc_2827', 'doc_2828', 'doc_2829', 'doc_3116', 'doc_3149'], 23: ['doc_2578', 'doc_2849', 'doc_3137', 'doc_3148'], 24: ['doc_268', 'doc_1696', 'doc_1892', 'doc_2069', 'doc_2123', 'doc_2297', 'doc_2373', 'doc_2667', 'doc_2862', 'doc_2970', 'doc_2996', 'doc_3078', 'doc_3098'], 25: ['doc_268', 'doc_757', 'doc_963', 'doc_1408', 'doc_1518', 'doc_1526', 'doc_1533', 'doc_1572', 'doc_1653', 'doc_1698', 'doc_1719', 'doc_1805', 'doc_1892', 'doc_1901', 'doc_2085', 'doc_2095', 'doc_2218', 'doc_2277', 'doc_2318', 'doc_2319', 'doc_2358', 'doc_2373', 'doc_2434', 'doc_2452', 'doc_2535', 'doc_2582', 'doc_2667', 'doc_2668', 'doc_2669', 'doc_2681', 'doc_2741', 'doc_2765', 'doc_2798', 'doc_2818', 'doc_2831', 'doc_2859', 'doc_2862', 'doc_2863', 'doc_2881', 'doc_2918', 'doc_2928', 'doc_2984', 'doc_2988', 'doc_2996', 'doc_3006', 'doc_3048', 'doc_3059', 'doc_3067', 'doc_3088', 'doc_3089', 'doc_3119'], 26: ['doc_1071', 'doc_1198', 'doc_1338', 'doc_1749', 'doc_1828', 'doc_1854', 'doc_1960', 'doc_2080', 'doc_2150', 'doc_2256', 'doc_2320', 'doc_2342', 'doc_2376', 'doc_2379', 'doc_2541', 'doc_2597', 'doc_2618', 'doc_2632', 'doc_2700', 'doc_2740', 'doc_2777', 'doc_2851', 'doc_2866', 'doc_2912', 'doc_2938', 'doc_3039', 'doc_3043', 'doc_3048', 'doc_3082', 'doc_3128'], 27: ['doc_1641', 'doc_1642', 'doc_1750', 'doc_1752', 'doc_1879', 'doc_1884', 'doc_1901', 'doc_2095', 'doc_2297', 'doc_2435', 'doc_2481', 'doc_2498', 'doc_2560', 'doc_2596', 'doc_2669', 'doc_2734', 'doc_2747', 'doc_2768', 'doc_2798', 'doc_2818', 'doc_2859', 'doc_2864', 'doc_2902', 'doc_2918', 'doc_2955', 'doc_2983', 'doc_2988', 'doc_3000', 'doc_3052'], 28: ['doc_2578', 'doc_2849', 'doc_2890', 'doc_2949', 'doc_3032'], 29: ['doc_377', 'doc_513', 'doc_610', 'doc_935', 'doc_1094', 'doc_1420', 'doc_1537', 'doc_1538', 'doc_1539', 'doc_1840', 'doc_1841', 'doc_1967', 'doc_2028', 'doc_2089', 'doc_2120', 'doc_2462', 'doc_2927', 'doc_2932', 'doc_3037'], 30: ['doc_1926', 'doc_2486', 'doc_2786', 'doc_2917'], 31: ['doc_2125', 'doc_3047'], 32: ['doc_366', 'doc_1145', 'doc_3139'], 33: ['doc_2805'], 36: ['doc_1265', 'doc_1350', 'doc_1683', 'doc_1768', 'doc_1787', 'doc_1825', 'doc_1836', 'doc_2015', 'doc_2084', 'doc_2110', 'doc_2179', 'doc_2340', 'doc_2423', 'doc_2702', 'doc_2708', 'doc_2733', 'doc_2824', 'doc_2836', 'doc_2986', 'doc_3094'], 37: ['doc_2265', 'doc_2377', 'doc_2558', 'doc_2625', 'doc_2632', 'doc_2651', 'doc_2738', 'doc_2840', 'doc_2939', 'doc_2941', 'doc_3144', 'doc_3148'], 38: ['doc_2265', 'doc_2558', 'doc_2625', 'doc_2632', 'doc_2651', 'doc_2868', 'doc_2939', 'doc_2940', 'doc_2941', 'doc_2956', 'doc_2957', 'doc_2958', 'doc_2960', 'doc_3031', 'doc_3103', 'doc_3150'], 39: ['doc_1693', 'doc_1861', 'doc_2126', 'doc_2265', 'doc_2317', 'doc_2558', 'doc_2625', 'doc_2632', 'doc_2651', 'doc_2939', 'doc_2941', 'doc_3031'], 40: ['doc_1614', 'doc_2126', 'doc_2148', 'doc_2265', 'doc_2651', 'doc_2939', 'doc_2940', 'doc_2941', 'doc_2956', 'doc_2958'], 42: ['doc_963', 'doc_1069', 'doc_1518', 'doc_1572', 'doc_1653', 'doc_1805', 'doc_1827', 'doc_1884', 'doc_2022', 'doc_2085', 'doc_2151', 'doc_2247', 'doc_2318', 'doc_2344', 'doc_2522', 'doc_2542', 'doc_2749', 'doc_2951', 'doc_2984', 'doc_3048', 'doc_3072'], 43: ['doc_122', 'doc_266', 'doc_297', 'doc_462', 'doc_1113', 'doc_1325', 'doc_1528', 'doc_1554', 'doc_1686', 'doc_1697', 'doc_2004', 'doc_2195', 'doc_2201', 'doc_2211', 'doc_2382', 'doc_2400', 'doc_2421', 'doc_2514', 'doc_2523', 'doc_2655', 'doc_2687', 'doc_2751', 'doc_2754', 'doc_2771', 'doc_2788', 'doc_2811', 'doc_2826', 'doc_2827', 'doc_2828', 'doc_2829', 'doc_2841', 'doc_2883', 'doc_2910', 'doc_2913', 'doc_2924', 'doc_2994', 'doc_3047', 'doc_3062', 'doc_3116', 'doc_3149', 'doc_3172'], 44: ['doc_1804', 'doc_1891', 'doc_2004', 'doc_2382', 'doc_2514', 'doc_2523', 'doc_2547', 'doc_2687', 'doc_2751', 'doc_2771', 'doc_2827', 'doc_2829', 'doc_2910', 'doc_2913', 'doc_2924', 'doc_3013', 'doc_3047'], 45: ['doc_268', 'doc_1831', 'doc_1935', 'doc_2140', 'doc_2257', 'doc_2359', 'doc_2360', 'doc_2452', 'doc_2493', 'doc_2669', 'doc_2680', 'doc_2716', 'doc_2765', 'doc_2816', 'doc_2878', 'doc_2882', 'doc_2900', 'doc_2964', 'doc_2965', 'doc_2969', 'doc_3002', 'doc_3058', 'doc_3129', 'doc_3137', 'doc_3152', 'doc_3168'], 48: ['doc_149', 'doc_1353', 'doc_1666', 'doc_1729', 'doc_1797', 'doc_1863', 'doc_2073', 'doc_2223', 'doc_2226', 'doc_2285', 'doc_2325', 'doc_2589'], 49: ['doc_1152', 'doc_1515', 'doc_1681', 'doc_2127', 'doc_2390', 'doc_2561', 'doc_2795', 'doc_2832'], 57: ['doc_3077'], 58: ['doc_432', 'doc_536', 'doc_1293', 'doc_1344', 'doc_1398', 'doc_1411', 'doc_1420', 'doc_1445', 'doc_1619', 'doc_1629', 'doc_1631', 'doc_1691', 'doc_1709', 'doc_1812', 'doc_1944', 'doc_2098', 'doc_2115', 'doc_2122', 'doc_2123', 'doc_2249', 'doc_2349', 'doc_2395', 'doc_2634', 'doc_2636', 'doc_2719', 'doc_2731', 'doc_2825', 'doc_3159', 'doc_3166', 'doc_3167'], 59: ['doc_440', 'doc_944', 'doc_1112', 'doc_1170', 'doc_1235', 'doc_1314', 'doc_1324', 'doc_1456', 'doc_1457', 'doc_1700', 'doc_1785', 'doc_1786', 'doc_1855', 'doc_1860', 'doc_1885', 'doc_1973', 'doc_2018', 'doc_2032', 'doc_2033', 'doc_2092', 'doc_2107', 'doc_2111', 'doc_2127', 'doc_2203', 'doc_2251', 'doc_2274', 'doc_2359', 'doc_2412', 'doc_2524', 'doc_2530', 'doc_2532', 'doc_2537', 'doc_2543', 'doc_2552', 'doc_2559', 'doc_2631', 'doc_2673', 'doc_2905', 'doc_2974', 'doc_2991', 'doc_3053', 'doc_3083', 'doc_3126'], 60: ['doc_2023', 'doc_2046', 'doc_2198', 'doc_2377', 'doc_2406', 'doc_2452', 'doc_2493', 'doc_2516', 'doc_2526', 'doc_2593', 'doc_2710', 'doc_2715', 'doc_2716', 'doc_2717', 'doc_2718', 'doc_2765', 'doc_2816', 'doc_2817', 'doc_2882', 'doc_2957', 'doc_2959', 'doc_2960', 'doc_2964', 'doc_2976', 'doc_3087', 'doc_3137', 'doc_3147'], 61: ['doc_239', 'doc_440', 'doc_634', 'doc_1032', 'doc_1236', 'doc_1457', 'doc_1514', 'doc_1675', 'doc_1830', 'doc_1927', 'doc_1976', 'doc_2160', 'doc_2307', 'doc_2363', 'doc_2451', 'doc_2452', 'doc_2524', 'doc_2575', 'doc_2631', 'doc_2641', 'doc_2711', 'doc_2765', 'doc_2965', 'doc_2966', 'doc_2976', 'doc_2990', 'doc_3001', 'doc_3012', 'doc_3134', 'doc_3168', 'doc_3169'], 62: ['doc_950', 'doc_1601', 'doc_1811', 'doc_2289', 'doc_2664', 'doc_2714', 'doc_3075', 'doc_3156'], 63: ['doc_950', 'doc_1601', 'doc_1795', 'doc_1811', 'doc_2266', 'doc_2289', 'doc_2557', 'doc_2664', 'doc_2714', 'doc_2973', 'doc_3075', 'doc_3156'], 64: ['doc_2651']}\n"
          ]
        }
      ],
      "source": [
        "tab = make_query_corpus(query_path)\n",
        "for i in range(len(tab)):\n",
        "  tab[i] = re.sub('\\n',' ',tab[i])\n",
        "  tab[i] = tab[i].strip()\n",
        "print(tab)\n",
        "\n",
        "with open(qrels_path, 'r') as f:\n",
        "\tqfile = f.read().splitlines()\n",
        "print(qfile)\n",
        "\n",
        "dictio = {}\n",
        "for f in qfile:\n",
        "  t = f.split()\n",
        "  key = int(t[0])\n",
        "  if not key in dictio:\n",
        "    dictio[key] = []\n",
        "  dictio[key].append('doc_'+str(int(t[1])))\n",
        "print(dictio)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8M85KC3RvutM",
        "outputId": "0d39ade5-59b8-4fc1-833c-273e7abc4aa4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1 : F1-Score: 0.20000000000000004\n",
            "2 : F1-Score: 0\n",
            "3 : F1-Score: 0.16666666666666666\n",
            "4 : F1-Score: 0.25\n",
            "5 : F1-Score: 0\n",
            "6 : F1-Score: 0\n",
            "7 : F1-Score: 0.2857142857142857\n",
            "8 : F1-Score: 0.3333333333333333\n",
            "9 : F1-Score: 0.4444444444444444\n",
            "10 : F1-Score: 0.37142857142857144\n",
            "11 : F1-Score: 0.5263157894736842\n",
            "12 : F1-Score: 0.20000000000000004\n",
            "13 : F1-Score: 0.2727272727272727\n",
            "14 : F1-Score: 0.5\n",
            "15 : F1-Score: 0.20000000000000004\n",
            "16 : F1-Score: 0.11764705882352941\n",
            "17 : F1-Score: 0.125\n",
            "18 : F1-Score: 0.18181818181818182\n",
            "19 : F1-Score: 0.45454545454545453\n",
            "20 : F1-Score: 0\n",
            "21 : F1-Score: 0.09090909090909091\n",
            "22 : F1-Score: 0.47058823529411764\n",
            "23 : F1-Score: 0\n",
            "24 : F1-Score: 0.15384615384615385\n",
            "25 : F1-Score: 0.3333333333333333\n",
            "26 : F1-Score: 0.3333333333333333\n",
            "27 : F1-Score: 0.3103448275862069\n",
            "28 : F1-Score: 0.6\n",
            "29 : F1-Score: 0.7368421052631579\n",
            "30 : F1-Score: 0.25\n",
            "31 : F1-Score: 0\n",
            "32 : F1-Score: 0.6666666666666666\n",
            "33 : F1-Score: 0\n",
            "34 : F1-Score: 0.25\n",
            "35 : F1-Score: 0.16666666666666666\n",
            "36 : F1-Score: 0.5\n",
            "37 : F1-Score: 0.3333333333333333\n",
            "38 : F1-Score: 0.5\n",
            "39 : F1-Score: 0.23809523809523808\n",
            "40 : F1-Score: 0.12195121951219512\n",
            "41 : F1-Score: 0.058823529411764705\n",
            "42 : F1-Score: 0.23076923076923078\n",
            "43 : F1-Score: 0.08333333333333333\n",
            "44 : F1-Score: 0\n",
            "45 : F1-Score: 1.0\n",
            "46 : F1-Score: 0.20000000000000004\n",
            "47 : F1-Score: 0.3488372093023256\n",
            "48 : F1-Score: 0.14814814814814814\n",
            "49 : F1-Score: 0.3870967741935484\n",
            "50 : F1-Score: 0.25\n",
            "51 : F1-Score: 0.3333333333333333\n",
            "52 : F1-Score: 0\n"
          ]
        }
      ],
      "source": [
        "tab_f1_score = []\n",
        "num=0\n",
        "for x in dictio:\n",
        "  num=num+1\n",
        "  y_true = dictio.get(x)\n",
        "  query = tab[x - 1]\n",
        "  y_pred = get_result(query , list(Data.keys()) , 'cosine' , Data , inv_index , len(dictio.get(x)))\n",
        "  y_pred_tab=[]\n",
        "  for i in range(len(y_pred)):\n",
        "    y_pred_tab.append(y_pred[i][0])\n",
        "\n",
        "  true_positive = 0\n",
        "  for doc in y_pred_tab:\n",
        "    if doc in y_true:\n",
        "      true_positive = true_positive + 1\n",
        "\n",
        "  false_positive = 0\n",
        "  for doc in y_pred_tab:\n",
        "    if not doc in y_true:\n",
        "      false_positive = false_positive + 1\n",
        "\n",
        "  false_negative = 0\n",
        "  for doc in y_true:\n",
        "    if not doc in y_pred_tab:\n",
        "      false_negative = false_negative + 1\n",
        "\n",
        "  precision = true_positive / (true_positive + false_positive)\n",
        "  recall = true_positive / (true_positive + false_negative)\n",
        "  if precision==0 and recall==0:\n",
        "    f1=0\n",
        "  else:\n",
        "    f1 = 2 * precision * recall / (precision + recall)\n",
        "\n",
        "  print(num,\": F1-Score:\",f1)\n",
        "  tab_f1_score.append(f1)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rnxd44j5Cnou",
        "outputId": "3df8b142-f376-4a6a-db4f-fc87785541f5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.26395947733281927\n"
          ]
        }
      ],
      "source": [
        "print(statistics.mean(tab_f1_score))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.11.2"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}