bound.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "# edit distance 1000x1000: 100%|██████████| 1000/1000 [02:04<00:00,  8.02it/s]\n",
      "  0%|          | 0/52 [00:00<?, ?it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Calculate edit distance time: 124.6652319431305\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 52/52 [1:32:50<00:00, 91.40s/it] "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "52.0 1.8483353884093712 28.439545176737834\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import string\n",
    "import numpy as np\n",
    "from multiprocessing import cpu_count\n",
    "np.random.seed(1)\n",
    "random.seed(1)\n",
    "\n",
    "C = 52 \n",
    "M = 1000\n",
    "letters = list(range(C))\n",
    "\n",
    "def randomString(stringLength):\n",
    "    \"\"\"Generate a random string of fixed length \"\"\"\n",
    "    return [random.choice(letters) for _ in range(stringLength)]\n",
    "\n",
    "def int2str(l):\n",
    "    return \"\".join(chr(i+ord('a')) for i in l)\n",
    "\n",
    "N = 1000\n",
    "strings = [randomString(random.randint(1, M)) for _ in range(N)]\n",
    "lengths = [len(i) for i in  strings]\n",
    "def one_hot(s):\n",
    "    encode = np.zeros((C, M), dtype=np.int)\n",
    "    encode[np.array(s), np.arange(len(s))] = 1\n",
    "    return encode\n",
    "\n",
    "oh_strs = [one_hot(s) for s in strings]\n",
    "or_strs = [int2str(s) for s in strings]\n",
    "\n",
    "from datasets import all_pair_distance\n",
    "knnd = all_pair_distance(or_strs, or_strs, cpu_count())\n",
    "\n",
    "oh_strs = np.array(oh_strs)\n",
    "\n",
    "import tqdm\n",
    "dist = []\n",
    "def int2str(s):\n",
    "    return \"\".join(str(i) for i in s)\n",
    "for i in tqdm.tqdm(range(C)):\n",
    "    ss = oh_strs[:, i, :]\n",
    "    ss = [int2str(s[:lengths[i]]) for i, s in enumerate(ss)]\n",
    "    d = all_pair_distance(ss, ss, 8, progress=False)\n",
    "    dist.append(d)\n",
    "\n",
    "dist = np.array(dist)\n",
    "bound = np.sum(dist, axis=0)\n",
    "index = np.where(knnd != 0)\n",
    "ration = bound[index] / knnd[index]\n",
    "print(np.max(ration), np.min(ration), np.mean(ration))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1000, 1000)\n",
      "(1000, 1000)\n",
      "(array([], dtype=int64), array([], dtype=int64))\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/xinyan/.conda/envs/py3/lib/python3.6/site-packages/ipykernel_launcher.py:3: RuntimeWarning: invalid value encountered in true_divide\n",
      "  This is separate from the ipykernel package so we can avoid doing imports until\n"
     ]
    }
   ],
   "source": [
    "print(knnd.shape)\n",
    "print(bound.shape)\n",
    "idx = np.where( bound/knnd == 1.6344086021505377)\n",
    "print(idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "pairs = list((or_strs[i], or_strs[j]) for i, j  in zip(idx[0], idx[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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": 1
}