similar_items.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import glob\n",
    "import random\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "import multiprocessing\n",
    "from multiprocessing import Pool\n",
    "from functools import partial\n",
    "from multiprocessing import Manager"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "shingle_size = 5\n",
    "jaccard_threshold = 0.25\n",
    "minhash_threshold = 0.25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_shingles(filename):\n",
    "    print(\"==== Creating shingles for file: {}\".format(filename))\n",
    "    shingles_set = set()\n",
    "\n",
    "    with open(filename, 'rt', encoding='latin1') as file:\n",
    "        for line in file:\n",
    "            line = line.strip().lower()\n",
    "            shingles_set.update([line[start: (start + shingle_size)] for start in range(0, len(line) - shingle_size)])\n",
    "    \n",
    "    shingles_set = set(map(lambda x: x.replace(\" \",\"_\"), shingles_set))\n",
    "\n",
    "    print(\"===== Done ======\")\n",
    "    #print(shingles_set)\n",
    "    return shingles_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "==== Creating shingles for file: ./new_data/accuracy_garmin_nuvi_255W_gps.txt.data\n",
      "===== Done ======\n",
      "==== Creating shingles for file: ./new_data/performance_netbook_1005ha.txt.data\n",
      "===== Done ======\n",
      "==== Creating shingles for file: ./new_data/display_garmin_nuvi_255W_gps.txt.data\n",
      "===== Done ======\n",
      "==== Creating shingles for file: ./new_data/screen_ipod_nano_8gb.txt.data\n",
      "===== Done ======\n",
      "==== Creating shingles for file: ./new_data/performance_honda_accord_2008.txt.data\n",
      "===== Done ======\n",
      "==== Creating shingles for file: ./new_data/battery-life_ipod_nano_8gb.txt.data\n",
      "===== Done ======\n",
      "==== Creating shingles for file: ./new_data/quality_toyota_camry_2007.txt.data\n",
      "===== Done ======\n",
      "==== Creating shingles for file: ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "===== Done ======\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "data_dir = \"./new_data\"\n",
    "filenames = [f for f in glob.glob(data_dir+\"/*\")]\n",
    "documents_shingles = [get_shingles(f) for f in filenames]\n",
    "\n",
    "print(len(documents_shingles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jaccard_similarity(set_one, set_two):\n",
    "    intersection = set_one.intersection(set_two)\n",
    "    union = set_one.union(set_two)\n",
    "    return len(intersection)/len(union)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=========== Similar documents are ===========\n",
      "./new_data/display_garmin_nuvi_255W_gps.txt.data and ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "=============================================\n",
      "Range of similarity scores is 0.09442776109442776 to 0.26670146137787054\n"
     ]
    }
   ],
   "source": [
    "total_docs = len(filenames)\n",
    "similar_docs = []\n",
    "\n",
    "sim_scores = []\n",
    "\n",
    "for i in range(total_docs):\n",
    "    j = i+1\n",
    "    while j < total_docs:\n",
    "        \n",
    "        #print(\"*** Computing similarity between file:{} and file:{} ***\".format(filenames[i],filenames[j]))\n",
    "        sim = jaccard_similarity(documents_shingles[i], documents_shingles[j])\n",
    "        #print(sim)\n",
    "        sim_scores.append(sim)\n",
    "        \n",
    "        if sim >= jaccard_threshold :\n",
    "              similar_docs.append((filenames[i],filenames[j],jaccard_similarity))\n",
    "\n",
    "        j += 1      \n",
    "              \n",
    "print(\"=========== Similar documents are ===========\")\n",
    "for similar_doc in similar_docs:\n",
    "    print(\"{} and {}\".format(similar_doc[0], similar_doc[1]))\n",
    "print(\"=============================================\")\n",
    "\n",
    "sim_scores = sorted(sim_scores)\n",
    "print(\"Range of similarity scores is {} to {}\".format(sim_scores[0],sim_scores[-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15188\n"
     ]
    }
   ],
   "source": [
    "#Generating all the shingles space\n",
    "\n",
    "all_shingles_space = set()\n",
    "for doc_shingle in documents_shingles:\n",
    "    all_shingles_space.update(doc_shingle)\n",
    "    \n",
    "all_shingles_space = list(all_shingles_space)\n",
    "print(len(all_shingles_space))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=========Total rows ===== : 15188\n",
      "===============================\n"
     ]
    }
   ],
   "source": [
    "\n",
    "documents_vec = [[] for i in range(total_docs)]\n",
    "for shingle in all_shingles_space:\n",
    "    for i in range(total_docs):\n",
    "        documents_vec[i].append(int(shingle in documents_shingles[i]))\n",
    "        \n",
    "print(\"=========Total rows ===== : {}\".format(len(documents_vec[0])))\n",
    "#print(documents_vec[0])\n",
    "print(\"===============================\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15188\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Doc1</th>\n",
       "      <th>Doc2</th>\n",
       "      <th>Doc3</th>\n",
       "      <th>Doc4</th>\n",
       "      <th>Doc5</th>\n",
       "      <th>Doc6</th>\n",
       "      <th>Doc7</th>\n",
       "      <th>Doc8</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Doc1  Doc2  Doc3  Doc4  Doc5  Doc6  Doc7  Doc8\n",
       "0     0     1     0     0     1     0     0     0\n",
       "1     0     1     0     0     0     0     0     0\n",
       "2     0     1     0     0     0     0     0     0\n",
       "3     1     0     0     0     0     0     0     0\n",
       "4     0     1     0     0     0     0     0     0"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_data = {}\n",
    "for doc_id,doc_vec in enumerate(documents_vec):\n",
    "    df_data[\"Doc\"+str(doc_id+1)] = doc_vec\n",
    "    \n",
    "vec_df = pd.DataFrame(df_data)\n",
    "print(len(vec_df))\n",
    "vec_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_rows = vec_df.shape[0]\n",
    "\n",
    "# hashing functions of the form : (a(x)+b)mod(num_columns)\n",
    "\n",
    "num_hash_fn = 100\n",
    "all_a = [random.randint(num_rows+10,num_rows+1000) for i in range(num_hash_fn)]\n",
    "all_b = [random.randint(num_rows+2000,num_rows+3000) for i in range(num_hash_fn)]\n",
    "\n",
    "hash_values = list(zip(all_a, all_b))\n",
    "num_columns = total_docs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hash_row(a,b,r,n):\n",
    "    return int((a*r + b)%n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Doc1</th>\n",
       "      <th>Doc2</th>\n",
       "      <th>Doc3</th>\n",
       "      <th>Doc4</th>\n",
       "      <th>Doc5</th>\n",
       "      <th>Doc6</th>\n",
       "      <th>Doc7</th>\n",
       "      <th>Doc8</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "      <td>inf</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Doc1  Doc2  Doc3  Doc4  Doc5  Doc6  Doc7  Doc8\n",
       "0   inf   inf   inf   inf   inf   inf   inf   inf\n",
       "1   inf   inf   inf   inf   inf   inf   inf   inf\n",
       "2   inf   inf   inf   inf   inf   inf   inf   inf\n",
       "3   inf   inf   inf   inf   inf   inf   inf   inf\n",
       "4   inf   inf   inf   inf   inf   inf   inf   inf"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sig_data = np.full((num_hash_fn,total_docs),np.inf)\n",
    "sig_cols = [\"Doc\"+str(i) for i in range(1,total_docs+1)]\n",
    "\n",
    "signature_df = pd.DataFrame(data=sig_data, columns=sig_cols)\n",
    "signature_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15188\n"
     ]
    }
   ],
   "source": [
    "print(num_rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "took 283.4990425109863 seconds.\n"
     ]
    }
   ],
   "source": [
    "# Implementing min hash algorithm (TODO: Optimize this step, using multi-cores)\n",
    "start_time = time.time() \n",
    "\n",
    "for row in range(num_rows):\n",
    "    # Computing all hash functions for a row\n",
    "    hash_outputs = []\n",
    "    for i in range(num_hash_fn):\n",
    "        hash_outputs.append(hash_row(*hash_values[i], row, num_rows))\n",
    "        \n",
    "    cols_values = vec_df.loc[row]\n",
    "    \n",
    "    for col_id, col_val in enumerate(cols_values):\n",
    "        if col_val == 1:\n",
    "            for hash_id, hash_val in enumerate(hash_outputs):\n",
    "                if hash_val < signature_df.loc[hash_id][col_id]:\n",
    "                    signature_df.loc[hash_id][col_id] = hash_val\n",
    "                    \n",
    "end_time = time.time() # for profiling\n",
    "\n",
    "print(\"took {0} seconds.\".format((end_time-start_time)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Doc1</th>\n",
       "      <th>Doc2</th>\n",
       "      <th>Doc3</th>\n",
       "      <th>Doc4</th>\n",
       "      <th>Doc5</th>\n",
       "      <th>Doc6</th>\n",
       "      <th>Doc7</th>\n",
       "      <th>Doc8</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>11.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>2.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>3.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>7.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>3.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.0</td>\n",
       "      <td>3.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0.0</td>\n",
       "      <td>2.0</td>\n",
       "      <td>8.0</td>\n",
       "      <td>10.0</td>\n",
       "      <td>4.0</td>\n",
       "      <td>10.0</td>\n",
       "      <td>4.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1.0</td>\n",
       "      <td>5.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>3.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Doc1  Doc2  Doc3  Doc4  Doc5  Doc6  Doc7  Doc8\n",
       "0   5.0   6.0  11.0   3.0   2.0   6.0   6.0   0.0\n",
       "1   3.0   3.0   3.0   3.0   7.0   3.0   3.0   3.0\n",
       "2   1.0   3.0   5.0   1.0   3.0   3.0   5.0   3.0\n",
       "3   0.0   2.0   8.0  10.0   4.0  10.0   4.0   0.0\n",
       "4   1.0   5.0   3.0   1.0   3.0   3.0   1.0   3.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "signature_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "====== Similar docs using MinHashing are ============\n",
      "./new_data/accuracy_garmin_nuvi_255W_gps.txt.data and ./new_data/performance_netbook_1005ha.txt.data\n",
      "./new_data/accuracy_garmin_nuvi_255W_gps.txt.data and ./new_data/battery-life_ipod_nano_8gb.txt.data\n",
      "./new_data/accuracy_garmin_nuvi_255W_gps.txt.data and ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "./new_data/performance_netbook_1005ha.txt.data and ./new_data/performance_honda_accord_2008.txt.data\n",
      "./new_data/performance_netbook_1005ha.txt.data and ./new_data/battery-life_ipod_nano_8gb.txt.data\n",
      "./new_data/display_garmin_nuvi_255W_gps.txt.data and ./new_data/performance_honda_accord_2008.txt.data\n",
      "./new_data/display_garmin_nuvi_255W_gps.txt.data and ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "./new_data/screen_ipod_nano_8gb.txt.data and ./new_data/battery-life_ipod_nano_8gb.txt.data\n",
      "./new_data/screen_ipod_nano_8gb.txt.data and ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "./new_data/battery-life_ipod_nano_8gb.txt.data and ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "======================================================\n"
     ]
    }
   ],
   "source": [
    "# Finding similar items using min hashing\n",
    "minhash_similar = []\n",
    "for i in range(1,total_docs+1):\n",
    "    j = i+1\n",
    "    \n",
    "    while j <= total_docs:\n",
    "        #print(\"=== Computing similarity between file:{} and file:{} ===\".format(filenames[i-1],filenames[j-1]))\n",
    "        sim = np.sum(signature_df[\"Doc\"+str(i)] == signature_df[\"Doc\"+str(j)])/num_hash_fn\n",
    "        #print(sim)\n",
    "\n",
    "        if sim >= minhash_threshold :\n",
    "              minhash_similar.append((filenames[i-1],filenames[j-1],sim))\n",
    "\n",
    "        j += 1         \n",
    "        \n",
    "print(\"====== Similar docs using MinHashing are ============\")\n",
    "for similar_doc in minhash_similar:\n",
    "    print(\"{} and {}\".format(similar_doc[0], similar_doc[1]))\n",
    "print(\"======================================================\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "**************** Threshold chosen is 0.30867895949930413 ***************\n"
     ]
    }
   ],
   "source": [
    "# Defining parameters for lsh\n",
    "\n",
    "b = 34\n",
    "r = 3\n",
    "\n",
    "t = pow(1/b, 1/r)\n",
    "print(\"**************** Threshold chosen is {} ***************\".format(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# hashing functions of the form : (a(x)+b)mod(num_buckets)\n",
    "\n",
    "num_buckets = 100003\n",
    "num_lsh_hashes = b\n",
    "all_a = [random.randint(0,num_buckets+100000) for i in range(num_lsh_hashes)]\n",
    "all_b = [random.randint(0,num_buckets+100000) for i in range(num_lsh_hashes)]\n",
    "\n",
    "\n",
    "lsh_hash_values = list(zip(all_a, all_b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "====== Candidate pairs are =======\n",
      "('Doc1', 'Doc8')\n",
      "('Doc2', 'Doc8')\n",
      "('Doc3', 'Doc8')\n",
      "('Doc1', 'Doc7')\n",
      "('Doc4', 'Doc6', 'Doc8')\n",
      "('Doc5', 'Doc8')\n",
      "('Doc1', 'Doc2')\n",
      "('Doc3', 'Doc7')\n",
      "('Doc4', 'Doc5')\n",
      "('Doc2', 'Doc6')\n",
      "==================================\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    del lsh_hashes\n",
    "except:\n",
    "    pass\n",
    "\n",
    "\n",
    "lsh_hashes = []\n",
    "\n",
    "for i in range(b):\n",
    "    lsh_hashes.append({})\n",
    "    for j in range(total_docs):\n",
    "        col_band = signature_df.loc[i*r:(i+1)*r-1, \"Doc\"+str(j+1)]\n",
    "        col_int = int(\"\".join([str(int(x)) for x in list(col_band)]))\n",
    "        \n",
    "        hash_output = hash_row(*lsh_hash_values[i], col_int, num_buckets)\n",
    "        \n",
    "        if hash_output in lsh_hashes[i]:\n",
    "            lsh_hashes[i][hash_output].update([\"Doc\"+str(j+1)])\n",
    "        else:\n",
    "            lsh_hashes[i][hash_output] = set([\"Doc\"+str(j+1)])\n",
    "\n",
    "candidate_pairs = []\n",
    "#print(lsh_hashes)\n",
    "for lsh_hash in lsh_hashes:\n",
    "    for k,v in lsh_hash.items():\n",
    "        if len(v) > 1:\n",
    "            candidate_pairs.append(tuple(sorted(list(v))))\n",
    "\n",
    "candidate_pairs = set(candidate_pairs)            \n",
    "print(\"====== Candidate pairs are =======\")\n",
    "[print(x) for x in candidate_pairs]\n",
    "print(\"==================================\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "====== Similar docs using LSH are ====================\n",
      "./new_data/accuracy_garmin_nuvi_255W_gps.txt.data and ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "./new_data/display_garmin_nuvi_255W_gps.txt.data and ./new_data/speed_garmin_nuvi_255W_gps.txt.data\n",
      "./new_data/screen_ipod_nano_8gb.txt.data and ./new_data/battery-life_ipod_nano_8gb.txt.data\n",
      "./new_data/accuracy_garmin_nuvi_255W_gps.txt.data and ./new_data/performance_netbook_1005ha.txt.data\n",
      "./new_data/performance_netbook_1005ha.txt.data and ./new_data/battery-life_ipod_nano_8gb.txt.data\n",
      "======================================================\n"
     ]
    }
   ],
   "source": [
    "lsh_similar = []\n",
    "for candidate_pair in candidate_pairs:\n",
    "        file1 = int(candidate_pair[0][3:])-1\n",
    "        file2 = int(candidate_pair[1][3:])-1\n",
    "        #print(\"=== Computing similarity between file:{} and file:{} ===\".format(filenames[file1],filenames[file2]))\n",
    "        sim = np.sum(signature_df[candidate_pair[0]] == signature_df[candidate_pair[1]])/num_hash_fn\n",
    "        #print(sim)\n",
    "\n",
    "        if sim >= minhash_threshold :\n",
    "              lsh_similar.append((filenames[file1],filenames[file2],sim))\n",
    "\n",
    "        j += 1         \n",
    "        \n",
    "print(\"====== Similar docs using LSH are ====================\")\n",
    "for similar_doc in lsh_similar:\n",
    "    print(\"{} and {}\".format(similar_doc[0], similar_doc[1]))\n",
    "print(\"======================================================\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}