FastText_training.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Password similarity measure using word embeddings with FastText"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Author: _Karina Chichifoi_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 0. Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The purpose of this project is to see how similar are the passwords associated to a specific user. Word embeddings are useful for this task, because they can give some additional information about word contexts.\n",
    "\n",
    "In this notebook FastText is used as word embedding model. It represents each word as an _n-gram_ of characters. This method allows to understand the meaning of short words, and also of prefixes and suffixes, making the process of measuring the similarity of passwords easier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Preconditions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before training FastText, the following operation were performed on a 43 GB breach:\n",
    "- Removed passwords longer than 30 characters or shorter than 4.\n",
    "- Removed non ASCII printable characters in a password.\n",
    "- Removed bot, which are recognisable by the same mail used more than 100 times.\n",
    "- Removed HEX passwords (identified by `$HEX[]` and `\\x`).\n",
    "- Removed HTML char set.\n",
    "- Removed mail which appear more than 100 times and less than 2.\n",
    "- Removed mail with non-valid password.\n",
    "\n",
    "After that the passwords were converted in a key-press sequence, thanks to ```word2keypress``` python library. In this way is easier to see more similarities between two passwords.\n",
    "The results were saved in a csv file, which will be used as FastText dataset, in this way:\n",
    "\n",
    "```sample@gmail.com: [\"'97314348'\", \"'voyager1'\"]```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Environment setup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First of all import all useful libraries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from gensim.models import FastText\n",
    "import time\n",
    "import sys\n",
    "from pathlib import Path\n",
    "from PasswordRetriever import PasswordRetriever"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```PasswordRetriever``` is a helper class which retrieves a list of passwords from the cleaned csv file."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Train FastText model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 FastText parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Choose the parameters for FastText embedding model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "negative = 5\n",
    "subsampling = 1e-3\n",
    "min_count = 10\n",
    "min_n = 1  \n",
    "max_n = 4  \n",
    "SIZE = 200  # dimension of the model\n",
    "sg = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case it was used the _skip-gram approach_ (`sg = 1`) with _negative sampling_.\n",
    "\n",
    "- _Skip-gram model_ is chosen, as the distributed representation of the input word is used to predict the context.\n",
    "_Skip-gram model_ works better with subword information, so it is recommended for learning passwords and rare words in general.\n",
    "\n",
    "- _Negative sampling_ makes the training faster. Each training sample updates only a small percentage of the model's weights. For larger datasets (like this case) it is recommended to set _negative sampling_ between 2 and 5.\n",
    "\n",
    "- The dimension of vectors is set to ```200```, in order to have train the model faster. Generally it is recommended to have `SIZE = 300`.  \n",
    "\n",
    "- The ```subsampling``` ignores the most frequent password (more than 1000 occurrences).\n",
    "\n",
    "- ```min_count``` represents the minimum number of occurences of a password in the training dataset.\n",
    "\n",
    "- ```min_n``` and ```max_n``` are the number of respectively _minimum_ and _maximum n-grams_.\n",
    "    - _N-grams_ are used in statistical natural language processing to predict a word and/or the context of a word. \n",
    "    In this case they represent a contiguous sequence of n characters and their purpose is to give subword information.\n",
    "\n",
    "    For example a password `w = qwerty` with `min_n = 4` and `m_max = 5`, will have the following n-grams.\n",
    "    `zw = {<qwe, qwer, wert, erty, rty>, <qwer, qwert, werty, erty>}`\n",
    "\n",
    "    NB `<` and `>` are considered as characters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Training FastText"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The list of password related to every user is obtained from the helper class `PasswordRetriever`.\n",
    "FastText is ready to train the model, based on `password_list`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Processed 0 lines in 3.981590270996094e-05 seconds.\n",
      "Processed 1000000 lines in 8.32761836051941 seconds.\n",
      "Processed 2000000 lines in 8.211445093154907 seconds.\n",
      "Processed 3000000 lines in 8.039046287536621 seconds.\n",
      "Processed 4000000 lines in 8.645042657852173 seconds.\n",
      "Processed 5000000 lines in 8.688397884368896 seconds.\n",
      "Processed 6000000 lines in 8.762989521026611 seconds.\n",
      "Processed 7000000 lines in 9.28832745552063 seconds.\n",
      "Processed 8000000 lines in 9.370487928390503 seconds.\n",
      "Processed 9000000 lines in 8.766379356384277 seconds.\n",
      "Processed 10000000 lines in 8.871519088745117 seconds.\n",
      "Processed 11000000 lines in 8.899347305297852 seconds.\n",
      "Processed 12000000 lines in 8.987047910690308 seconds.\n",
      "Processed 13000000 lines in 9.068806409835815 seconds.\n",
      "Processed 14000000 lines in 9.055849313735962 seconds.\n",
      "Processed 15000000 lines in 10.101937294006348 seconds.\n",
      "Processed 16000000 lines in 9.06157922744751 seconds.\n",
      "Processed 17000000 lines in 9.10492467880249 seconds.\n",
      "Processed 18000000 lines in 10.152393817901611 seconds.\n",
      "Processed 19000000 lines in 9.125312089920044 seconds.\n",
      "Processed 20000000 lines in 9.097816228866577 seconds.\n",
      "Processed 21000000 lines in 9.12251877784729 seconds.\n",
      "Processed 22000000 lines in 9.093791246414185 seconds.\n",
      "Processed 23000000 lines in 9.09725308418274 seconds.\n",
      "Processed 24000000 lines in 9.079681396484375 seconds.\n",
      "Processed 25000000 lines in 9.053807497024536 seconds.\n",
      "Processed 26000000 lines in 9.03109622001648 seconds.\n",
      "Processed 27000000 lines in 8.978954076766968 seconds.\n",
      "Processed 28000000 lines in 9.01730990409851 seconds.\n",
      "Processed 29000000 lines in 8.99671220779419 seconds.\n",
      "Processed 30000000 lines in 9.134580612182617 seconds.\n",
      "Processed 31000000 lines in 9.142038345336914 seconds.\n",
      "Processed 32000000 lines in 11.395709753036499 seconds.\n",
      "Processed 33000000 lines in 9.098125457763672 seconds.\n",
      "Processed 34000000 lines in 9.047677993774414 seconds.\n",
      "Processed 35000000 lines in 9.141824960708618 seconds.\n",
      "Processed 36000000 lines in 9.070488452911377 seconds.\n",
      "Processed 37000000 lines in 9.11714506149292 seconds.\n",
      "Processed 38000000 lines in 9.115279197692871 seconds.\n",
      "Processed 39000000 lines in 9.222779273986816 seconds.\n",
      "Processed 40000000 lines in 12.469627141952515 seconds.\n",
      "Processed 41000000 lines in 9.035439014434814 seconds.\n",
      "Processed 42000000 lines in 9.068572759628296 seconds.\n",
      "Processed 43000000 lines in 9.12914228439331 seconds.\n",
      "Processed 44000000 lines in 8.993815898895264 seconds.\n",
      "Processed 45000000 lines in 9.00800609588623 seconds.\n",
      "Processed 46000000 lines in 9.024227380752563 seconds.\n",
      "Processed 47000000 lines in 9.021472454071045 seconds.\n",
      "Processed 48000000 lines in 8.967662572860718 seconds.\n",
      "Processed 49000000 lines in 8.985406875610352 seconds.\n",
      "Processed 50000000 lines in 9.039650440216064 seconds.\n",
      "Processed 51000000 lines in 9.08467411994934 seconds.\n",
      "Processed 52000000 lines in 9.0839102268219 seconds.\n",
      "Processed 53000000 lines in 9.127612113952637 seconds.\n",
      "Processed 54000000 lines in 9.102632284164429 seconds.\n",
      "Processed 55000000 lines in 9.06694221496582 seconds.\n",
      "Processed 56000000 lines in 9.07617974281311 seconds.\n",
      "Processed 57000000 lines in 9.10299038887024 seconds.\n",
      "Processed 58000000 lines in 9.046988010406494 seconds.\n",
      "Processed 59000000 lines in 9.157943725585938 seconds.\n",
      "Processed 60000000 lines in 9.198299646377563 seconds.\n",
      "Processed 61000000 lines in 8.971093654632568 seconds.\n",
      "Processed 62000000 lines in 9.030171632766724 seconds.\n",
      "Processed 63000000 lines in 9.123520374298096 seconds.\n",
      "Processed 64000000 lines in 9.061663389205933 seconds.\n",
      "Processed 65000000 lines in 9.217504262924194 seconds.\n",
      "Processed 66000000 lines in 9.282256841659546 seconds.\n",
      "Processed 67000000 lines in 9.325484037399292 seconds.\n",
      "Processed 68000000 lines in 9.308762073516846 seconds.\n",
      "Processed 69000000 lines in 9.153597593307495 seconds.\n",
      "Processed 70000000 lines in 59.942655086517334 seconds.\n",
      "Processed 71000000 lines in 15.626888036727905 seconds.\n",
      "Processed 72000000 lines in 15.284328937530518 seconds.\n",
      "Processed 73000000 lines in 14.423210859298706 seconds.\n",
      "Processed 74000000 lines in 14.071412563323975 seconds.\n",
      "Processed 75000000 lines in 13.326776504516602 seconds.\n",
      "Processed 76000000 lines in 17.802956581115723 seconds.\n",
      "Processed 77000000 lines in 23.796905994415283 seconds.\n",
      "Processed 78000000 lines in 15.765059232711792 seconds.\n",
      "Processed 79000000 lines in 12.600426435470581 seconds.\n",
      "Processed 80000000 lines in 11.476953744888306 seconds.\n",
      "Processed 81000000 lines in 10.931641578674316 seconds.\n",
      "Processed 82000000 lines in 10.81622838973999 seconds.\n",
      "Processed 83000000 lines in 10.5299973487854 seconds.\n",
      "Processed 84000000 lines in 11.22444486618042 seconds.\n",
      "Processed 85000000 lines in 12.531036138534546 seconds.\n",
      "Processed 86000000 lines in 12.122101783752441 seconds.\n",
      "Processed 87000000 lines in 12.492013692855835 seconds.\n",
      "Processed 88000000 lines in 89.16427731513977 seconds.\n",
      "Processed 89000000 lines in 36.113338232040405 seconds.\n",
      "Processed 90000000 lines in 26.342081308364868 seconds.\n",
      "Processed 91000000 lines in 35.848020792007446 seconds.\n",
      "Processed 92000000 lines in 27.278318405151367 seconds.\n",
      "Processed 93000000 lines in 19.207103729248047 seconds.\n",
      "Processed 94000000 lines in 16.861185312271118 seconds.\n",
      "Processed 95000000 lines in 19.221708059310913 seconds.\n",
      "Processed 96000000 lines in 20.081425428390503 seconds.\n",
      "Processed 97000000 lines in 19.948221921920776 seconds.\n",
      "Processed 98000000 lines in 28.352442741394043 seconds.\n",
      "Processed 99000000 lines in 26.517688751220703 seconds.\n",
      "Processed 100000000 lines in 26.641544103622437 seconds.\n",
      "Processed 101000000 lines in 33.65659737586975 seconds.\n",
      "Processed 102000000 lines in 36.85259246826172 seconds.\n",
      "Processed 103000000 lines in 32.91370439529419 seconds.\n",
      "Processed 104000000 lines in 36.43045735359192 seconds.\n",
      "Processed 105000000 lines in 32.94820046424866 seconds.\n",
      "Processed 106000000 lines in 35.32076954841614 seconds.\n",
      "Processed 107000000 lines in 41.591822147369385 seconds.\n",
      "Processed 108000000 lines in 38.25136351585388 seconds.\n",
      "Processed 109000000 lines in 40.081403493881226 seconds.\n",
      "Processed 110000000 lines in 40.88752841949463 seconds.\n",
      "Processed 111000000 lines in 45.31127166748047 seconds.\n",
      "Processed 112000000 lines in 51.101927518844604 seconds.\n",
      "Processed 113000000 lines in 43.772372245788574 seconds.\n",
      "Processed 114000000 lines in 47.324684619903564 seconds.\n",
      "Processed 115000000 lines in 50.812888383865356 seconds.\n",
      "Processed 116000000 lines in 57.414888858795166 seconds.\n",
      "Processed 117000000 lines in 56.47319793701172 seconds.\n",
      "Processed 118000000 lines in 54.114577770233154 seconds.\n",
      "Processed 119000000 lines in 56.30802869796753 seconds.\n",
      "Processed 120000000 lines in 63.7755823135376 seconds.\n",
      "Processed 121000000 lines in 58.16217637062073 seconds.\n",
      "Processed 122000000 lines in 61.00149893760681 seconds.\n",
      "Processed 123000000 lines in 69.86021065711975 seconds.\n",
      "Processed 124000000 lines in 64.04530143737793 seconds.\n",
      "Processed 125000000 lines in 64.36019206047058 seconds.\n",
      "Processed 126000000 lines in 71.97378921508789 seconds.\n",
      "Processed 127000000 lines in 67.79710555076599 seconds.\n",
      "Processed 128000000 lines in 73.25906944274902 seconds.\n",
      "Processed 0 lines in 0.0012106895446777344 seconds.\n",
      "Processed 1000000 lines in 68.84693598747253 seconds.\n",
      "Processed 2000000 lines in 11.168041467666626 seconds.\n",
      "Processed 3000000 lines in 10.97093653678894 seconds.\n",
      "Processed 4000000 lines in 10.846105098724365 seconds.\n",
      "Processed 5000000 lines in 13.275620698928833 seconds.\n",
      "Processed 6000000 lines in 13.063545227050781 seconds.\n",
      "Processed 7000000 lines in 12.564296960830688 seconds.\n",
      "Processed 8000000 lines in 12.878262281417847 seconds.\n",
      "Processed 9000000 lines in 12.729820966720581 seconds.\n",
      "Processed 10000000 lines in 12.885352373123169 seconds.\n",
      "Processed 11000000 lines in 12.729207515716553 seconds.\n",
      "Processed 12000000 lines in 12.521856546401978 seconds.\n",
      "Processed 13000000 lines in 12.789563417434692 seconds.\n",
      "Processed 14000000 lines in 12.83245849609375 seconds.\n",
      "Processed 15000000 lines in 12.590209722518921 seconds.\n",
      "Processed 16000000 lines in 12.782467126846313 seconds.\n",
      "Processed 17000000 lines in 13.394484281539917 seconds.\n",
      "Processed 18000000 lines in 12.518709897994995 seconds.\n",
      "Processed 19000000 lines in 13.153722047805786 seconds.\n",
      "Processed 20000000 lines in 12.642543315887451 seconds.\n",
      "Processed 21000000 lines in 12.824453830718994 seconds.\n",
      "Processed 22000000 lines in 12.80319595336914 seconds.\n",
      "Processed 23000000 lines in 12.429438829421997 seconds.\n",
      "Processed 24000000 lines in 12.715332746505737 seconds.\n",
      "Processed 25000000 lines in 12.624751329421997 seconds.\n",
      "Processed 26000000 lines in 12.150895357131958 seconds.\n",
      "Processed 27000000 lines in 12.52712607383728 seconds.\n",
      "Processed 28000000 lines in 12.489778518676758 seconds.\n",
      "Processed 29000000 lines in 12.003856420516968 seconds.\n",
      "Processed 30000000 lines in 12.621047019958496 seconds.\n",
      "Processed 31000000 lines in 12.22782015800476 seconds.\n",
      "Processed 32000000 lines in 12.595577955245972 seconds.\n",
      "Processed 33000000 lines in 12.373632669448853 seconds.\n",
      "Processed 34000000 lines in 12.230362892150879 seconds.\n",
      "Processed 35000000 lines in 12.997738122940063 seconds.\n",
      "Processed 36000000 lines in 12.191466093063354 seconds.\n",
      "Processed 37000000 lines in 11.980647087097168 seconds.\n",
      "Processed 38000000 lines in 12.391333818435669 seconds.\n",
      "Processed 39000000 lines in 12.349311828613281 seconds.\n",
      "Processed 40000000 lines in 11.808176040649414 seconds.\n",
      "Processed 41000000 lines in 12.29535460472107 seconds.\n",
      "Processed 42000000 lines in 12.19413948059082 seconds.\n",
      "Processed 43000000 lines in 12.704156160354614 seconds.\n",
      "Processed 44000000 lines in 12.557606220245361 seconds.\n",
      "Processed 45000000 lines in 12.371106147766113 seconds.\n",
      "Processed 46000000 lines in 34.98995327949524 seconds.\n",
      "Processed 47000000 lines in 11.995881795883179 seconds.\n",
      "Processed 48000000 lines in 11.431119203567505 seconds.\n",
      "Processed 49000000 lines in 12.025180339813232 seconds.\n",
      "Processed 50000000 lines in 12.048519134521484 seconds.\n",
      "Processed 51000000 lines in 12.041435241699219 seconds.\n",
      "Processed 52000000 lines in 11.79090666770935 seconds.\n",
      "Processed 53000000 lines in 11.537108659744263 seconds.\n",
      "Processed 54000000 lines in 12.094674348831177 seconds.\n",
      "Processed 55000000 lines in 12.104140996932983 seconds.\n",
      "Processed 56000000 lines in 11.597570896148682 seconds.\n",
      "Processed 57000000 lines in 12.383633136749268 seconds.\n",
      "Processed 58000000 lines in 11.721169233322144 seconds.\n",
      "Processed 59000000 lines in 11.667007684707642 seconds.\n",
      "Processed 60000000 lines in 12.244426727294922 seconds.\n",
      "Processed 61000000 lines in 11.695767402648926 seconds.\n",
      "Processed 62000000 lines in 11.891989946365356 seconds.\n",
      "Processed 63000000 lines in 12.039416790008545 seconds.\n",
      "Processed 64000000 lines in 11.809604167938232 seconds.\n",
      "Processed 65000000 lines in 12.06983470916748 seconds.\n",
      "Processed 66000000 lines in 12.020373344421387 seconds.\n",
      "Processed 67000000 lines in 11.88576602935791 seconds.\n",
      "Processed 68000000 lines in 11.930294275283813 seconds.\n",
      "Processed 69000000 lines in 12.053581476211548 seconds.\n",
      "Processed 70000000 lines in 11.619017362594604 seconds.\n",
      "Processed 71000000 lines in 11.87468957901001 seconds.\n",
      "Processed 72000000 lines in 11.641377925872803 seconds.\n",
      "Processed 73000000 lines in 12.135434865951538 seconds.\n",
      "Processed 74000000 lines in 11.893250226974487 seconds.\n",
      "Processed 75000000 lines in 11.928030490875244 seconds.\n",
      "Processed 76000000 lines in 11.72824478149414 seconds.\n",
      "Processed 77000000 lines in 12.0641348361969 seconds.\n",
      "Processed 78000000 lines in 11.683890104293823 seconds.\n",
      "Processed 79000000 lines in 12.238908052444458 seconds.\n",
      "Processed 80000000 lines in 12.004598379135132 seconds.\n",
      "Processed 81000000 lines in 11.597167730331421 seconds.\n",
      "Processed 82000000 lines in 12.103559732437134 seconds.\n",
      "Processed 83000000 lines in 11.682849884033203 seconds.\n",
      "Processed 84000000 lines in 11.768422365188599 seconds.\n",
      "Processed 85000000 lines in 11.707257747650146 seconds.\n",
      "Processed 86000000 lines in 11.560875177383423 seconds.\n",
      "Processed 87000000 lines in 11.979645013809204 seconds.\n",
      "Processed 88000000 lines in 11.808533191680908 seconds.\n",
      "Processed 89000000 lines in 11.901595830917358 seconds.\n",
      "Processed 90000000 lines in 11.892274379730225 seconds.\n",
      "Processed 91000000 lines in 11.577476501464844 seconds.\n",
      "Processed 92000000 lines in 11.936104536056519 seconds.\n",
      "Processed 93000000 lines in 11.740949153900146 seconds.\n",
      "Processed 94000000 lines in 11.646675825119019 seconds.\n",
      "Processed 95000000 lines in 12.04584813117981 seconds.\n",
      "Processed 96000000 lines in 11.902093887329102 seconds.\n",
      "Processed 97000000 lines in 11.558668613433838 seconds.\n",
      "Processed 98000000 lines in 11.930173635482788 seconds.\n",
      "Processed 99000000 lines in 11.937313556671143 seconds.\n",
      "Processed 100000000 lines in 11.994746685028076 seconds.\n",
      "Processed 101000000 lines in 11.902766704559326 seconds.\n",
      "Processed 102000000 lines in 11.835922718048096 seconds.\n",
      "Processed 103000000 lines in 11.768280267715454 seconds.\n",
      "Processed 104000000 lines in 11.986276626586914 seconds.\n",
      "Processed 105000000 lines in 11.935389518737793 seconds.\n",
      "Processed 106000000 lines in 12.108407258987427 seconds.\n",
      "Processed 107000000 lines in 12.262128353118896 seconds.\n",
      "Processed 108000000 lines in 11.661928176879883 seconds.\n",
      "Processed 109000000 lines in 12.113945722579956 seconds.\n",
      "Processed 110000000 lines in 11.903327703475952 seconds.\n",
      "Processed 111000000 lines in 11.74354100227356 seconds.\n",
      "Processed 112000000 lines in 12.09400725364685 seconds.\n",
      "Processed 113000000 lines in 11.51280426979065 seconds.\n",
      "Processed 114000000 lines in 11.813150882720947 seconds.\n",
      "Processed 115000000 lines in 12.034647226333618 seconds.\n",
      "Processed 116000000 lines in 11.698277235031128 seconds.\n",
      "Processed 117000000 lines in 11.899101495742798 seconds.\n",
      "Processed 118000000 lines in 12.215120077133179 seconds.\n",
      "Processed 119000000 lines in 11.730506896972656 seconds.\n",
      "Processed 120000000 lines in 11.928377389907837 seconds.\n",
      "Processed 121000000 lines in 12.15605902671814 seconds.\n",
      "Processed 122000000 lines in 11.713261842727661 seconds.\n",
      "Processed 123000000 lines in 11.789839744567871 seconds.\n",
      "Processed 124000000 lines in 11.949562549591064 seconds.\n",
      "Processed 125000000 lines in 11.529197454452515 seconds.\n",
      "Processed 126000000 lines in 11.487278699874878 seconds.\n",
      "Processed 127000000 lines in 11.353040933609009 seconds.\n",
      "Processed 128000000 lines in 11.493170976638794 seconds.\n",
      "Processed 0 lines in 0.0002105236053466797 seconds.\n",
      "Processed 1000000 lines in 10.724919080734253 seconds.\n",
      "Processed 2000000 lines in 9.67183780670166 seconds.\n",
      "Processed 3000000 lines in 10.108468055725098 seconds.\n",
      "Processed 4000000 lines in 10.212220430374146 seconds.\n",
      "Processed 5000000 lines in 12.080944538116455 seconds.\n",
      "Processed 6000000 lines in 11.50892424583435 seconds.\n",
      "Processed 7000000 lines in 11.744571924209595 seconds.\n",
      "Processed 8000000 lines in 11.612807512283325 seconds.\n",
      "Processed 9000000 lines in 11.911502838134766 seconds.\n",
      "Processed 10000000 lines in 11.78684687614441 seconds.\n",
      "Processed 11000000 lines in 11.652033567428589 seconds.\n",
      "Processed 12000000 lines in 11.784423589706421 seconds.\n",
      "Processed 13000000 lines in 11.707046270370483 seconds.\n",
      "Processed 14000000 lines in 12.23026418685913 seconds.\n",
      "Processed 15000000 lines in 12.089486360549927 seconds.\n",
      "Processed 16000000 lines in 12.041897296905518 seconds.\n",
      "Processed 17000000 lines in 12.540453910827637 seconds.\n",
      "Processed 18000000 lines in 12.426127672195435 seconds.\n",
      "Processed 19000000 lines in 12.230402946472168 seconds.\n",
      "Processed 20000000 lines in 12.567630052566528 seconds.\n",
      "Processed 21000000 lines in 12.378057479858398 seconds.\n",
      "Processed 22000000 lines in 12.146494626998901 seconds.\n",
      "Processed 23000000 lines in 12.354315042495728 seconds.\n",
      "Processed 24000000 lines in 11.994749784469604 seconds.\n",
      "Processed 25000000 lines in 11.93916392326355 seconds.\n",
      "Processed 26000000 lines in 12.060572862625122 seconds.\n",
      "Processed 27000000 lines in 11.688495635986328 seconds.\n",
      "Processed 28000000 lines in 12.131058931350708 seconds.\n",
      "Processed 29000000 lines in 11.855942487716675 seconds.\n",
      "Processed 30000000 lines in 11.799220561981201 seconds.\n",
      "Processed 31000000 lines in 12.24069881439209 seconds.\n",
      "Processed 32000000 lines in 12.272900104522705 seconds.\n",
      "Processed 33000000 lines in 11.850889921188354 seconds.\n",
      "Processed 34000000 lines in 11.987865447998047 seconds.\n",
      "Processed 35000000 lines in 12.581097602844238 seconds.\n",
      "Processed 36000000 lines in 11.823526620864868 seconds.\n",
      "Processed 37000000 lines in 12.001393556594849 seconds.\n",
      "Processed 38000000 lines in 11.556404113769531 seconds.\n",
      "Processed 39000000 lines in 12.053769588470459 seconds.\n",
      "Processed 40000000 lines in 12.110000610351562 seconds.\n",
      "Processed 41000000 lines in 11.579465389251709 seconds.\n",
      "Processed 42000000 lines in 12.11417818069458 seconds.\n",
      "Processed 43000000 lines in 12.2826988697052 seconds.\n",
      "Processed 44000000 lines in 11.893769264221191 seconds.\n",
      "Processed 45000000 lines in 12.082493305206299 seconds.\n",
      "Processed 46000000 lines in 11.771172285079956 seconds.\n",
      "Processed 47000000 lines in 12.247114896774292 seconds.\n",
      "Processed 48000000 lines in 11.835518598556519 seconds.\n",
      "Processed 49000000 lines in 11.670758962631226 seconds.\n",
      "Processed 50000000 lines in 12.360666751861572 seconds.\n",
      "Processed 51000000 lines in 12.108993768692017 seconds.\n",
      "Processed 52000000 lines in 11.669157981872559 seconds.\n",
      "Processed 53000000 lines in 12.025634527206421 seconds.\n",
      "Processed 54000000 lines in 11.852323532104492 seconds.\n",
      "Processed 55000000 lines in 11.620748519897461 seconds.\n",
      "Processed 56000000 lines in 11.940655708312988 seconds.\n",
      "Processed 57000000 lines in 11.87061071395874 seconds.\n",
      "Processed 58000000 lines in 11.914406299591064 seconds.\n",
      "Processed 59000000 lines in 11.905610084533691 seconds.\n",
      "Processed 60000000 lines in 11.92343282699585 seconds.\n",
      "Processed 61000000 lines in 12.119637966156006 seconds.\n",
      "Processed 62000000 lines in 11.82524037361145 seconds.\n",
      "Processed 63000000 lines in 11.752005338668823 seconds.\n",
      "Processed 64000000 lines in 12.127564668655396 seconds.\n",
      "Processed 65000000 lines in 11.99790072441101 seconds.\n",
      "Processed 66000000 lines in 11.839207887649536 seconds.\n",
      "Processed 67000000 lines in 12.03927993774414 seconds.\n",
      "Processed 68000000 lines in 11.575611114501953 seconds.\n",
      "Processed 69000000 lines in 12.175341367721558 seconds.\n",
      "Processed 70000000 lines in 11.906296253204346 seconds.\n",
      "Processed 71000000 lines in 11.557367086410522 seconds.\n",
      "Processed 72000000 lines in 11.848133087158203 seconds.\n",
      "Processed 73000000 lines in 12.00445294380188 seconds.\n",
      "Processed 74000000 lines in 11.624146223068237 seconds.\n",
      "Processed 75000000 lines in 12.15938949584961 seconds.\n",
      "Processed 76000000 lines in 11.794418573379517 seconds.\n",
      "Processed 77000000 lines in 11.354492664337158 seconds.\n",
      "Processed 78000000 lines in 12.09618330001831 seconds.\n",
      "Processed 79000000 lines in 11.68315076828003 seconds.\n",
      "Processed 80000000 lines in 12.117294073104858 seconds.\n",
      "Processed 81000000 lines in 12.087356805801392 seconds.\n",
      "Processed 82000000 lines in 11.577133178710938 seconds.\n",
      "Processed 83000000 lines in 11.845413446426392 seconds.\n",
      "Processed 84000000 lines in 12.003115177154541 seconds.\n",
      "Processed 85000000 lines in 11.433077573776245 seconds.\n",
      "Processed 86000000 lines in 12.0409677028656 seconds.\n",
      "Processed 87000000 lines in 11.689669609069824 seconds.\n",
      "Processed 88000000 lines in 11.710347175598145 seconds.\n",
      "Processed 89000000 lines in 12.151530265808105 seconds.\n",
      "Processed 90000000 lines in 11.451151847839355 seconds.\n",
      "Processed 91000000 lines in 11.936026573181152 seconds.\n",
      "Processed 92000000 lines in 12.07900595664978 seconds.\n",
      "Processed 93000000 lines in 11.496222019195557 seconds.\n",
      "Processed 94000000 lines in 11.88033413887024 seconds.\n",
      "Processed 95000000 lines in 11.842597246170044 seconds.\n",
      "Processed 96000000 lines in 11.585114479064941 seconds.\n",
      "Processed 97000000 lines in 11.778516292572021 seconds.\n",
      "Processed 98000000 lines in 11.988902807235718 seconds.\n",
      "Processed 99000000 lines in 11.826102018356323 seconds.\n",
      "Processed 100000000 lines in 11.969173908233643 seconds.\n",
      "Processed 101000000 lines in 11.869528532028198 seconds.\n",
      "Processed 102000000 lines in 12.113907098770142 seconds.\n",
      "Processed 103000000 lines in 11.890297412872314 seconds.\n",
      "Processed 104000000 lines in 11.837042093276978 seconds.\n",
      "Processed 105000000 lines in 11.963999032974243 seconds.\n",
      "Processed 106000000 lines in 12.058017492294312 seconds.\n",
      "Processed 107000000 lines in 11.867327213287354 seconds.\n",
      "Processed 108000000 lines in 12.0079026222229 seconds.\n",
      "Processed 109000000 lines in 11.621639251708984 seconds.\n",
      "Processed 110000000 lines in 12.003088235855103 seconds.\n",
      "Processed 111000000 lines in 11.882352828979492 seconds.\n",
      "Processed 112000000 lines in 11.59533429145813 seconds.\n",
      "Processed 113000000 lines in 11.837088346481323 seconds.\n",
      "Processed 114000000 lines in 11.868823766708374 seconds.\n",
      "Processed 115000000 lines in 11.716094970703125 seconds.\n",
      "Processed 116000000 lines in 12.077614068984985 seconds.\n",
      "Processed 117000000 lines in 11.940791130065918 seconds.\n",
      "Processed 118000000 lines in 11.683695793151855 seconds.\n",
      "Processed 119000000 lines in 12.127585411071777 seconds.\n",
      "Processed 120000000 lines in 11.722809553146362 seconds.\n",
      "Processed 121000000 lines in 12.12535810470581 seconds.\n",
      "Processed 122000000 lines in 11.733335256576538 seconds.\n",
      "Processed 123000000 lines in 11.568918228149414 seconds.\n",
      "Processed 124000000 lines in 12.226501703262329 seconds.\n",
      "Processed 125000000 lines in 11.40297794342041 seconds.\n",
      "Processed 126000000 lines in 11.194119215011597 seconds.\n",
      "Processed 127000000 lines in 11.655784130096436 seconds.\n",
      "Processed 128000000 lines in 11.585093021392822 seconds.\n",
      "Processed 0 lines in 0.0001685619354248047 seconds.\n",
      "Processed 1000000 lines in 10.284428358078003 seconds.\n",
      "Processed 2000000 lines in 10.039156913757324 seconds.\n",
      "Processed 3000000 lines in 10.286544561386108 seconds.\n",
      "Processed 4000000 lines in 9.930092573165894 seconds.\n",
      "Processed 5000000 lines in 12.474860191345215 seconds.\n",
      "Processed 6000000 lines in 11.3857421875 seconds.\n",
      "Processed 7000000 lines in 11.675435781478882 seconds.\n",
      "Processed 8000000 lines in 11.88646125793457 seconds.\n",
      "Processed 9000000 lines in 11.549269437789917 seconds.\n",
      "Processed 10000000 lines in 12.0137197971344 seconds.\n",
      "Processed 11000000 lines in 12.12113094329834 seconds.\n",
      "Processed 12000000 lines in 12.027921676635742 seconds.\n",
      "Processed 13000000 lines in 12.263740301132202 seconds.\n",
      "Processed 14000000 lines in 12.240964651107788 seconds.\n",
      "Processed 15000000 lines in 12.216225147247314 seconds.\n",
      "Processed 16000000 lines in 12.209858655929565 seconds.\n",
      "Processed 17000000 lines in 12.733371496200562 seconds.\n",
      "Processed 18000000 lines in 12.959535598754883 seconds.\n",
      "Processed 19000000 lines in 12.204669713973999 seconds.\n",
      "Processed 20000000 lines in 12.594193458557129 seconds.\n",
      "Processed 21000000 lines in 12.1932954788208 seconds.\n",
      "Processed 22000000 lines in 12.227113723754883 seconds.\n",
      "Processed 23000000 lines in 12.03664231300354 seconds.\n",
      "Processed 24000000 lines in 12.078031539916992 seconds.\n",
      "Processed 25000000 lines in 12.105196714401245 seconds.\n",
      "Processed 26000000 lines in 11.665601968765259 seconds.\n",
      "Processed 27000000 lines in 11.893452167510986 seconds.\n",
      "Processed 28000000 lines in 11.871276378631592 seconds.\n",
      "Processed 29000000 lines in 11.692375421524048 seconds.\n",
      "Processed 30000000 lines in 12.258906602859497 seconds.\n",
      "Processed 31000000 lines in 12.105127334594727 seconds.\n",
      "Processed 32000000 lines in 12.061408281326294 seconds.\n",
      "Processed 33000000 lines in 12.181289196014404 seconds.\n",
      "Processed 34000000 lines in 11.72019624710083 seconds.\n",
      "Processed 35000000 lines in 12.826728820800781 seconds.\n",
      "Processed 36000000 lines in 12.203193187713623 seconds.\n",
      "Processed 37000000 lines in 11.541372060775757 seconds.\n",
      "Processed 38000000 lines in 12.04323673248291 seconds.\n",
      "Processed 39000000 lines in 11.960012674331665 seconds.\n",
      "Processed 40000000 lines in 11.814802169799805 seconds.\n",
      "Processed 41000000 lines in 11.885330438613892 seconds.\n",
      "Processed 42000000 lines in 12.102266073226929 seconds.\n",
      "Processed 43000000 lines in 11.970007181167603 seconds.\n",
      "Processed 44000000 lines in 11.975599765777588 seconds.\n",
      "Processed 45000000 lines in 11.771612167358398 seconds.\n",
      "Processed 46000000 lines in 12.05254578590393 seconds.\n",
      "Processed 47000000 lines in 12.190344333648682 seconds.\n",
      "Processed 48000000 lines in 11.416346073150635 seconds.\n",
      "Processed 49000000 lines in 11.948322057723999 seconds.\n",
      "Processed 50000000 lines in 12.202114820480347 seconds.\n",
      "Processed 51000000 lines in 11.811622858047485 seconds.\n",
      "Processed 52000000 lines in 11.958524465560913 seconds.\n",
      "Processed 53000000 lines in 11.865950107574463 seconds.\n",
      "Processed 54000000 lines in 11.55617380142212 seconds.\n",
      "Processed 55000000 lines in 12.0974440574646 seconds.\n",
      "Processed 56000000 lines in 11.644142866134644 seconds.\n",
      "Processed 57000000 lines in 12.029594898223877 seconds.\n",
      "Processed 58000000 lines in 11.755115985870361 seconds.\n",
      "Processed 59000000 lines in 11.754723072052002 seconds.\n",
      "Processed 60000000 lines in 12.040339946746826 seconds.\n",
      "Processed 61000000 lines in 11.977319240570068 seconds.\n",
      "Processed 62000000 lines in 11.637598276138306 seconds.\n",
      "Processed 63000000 lines in 11.80990219116211 seconds.\n",
      "Processed 64000000 lines in 11.804283618927002 seconds.\n",
      "Processed 65000000 lines in 11.899480819702148 seconds.\n",
      "Processed 66000000 lines in 11.878230333328247 seconds.\n",
      "Processed 67000000 lines in 12.023569583892822 seconds.\n",
      "Processed 68000000 lines in 11.996032238006592 seconds.\n",
      "Processed 69000000 lines in 12.08763313293457 seconds.\n",
      "Processed 70000000 lines in 11.769520044326782 seconds.\n",
      "Processed 71000000 lines in 11.864135026931763 seconds.\n",
      "Processed 72000000 lines in 12.032171726226807 seconds.\n",
      "Processed 73000000 lines in 11.752153396606445 seconds.\n",
      "Processed 74000000 lines in 11.770246982574463 seconds.\n",
      "Processed 75000000 lines in 11.743780374526978 seconds.\n",
      "Processed 76000000 lines in 11.704986095428467 seconds.\n",
      "Processed 77000000 lines in 11.834059715270996 seconds.\n",
      "Processed 78000000 lines in 11.838377952575684 seconds.\n",
      "Processed 79000000 lines in 11.960946321487427 seconds.\n",
      "Processed 80000000 lines in 12.059160470962524 seconds.\n",
      "Processed 81000000 lines in 11.739572525024414 seconds.\n",
      "Processed 82000000 lines in 12.112396478652954 seconds.\n",
      "Processed 83000000 lines in 11.472449779510498 seconds.\n",
      "Processed 84000000 lines in 11.976158857345581 seconds.\n",
      "Processed 85000000 lines in 11.869161128997803 seconds.\n",
      "Processed 86000000 lines in 11.441739559173584 seconds.\n",
      "Processed 87000000 lines in 12.081352949142456 seconds.\n",
      "Processed 88000000 lines in 12.062784671783447 seconds.\n",
      "Processed 89000000 lines in 11.772976636886597 seconds.\n",
      "Processed 90000000 lines in 11.97042989730835 seconds.\n",
      "Processed 91000000 lines in 11.840981245040894 seconds.\n",
      "Processed 92000000 lines in 11.739185810089111 seconds.\n",
      "Processed 93000000 lines in 11.718203783035278 seconds.\n",
      "Processed 94000000 lines in 11.593910455703735 seconds.\n",
      "Processed 95000000 lines in 11.967028617858887 seconds.\n",
      "Processed 96000000 lines in 11.914409875869751 seconds.\n",
      "Processed 97000000 lines in 11.392530679702759 seconds.\n",
      "Processed 98000000 lines in 12.27536916732788 seconds.\n",
      "Processed 99000000 lines in 12.178623914718628 seconds.\n",
      "Processed 100000000 lines in 11.666812896728516 seconds.\n",
      "Processed 101000000 lines in 12.084217071533203 seconds.\n",
      "Processed 102000000 lines in 11.728784322738647 seconds.\n",
      "Processed 103000000 lines in 11.969763040542603 seconds.\n",
      "Processed 104000000 lines in 11.896027326583862 seconds.\n",
      "Processed 105000000 lines in 11.9878089427948 seconds.\n",
      "Processed 106000000 lines in 11.979403734207153 seconds.\n",
      "Processed 107000000 lines in 12.242844820022583 seconds.\n",
      "Processed 108000000 lines in 11.823075771331787 seconds.\n",
      "Processed 109000000 lines in 11.941327571868896 seconds.\n",
      "Processed 110000000 lines in 11.964528322219849 seconds.\n",
      "Processed 111000000 lines in 11.766153573989868 seconds.\n",
      "Processed 112000000 lines in 11.979164600372314 seconds.\n",
      "Processed 113000000 lines in 11.586692571640015 seconds.\n",
      "Processed 114000000 lines in 11.805408954620361 seconds.\n",
      "Processed 115000000 lines in 12.127535820007324 seconds.\n",
      "Processed 116000000 lines in 11.66924786567688 seconds.\n",
      "Processed 117000000 lines in 11.909772872924805 seconds.\n",
      "Processed 118000000 lines in 12.112474203109741 seconds.\n",
      "Processed 119000000 lines in 11.732733488082886 seconds.\n",
      "Processed 120000000 lines in 11.751224040985107 seconds.\n",
      "Processed 121000000 lines in 11.971590280532837 seconds.\n",
      "Processed 122000000 lines in 11.635748386383057 seconds.\n",
      "Processed 123000000 lines in 11.804076194763184 seconds.\n",
      "Processed 124000000 lines in 11.829573154449463 seconds.\n",
      "Processed 125000000 lines in 11.57503366470337 seconds.\n",
      "Processed 126000000 lines in 11.492624521255493 seconds.\n",
      "Processed 127000000 lines in 11.298207759857178 seconds.\n",
      "Processed 128000000 lines in 11.433485984802246 seconds.\n",
      "Processed 0 lines in 0.00020456314086914062 seconds.\n",
      "Processed 1000000 lines in 10.462962627410889 seconds.\n",
      "Processed 2000000 lines in 9.95208740234375 seconds.\n",
      "Processed 3000000 lines in 9.9474937915802 seconds.\n",
      "Processed 4000000 lines in 10.263622283935547 seconds.\n",
      "Processed 5000000 lines in 11.480395078659058 seconds.\n",
      "Processed 6000000 lines in 11.746907949447632 seconds.\n",
      "Processed 7000000 lines in 11.462883472442627 seconds.\n",
      "Processed 8000000 lines in 11.825155019760132 seconds.\n",
      "Processed 9000000 lines in 11.741087198257446 seconds.\n",
      "Processed 10000000 lines in 11.709346532821655 seconds.\n",
      "Processed 11000000 lines in 11.97491717338562 seconds.\n",
      "Processed 12000000 lines in 12.119851112365723 seconds.\n",
      "Processed 13000000 lines in 11.898428440093994 seconds.\n",
      "Processed 14000000 lines in 12.100630760192871 seconds.\n",
      "Processed 15000000 lines in 12.112005949020386 seconds.\n",
      "Processed 16000000 lines in 12.011102676391602 seconds.\n",
      "Processed 17000000 lines in 12.529447078704834 seconds.\n",
      "Processed 18000000 lines in 12.218099117279053 seconds.\n",
      "Processed 19000000 lines in 12.107082605361938 seconds.\n",
      "Processed 20000000 lines in 12.4843008518219 seconds.\n",
      "Processed 21000000 lines in 12.455096244812012 seconds.\n",
      "Processed 22000000 lines in 11.872814655303955 seconds.\n",
      "Processed 23000000 lines in 12.276739597320557 seconds.\n",
      "Processed 24000000 lines in 11.623926639556885 seconds.\n",
      "Processed 25000000 lines in 12.11262035369873 seconds.\n",
      "Processed 26000000 lines in 12.29214859008789 seconds.\n",
      "Processed 27000000 lines in 11.742772579193115 seconds.\n",
      "Processed 28000000 lines in 11.998782396316528 seconds.\n",
      "Processed 29000000 lines in 11.92184042930603 seconds.\n",
      "Processed 30000000 lines in 11.926289558410645 seconds.\n",
      "Processed 31000000 lines in 11.925652265548706 seconds.\n",
      "Processed 32000000 lines in 11.967062711715698 seconds.\n",
      "Processed 33000000 lines in 11.953768730163574 seconds.\n",
      "Processed 34000000 lines in 12.165066957473755 seconds.\n",
      "Processed 35000000 lines in 12.576435565948486 seconds.\n",
      "Processed 36000000 lines in 11.860587120056152 seconds.\n",
      "Processed 37000000 lines in 11.94038438796997 seconds.\n",
      "Processed 38000000 lines in 11.842467069625854 seconds.\n",
      "Processed 39000000 lines in 12.158400774002075 seconds.\n",
      "Processed 40000000 lines in 11.975207567214966 seconds.\n",
      "Processed 41000000 lines in 11.844210386276245 seconds.\n",
      "Processed 42000000 lines in 12.002034902572632 seconds.\n",
      "Processed 43000000 lines in 12.023306846618652 seconds.\n",
      "Processed 44000000 lines in 12.134228467941284 seconds.\n",
      "Processed 45000000 lines in 11.975858211517334 seconds.\n",
      "Processed 46000000 lines in 11.73196029663086 seconds.\n",
      "Processed 47000000 lines in 12.01955270767212 seconds.\n",
      "Processed 48000000 lines in 11.939664125442505 seconds.\n",
      "Processed 49000000 lines in 11.695724964141846 seconds.\n",
      "Processed 50000000 lines in 12.293793201446533 seconds.\n",
      "Processed 51000000 lines in 12.177726745605469 seconds.\n",
      "Processed 52000000 lines in 11.794549226760864 seconds.\n",
      "Processed 53000000 lines in 12.090079307556152 seconds.\n",
      "Processed 54000000 lines in 11.518725633621216 seconds.\n",
      "Processed 55000000 lines in 12.311357021331787 seconds.\n",
      "Processed 56000000 lines in 11.964573383331299 seconds.\n",
      "Processed 57000000 lines in 11.741966962814331 seconds.\n",
      "Processed 58000000 lines in 11.874887704849243 seconds.\n",
      "Processed 59000000 lines in 12.559490203857422 seconds.\n",
      "Processed 60000000 lines in 12.336033582687378 seconds.\n",
      "Processed 61000000 lines in 11.984862089157104 seconds.\n",
      "Processed 62000000 lines in 11.863746166229248 seconds.\n",
      "Processed 63000000 lines in 11.452987432479858 seconds.\n",
      "Processed 64000000 lines in 12.267062425613403 seconds.\n",
      "Processed 65000000 lines in 11.617954730987549 seconds.\n",
      "Processed 66000000 lines in 11.970846891403198 seconds.\n",
      "Processed 67000000 lines in 12.245222330093384 seconds.\n",
      "Processed 68000000 lines in 11.520379543304443 seconds.\n",
      "Processed 69000000 lines in 11.980661630630493 seconds.\n",
      "Processed 70000000 lines in 12.064447402954102 seconds.\n",
      "Processed 71000000 lines in 11.574032068252563 seconds.\n",
      "Processed 72000000 lines in 11.813563585281372 seconds.\n",
      "Processed 73000000 lines in 12.102405786514282 seconds.\n",
      "Processed 74000000 lines in 11.42347764968872 seconds.\n",
      "Processed 75000000 lines in 12.1208655834198 seconds.\n",
      "Processed 76000000 lines in 11.680182695388794 seconds.\n",
      "Processed 77000000 lines in 11.763726949691772 seconds.\n",
      "Processed 78000000 lines in 12.015680074691772 seconds.\n",
      "Processed 79000000 lines in 11.733760118484497 seconds.\n",
      "Processed 80000000 lines in 11.967881441116333 seconds.\n",
      "Processed 81000000 lines in 12.108114242553711 seconds.\n",
      "Processed 82000000 lines in 11.555633306503296 seconds.\n",
      "Processed 83000000 lines in 11.863751888275146 seconds.\n",
      "Processed 84000000 lines in 12.066988229751587 seconds.\n",
      "Processed 85000000 lines in 11.336068630218506 seconds.\n",
      "Processed 86000000 lines in 11.733604192733765 seconds.\n",
      "Processed 87000000 lines in 11.556889295578003 seconds.\n",
      "Processed 88000000 lines in 11.884316205978394 seconds.\n",
      "Processed 89000000 lines in 11.912233352661133 seconds.\n",
      "Processed 90000000 lines in 11.863785982131958 seconds.\n",
      "Processed 91000000 lines in 11.709333419799805 seconds.\n",
      "Processed 92000000 lines in 11.702888488769531 seconds.\n",
      "Processed 93000000 lines in 11.484879732131958 seconds.\n",
      "Processed 94000000 lines in 11.775110721588135 seconds.\n",
      "Processed 95000000 lines in 11.34738540649414 seconds.\n",
      "Processed 96000000 lines in 11.901907920837402 seconds.\n",
      "Processed 97000000 lines in 11.836457252502441 seconds.\n",
      "Processed 98000000 lines in 11.554369688034058 seconds.\n",
      "Processed 99000000 lines in 12.211972713470459 seconds.\n",
      "Processed 100000000 lines in 11.986082792282104 seconds.\n",
      "Processed 101000000 lines in 11.917129278182983 seconds.\n",
      "Processed 102000000 lines in 11.970086097717285 seconds.\n",
      "Processed 103000000 lines in 11.64471960067749 seconds.\n",
      "Processed 104000000 lines in 11.861784219741821 seconds.\n",
      "Processed 105000000 lines in 12.029907941818237 seconds.\n",
      "Processed 106000000 lines in 11.730420589447021 seconds.\n",
      "Processed 107000000 lines in 12.291051626205444 seconds.\n",
      "Processed 108000000 lines in 12.040540218353271 seconds.\n",
      "Processed 109000000 lines in 11.878763437271118 seconds.\n",
      "Processed 110000000 lines in 11.9847252368927 seconds.\n",
      "Processed 111000000 lines in 11.982088088989258 seconds.\n",
      "Processed 112000000 lines in 11.57691240310669 seconds.\n",
      "Processed 113000000 lines in 11.921887636184692 seconds.\n",
      "Processed 114000000 lines in 11.763331890106201 seconds.\n",
      "Processed 115000000 lines in 11.683130025863647 seconds.\n",
      "Processed 116000000 lines in 11.996730089187622 seconds.\n",
      "Processed 117000000 lines in 11.809902667999268 seconds.\n",
      "Processed 118000000 lines in 11.833222150802612 seconds.\n",
      "Processed 119000000 lines in 12.056010246276855 seconds.\n",
      "Processed 120000000 lines in 11.568624258041382 seconds.\n",
      "Processed 121000000 lines in 11.771402359008789 seconds.\n",
      "Processed 122000000 lines in 11.952086687088013 seconds.\n",
      "Processed 123000000 lines in 11.53704047203064 seconds.\n",
      "Processed 124000000 lines in 12.003801584243774 seconds.\n",
      "Processed 125000000 lines in 11.643650531768799 seconds.\n",
      "Processed 126000000 lines in 11.146406173706055 seconds.\n",
      "Processed 127000000 lines in 11.41442084312439 seconds.\n",
      "Processed 128000000 lines in 11.489405870437622 seconds.\n",
      "Processed 0 lines in 0.00021386146545410156 seconds.\n",
      "Processed 1000000 lines in 10.371429204940796 seconds.\n",
      "Processed 2000000 lines in 9.91352367401123 seconds.\n",
      "Processed 3000000 lines in 10.065481424331665 seconds.\n",
      "Processed 4000000 lines in 9.885550498962402 seconds.\n",
      "Processed 5000000 lines in 11.731579065322876 seconds.\n",
      "Processed 6000000 lines in 11.536762714385986 seconds.\n",
      "Processed 7000000 lines in 11.319538831710815 seconds.\n",
      "Processed 8000000 lines in 11.839346170425415 seconds.\n",
      "Processed 9000000 lines in 11.698782920837402 seconds.\n",
      "Processed 10000000 lines in 11.682351112365723 seconds.\n",
      "Processed 11000000 lines in 11.910801410675049 seconds.\n",
      "Processed 12000000 lines in 11.96164059638977 seconds.\n",
      "Processed 13000000 lines in 12.114214658737183 seconds.\n",
      "Processed 14000000 lines in 11.952473402023315 seconds.\n",
      "Processed 15000000 lines in 11.936307191848755 seconds.\n",
      "Processed 16000000 lines in 12.195603609085083 seconds.\n",
      "Processed 17000000 lines in 12.795983076095581 seconds.\n",
      "Processed 18000000 lines in 11.953816413879395 seconds.\n",
      "Processed 19000000 lines in 12.422369480133057 seconds.\n",
      "Processed 20000000 lines in 12.02605390548706 seconds.\n",
      "Processed 21000000 lines in 12.616049528121948 seconds.\n",
      "Processed 22000000 lines in 12.22676396369934 seconds.\n",
      "Processed 23000000 lines in 12.08490252494812 seconds.\n",
      "Processed 24000000 lines in 12.117879629135132 seconds.\n",
      "Processed 25000000 lines in 11.85872745513916 seconds.\n",
      "Processed 26000000 lines in 11.914147138595581 seconds.\n",
      "Processed 27000000 lines in 11.900719404220581 seconds.\n",
      "Processed 28000000 lines in 12.067522525787354 seconds.\n",
      "Processed 29000000 lines in 11.711101055145264 seconds.\n",
      "Processed 30000000 lines in 12.320088624954224 seconds.\n",
      "Processed 31000000 lines in 11.749680280685425 seconds.\n",
      "Processed 32000000 lines in 12.41182827949524 seconds.\n",
      "Processed 33000000 lines in 12.011333227157593 seconds.\n",
      "Processed 34000000 lines in 11.781742572784424 seconds.\n",
      "Processed 35000000 lines in 12.85522723197937 seconds.\n",
      "Processed 36000000 lines in 11.992290735244751 seconds.\n",
      "Processed 37000000 lines in 11.609273433685303 seconds.\n",
      "Processed 38000000 lines in 12.125556707382202 seconds.\n",
      "Processed 39000000 lines in 11.991265058517456 seconds.\n",
      "Processed 40000000 lines in 11.614512920379639 seconds.\n",
      "Processed 41000000 lines in 12.132987976074219 seconds.\n",
      "Processed 42000000 lines in 11.835170030593872 seconds.\n",
      "Processed 43000000 lines in 12.116438388824463 seconds.\n",
      "Processed 44000000 lines in 12.135698556900024 seconds.\n",
      "Processed 45000000 lines in 11.884912490844727 seconds.\n",
      "Processed 46000000 lines in 11.869536876678467 seconds.\n",
      "Processed 47000000 lines in 12.339436531066895 seconds.\n",
      "Processed 48000000 lines in 11.496733665466309 seconds.\n",
      "Processed 49000000 lines in 11.85990595817566 seconds.\n",
      "Processed 50000000 lines in 12.67507815361023 seconds.\n",
      "Processed 51000000 lines in 11.64052939414978 seconds.\n",
      "Processed 52000000 lines in 11.800786018371582 seconds.\n",
      "Processed 53000000 lines in 11.819554567337036 seconds.\n",
      "Processed 54000000 lines in 11.866558074951172 seconds.\n",
      "Processed 55000000 lines in 12.04162073135376 seconds.\n",
      "Processed 56000000 lines in 11.898288488388062 seconds.\n",
      "Processed 57000000 lines in 12.073296785354614 seconds.\n",
      "Processed 58000000 lines in 11.88059949874878 seconds.\n",
      "Processed 59000000 lines in 11.70943284034729 seconds.\n",
      "Processed 60000000 lines in 12.18765926361084 seconds.\n",
      "Processed 61000000 lines in 11.553351163864136 seconds.\n",
      "Processed 62000000 lines in 11.97730278968811 seconds.\n",
      "Processed 63000000 lines in 11.8502676486969 seconds.\n",
      "Processed 64000000 lines in 11.81417727470398 seconds.\n",
      "Processed 65000000 lines in 12.083797216415405 seconds.\n",
      "Processed 66000000 lines in 11.995069742202759 seconds.\n",
      "Processed 67000000 lines in 11.977404594421387 seconds.\n",
      "Processed 68000000 lines in 11.837334632873535 seconds.\n",
      "Processed 69000000 lines in 12.076175451278687 seconds.\n",
      "Processed 70000000 lines in 11.864582777023315 seconds.\n",
      "Processed 71000000 lines in 11.84519910812378 seconds.\n",
      "Processed 72000000 lines in 11.598612070083618 seconds.\n",
      "Processed 73000000 lines in 12.174880027770996 seconds.\n",
      "Processed 74000000 lines in 11.744898319244385 seconds.\n",
      "Processed 75000000 lines in 11.774956941604614 seconds.\n",
      "Processed 76000000 lines in 12.019569158554077 seconds.\n",
      "Processed 77000000 lines in 11.80133605003357 seconds.\n",
      "Processed 78000000 lines in 11.841987371444702 seconds.\n",
      "Processed 79000000 lines in 11.878009557723999 seconds.\n",
      "Processed 80000000 lines in 11.786965131759644 seconds.\n",
      "Processed 81000000 lines in 11.597920417785645 seconds.\n",
      "Processed 82000000 lines in 12.385830879211426 seconds.\n",
      "Processed 83000000 lines in 11.53875207901001 seconds.\n",
      "Processed 84000000 lines in 11.96531891822815 seconds.\n",
      "Processed 85000000 lines in 11.732539892196655 seconds.\n",
      "Processed 86000000 lines in 11.476588487625122 seconds.\n",
      "Processed 87000000 lines in 11.847708702087402 seconds.\n",
      "Processed 88000000 lines in 12.041157245635986 seconds.\n",
      "Processed 89000000 lines in 11.776954889297485 seconds.\n",
      "Processed 90000000 lines in 11.909484386444092 seconds.\n",
      "Processed 91000000 lines in 11.71180009841919 seconds.\n",
      "Processed 92000000 lines in 11.516483306884766 seconds.\n",
      "Processed 93000000 lines in 11.727542161941528 seconds.\n",
      "Processed 94000000 lines in 11.458016395568848 seconds.\n",
      "Processed 95000000 lines in 11.830156087875366 seconds.\n",
      "Processed 96000000 lines in 11.930320739746094 seconds.\n",
      "Processed 97000000 lines in 11.60464596748352 seconds.\n",
      "Processed 98000000 lines in 12.019718885421753 seconds.\n",
      "Processed 99000000 lines in 12.29069447517395 seconds.\n",
      "Processed 100000000 lines in 11.789185762405396 seconds.\n",
      "Processed 101000000 lines in 12.126100301742554 seconds.\n",
      "Processed 102000000 lines in 11.912652969360352 seconds.\n",
      "Processed 103000000 lines in 11.661912679672241 seconds.\n",
      "Processed 104000000 lines in 12.02697467803955 seconds.\n",
      "Processed 105000000 lines in 11.789957523345947 seconds.\n",
      "Processed 106000000 lines in 12.0976243019104 seconds.\n",
      "Processed 107000000 lines in 12.22239875793457 seconds.\n",
      "Processed 108000000 lines in 11.693696022033691 seconds.\n",
      "Processed 109000000 lines in 11.897872924804688 seconds.\n",
      "Processed 110000000 lines in 11.835729360580444 seconds.\n",
      "Processed 111000000 lines in 11.6429443359375 seconds.\n",
      "Processed 112000000 lines in 11.99439287185669 seconds.\n",
      "Processed 113000000 lines in 11.529836654663086 seconds.\n",
      "Processed 114000000 lines in 11.98662281036377 seconds.\n",
      "Processed 115000000 lines in 12.019933223724365 seconds.\n",
      "Processed 116000000 lines in 11.736188411712646 seconds.\n",
      "Processed 117000000 lines in 11.98626971244812 seconds.\n",
      "Processed 118000000 lines in 12.186249494552612 seconds.\n",
      "Processed 119000000 lines in 11.818801879882812 seconds.\n",
      "Processed 120000000 lines in 12.083193063735962 seconds.\n",
      "Processed 121000000 lines in 11.582455158233643 seconds.\n",
      "Processed 122000000 lines in 12.037126779556274 seconds.\n",
      "Processed 123000000 lines in 11.726020336151123 seconds.\n",
      "Processed 124000000 lines in 11.839289426803589 seconds.\n",
      "Processed 125000000 lines in 11.605871200561523 seconds.\n",
      "Processed 126000000 lines in 11.548797607421875 seconds.\n",
      "Processed 127000000 lines in 11.143155574798584 seconds.\n",
      "Processed 128000000 lines in 11.692105054855347 seconds.\n",
      "Time taken: 11547.674425840378\n"
     ]
    }
   ],
   "source": [
    "filename='../train.csv'\n",
    "password_list = PasswordRetriever(filename)\n",
    "start = time.time()\n",
    "trained_model = FastText(password_list, size=SIZE, min_count=min_count, workers=12,\n",
    "                         negative=negative, sample=subsampling, window=20,\n",
    "                         min_n=min_n, max_n=max_n)\n",
    "end = time.time()\n",
    "print(\"Time taken: {}\".format(end - start))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Saving the model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, the trained model is saved as `.bin`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from gensim.models.fasttext import save_facebook_model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Model saved successfully.\n"
     ]
    }
   ],
   "source": [
    "save_facebook_model(trained_model, \"model_password_similarity.bin\")\n",
    "print(\"Model saved successfully.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Compressing the model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The trained model has 4.8GB. There are some problems about the size:\n",
    "- Too much space occupied in memory.\n",
    "- It is harder to use the model in client/server architectures. Everyone should use this model, which can be sent as a payload. Embeddings are not reversible, and they guarantee password anonymization.\n",
    "\n",
    "For these reasons, `compress_fasttext` is used."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gensim\n",
    "import compress_fasttext\n",
    "# from gensim.models.fasttext import load_facebook_vectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " In order to obtain a compressed model, without impacting significantly on performances, _product quantitation_ and _feature selection_ are applied.\n",
    " \n",
    " - _Feature selection_ is the process of selecting a subset of relevant features for use in model construction or in other words, the selection of the most important features.\n",
    "\n",
    " - _Product quantization_ is a particolar type of _vector quantization_, a lossy compression technique used in speech and image coding. A product quantizer can generate anexponentially large codebook at very low memory/time cost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "big_model = gensim.models.fasttext.load_facebook_vectors('model_password_similarity.bin')\n",
    "small_model = compress_fasttext.prune_ft_freq(big_model, pq=True)\n",
    "small_model.save('compressed_model')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The compressed_model is 20MB."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "<a name=\"gensim-fasttext\">[1]</a> [Gensim FastText documentation](https://radimrehurek.com/gensim/models/fasttext.html)\n",
    "\n",
    "<a name=\"cbow_skipgram\">[2]</a> [Differences between cbow and skipgram](https://fasttext.cc/docs/en/unsupervised-tutorial.html)\n",
    "\n",
    "<a name=\"negative_sampling\">[3]</a> [Negative sampling](http://mccormickml.com/2017/01/11/word2vec-tutorial-part-2-negative-sampling/)\n",
    "\n",
    "<a name=\"compress_fasttext\">[4]</a> [Compress FastText package](https://pypi.org/project/compress-fasttext/)\n",
    "\n",
    "<a name=\"feature-selection\">[5]</a> [Feature selection](https://towardsdatascience.com/feature-selection-and-dimensionality-reduction-f488d1a035de)\n",
    "\n",
    "<a name=\"product-quantization\">[6]</a> [Product quantization](https://www.microsoft.com/en-us/research/wp-content/uploads/2013/11/pami13opq.pdf)\n",
    "\n",
    "<a name=\"paper-bijeeta\">[7]</a> [PPSM description from the paper \"Beyond Credential Stuffing: Password Similarity Models using Neural Networks\"](https://www.cs.cornell.edu/~rahul/papers/ppsm.pdf)\n",
    "\n",
    "<a name=\"repo-bijeeta\">[8]</a> [PPSM repository from the paper \"Beyond Credential Stuffing: Password Similarity Models using Neural Networks\"](https://github.com/Bijeeta/credtweak)"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}