{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Dear difflib, What The F@&#! ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## TL,DR:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Acording to difflib, the following strings: 'baaaaa', 'aaabaa' and 'aaaaba' share 5 caracters with 'aaaaaa', but 'aabaaa' share only 3 .... but only if the change is in the first half of the string." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5\n", "4\n", "3\n", "5\n", "- Control -\n", "6\n" ] } ], "source": [ "import difflib\n", "print sum(x.size for x in difflib.SequenceMatcher(None, '-aaaaa', 'aaaaaa').get_matching_blocks())\n", "print sum(x.size for x in difflib.SequenceMatcher(None, 'a-aaaa', 'aaaaaa').get_matching_blocks())\n", "print sum(x.size for x in difflib.SequenceMatcher(None, 'aa-aaa', 'aaaaaa').get_matching_blocks())\n", "print sum(x.size for x in difflib.SequenceMatcher(None, 'aaa-aa', 'aaaaaa').get_matching_blocks())\n", "print '- Control -'\n", "print sum(x.size for x in difflib.SequenceMatcher(None, 'aaaaaa', 'aaaaaa').get_matching_blocks())\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It only get weirder and more fractal if you read the rest" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Context" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A few weeks back I was in [EuroSciPy](http://euroscipy.org), where I had to dive a little deeper than usual into difflib.\n", "Indead, one often requested feature in [IPython](http://ipython.org) is to be able to diff notebooks, so I started looking at how this can be done. Thanks to [@MinRK](http://github.com/minrk) for helping me figuring out the rest of this post and give me some nices ideas of graphs.\n", "\n", "Naturaly I turned myself toward [difflib] :\n", "\n", "\n", "> This module provides classes and functions for comparing sequences. It can be used for example, for comparing files, and can produce difference information in various formats, including HTML and context and unified diffs. For comparing directories and files, see also, the filecmp module.\n", "\n", "[difflib]: http://docs.python.org/2/library/difflib.html\n", "\n", "More especially, I am interested in [`SequenceMatcher`](http://docs.python.org/2/library/difflib.html#difflib.SequenceMatcher) which aims to be : \n", "\n", "> [...] a flexible class for comparing pairs of sequences of any type, so long as the sequence elements are hashable." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is also explicitely state that generated diff might not be minimal, but might looks more \"human readable\" than classical diff (emphasis mine). \n", "\n", "> The basic algorithm [..] is a little fancier than,[...] \u201cgestalt pattern matching.\u201d The idea is to find the longest contiguous matching subsequence that contains no \u201cjunk\u201d elements [...]. The same idea is then applied recursively to the pieces of the sequences to the left and to the right of the matching subsequence. This **does not yield minimal edit sequences**, but does tend to yield matches that **\u201clook right\u201d** to people.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To do that, we need to define \"junk\" which are things you don't want the algorithme to match on. \n", "Let see a common example in python where when you add a function with a derorator, the decorator is often added to the \"next\" function." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "s1 = \"\"\"\n", "@decorate\n", "def fun1():\n", " return 1\n", " \n", "@decorate\n", "def fun3():\n", " return 3\n", "\"\"\"\n", "\n", "s2 = \"\"\"\n", "@decorate\n", "def fun1():\n", " return 1\n", " \n", "@decorate\n", "def fun2():\n", " return 2\n", " \n", "@decorate\n", "def fun3():\n", " return 3\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Classical diff" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " \n", " @decorate\n", " def fun1():\n", " return 1\n", " \n", " @decorate\n", "+ def fun2():\n", "+ return 2\n", "+ \n", "+ @decorate\n", " def fun3():\n", " return 3\n", "\n" ] } ], "source": [ "import difflib\n", "print ''.join(difflib.ndiff(s1.splitlines(1), s2.splitlines(1)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we will tell it that blank line are junk:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " \n", " @decorate\n", " def fun1():\n", " return 1\n", " \n", "+ @decorate\n", "+ def fun2():\n", "+ return 2\n", "+ \n", " @decorate\n", " def fun3():\n", " return 3\n", "\n" ] } ], "source": [ "blankline = lambda x:x.strip() ==''\n", "print ''.join(difflib.ndiff(s1.splitlines(1), s2.splitlines(1), linejunk=blankline))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is clearly better, as hunk do not have blank lines in the midlle, but more on sides." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Where it gets weird" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Things is, `SequenceMatcher` is also the method that help you get the proximity between two strings.\n", "If the sequence you pass to `SequenceMatcher` is a string, it will try to match each caracters." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from difflib import SequenceMatcher" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.0\n", "0.0\n" ] } ], "source": [ "print SequenceMatcher('hello world','hello world').ratio()\n", "print SequenceMatcher('xyz','abc').ratio()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Oh, sorry, you need to explicitelty, pass the `isjunk` function. Hopefully, it accepts `None`." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1.0\n", "0.0\n" ] } ], "source": [ "print SequenceMatcher(None, 'hello world','hello world').ratio()\n", "print SequenceMatcher(None, 'xyz','abc').ratio()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ok, that's better, it goes from 0.0 for completely different strings (nothing in common) to 1.0 for perfectly matching strings.\n", "\n", "API is weird, but for compatibility we keep the old one... fine with me" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "let's try longer..." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.0\n" ] } ], "source": [ "print SequenceMatcher(None, 'y'+'abc'*150,'x'+'abc'*150).ratio()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Still, don't pass it strings longer than 200 char, it automatically detect junk... Yes this is documented, but not obvisous." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.9977827051\n" ] } ], "source": [ "print SequenceMatcher(None, 'y'+'abc'*150,'x'+'abc'*150, autojunk=False).ratio()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So let's define a custom SequenceMatcher that make sens for the rest of the post, so that `isjunk`is `None` by default, and no `autojunk` for `n > 200`, and a simple `ratio(a, b)` method as a shortcut." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def MySequenceMatcher( seq1, seq2, isjunk=None, autojunk=False):\n", " return SequenceMatcher(isjunk, seq1, seq2, autojunk=autojunk)\n", "\n", "def ratio(a,b):\n", " return MySequenceMatcher(a,b).ratio()" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1.0\n", "0.75\n" ] } ], "source": [ "print ratio('abc','abc')\n", "print ratio('abcd','abcf')\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Where it gets weirder" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I'll probably won't go into how we found out the following, but for some reason `ratio(a,b)` was different from `ratio(reversed(a),reversed(b))`, that is to say `ratio('ab...yz','ab...yz') != ratio('zy...ba','zy...ba')` in some case. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So let's look at what happend if we compare a string against itself, with only one modification, as a function as the position of the modification, that is to say the ratio of `aaaa...` vs `baaa...` vs `abaa...` vs `aaba...`" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [], "source": [ "%matplotlib inline\n", "import matplotlib\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "aaaaaaaaaa ...\n", "aaaaaaaaaa ...\n", "-aaaaaaaaa ...\n", "a-aaaaaaaa ...\n", "aa-aaaaaaa ...\n", "aaa-aaaaaa ...\n", "aaaa-aaaaa ...\n", "aaaaa-aaaa ...\n", "aaaaaa-aaa ...\n", "aaaaaaa-aa ...\n", "aaaaaaaa-a ...\n", "..............\n" ] }, { "data": { "text/plain": [ "" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": [ "iVBORw0KGgoAAAANSUhEUgAAAYkAAAEPCAYAAAC3NDh4AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n", "AAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8VGWaL/BfLdlDNsgeSICwmBDZVEAQMKBGRxQVBBsd\n", "+/boTLc99qat3WrfP+aK2q3ddo+38Tq29vjpUdCA7ItpkrBE0kQSA0kgEM3CEpIKJAESslad+0dM\n", "nQRSqSScU+9bVb/v5+PHVOVUnSdPDnnqfZ9z3mNQFEUBERHRAIyiAyAiInmxSBARkUMsEkRE5BCL\n", "BBEROcQiQUREDulWJGw2G6xWq15vT0RELmDW40337NmDyspKLF++HHFxcYNuW1dXh+zsbJhMJixa\n", "tAixsbF6hERERCNg0Os6iePHjyMsLMxpkdi2bRseeOABAMCWLVuwfPlyPcIhIqIREN6TCAwMtH/t\n", "6+srMBIiIrqW8CLRdyDj4+MjMBIiIrqW8CLRt7ltMBgERkJERNfSpXHtSGlpKYxGI1JSUuzPtbW1\n", "AegZUfR+7UhWVhZMJpOuMRIReZqwsDDMnj17RK/VpUjs3bsXlZWV8Pf3R1JSEhYuXAgAyM/Ph8Fg\n", "6Fck5syZg/Xr10NRFCxdunTQ9zWZTJg1a5YeIRMReayioqIRv1a3s5v0kJ2dzSLxnby8PCxYsEB0\n", "GFJgLlTMhYq5UBUVFWHJkiUjeq3wngQREcmLIwkiIg93IyMJlzautXTuUjviQ/1Fh0EEALjY2oXL\n", "Hd2iwyCyiwvxg5/5xieL3LJIWG0KfpNVie/PjsXCCeGiwxGC860qGXLx/M4KAIDZJPY07qutVxEY\n", "FOh8Qy/g7bn430vGY2zYjX+QdssiYTIa8KvFSXj5i2+RPCYQcSF+okMiL9dhteGPyyYjKljsqgE9\n", "BXNkpzp6GuZCG27buJ4cGYg1M2PwanYVOq020eG4nOhPzjKRIRc2mwKTUfzFoDLkQhbMhTbctkgA\n", "wIMpYxAzyhfvH64VHQp5OasCCJ5pItKFWxcJg8GAX9wxDofPXEJeVbPocFwqLy9PdAjSkCEXVklG\n", "EjLkQhbMhTbcukgAQLCfGS/dmYQ/fXkG5690iA6HvJRVUWDi2mPkgdy+SADA1KggrJ4ejddyqtHl\n", "Jf0JzreqZMiFLCMJGXIhC+ZCGx5RJADg4WmRiAjwwQdfsT9BridLkSDSmscUCYPBgOcWjsOX1ZeQ\n", "X3NJdDi643yrSnQuFEWBVQFkqBGicyET5kIbHlMkACDE34xf35mEtw+eRv2VTtHhkJewfVcgjOxJ\n", "kAfyqCIBACnRQViRFoXXcqvQbXObZamGjfOtKtG5kKlpLToXMmEutOFxRQIAVtwchWBfM/7K/gS5\n", "gNWmwCjDXBORDjyySBgNBrywOBG5lU0oOOOZ/QnOt6pE58Im0YV0onMhE+ZCGx5ZJAAg9Lv+xO8P\n", "nEZDK/sTpB+e2USezGOLBACkxQRjeWokXs+phtXD+hOcb1WJzoXVxp6EjJgLbXh0kQCAVdOj4Wc2\n", "4qPC86JDIQ9lVTiSIM/l8UWitz+xt6IRR85eFh2OZjjfqhKdC6sNMEnyL0l0LmTCXGhDkkNbX+EB\n", "PnhxcSLe2l+Di61dosMhDyPTKbBEWvOKIgEA0+NG4f6USLye6xn9Cc63qkTnQqbGtehcyIS50IbX\n", "FAkAeGx6NExG4H++rhMdCnkQjiTIk3lVkei97emekxdRdM69+xOcb1WJzkXPSEJoCHaicyET5kIb\n", "khzarhMe6IMXFiXid/tr0HiV/Qm6cT2L+3EkQZ7J64oEAMyMH4X7poxx6/4E51tVonPBnoScmAtt\n", "eGWRAIA1M2MAAJ8Usz9BN8Ym0cV0RFrz2iLR25/YeeICimuviA5n2DjfqhKdC5kuphOdC5kwF9rw\n", "2iIBAKODfPD8okT8dl8NmtrYn6CRkeliOiKtef2hfUtCCO6eFIHf7quBTXGf/gTnW1WicyHTKbCi\n", "cyET5kIbXl8kAOCfZ8ei02rDp0frRYdCbkimxjWR1lgk0NOf+PWdSdhS1oCSuhbR4QwJ51tVonMh\n", "00hCdC5kwlxog0XiO5FBvnhu4Ti8nluNS+3dosMhN8KeBHkyHtp93DY2FOkTw/E7N+hPcL5VJToX\n", "vJ+EnJgLbbBIXOP7t8ShtdOKjccsokMhN2FVeI9r8lwsEtcwGw14KT0JG0ssKKuXtz/B+VaV6FzI\n", "1LgWnQuZMBfaYJEYQFSwL35+R09/4jL7E+SEVQFMctQIIs2Z9XjTuro6ZGdnw2QyYdGiRYiNjXW4\n", "rcViQU5ODgICApCWloYJEyboEdKwzUsMxbHzV/Dm/hr8x90TYJBkzrkX51tVonMh00hCdC5kwlxo\n", "Q5eRREFBAdasWYPVq1fj8OHDg2779ddfY/Xq1XjwwQdRW1urRzgj9oNb49Dc3o1NJexPkGM2iU6B\n", "JdKaLkUiMDDQ/rWvr++g2/r5+aGtrQ1WqxXFxcXo7OzUI6QR8TEZ8XJ6Ej49ZsEJS6vocPrhfKtK\n", "dC5kGkmIzoVMmAtt6FIklD6nj/r4+Ay67YIFC5CdnY2tW7di8uTJaG2V649xzCg//GzBWLyWU40r\n", "HexP0PV6ToEVHQWRPnQpElar1f61s7l8s9mM+++/Hw8//DCuXr2KoKCgQbfv++kgLy/PJY/nJ4Vh\n", "XmIoXtr8NQ4edP3+B3q8YMECofuX6XHv3LOo/VuVnqv2ZchHXzLEI/LxtTkRHY/oxyNlUBTtrxrb\n", "vHkzHnroISiKgh07dmDZsmUAgNLSUhiNRqSkpFz3mubmZuzYsQOPP/64w/fNzs7GrFmztA53SDqt\n", "Nvx8+yksTY7AQ9OihMRAcvrk6zp0dNvwv26NEx0K0YCKioqwZMmSEb1Wl5HEnDlzsH79eqxfvx5z\n", "5syxP5+fn49Dhw7127akpASZmZnIysrCo48+qkc4mvA1GfFK+nh8UlyPkw3ip8S0+ITgKUTngveT\n", "kBNzoQ1dToGNi4vDY489dt3zTz/99HXPpaWlIS0tTY8wNBcb4odn5ydgbU411i2fgmA/XdJHbsZq\n", "U2Dm4k3koXhkD9PC8eG4bWwI/nDwDHSYqRsyngOuEp0LmS6mE50LmTAX2mCRGIF/vS0edVc6sP3E\n", "BdGhkARkWuCPSGssEiPgazbi5fTx+FtRHU5duCokBs63qkTnwibRAn+icyET5kIbLBIjFB/qhx/P\n", "S8BrOVVo7bQ6fwF5LKtNnukmIq2xSNyAxRPDMTNuFP548LTL+xOcb1WJzoVMZzeJzoVMmAttsEjc\n", "oB/OTcCZS+3YWX5RdCgkiEzLchBpjUXiBvl915/4qPA8vr3ouv4E51tVonMh0wJ/onMhE+ZCGywS\n", "Ghgb5o8fzo3H2pxqXGV/wuv0jCRER0GkDx7aGlmSHIFp0cH405euuX6C860q0bnouU5CjpGE6FzI\n", "hLnQBouEhp65PQFVjW3Yc5L9CW/CngR5MhYJDfmbe9Z3+vDIeVQ1tum6L863qkTnQqaL6UTnQibM\n", "hTZYJDQ2Ltwf/zonDq9mV6Gti/0JbyDTKbBEWmOR0MFdk0bjpqggvHPorG774HyrSnQurDZI07gW\n", "nQuZMBfakOTQ9jw/vj0BFQ1XkXWK/QlPZ1UUGCWZbiLSGouETgJ8THh5SRLeL6hFTZP2/QnOt6pE\n", "50KmxrXoXMiEudAGi4SOksID8C+3xuHVnGq0d9tEh0M6sUp0MR2R1lgkdHbP5Agkjw7Anw+d0fR9\n", "Od+qEp0LG3sSUmIutCHJoe25DAYDfjJ/LMrqW7G3olF0OKQDjiTIk7FIuECAjwmvpI/He4fP4XRz\n", "uybvyflWlehcsCchJ+ZCGywSLjJhdAC+f0ss1mZXoYP9CY8i08V0RFpjkXCh+6aMRmK4P979x41f\n", "P8H5VpXoXFgV9iRkxFxoQ5JD2zsYDAb8dME4HK1tQe63TaLDIY3INN1EpDUWCRcL8jXh5fQkrMs/\n", "i3OXRt6f4HyrSnQuZGpci86FTJgLbbBICJA8JhBPzIrBqznV6GR/wu1xJEGejEVCkGU3jUFciB/e\n", "O3xuRK/nfKtKdC5kGkmIzoVMmAttsEgIYjAY8Is7xuHI2cs4UMX+hDuz2gAj/yWRh+KhLVBPf2I8\n", "3vnyLGovdwzrtZxvVYnOBe9xLSfmQhssEoJNjgzE92ZEY21OFTqt7E+4I/YkyJOxSEhgeWokIoN8\n", "8ZeC2iG/hvOtKtG5kKlIiM6FTJgLbTgtEp2dna6Iw6sZDAY8t3Ac8msuIa+6WXQ4NExWBTDJUSOI\n", "NOe0SLz11luor693RSxebZSfGS+lJ+FPeWdQd8V5f4LzrSrRuZBpJCE6FzJhLrThtEjMnTsXZWVl\n", "yMzMxIULF1wRk9e6KSoIq6ZHY21ONbrYn3ALNkUBAN6ZjjyW2dkG6enpAICuri7k5ubiwoULyMjI\n", "wPnz55Gamqp7gN7mkWmROHb+Cj78qhb/NjfB4Xacb1WJzIVMowiAx0VfzIU2nI4kuru7AQBnz55F\n", "Y2MjpkyZgoKCAmzcuFH34LyRwWDA8wsTcbC6Gfk1l0SHQ06wH0GezmmR+OCDD7B+/XrU1dVh9erV\n", "mD17NjIyMjB9+nRXxOeVQvzN+PWdSXj74GlYWgY+cYDzrSqRuZBtJMHjQsVcaMNpkQgNDcWqVasw\n", "b968fs9HREToFhQBqdHBWJEWhbU5Vei2KaLDIQdkKxJEWjMoiqL5X6C6ujpkZ2fDZDJh0aJFiI2N\n", "dbhtVVUVCgsLYbPZMG/ePIwdO9bhttnZ2Zg1a5bW4UrLpij4zReVSAr3x9Nz4kWHQwNoauvCv24q\n", "R+bjaaJDIXKoqKgIS5YsGdFrh30xXV1dndNtCgoKsGbNGqxevRqHDx8edNvy8nKsWLECjz76KEpK\n", "SoYbjkczGgx4YXEiciubcPg0+xMystnkueEQkR6cHt5lZWX9Hh86dMjpmwYGBtq/9vX1HXRbq9UK\n", "m80Gq9UKHQY1bi/0u/7EHw6eRkOr2p/gfKtKaE9ConWbAB4XfTEX2nBaJCoqKvo9NpudnjXb74+9\n", "j4/PoNtOmzYNb775Jt566y3MnDnT6Xt7o7SYYCxPjcTrOdWwsj8hFfYkyNMNe6Bsszm/yMtqtdq/\n", "Njj5lHX06FG8+OKL+OUvf4kjR44MNxyvsWp6NPzMRnxUeB4AzwHvS+h1EpKNJHhcqJgLbTgcFuzY\n", "sQNtbW0oLy9HV1eX/fno6Ginb9rW1gagZ0TR+zUAlJaWwmg0IiUlxf5c73SU0Wh0OuoAeoaQvb/8\n", "3uGkNzw2GgxYHFCH/yoLwM2xwbglIUSq+Lz1cUOHASZjhDTx8DEfO3o8Uk7Pbtq+fTuWLVs2rDet\n", "ra3F/v37oSgKli5diqioKADA+++/D4PBgKeeesq+bXl5OY4fPw4ASE1NxZQpUxy+r7ed3TSQo7VX\n", "8HpuNZ6Mu4x775wvOhwp9P3g4GqVF9vw233VeO+Rm4Ts/1oicyEb5kJ1I2c3OW0w3HvvvcN+07i4\n", "ODz22GPXPf/0009f99zUqVMxderUYe/DW02PG4X7bxqDz0904G7OhwtnVfg7IM/mtCcxlEY1udZj\n", "M2IQHh6K//na+enI3oBrN6n4yVnFXGhj2I3rffv26RAGDYfJaMCvFidh98kLKDp3WXQ4Xk22xjWR\n", "1oZdJJqbeVMcGRwvOowXFyXhd/trcPFql/MXeDCxazcBRokupuO1ASrmQhsO55LWrVuHlStXYteu\n", "Xf0ujisvL8fy5ctdEhwNbmb8KNw3ZQzeyK3GG/cmSzXt4S04kiBP57BIrFy5EuHh4QgNDe1XFLZs\n", "2eKSwGhwvfOta2bG4Fe7v8EnxXV4YpbjNbI8GXsSKs7Dq5gLbTgcKEdGRsJsNiM5Obn/C2QaW5O9\n", "P7HzxAUU114RHY7XsXEkQR7O6V/8adOm9XuckZGhWzA0dH3nW0cH+eD5RYn47b4aNHlhf0J0T0Km\n", "Bf44D69iLrQx7MPb2YJ9JMYtCSG4e1IEfru/xn7fZdKf1caRBHk2p0Vi8+bNroiDhmmg+dZ/nh2L\n", "TqsNG4rrBUQkjvC1m9iTkBJzoQ2nReLaBf12796tWzB0Y0xGA359ZxK2Hm/AsfMtosPxCrI1rom0\n", "5rRI+Pr6wmKx2B93dHToGhANjaP51sggXzy3cBze2FeN5jbv6E+Iv5+EsN1fh/PwKuZCG06LRGtr\n", "K95++21kZmYiMzOTd49zA7eNDUX6xHD8jv0J3fU0riWqEkQac7owU0BAAF5//XX7Y14nIQdn863f\n", "vyUOz++oQOYxC1ZNd768uzsT3ZMwStS45jy8irnQhtORxLXLy9588826BUPaMRsNeCk9CZtKLCir\n", "Y39CL+xJkKdzWiSCg4P7PZ4wYYJuwdDQDWW+NSrYFz+/Yxxey63G5fZuF0QlhtjrJOQ6BZbz8Crm\n", "QhvDvk6isLBQjzhIJ/MSQ7FwfBje3F8DJ/eXohGwKnJdTEekNac9iWPHjqG8vBzNzc0ICQlBdXU1\n", "Zs+e7YrYaBDDmW/9wa1x+MWOCmwqsWDFzZ7XnxA592yTbCTBeXgVc6ENp5+BysvL8eijjyI2Nhar\n", "V6/GxIkTXREXacjHZMTL6Un47JgFJyytosPxKLJdTEektSFdJwEAVqsVAODj46NvRDQkw51vjRnl\n", "h58uGIvXcqpxpcOz+hPCexISFQnOw6uYC204LRKdnZ0Aeq68tlqtnNd2Y/OTwjAvMRRvHTjN36NG\n", "bAqkupiOSGtOi8TixYsB9MzvrV+/HiEhIXrHREMw0vnWp26Lw4XWTmwpa9A4InFE30+C10nIibnQ\n", "htPGdVRUlP3/jz/+uO4Bkb58TUa8kj4eP9l2CinRQZgSGSQ6JLfGngR5umGfvNc7/URi3ch8a2yI\n", "H56dn4C1OdVo8YD+hPCehEQ1gvPwKuZCG8MuEnv27NEjDnKxhePDcWtCCP5w8Az7Ezeg5zoJiaoE\n", "kcaGXSSuXTqcxNBivvXf5sSj7koHtp+4oEFE4ojuSchUJDgPr2IutOGwJ/H73/8e48aNu+758vJy\n", "LF++XNegyDV8zUa8nD4eP9t+CjdFBWHSmEDRIbkd2Rb4I9Kaw5HExIkTsXLlyuv+S0tLc2V85IBW\n", "863xoX748bye/kRrp1WT93Q14T0JiUYSnIdXMRfacFgk5s2bN+DzYWFhugVDYiyeGI6ZccH4Yx6v\n", "nxguK6+TIA/nsEhERw+8xk/vdRMkltbzrT+cm4Azze3YWX5R0/d1BfYkVJyHVzEX2uD6lQQA8Puu\n", "P/FR4Xl8e/Gq6HDchmwL/BFpbdhFYt++fTqEQcOlx3zr2DB//HBuPNbmVOOqG/UnhN/jWqKRBOfh\n", "VcyFNoZdJJqbm/WIgySxJDkC06KD8Z9f8vqJoei5x7XoKIj04/AU2HXr1mHlypXYtWsXAgPVUyN5\n", "Cqwc9Jxvfeb2BPxk60nsOdWIe6eM1m0/WhF9j2uZpps4D69iLrThsEisXLkS4eHhCA0N7VcUtmzZ\n", "4pLASBx/c8/6Ts/trMDUyECMjwgQHZK0ZGtcE2nN4UA5MjISZrMZycnJ/V9g5NhaBnrPt44L98fT\n", "t8VhbU412rrk7k8I70lINJLgPLyKudCG07/406ZN6/c4IyNDt2BILndPHo0pkYH4v4fOig5FWuxJ\n", "kKcb9uFdUVGhRxw0TK6ab/332xNwsuEqsk7Je/2E8OskJBpJcB5exVxow+n9JLZt24b29nYYvvuH\n", "0NbWhtTUVKdvXFdXh+zsbJhMJixatAixsbEOt33zzTcxadIkAMCFCxfw1FNPDTV+0lmAjwkvpyfh\n", "hV3fYEpkIBLD2Z/oy6ooMLInQR7MaZFob2/Ho48+an/c3T20+w8UFBRgzZo1AHqa3YOdEfXss8/C\n", "398fAJciH6q8vDyXfVIaHxGAH9wah1dzqvHOg1Pgb5ZrfsWVubiWbI1rkbmQDXOhjSHd4zorKwv7\n", "9u3Dvn378Oc//3lIb9z3tFlfX99Bt+0tEBaLxX4nPJJLxuQITIwIwDr2J/qxKXLddIhIa05HEp2d\n", "nZgxYwbM5p5Nb7755iG9cd8LsXx8fIb0muPHj2Pu3LlD2tbbufoTksFgwE/mj8W/bz2J7G8asSQ5\n", "wqX7H4zYnoRcNx3iJ2cVc6ENpyMJo9GIqKgoREREICIiAvX19UN6Y6tVPW3SMMTGXnt7u31UQfIJ\n", "9O3pT/y/f5zDmeZ20eFIQbZTYIm05nQkUVNTg/Xr19tHEuXl5fjNb37j9I3b2toA9Iwoer8GgNLS\n", "UhiNRqSkpPTb3mazDekajL7zjL3nQXvj477ngLt6/0/Onoq1OVVYNeYifIzi83FtTly5/9arAfaR\n", "hAzHR0lJCX70ox9JE4/Ix++++y7S0tKkiUf045EyKE4W6Kmrq0NMTIz9cX19vcNlxPuqra3F/v37\n", "oSgKli5dau81vP/++zAYDNedwVRdXQ2bzYYJEyY4fM/s7GzMmjXL6b69gcimnKIoeC23GsG+Jvx0\n", "wfV3L3Q1kbl4fEMpfv9PkxE9avC+m6uwWatiLlRFRUVYsmTJiF7rtEhc69qi4UosEvJo7bTix1tO\n", "4snZsbhzYrjocIR57JNSvPPgZIwJkqNIEA3kRorEsM9l/Mc//jGiHZFnCfI14ZX0JKzLP4tzl7y3\n", "PyHbxXREWnNYJBoaGtDd3Y2GhoZ+/7W2troyPnJAhnVpkscE4olZMXg1pxqd3TZhcQhfu0mis5tk\n", "OC5kwVxow2GRyMzMRFNTE/72t7+hrKzM/t9Qz24i77DspjGIC/HDe4fPiQ5FCNkupiPSmsOzm555\n", "5hkAQHJycr/7WvOmQ3KQpSFnMBjwizvG4ZnN5ThQ2YSFE1zfnxB7PwlAphohy3EhA+ZCG057Eteu\n", "+nrt0uFEQb4mvJw+Hu8cOovayx2iw3EpG0cS5OGcFolrl9S4dulwEkO2+dbJkYH43oxorM2pQqfV\n", "tf0J4T0JiRrXsh0XIjEX2nBaJP7617+ipqYGBQUF+OSTT5h4cmh5aiQig3zxl4Ja0aG4hE1RYJNs\n", "uolIa06LxJgxY5CYmAiLxYLvfe97sFgsroiLnJBxvtVgMOC5heOQX3MJedWu612JyoVNAUyGoS87\n", "4woyHheiMBfacFokbLaeqYPeZTl4+1IazCg/M15KT8Kf8s7g/BXP7k/wzCbyBk7/4re0tOD06dMY\n", "PXo0ALk+NXkzmaf9booKwqrp0XgtpxpdLuhPiMqFjEVC5uPC1ZgLbTgtEvPnz0dpaSluvfVWfP31\n", "1zh//rwr4iI398i0SIQHmPHhV57bn5CtaU2kh2Gv3SQS125yL5fbu/HMlnL8eN5YzEsMFR2O5prb\n", "uvD0pnJkPp4mOhSiQbl07SaioQrxN+PXdybh7YOnYWnpFB2O5qzfNa6JPBmLhJtyl/nW1OhgrEiL\n", "wms51ei26TNoFdmTMLInIS3mQhssEqS7FTdHIcjXhP8+4ln9CfYkyBuwSLgpdzoH3Ggw4IXFicj5\n", "tgmHT1/S/P2FXSch4dlN7nRc6I250AaLBLlEqL8ZL92ZhD8cPI2GVs/oT1ht7EmQ52ORcFPuON86\n", "LSYYy1Mj8VpONawa9ieE9SQku5cE4J7HhV6YC22wSJBLrZoejQAfIz4qdP/rbWS8mI5IaywSbspd\n", "51uNBgN+uSgReysaceTsZU3eU1QuZGxcu+txoQfmQhssEuRy4QE++NWdiXhrfw0utnaJDmfErDbA\n", "xH9B5OF4iLspd59vvTl2FO6/aQxez73x/oTQnoRkIwl3Py60xFxog0WChHlsRgxMRuB/vq4THcqI\n", "sCdB3oBFwk15wnyryWjArxYnYc/Jiyg6N/L+hLCehE2BUbKRhCccF1phLrTBIkFChQf64IVFifjd\n", "/ho0XnWv/kTPKbCioyDSFw9xN+VJ860z40fhvilj8Ma+kfUnxK3dBPYkJMZcaINFgqSwZmYMFAVY\n", "X+w+/QkZL6Yj0hqLhJvytPnW3v7EjhMXcLT2yrBey7WbVJ52XNwI5kIbLBIkjdFBPnh+USJ+u68G\n", "TW3y9yd6ToEVHQWRvlgk3JSnzrfekhCCuyZF4Hf7amAb4k0ThfYkJBtJeOpxMRLMhTZYJEg6/zw7\n", "Fh1WGz49Wi86lEHJeDEdkdZYJNyUJ8+3mowG/PrOJGwpa0BJXYvT7UVeJyHbSMKTj4vhYi60wSJB\n", "UooM8sVzC8fh9dxqXGrvFh3OgKw2jiTI87FIuClvmG+9bWwo0ieGO+1PiFu7Sb4F/rzhuBgq5kIb\n", "kh3iRP19/5Y4tHZasfGYRXQo17EpCoySTTcRaY1Fwk15y3yr2WjAS+lJ2FhiQVn9wP0JoT0Jyaab\n", "vOW4GArmQhssEiS9qGBf/PyOnv7EZYn6E7zimryBLkWirq4OH3/8MTZs2IDz553fprKyshKZmZnY\n", "tm0bOjs79QjJ43jbfOu8xFDckRSGtw7UQLmmPyHyOgnZaoS3HReDYS60oUuRKCgowJo1a7B69Woc\n", "Pnx40G2bm5tx/vx5rFy5Eg888AB8fX31CIk8wA9ujUNTWzc2lTaIDgWAnNNNRFrTpUgEBgbav3b2\n", "R7+4uBhBQUH4/PPPcerUKT3C8UjeON/qYzLi5fQkfHq0Hicsrfbnhd7jWrKhhDceF44wF9rQpUj0\n", "nQ7w8fEZdFuLxYLm5mY8/PDDqKiogM1m0yMk8hAxo/zwswVj8VpONa50iO1P9CzwJzQEIt3pcohb\n", "rVb714YhDMcXLlwIAIiPj0djY+Og2/adZ8zLy/Pax71fyxKPKx/PTwrDvMRQvLT5axw8eH1OXBVP\n", "zdlzOF1dLTwffR+/++67UsUj8vG7774rVTyiH4+UQbm2C6iBzZs346GHHoKiKNixYweWLVsGACgt\n", "LYXRaERKSop92+LiYgQHByM5ORm5ublYsGCBw9FHdnY2Zs2apXW4bikvL8+rh9OdVht+vv0UliZH\n", "ILL5lJBcvJt/FtGjfPHwtCiX79sRbz8u+mIuVEVFRViyZMmIXmvWOBYAwJw5c7B+/XooioKlS5fa\n", "n8/Pz4fBYOhXJGbMmIGNGzeipKQEkZGRTqenqIe3H/y+JiNeSR+Pn2w7hbX3iPngIOMCf95+XPTF\n", "XGhDlyLd70nYAAAQKElEQVQRFxeHxx577Lrnn3766QG3X7FihR5hkIeLDfHDs/MT8GpOFd59aCqC\n", "fE0u3b+MC/wRaY1tNzelxVyjJ1g4PhwJplb84eDp666f0FvPPa5dukuneFyomAttsEiQ27s7qhO1\n", "lzuw/cQFl+5XxlNgibSmy3QT6Y/zrarFCxdg0qV2/Gx7BVKigpA8JtD5izRgtSkwsichLeZCGxxJ\n", "kEeID/XHM/MS8GpONVo7rc5foAGOJMgbsEi4Kc63qnpzcefEcMyIC8af8lzTn+i5x7XuuxkWHhcq\n", "5kIbkh3iRDfmR3MTcLq5HbtOXtR9XzKeAkukNRYJN8X5VlXfXPiZjXg5fTz++8h5fHvxqq77tUl4\n", "CiyPCxVzoQ0WCfI4Y8P88W9z4rE2pxpXdexPcCRB3oBFwk1xvlU1UC6WTopAanQQ/vPLM7r1J6wS\n", "LvDH40LFXGhDskOcSDs/vn0svm1sw55Tgy8aOVI9F9NxJEGejUXCTXG+VeUoF/5mI15JT8KHX9Wi\n", "qrFN8/3KeAosjwsVc6ENFgnyaInhAXj6tjiszalGW5e2/Qmu3UTegEXCTXG+VeUsF3dPHo3JkYF4\n", "59BZTfcrY+Oax4WKudAGiwR5hWdvT8BJSyuyTml3/YSMF9MRaY2HuJvifKtqKLkI8DHhlSXj8V+H\n", "z6GmSZv+hFXh2k0yYy60wSJBXmN8RAD+5dY4vJpTjfbuG7+XOnsS5A1YJNwU51tVw8lFxpTRmBAR\n", "gD8fOnPD+7WxJyE15kIbLBLkVQwGA346fyzK6luxt+LGrp9gT4K8AQ9xN8X5VtVwcxHoa8LL6Ul4\n", "7/A5nG5uH/F+ZZxu4nGhYi60wSJBXmni6EA8OTsWa7Or0DHC/oSMp8ASaY1Fwk1xvlU10lz809TR\n", "GBfuj3f/MbLrJ2QcSfC4UDEX2mCRIK9lMBjwswXjUFzbgtxvm4b9eqsCmOSqEUSaY5FwU5xvVd1I\n", "LoJ8TXglPQnr8s/i3KXh9SdkHEnwuFAxF9pgkSCvlzwmEE/MisGrOdXoHEZ/gj0J8gYsEm6K860q\n", "LXKx7KYxiAvxw38VnBvya2QcSfC4UDEX2mCRIEJPf+IXd4zDV2cu40CV8/6EoiiwKYBkNYJIcywS\n", "borzrSqtchHka8LL6ePxzpdncf5yx6Db9hYIg2TTTTwuVMyFNlgkiPqYHBmI782Ixqs5Vei0Ou5P\n", "yDjVRKQHFgk3xflWlda5WJ4aicggX/yloNbhNrI2rXlcqJgLbbBIEF3DYDDguYXjkF9zCXnVzQNu\n", "w5EEeQsWCTfF+VaVHrkY5WfGS+lJ+FPeGdRdub4/IeuFdDwuVMyFNlgkiBy4KSoIq6ZHY21ONbqu\n", "6U9wJEHegkXCTXG+VaVnLh6ZFonwADM+/Kp/f4I9CfkxF9pgkSAahMFgwPMLE3Gwuhn5NZfsz3Mk\n", "Qd6CRcJNcb5VpXcuQvzN+PWdSXj74GlYWjoByHvDIR4XKuZCGxIe5kTySY0Oxoq0KLyWU41umwKr\n", "osAo4XQTkdZ0KRJ1dXX4+OOPsWHDBpw/f37Qbbdv344tW7Zgy5YtKCkp0SMcj8T5VpWrcrHi5igE\n", "+Zrw30dqpZ1u4nGhYi60YdbjTQsKCrBmzRoAwJYtW7B8+XKH2/r7++Ouu+7SIwwiTRkNBrywOBE/\n", "2lyOIF+TlI1rIq3pUiQCAwPtX/v6+g66rdVqxeeffw5FUTB+/HjMmjVLj5A8DudbVa7MReh3/Ylf\n", "7foGSRH+LtvvUPG4UDEX2tClSCiKYv/ax8dn0G0zMjLsX+/evVuPcIg0lRYTjMdnxaDw7BXRoRDp\n", "TpeehNVqtX89nFUynRUUUnG+VSUiF6unR+P/3DPB5ft1hseFirnQhi4jiba2NgA9I4rerwGgtLQU\n", "RqMRKSkp9udqamqQmJgIAGhvH/z2kWFhYSgqKtIhYvcTGBjIXHyHuVAxFyrmQhUWFjbi1+pSJObM\n", "mYP169dDURQsXbrU/nx+fj4MBsN1RaKgoAAAMGPGjEHfd/bs2XqES0REDhiUvg0EIiKiPngxHRER\n", "OcQiQUREDrFIEBF5AJvN1u/MUq3o0rjWWl1dHbKzs2EymbBo0SLExsaKDsnlysrKcPLkSdhsNsyd\n", "OxcJCQlem5e2tjb88Y9/xJNPPom4uDgA3nuMVFZWorCwEH5+fsjIyEBjY6NX5qGqqgqFhYWw2WyY\n", "N28exo4d61XHxJ49e1BZWYnly5c7/Tcx7LwobmDr1q32rzdv3iwwEnH2799v/3rnzp2KonhvXnbv\n", "3q0UFhYq586dsz/njbloampS8vLy+j3njXlQFEXZtWuX/Wtv/fdRVlY2pH8Tw82LW0w3DWeZD0+1\n", "cOHC657zxrw0NTUhMDAQ/v79l8TwxlwUFxcjKCgIn3/+OU6dOgXAO/MA9FzA2zvdonx3wqa35qKX\n", "o59/uHlxiyKhDGOZD0/397//HbfddhsA78xLXl7egGvyeGMuLBYLmpub8fDDD6OiogI2m80r8wAA\n", "06ZNw5tvvom33noLM2fOBOCdx0Rfjn7+4ebFLXoSI13mw9Ps378fkyZNwpgxYwB4Z17q6+uxbds2\n", "WCwWJCUl2edfvTEXgDrCjI+PR2Njo9fm4ejRo3jxxRdhs9mwY8cOPPDAA16bi16Ofv7h5sUtioSj\n", "ZT68ycGDBxEdHY2kpCT7c96Yl6eeegoAcPz48X5LDXhjLiZPnozKykokJyejqakJqampXpkHQJ02\n", "MRqN9k/H3pqLXo5+/uHmxS2uuK6trcX+/fvty3xERUWJDsmlLBYLPvzwQ0ydOhUAcOXKFTzxxBNe\n", "m5fGxkZs3LgRSUlJuPvuuwF47zGyceNGmEwmREZGYsGCBV6bh/Lychw/fhwAkJqaiilTpnhVLvbu\n", "3YvKykr4+/sjKSkJCxcudPjzDzcvblEkiIhIDLdoXBMRkRgsEkRE5BCLBBEROcQiQUREDrFIEBGR\n", "QywSRETkEIsEAQAaGhqwbt26Ab+3Y8eOQV+7bt06NDQ06BHWiBQWFmLjxo3YsWMHsrKyXLrvL774\n", "Aps2ber33GC57erqwieffIJt27Zh586dqKmp6ff9G81tYWEh3nvvvRG/XrQvv/wSTU1NosPwam5x\n", "xTXpLzw8HCtXrhzwe86uyly5ciXCw8P1CGtEKisrHf4servnnnvw+eef93tusNx+++23SEtLQ1pa\n", "2oDfv9Hczp49+7rC4066urrQ3d0tOgyvxiLhJo4cOYIDBw4gJiYGgYGB6OrqQlhYGO666y4AQHt7\n", "O3bs2AEfHx9YrVaMGjXK/j0A2Lx5MxRFgY+PD+rr67F48WIkJycDAEpLS/HNN9/g0qVLePLJJ+2v\n", "6e7uxu7du1FeXo4tW7YAACZNmoTU1FQAQGdnJ/bs2YNvvvkGTzzxBCIjI/vFnJWVhZaWFphMJnR1\n", "dWHZsmXw8/NDVVUVNmzYgLFjxyI4OBgdHR249957ERIS4jQPg/2cvfH0jXfevHmIjo4e9D137tyJ\n", "r776CmlpaWhqaoKfnx86Ojrw4IMPIjIyctB9dnd3Y/PmzTAajVAU5bq1+R3ltvd7hw4dAtBTLMLD\n", "w7Fo0SKnue3u7sa2bdtgNBphMBhgMBhw//33w2jsmRjYu3cvGhsbYTabYTKZYLPZnOYV6FnTZ9eu\n", "XfYF4FpbWzFu3DjMnz8fNpsNmzZtgtlshqIoCA4Otl/tDvTcz6CqqgozZ87E6dOnAQAZGRkICQlB\n", "aWkpTpw4AR8fH7S0tCAjI6Pf+mOO9nn8+HEUFRXh3LlzCAoKgtFoxH333QezuefP1oEDB2CxWODr\n", "64v29nb7/oCefy+7d+/GE088gUOHDsHX1xfTp0/HpEmThpQL6mOoa5WTeK+//rrS0NBgf3z48GGl\n", "rKxMURRFyczMVFpaWuzfO3XqlJKfn68oiqJYrVblgw8+ULq6uhRFUZSLFy8qly9fvu79P/vsswH3\n", "6+j5Xrm5uYrFYun33JdffqmcPHnS/vjKlSvKpk2b7I//8pe/2ONpa2vrt8b9YAb7OYca77UsFouS\n", "lZWlKIqifPzxx/bncnJynO5z+/bt1/1OMjMzr9uHo5jKysrsv8OBDJTbrVu3KnV1dfbH9fX1yt69\n", "e+3v1zcfDQ0NyhtvvOHw/fvavXu3cvHiRfvjCxcuKCdOnBhw208//fS6595++23l2LFjg+6js7Oz\n", "3z0MnO0zNze3X357lZWVKQcPHuz3vtfm/bPPPlP27NkzaDzkHEcSbiQ+Pt7+CQwAZsyYgS+++AIp\n", "KSlQFAVBQUH2702aNAklJSUAehY9W7ZsGfbt24fu7m5cvXq136dAPZw7dw633367/XFwcHC/74eE\n", "hNg/Efr7+w95SmGwn/NG9C4K13ufCpPJZP90O9g+W1parvud9H6S1ovFYkF+fv6A8VdUVOCee+6x\n", "Pz9mzBgkJCQM6X1bWloQERFhfzx69GiMHj0aANDR0YGsrCxYrVYYjUZ8++23170+Pj5+wGmz8vJy\n", "lJaWwsfHB0ajsd8qpIPts5cywMpBlZWVaG9vt48YgZ5RyLX65oJGhkXCjZw7dw4XLlyw/1EqLi7G\n", "lClTAPQUgpaWFvsf41OnTtmX0T579iz8/f2xdOlSAEBzczMOHDiA++67T7dYExIScOrUKUyePBlA\n", "zx8DLQz0c97obSkH+iPkbJ+9uQ0KCur3OykqKnL6ftfue7jLWE+YMAHTpk3rtzBbb5GdNGkSiouL\n", "MXfuXAA9TfMzZ84M6X39/f3R2Nho/6Nts9nsq8zu2rULS5YssU/nDPQHeSDt7e04evQoVq1aBaBn\n", "Gq3viRCD7RMAzGbzgPdtnjZtGurq6uw/Z98ckLa4wJ8b2bBhA8xms/2PyujRo7F48WIA6ly92WyG\n", "zWZDUFCQ/VNUUVERjh8/juDgYBgMBrS2tuL+++9HSEiIfe7bZrOhpKQEaWlpCAsLs78v0DP329jY\n", "CKPRiO7ubtx+++2IiYmxz7dXVlYiOjoaQUFBmDt3LmJiYgCoPQmj0Yiuri488MAD8PPzQ2lpKTZv\n", "3oxHHnkEKSkpOHLkCLKysvDss89i1KhRg+ZgsJ/z8uXLyM3NxbFjx5CWlgaDwYAlS5ZcN4q51q5d\n", "u/DNN9/gmWeewYYNGzBr1izExMTgo48+wrPPPovu7m6H++zu7sbGjRvtn5KDg4Px1VdfYc2aNYiN\n", "jR00twUFBSguLgYAREVFISEhAbfccgsADCm37e3tAHo+5cfHx9tHbn//+9/R1NQEf39/tLe3w2Kx\n", "YO7cufb3dqS7uxtbt2619zGsVivuuOMOxMTEoKysDMePH4ePjw+6u7tRUVGBmTNnIiMjY8C8p6en\n", "23+XGzZsgL+/PxRFgaIoOHHiBNasWYOkpKRB9wn0rHi8fft2++8wODgY6enpAHqO69OnT/cbnTz0\n", "0EP232lhYaF9ZDN9+nSMHz9+0J+fBsYi4UYyMzOFnbVDRN6J10m4iSNHjqC8vBxbt27F5cuXRYdD\n", "RF6CIwkiInKIIwkiInKIRYKIiBxikSAiIodYJIiIyCEWCSIicohFgoiIHPr/DSffI6roES0AAAAA\n", "SUVORK5CYII=\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n = 100\n", "step = 1\n", "s1 = u'a'*n\n", "r = lambda x : ratio(x, s1)\n", "\n", "def modified(i):\n", " \"\"\" return the string s1, where the i-th is replaced by -\"\"\"\n", " return s1[:i-1]+u'-'+s1[i+1:]\n", "\n", "xx = range(1, n, step)\n", "\n", "\n", "print(s1[:10]),'...'\n", "for i in range(10):\n", " print(modified(i)[:10]),'...'\n", "print('..............')\n", "distance = map( r, [modified(i) for i in xx])\n", "\n", "plt.plot(xx, distance)\n", "plt.ylabel('similarity')\n", "plt.xlabel('position of modified caracter')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "WWWHHHHAAAAAT ???" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Hum..let's look with some other string, basically same as before, but with repeating sequence `ababab..`, `abcabcabcabc...`" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import string" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": [ "iVBORw0KGgoAAAANSUhEUgAAA7QAAAHuCAYAAACvTUAWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n", "AAALEgAACxIB0t1+/AAAIABJREFUeJzt3X1wleWd//FPnmN4FJGQYDEqD/54UsBFa12xQGPaQUul\n", "IQhE11nUVSodpet2sNuZZWq7q9iuyxbXJe3++ttpISoPPhRialToKVQQoggpVUrBVg3BBirYBEjO\n", "/fuDySkBkpMr5D4nV77v10ynuU/uO+cib6J+zzlXTkoQBIEAAAAAAPBMarIXAAAAAABAZzDQAgAA\n", "AAC8xEALAAAAAPASAy0AAAAAwEsMtAAAAAAAL4U20EajUTU3N4f15QEAAAAAxqWH8UUrKiq0b98+\n", "zZgxQ/n5+e2eW1tbq6qqKqWlpWny5MnKy8sLY0kAAAAAgB4mJaz3oa2pqVH//v3jDrQvvPCCbr31\n", "VknSunXrNGPGjDCWAwAAAADoYZK+hzYnJyf2cWZmZhJXAgAAAADwSdIH2tOfIM7IyEjiSgAAAAAA\n", "PgllD62L039xVEpKSrvnVlZWKi0tLewlAQAAAACSoH///po4cWKHz0/oQLtr1y6lpqZq1KhRsdsa\n", "GhoknXqmtuXjtqSlpWnChAmhrhEAAAAAkBw7duxwOj+Ulxy/8sorikQieuWVV7Rp06bY7Vu2bNHm\n", "zZtbnXvttddq5cqVWrlypa699towloMeIhKJJHsJSBLa20Z/u2hvG/3toj1chPIM7bRp0855+913\n", "333Wbfn5+br99tvDWAYAAAAAoAcL7W17wlBVVcVLjgEAAACgh9qxY4emTp3a4fOT/luOAQAAAADo\n", "DAZaeIP9FHbR3jb620V72+hvF+3hgoEWAAAAAOAl9tACAAAAALoF9tACAAAAAExgoIU32E9hF+1t\n", "o79dtLeN/nbRHi4YaAEAAAAAXmIPLQAAAACgW2APLQAAAADABAZaeIP9FHbR3jb620V72+hvF+3h\n", "goEWAAAAAOAl9tACAAAAALoF9tACAAAAAExgoIU32E9hF+1to79dtLeN/nbRHi4YaAEAAAAAXmIP\n", "LQAAAACgW3DdQ5se4lq6hVHLn072EgAACdY3K0u//vu/6/D5k578oY5l9Ph/JQIAukDN/fcmewk4\n", "TY//t3dn/sIVllWrcv74Dp9fMfh6FdVudr6f7mr2YxO16uHtyV7GWSKRiG644YZkLyNpDsy6T5c+\n", "81Syl5EU1ttb15n+rg9mHstI5z9QuiF+9m2jv120hwv20AIAAAAAvMRAC2/wSJ1dtLeN/nbR3jb6\n", "20V7uGCgBQAAAAB4iYEW3uA9yeyivW30t4v2ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9bfS3i/a2\n", "0d8u2sMFAy0AAAAAwEsMtPAG+ynsor1t9LeL9rbR3y7awwUDLQAAAADASwy08Ab7KeyivW30t4v2\n", "ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9bfS3i/a20d8u2sMFAy0AAAAAwEvpyV5Ad9QnK02FZdUd\n", "Pv+hENeCv2I/hV20t43+dtHeNvrbRXu4YKA9h9Wl45zOr/hWSAsBAAAAALSJlxzDG+ynsIv2ttHf\n", "LtrbRn+7aA8XDLQAAAAAAC8x0MIb7Kewi/a20d8u2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR\n", "3y7a20Z/u2gPFwy0AAAAAAAvMdDCG+ynsIv2ttHfLtrbRn+7aA8XDLQAAAAAAC8x0MIb7Kewi/a2\n", "0d8u2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR3y7a20Z/u2gPFwy0AAAAAAAvpSd7AT1BU1a2\n", "KgZfn+xldJ2Hkr2Ac4tEIjxiZxTtbaO/XbS3jf520R4uGGi7wPQDrzpfU1hWrcr5452uWbq4Qt/4\n", "bpHzfbn6v49NDP0+AAAAAOB88ZJjeINH6uyivW30t4v2ttHfLtrDBQMtAAAAAMBLDLTwBu9JZhft\n", "baO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9hF+1to79dtLeN/nbRHi4YaAEAAAAAXmKghTfYT2EX\n", "7W2jv120t43+dtEeLhhoAQAAAABeYqCFN9hPYRftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9h\n", "F+1to79dtLeN/nbRHi4YaAEAAAAAXkpP9gKs6pOVpsKyaqdrCkNaiy/YT2EX7W2jv120t43+dtEe\n", "Lhhok2R16Tjna5YurghhJQAAAADgJ15yDG+wn8Iu2ttGf7tobxv97aI9XDDQAgAAAAC8xEALb7Cf\n", "wi7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtvsJ/CLtrbRn+7aG8b/e2iPVww0AIAAAAAvMRAC2+w\n", "n8Iu2ttGf7tobxv97aI9XDDQAgAAAAC8xEALb7Cfwi7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtv\n", "sJ/CLtrbRn+7aG8b/e2iPVww0AIAAAAAvJSe7AWg45pSU7R0cUX4d9Q//LvojEgkwiN2RtHeNvrb\n", "RXvb6G8X7eGCgdYj3/zOzc7XFJZVq3L+eKdrZj/2iPP9AAAAAECi8ZJjeINH6uyivW30t4v2ttHf\n", "LtrDBQMtAAAAAMBLDLTwBu9JZhftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9hF+1to79dtLeN\n", "/nbRHi5C+S3HtbW1qqqqUlpamiZPnqy8vLw2z62rq9Orr76qCy64QGPHjtXll18expIAAAAAAD1M\n", "KM/Qbt26VXPnztXs2bP1xhtvtHtudXW1Zs+erS9/+cv68MMPw1gOegj2U9hFe9vobxftbaO/XbSH\n", "i1AG2pycnNjHmZmZ7Z6blZWlhoYGNTc366233tKJEyfCWBIAAAAAoIcJ5SXHQRDEPs7IyGj33Btu\n", "uEEVFRU6ceKERowYoU8//TTuEAyb2E9hF+1to79dtLeN/nbRHi5CGWibm5tjH6ekpLS/gPR0TZ8+\n", "XZK0bt069erVK4wlAQAAAAB6mFBectzQ0CDp1DO1LR9L0q5du1RTU3POa44cOaJjx47FfXb29NfU\n", "RyIRjuMcn647rOd8jp966qlutZ5EH7fc1l3Wk8jjlo+7y3o47v79W24L63yOE3N85t+BZK+H48Qe\n", "09/u8VNPPdWt1sNxYo9dpQSnvz64i3z44YfauHGjgiDQtGnTNGjQIEnSihUrlJKSovnz58fOfeed\n", "d7Rnzx4FQaAZM2a0O9BWVVVpwoQJXb3cHq2wrFqV88c7XTP7sYla9fD2kFbUeZFIxPRLUA7Muk+X\n", "PvNU/BN7IOvtretM/1HLn1bN/feGdj4Sg5992+hvF+1t27Fjh6ZOndrh89PDWER+fr5uv/32s26/\n", "++67z7pt7NixGjt2bBjLgKQ+WWkqLKt2umZASGs5X/yDzS7a20Z/u2hvG/3toj1chDLQovtYXTrO\n", "+ZrZj4WwEAAAAADoYqHsoQXC0JnX1KNnoL1t9LeL9rbR3y7awwUDLQAAAADASwy08Ab7KeyivW30\n", "t4v2ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9bfS3i/a20d8u2sMFAy0AAAAAwEsMtPAG+ynsor1t\n", "9LeL9rbR3y7awwUDLQAAAADASwy08Ab7KeyivW30t4v2ttHfLtrDBQMtAAAAAMBLDLTwBvsp7KK9\n", "bfS3i/a20d8u2sMFAy0AAAAAwEvpyV4Aup/MxhTNfmxispeBM/ybJiV7CUkTiUR4tNYw+ttFe9vo\n", "bxft4YKBFmf5f99+0+n8wrJqVc4f73TN0sUV+sZ3i5yu6cw/3CoGX6+i2s1O13RXB2bdl+wlAAAA\n", "AN0KLzmGN3ikzi7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtv8J5kdtHeNvrbRXvb6G8X7eGCgRYA\n", "AAAA4CUGWniD/RR20d42+ttFe9vobxft4YKBFgAAAADgJQZaeIP9FHbR3jb620V72+hvF+3hgoEW\n", "AAAAAOAlBlp4g/0UdtHeNvrbRXvb6G8X7eGCgRYAAAAA4CUGWniD/RR20d42+ttFe9vobxft4YKB\n", "FgAAAADgpfRkLwD+65OVpsKyaqdrCjtxP+ynsIv2ttHfLtrbRn+7aA8XDLQ4b6tLxzlfs3RxRQgr\n", "AQAAAGAJLzmGN9hPYRftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU32E9hF+1to79dtLeN/nbRHi4Y\n", "aAEAAAAAXmKghTfYT2EX7W2jv120t43+dtEeLhhoAQAAAABeYqCFN9hPYRftbaO/XbS3jf520R4u\n", "GGgBAAAAAF5ioIU32E9hF+1to79dtLeN/nbRHi4YaAEAAAAAXmKghTfYT2EX7W2jv120t43+dtEe\n", "LhhoAQAAAABeSk/2AmBTU2qKli6uCP1+xoR+D0iESCTCo7WG0d8u2ttGf7toDxcMtEiKb37nZudr\n", "CsuqVTl/vNM1FT9e4nw/AAAAAPzAS44BdHs8Smsb/e2ivW30t4v2cMFACwAAAADwEgMtgG6P96Oz\n", "jf520d42+ttFe7hgoAUAAAAAeImBFkC3x14a2+hvF+1to79dtIcLBloAAAAAgJcYaAF0e+ylsY3+\n", "dtHeNvrbRXu4YKAFAAAAAHiJgRZAt8deGtvobxftbaO/XbSHCwZaAAAAAICXGGgBdHvspbGN/nbR\n", "3jb620V7uGCgBQAAAAB4KT3ZCwA6qk9WmgrLqp2ueSiktSCx2EtjG/3tor1t9LeL9nDBQAtvrC4d\n", "53xNxbdCWAgAAACAboGXHMMb7Kewi/a20d8u2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR3y7a\n", "20Z/u2gPFwy0AAAAAAAvMdDCG+ynsIv2ttHfLtrbRn+7aA8XDLQAAAAAAC8x0MIb7Kewi/a20d8u\n", "2ttGf7toDxcMtAAAAAAALzHQwhvsp7CL9rbR3y7a20Z/u2gPFwy0AAAAAAAvMdDCG+ynsIv2ttHf\n", "LtrbRn+7aA8XDLQAAAAAAC+lJ3sBQEdFIhHnR+yasrJVMfj6kFaUWP/nxquSvYSk6Ux79Bz0t4v2\n", "ttHfLtrDBQMterTpB151Or+wrFqV88c7XbN0cYW+8d0ip2s648Cs+0K/DwAAAMAnvOQY3uCROrto\n", "bxv97aK9bfS3i/ZwwUALAAAAAPASAy28wXuS2UV72+hvF+1to79dtIcLBloAAAAAgJcYaOEN9lPY\n", "RXvb6G8X7W2jv120hwsGWgAAAACAlxho4Q32U9hFe9vobxftbaO/XbSHCwZaAAAAAICXGGjhDfZT\n", "2EV72+hvF+1to79dtIcLBloAAAAAgJcYaOEN9lPYRXvb6G8X7W2jv120h4v0ML5obW2tqqqqlJaW\n", "psmTJysvL6/Nc3//+99r+/btikaj+uxnP6vPfOYzYSwJAAAAANDDhDLQbt26VXPnzpUkrVu3TjNm\n", "zGjz3D179uirX/2qJGn9+vUMtGhTIvZT9MlKU2FZtdM1hSGtBX/FXhrb6G8X7W2jv120h4tQBtqc\n", "nJzYx5mZme2e29zcrGg0qiAIFARBGMsBOmx16Tjna5YurghhJQAAAADiCWUP7emDaUZGRrvnjhkz\n", "Ro8//riWLl2q8ePHh7Ec9BDsp7CL9rbR3y7a20Z/u2gPF6EMtM3NzbGPU1JS2j337bff1j/90z/p\n", "H//xH/Xmm2/G/dqn/wWPRCIcGzp+5513utV6En3cclt3WQ/HHHfn45bbwjqfY4455pjj8I7feeed\n", "brUejhN77ColCOF1vmvXrtVXvvIVBUGgl156SbfccoskadeuXUpNTdWoUaNi527YsEFf/OIXz/r4\n", "XKqqqjRhwoSuXi5wXpYurtA3vlsU+v0cmHWfLn3mqdDvB+gJRi1/WjX33xva+QAAIBw7duzQ1KlT\n", "O3x+ehiLuPbaa7Vy5UoFQaBp06bFbt+yZYtSUlJaDbSXXXaZ1qxZI0kaPXp0GMsBAAAAAPRAoQy0\n", "+fn5uv3228+6/e677z7rtiuvvFJXXnllGMtADxOJRPitd0bR3jb620V72+hvF+3hIpQ9tAAAAAAA\n", "hI2BFt7gkTq7aG8b/e2ivW30t4v2cMFACwAAAADwEgMtvNGZX+ONnoH2ttHfLtrbRn+7aA8XDLQA\n", "AAAAAC8x0MIb7Kewi/a20d8u2ttGf7toDxdxB9oTJ04kYh0AAAAAADiJ+z60S5cu1d///d8rNzc3\n", "EesB2tRd35OsKTVFSxdXhH4/xaHfQ/fVXdsjMehvF+1to79dtIeLuAPtddddp927d2vTpk36/Oc/\n", "r4EDByZiXYA3vvmdm52vKSyrVuX88U7XHJj1vPP9AAAAAD1Z3IF2ypQpkqSTJ0/qtdde08cff6yi\n", "oiJ99NFHGj16dOgLBFrwSJ1dtLeN/nbR3jb620V7uIi7h7apqUmS9Mc//lH19fUaOXKktm7dquee\n", "ey70xQEAAAAA0Ja4A+2PfvQjrVy5UrW1tZo9e7YmTpyooqIiXXXVVYlYHxDDe5LZRXvb6G8X7W2j\n", "v120h4u4Lznu16+fZs2apdTU1rPvgAEDQlsUAAAAAADxxB1oZ8+efc7bb7zxxi5fDNAe9lPYRXvb\n", "6G8X7W2jv120h4u4Lzk+U21tbRjrAAAAAADASdyBdvfu3a2ON2/eHNpigPawn8Iu2ttGf7tobxv9\n", "7aI9XMQdaN97771Wx+npcV+lDAAAAABA6JxfchyNRsNYBxAX+ynsor1t9LeL9rbR3y7aw0WbT7e+\n", "9NJLamho0J49e3Ty5MnY7bm5uQlZGAAAAAAA7WnzGdrp06eruLhYV199tYqLi2P/47cbI1nYT2EX\n", "7W2jv120t43+dtEeLuK+5PiLX/xiItYBAAAAAICTuL/hiV8Che6iJ+2n6JOVpsKyaqdrVoS0Fh/0\n", "pPZwR3+7aG8b/e2iPVw4T6uvv/66brrpphCWAtixunSc8zUHKkNYCAAAAOAx599yfOTIkTDWAcTF\n", "fgq7aG8b/e2ivW30t4v2cNHmM7TLly9XcXGx1q9fr5ycnNjte/bs0YwZMxKyOAAAAAAA2tLmQFtc\n", "XKwLL7xQ/fr1azXArlu3LiELA87Efgq7aG8b/e2ivW30t4v2cNHmQHvxxRdLkoYNG9bq9tRU51cp\n", "AwAAAADQ5eJOp2PGjGl1XFRUFNpigPawn8Iu2ttGf7tobxv97aI9XDg/3ZqZmRnGOgAAAAAAcBJ3\n", "oF27dm0i1gHExX4Ku2hvG/3tor1t9LeL9nARd6CNRqOtjjds2BDaYgAAAAAA6Ki4A21mZqbq6upi\n", "x8ePHw91QUBb2E9hF+1to79dtLeN/nbRHi7a/C3HLT799FP94Ac/0IQJEyTxPrQAAAAAgO4h7kB7\n", "wQUX6Hvf+17smPehRbKwn8Iu2ttGf7tobxv97aI9XMR9yfHUqVNbHY8bNy60xQAAAAAA0FFxn6Ht\n", "3bt3q+PLL788tMUA7YlEIqYfsftLWpMOzLov2csA/HDT1cleAbqA9X/uW0d/u2gPF3EH2jNt375d\n", "EydODGMtANrxf1aucDq/sKxalfPHO12zdHGFvvHdIqdrOqNi8PUqqt3c4fO787/YZj82Uase3p7s\n", "ZfRoneq//OlwFgMAALqVuAPtzp07tWfPHh05ckR9+/bV/v37GWiRFN11oEH4aG8b/e2ivW30t4v2\n", "cBF3D+2ePXs0a9Ys5eXlafbs2briiisSsS4AAAAAANrVofehlaTm5mZJUkZGRrgrAtrAe5LZRXvb\n", "6G8X7W2jv120h4u4A+2JEyckSdFoVM3NzQqCIPRFAQAAAAAQT9yB9qabbpJ06rXsK1euVN++fcNe\n", "E3BO7Kewi/a20d8u2ttGf7toDxdxfynUoEGDYv8/b9680BcEAAAAAEBHxH2G9kwtL0EGEo39FHbR\n", "3jb620V72+hvF+3hwnmgraioCGMdAAAAAAA4cR5oo9FoGOsA4mI/hV20t43+dtHeNvrbRXu4aHMP\n", "7RNPPKGhQ4eedfuePXs0Y8aMUBcFAAAAAEA8bT5De8UVV6i4uPis/40dOzaR6wNi2E9hF+1to79d\n", "tLeN/nbRHi7aHGg/+9nPnvP2/v37h7YYAAAAAAA6qs2XHOfm5p7z9pb3pQUSjf0UbvpkpamwrNrp\n", "msKQ1nK+aG8b/e2ivW30t4v2cBH3fWgB+Gl16Tjna5Yu5reYAwAAwB/Ov+X49ddfD2EZQHzsp7CL\n", "9rbR3y7a20Z/u2gPF84D7ZEjR8JYBwAAAAAATtp8yfHy5ctVXFys9evXKycnJ3Y7b9uDZGE/hV20\n", "t43+dtHeNvrbRXu4aHOgLS4u1oUXXqh+/fq1GmDXrVuXkIUBAAAAANCeNl9yfPHFFys9PV3Dhg1r\n", "fUGq86uUgS7Bfgq7aG8b/e2ivW30t4v2cBF3Oh0zZkyr46KiotAWAwAAAABARzk/3free++FsQ4g\n", "LvZT2EV72+hvF+1to79dtIeLuO9D+8ILL6ixsVEpKSmSpIaGBo0ePTr0hQEAAAAA0J64z9A2NjZq\n", "1qxZKi4uVnFxsebMmZOIdQFnYT+FXbS3jf520d42+ttFe7iI+wztiRMnVFlZqczMTEnS22+/ra9/\n", "/euhLwwAAAAAgPZ0aKC9+uqrlZ5+6tRx48aFvijgXNhPYRftbaO/XbS3jf520R4u4r7kODU1VYMG\n", "DdKAAQM0YMAAHTx4MBHrAgAAAACgXXGfoT1w4IBWrlwZe4Z2z549+ud//ufQFwacKRKJ8IhdyJpS\n", "U7R0cUXo9zMm/imt0N42+ttFe9vobxft4SLuQHvvvfdq8ODBsWOeoQV6rm9+52bnawrLqlU5f7zT\n", "NRU/XuJ8PwAAAMCZ4r7k+PRhVpKCIAhtMUB7eKTOLtrbRn+7aG8b/e2iPVzEHWjP9Otf/zqMdQAA\n", "AAAA4KTNgfbQoUNqamrSoUOHWv3v008/TeT6gBjek8wu2ttGf7tobxv97aI9XLS5h/bZZ59VcXGx\n", "/vd//1cTJkyI3c4eWgAAAABAd9DmQHv//fdLkoYNG6abbropdvuRI0dCXxRwLuynsIv2ttHfLtrb\n", "Rn+7aA8XcffQFhUVtToeNmxYaIsBAAAAAKCj4g60mZmZrY7HjHF9B0mga7Cfwi7a20Z/u2hvG/3t\n", "oj1cxH0f2v/5n//RlClTdPDgQe3du1dDhw7lZQAAAAAAgKSL+wztwIEDdemll6qurk5z5sxRXV1d\n", "ItYFnIUHUuyivW30t4v2ttHfLtrDRdyBNhqNSpLS0089mZua6vzWtQAAAAAAdLm40+mxY8f0/vvv\n", "66KLLpIkpaSkhL4o4FzYT2EX7W2jv120t43+dtEeLuIOtJ/73Oe0a9cu/c3f/I2qq6v10UcfJWJd\n", "AAAAAAC0K+4vhSooKFBBQYEkafz48Ro/fnzYawLOif0UdtHeNvrbRXvb6G8X7eEi7kALAO3pk5Wm\n", "wrJqp2seCmktAAAAsIWBFt6IRCI8YtcNrS4d53xNxbfczqe9bfS3i/a20d8u2sMFv7IYAAAAAOCl\n", "0J6hra2tVVVVldLS0jR58mTl5eW1ee7jjz+u4cOHS5I+/vhjzZ8/P6xlwWM8UmcX7W2jv120t43+\n", "dtEeLkIbaLdu3aq5c+dKktatW6cZM2a0ee4DDzyg7OxsSVJFRUVYSwIAAAAA9CChveQ4Jycn9nFm\n", "Zma757YMs3V1dRo0aFBYS4LneE8yu2hvG/3tor1t9LeL9nAR2kAbBEHs44yMjA5dU1NTo1GjRoW1\n", "JAAAAABADxLaQNvc3Bz7OCUlpUPXNDY2xp6tbcvpj9hEIhGODR233NZd1sNx4o5vuOGGbrUejrt/\n", "/5bbwjqf48Qct+yj6y7r4Tixx/S3e3y67rAejpPXvyNSgtOfSu1Ca9eu1Ve+8hUFQaCXXnpJt9xy\n", "iyRp165dSk1NPeuZ2Gg0qldeeUWFhYVtfs2qqipNmDAhjOUCSKCKwderqHZzspfRJWY/NlGrHt6e\n", "7GXgDKOWP62a++8N7XwAABCOHTt2aOrUqR0+P7RnaK+99lqtXLlSK1eu1LXXXhu7fcuWLdq8+ez/\n", "kH3//fc1bNiwsJaDHqAzj9igZ6C9bfS3i/a20d8u2sNFelhfOD8/X7fffvtZt999993nPL+goCCs\n", "pQAAAAAAeqDQnqEFuhrvSWYX7W2jv120t43+dtEeLhhoAQAAAABeYqCFN9hPYRftbaO/XbS3jf52\n", "0R4uQttDCwBtacrKVsXg652uqQhpLeftoWQvAAAAwC4GWniD/RQ9x/QDrzqdX1hWrcr5452uWbq4\n", "Qt/4bpHTNZ3xfx+bGPp9WMfPvl20t43+dtEeLnjJMQAAAADASwy08Ab7KQCb+Nm3i/a20d8u2sMF\n", "Ay0AAAAAwEsMtPAG+ykAm/jZt4v2ttHfLtrDBQMtAAAAAMBLDLTwBvspAJv42beL9rbR3y7awwUD\n", "LQAAAADASwy08Ab7KQCb+Nm3i/a20d8u2sMFAy0AAAAAwEsMtPAG+ykAm/jZt4v2ttHfLtrDBQMt\n", "AAAAAMBLDLTwBvspAJv42beL9rbR3y7aw0V6shcAAPH0yUpTYVm10zWFIa0FAAAA3QcDLbwRiUR4\n", "xM6oBy/7xLn90sUVIa0GicbPvl20t43+dtEeLnjJMQAAAADASwy08AaP1NlFe9vobxftbaO/XbSH\n", "CwZaAAAAAICXGGjhDd6TzC7a20Z/u2hvG/3toj1cMNACAAAAALzEQAtvsJ/CLtrbRn+7aG8b/e2i\n", "PVww0AIAAAAAvMRAC2+wn8Iu2ttGf7tobxv97aI9XDDQAgAAAAC8xEALb7Cfwi7a20Z/u2hvG/3t\n", "oj1cMNACAAAAALzEQAtvsJ/CLtrbRn+7aG8b/e2iPVykJ3sBABCGptQULV1cEf4d9Q//LgAAAHBu\n", "DLTwBvsp7OpM+29+52bnawrLqlU5f7zTNbMfe8T5fuCGn327aG8b/e2iPVzwkmMAAAAAgJcYaOEN\n", "9lPYRXvb6G8X7W2jv120hwsGWgAAAACAlxho4Q32U9hFe9vobxftbaO/XbSHCwZaAAAAAICXGGjh\n", "DfZT2EV72+hvF+1to79dtIcLBloAAAAAgJcYaOEN9lPYRXvb6G8X7W2jv120hwsGWgAAAACAlxho\n", "4Q32U9hUrSaqAAAgAElEQVRFe9vobxftbaO/XbSHCwZaAAAAAICXGGjhDfZT2EV72+hvF+1to79d\n", "tIeL9GQvAAC6iz5ZaSosq3a6ZkBIawEAAEB8DLTwRiQS4RE7oxLVfnXpOOdrZj8WwkLQCj/7dtHe\n", "NvrbRXu44CXHAAAAAAAvMdDCGzxSZxftbaO/XbS3jf520R4uGGgBAAAAAF5ioIU3eE8yu2hvG/3t\n", "or1t9LeL9nDBQAsAAAAA8BIDLbzBfgq7aG8b/e2ivW30t4v2cMFACwAAAADwEgMtvMF+Crtobxv9\n", "7aK9bfS3i/ZwwUALAAAAAPASAy28wX4Ku2hvG/3tor1t9LeL9nDBQAsAAAAA8BIDLbzBfgq7aG8b\n", "/e2ivW30t4v2cJGe7AUAgM8yG1M0+7GJyV5Gj/efmx0v6H1PKOsAAADdCwMtvMF+Cru6c/v/9+03\n", "nc4vLKtW5fzxTtcsXVyhb3y3yOmazqgYfL2Kal0nx+5p1PKnk70EdIHu/LOP8NHfLtrDBS85BgAA\n", "AAB4iYEW3mA/hV20t43+dtHeNvrbRXu4YKAFAAAAAHiJgRbeYD+FXbS3jf520d42+ttFe7hgoAUA\n", "AAAAeImBFt5gP4VdtLeN/nbR3jb620V7uOBtewAAAAAgJEEQqK6uTs3NzcleSreRlpamQYMGKSUl\n", "5by/FgMtvMF+Crtobxv97aK9bfS3q6e1r6urU58+fZSTk5PspXQbf/nLX1RXV6fc3Nzz/lq85BgA\n", "AAAAQtLc3Mwwe4acnJwue8aagRbeYD+FXbS3jf520d42+ttFe7hgoAUAAAAAeImBFt7oafsp0HG0\n", "t43+dtHeNvrbRXs/NDY2JnsJkvilUACQUH2y0lRYVu10TWFIawEAAHaVl5dr586devTRRzt8TWNj\n", "o374wx/q8OHDGj16tG6//fYQV9gxDLTwRiQS4RE7o3pS+9Wl45yvWbq4IoSV+KMn9Ycb2ttGf7to\n", "nxglJSXav3+/0zXZ2dlatGiR/vCHP3Sbvc4MtAAAAABgWGlpqYYOHao77rhDlZWVikajrT6fn5+v\n", "4uLiJK2ufQy08AaP1NlFe9vobxftbaO/Xdbau25Fakvl/PHO1wRBoGXLlumuu+7SlClTJEkjR47s\n", "kvUkCgMtAAAAACRJZwbRrrJt2zYNHz5cM2fOlCQ1NDRoxYoVCoKg1Xl5eXmaNWtWMpYYFwMtvMF+\n", "Crtobxv97aK9bfS3i/aJM2nSJC1atEhLlizRggULlJubq4ULF8a97syBN5kYaAEAAADAmPLych09\n", "elTp6emaN2+e5syZo3vuuUclJSVtXtPY2KgVK1aovr5e+/fvV11dnW699VZddtllCVx5awy08AaP\n", "1NlFe9vobxftbaO/XbRPjJKSktjwOmLECFVVVcW9Jjs7Ww888EDYS3MSykBbW1urqqoqpaWlafLk\n", "ycrLy2v3/H379mn79u3KyspSUVGRMjMzw1gWAAAAAKAHSQ3ji27dulVz587V7Nmz9cYbb7R77pEj\n", "R/TRRx+puLhYt956K8Ms2tRd3usKiUd72+hvF+1to79dtIeLUAbanJyc2MfxBtS33npLvXr10po1\n", "a/Tuu++GsRwAAAAAQA8UykB7+m+9ysjIaPfcuro6HTlyRLfddpvee++9s97EF2jBfgq7aG8b/e2i\n", "vW30t4v2cBHKQNvc3Bz7OCUlJe75N954oyRpyJAhqq+vD2NJAAAAAIAeJpSBtqGhQdKpZ2pbPpak\n", "Xbt2qaamptW5I0aM0L59+yRJhw8fVr9+/dr92qe/pj4SiXBs6Pipp57qVuvhOHHHLR93l/X01OPT\n", "dYf1nE//M/9MXX0+x4k5PvPvQLLXw3Fij+lv9/ipp57qVus53+M///nPwrmd6/vlKiUI4V1xP/zw\n", "Q23cuFFBEGjatGkaNGiQJGnFihVKSUnR/PnzW53/3HPPKS0tTRdffHG7LzGoqqrShAkTunq58EQk\n", "wptsW2W9/b9+62WlR8N/A/MxP16iotrNod+Pq870H7X8adXcf29o5yMxrP/sW0d/u3pa+w8//FD5\n", "+fnJXka309b3ZceOHZo6dWqHv04oA21YGGgBoGMKy6pVOX+80zUVg6/vlgNtZzDQAgC6Cwbac+uq\n", "gTaUlxwDAAAAABA2Blp4ozOvqUfPQHvb6G8X7W2jv120T4zy8nI98sgjztc9++yzeuKJJ/T9739f\n", "zzzzTAgrc8NACwAAAADGlJSUqG/fvk7X7N+/X/369dOiRYv00EMPqbGxUfv37w9ngR2UntR7Bxz0\n", "pF8OADe0t43+dtHeNvrbZa390sUVXfJ1vvHdok5fW1paqqFDh+qOO+5QZWWlotFoq8/n5+eruLhY\n", "BQUFKigoiN1+4sQJZWdnd/p+uwIDLQAAAAAkyfkMoucrCAItW7ZMd911l6ZMmSJJGjlyZIeuffnl\n", "lzVw4EANHjw4zCXGxUuO4Q32U9hFe9vobxftbaO/XbRPnG3btumDDz7QlVdeKUlqaGjQf/zHf+jJ\n", "J59s9b8z98r+9Kc/VWpqqmbMmJGMZbfCM7QAAAAAYNCkSZO0aNEiLVmyRAsWLFBubq4WLlzY5vnR\n", "aFRPPvmkPve5z2nSpEkJXGnbGGjhDWv7KfBXtLeN/nbR3jb620X7xCgvL9fRo0eVnp6uefPmac6c\n", "ObrnnntUUlLS5jVPP/20Dhw4oNTUVG3ZskUfffSRvvrVr+qaa65J4MpbY6AFAAAAAGNKSkpiw+uI\n", "ESNUVVUV95r77rsv7GU5Yw8tvMF+Crtobxv97aK9bfS3i/ZwwUALAAAAAPASAy28wX4Ku2hvG/3t\n", "or1t9LeL9nDBHloA6IH6ZKWpsKza6ZqHQloLAABAWBho4Y1IJMIjdkbR3t3q0nHO11R8K4SFdAH6\n", "20V72+hvF+3hgpccAwAAAAC8xEALb/BInV20t43+dtHeNvrbRXu4YKAFAAAAAHiJgRbe4D3J7KK9\n", "bfS3i/a20d8u2idGeXm5HnnkkU5de+LECT344IP6t3/7ty5elTsGWgAAAAAwpqSkRH379u3Utf/9\n", "3/+tRYsWdfGKOoffcgxvsJ/CLtrbRn+7aG8b/e2ifeKVlpZq6NChuuOOO1RZWaloNNrq8/n5+Sou\n", "LpYk1dTUqF+/frrkkkuSsdSzMNACAAAAQJJUDL6+S75OUe1m52uCINCyZct01113acqUKZKkkSNH\n", "tnl+NBpVeXm5/uVf/qXT6+xqDLTwBu9JZhftbaO/XbS3jf52WWvfmUG0q2zbtk3Dhw/XzJkzJUkN\n", "DQ1asWKFgiBodV5eXp5mzZqld999V01NTXryySclSW+88YaOHDmi/v37J3ztLRhoAQAAAMCgSZMm\n", "adGiRVqyZIkWLFig3NxcLVy4sM3zr7zySj366KOx48bGxqQOsxK/FAoesfRIHVqjvW30t4v2ttHf\n", "LtonRnl5uY4ePar09HTNmzdPc+bMUXl5eYeura+v15NPPqmtW7fqyJEjIa+0fTxDCwAAAADGlJSU\n", "qKSkRJI0YsQIVVVVdfjaAQMG6Otf/7q+/vWvh7W8DuMZWniD9ySzi/a20d8u2ttGf7toDxc8QwsA\n", "kCQ1ZWV32W9a7GoVrhd8+84wlgEAALoZBlp4g/0UdtE+MaYfeNXp/MKyalXOH+90zdLFFfrGd4uc\n", "rumMh5Y/Hfp9IHz87NtGf7toDxe85BgAAAAA4CUGWniD/RR20d42+ttFe9vobxft4YKBFgAAAADg\n", "JQZaeIP9FHbR3jb620V72+hvF+3hgoEWAAAAAOAlBlp4g/0UdtHeNvrbRXvb6G8X7ROjvLxcjzzy\n", "iPN1Gzdu1GOPPaYf/OAH+slPfhLCytww0AIAAACAMSUlJerbt6/zdZs2bdLDDz+sBx98UBdccIF+\n", "97vfhbC6juN9aOEN9lPYRXvb6G8X7W2jv120T7zS0lINHTpUd9xxhyorKxWNRlt9Pj8/X8XFxZKk\n", "EydOKAgCpaSk6OOPP9YFF1yQjCXHMNACAAAAQJLMfmxil3ydVQ9vd74mCAItW7ZMd911l6ZMmSJJ\n", "GjlyZLvXfP7zn9esWbM0ZMgQDRw4UPn5+Z1ab1dhoIU3IpEIj9gZRXvb6G8X7W2jv13W2ndmEO0q\n", "27Zt0/DhwzVz5kxJUkNDg1asWKEgCFqdl5eXp1mzZun48ePauHGjnn32WUnSypUrtXPnTo0bNy7h\n", "a2/BQAsAAAAABk2aNEmLFi3SkiVLtGDBAuXm5mrhwoVtnt/U1KR+/frFjgsKCvSnP/0pEUttEwMt\n", "vGHpkTq0Rnvb6G8X7W2jv120T4zy8nIdPXpU6enpmjdvnubMmaN77rlHJSUlbV7Tq1cvjRgxQk88\n", "8YTS09OVlpamr33tawlc9dkYaAEAndInK02FZdVO1xSGtBYAAOCmpKQkNryOGDFCVVVVHbpu+vTp\n", "mj59ephLc8JAC29Y20+Bv6J997S61H2/zNLFFc7X0N8u2ttGf7toDxe8Dy0AAAAAwEsMtPAGj9TZ\n", "RXvb6G8X7W2jv120hwsGWgAAAACAlxho4Y1IJJLsJSBJaG8b/e2ivW30t4v2cMFACwAAAADwEgMt\n", "vMF+Crtobxv97aK9bfS3i/ZwwUALAAAAAPASAy28wX4Ku2hvG/3tor1t9LeL9n5obGxM9hIkSenJ\n", "XgAAAAAAILHKy8u1c+dOPfroox2+prGxUT/84Q91+PBhjR49WrfffvtZ5xw8eFA/+9nP1NzcrCFD\n", "hpzznK7EQAtvsJ/CLtrbRn+7aG8b/e2ifWKUlJRo//79TtdkZ2dr0aJF+sMf/nDOZ9I/+eQTrVy5\n", "UgsXLlRaWloXrbR9DLQAAAAAkCQHZt3XJV/n0mee6vS1paWlGjp0qO644w5VVlYqGo22+nx+fr6K\n", "i4vjfp3y8nLdeOONWrp0qS644ALNnz9fOTk5nV5XRzDQwhuRSIRH7IyivW30t4v2ttHfLmvtz2cQ\n", "PV9BEGjZsmW66667NGXKFEnSyJEjO/31PvjgA3300Uf69re/rT//+c/6r//6Lz300ENdtdxzYqAF\n", "ACRMU2qKli6ucL7u1+sdr7nE+S4AADBn27ZtGj58uGbOnClJamho0IoVKxQEQavz8vLyNGvWrLhf\n", "LzMzU3/3d38nSerXr1+Xr/dcGGjhDUuP1KE12vcc3/zOzc7XFJZVq3L+eKdrfrz8aef7QffDz75t\n", "9LeL9okzadIkLVq0SEuWLNGCBQuUm5urhQsXxr3uzIG3RWFhoV577TXNnTtXQRCoqampq5d8FgZa\n", "AAAAADCmvLxcR48eVXp6uubNm6c5c+bonnvuUUlJSZvXNDY2asWKFaqvr9f+/ftVV1enW2+9VZdd\n", "dpkk6ZprrtGbb76pxx9/XI2NjZo3b17ofw4GWnjD2n4K/BXtAZv42beN/nbRPjFKSkpiw+uIESNU\n", "VVUV95rs7Gw98MAD7Z7zD//wD12yvo5KTei9AQAAAADQRRho4Q0eqbOL9oBN/OzbRn+7aA8XDLQA\n", "AAAAAC8x0MIbkUgk2UtAktAesImffdvobxft4YKBFgAAAADgJQZaeIP9FHbRHrCJn33b6G8X7eGC\n", "gRYAAAAA4CUGWniD/RR20R6wiZ992+hvF+3hIj3ZCwAAAAAAJFZ5ebl27typRx991Om6//zP/9TJ\n", "kyeVmpqqEydO6MEHH1R6+qmxcuvWrXr99deVnZ2tkydP6sEHH1RqarjPoTLQwhvsp7CL9oBN/Ozb\n", "Rn+7aJ8YJSUl2r9/v/N1X/va12IfP/PMM9q7d6+uvPJKSVJ1dbUefvhhSdLevXu1atUqzZkzp0vW\n", "2xYGWgBAt9YnK02FZdXJXgYAAD1WaWmphg4dqjvuuEOVlZWKRqOtPp+fn6/i4uLYcU1NjcrKynTh\n", "hRdq1qxZsdvvvffe2MdHjx5Vnz59Ql87Ay28EYlEeMTOKNrb9uBlnzj3H7V8a0irQSLxs28b/e2y\n", "1n7U8qe75OvU3H9v/JPOEASBli1bprvuuktTpkyRJI0cOTLudaNGjdL3v/99LVu2TL/97W/Pumbv\n", "3r167bXX9NBDDzmvyRUDLQAAAAAkSWcG0a6ybds2DR8+XDNnzpQkNTQ0aMWKFQqCoNV5eXl5rZ6J\n", "bXH33XerrKys1UD761//Wjt27EjIMCsx0MIjlh6pQ2u0t43+dtHeNvrbRfvEmTRpkhYtWqQlS5Zo\n", "wYIFys3N1cKFC9s8/9ChQ7rgggvUu3dvSdLmzZs1fvz42Oeff/55ffrpp7r//vtDX3sLBloAAAAA\n", "MKa8vFxHjx5Venq65s2bpzlz5uiee+5RSUlJm9dkZGToySefVEZGhjIyMjRgwADdeeedkqS3335b\n", "P/nJTzR58mQ9+eSTkqTMzEzdd999of45GGjhDWv7KfBXtLeN/nbR3jb620X7xCgpKYkNryNGjFBV\n", "VVXca/r3769HHnnknJ+76qqrtGbNmi5dY0eE+6ZAAAAAAACEhIEW3uCROrtobxv97aK9bfS3i/Zw\n", "wUALAAAAAPASAy28EYlEkr0EJAntbaO/XbS3jf520R4uGGgBAAAAICRBEJz1vq7WdeX3hIEW3mA/\n", "hV20t43+dtHeNvrb1dPa9+vXT/X19cleRrdSX1+vfv36dcnX4m17AAAAACAkvXv31vHjx/Xhhx8m\n", "eyndRlZWlnr37t0lX4uBFt7gPcnsor1t9LeL9rbR366e2P6iiy5K9hJ6rFAG2traWlVVVSktLU2T\n", "J09WXl5em+e++OKLam5uliRdccUVGjt2bBhLAgAY0vtkk0Ytf9rpfAAA4J+UIIQdyi+88IJuvfVW\n", "SdK6des0Y8aMNs/9xS9+oS984Qsd+rpVVVWaMGFCl6wRAAAAANC97NixQ1OnTu3w+aE8Q5uTkxP7\n", "ODMzs91zm5ubtWbNGgVBoMsuu4yBFQAAAADQIaH8luPTn/TNyMho99yioiLddtttmjlzpg4ePBjG\n", "ctBD8J5kdtHeNvrbRXvb6G8X7eEilGdoW/bESlJKSkqHr4s3/Pbv3187duzo9Lrgt5ycHPobRXvb\n", "6G8X7W2jv120t61///5O54cy0DY0NEg69Uxty8eStGvXLqWmpmrUqFGx2w4cOKBLL71UktTY2Nju\n", "1504cWIIqwUAAAAA+CiUgfbaa6/VypUrFQSBpk2bFrt9y5YtSklJOWug3bp1qyTp6quvDmM5AAAA\n", "AIAeKJTfcgwAAAAAQNhC+aVQAAAAAACEjYEW3VY0Gm31C8YAAAAA4HSh7KHtarW1taqqqlJaWpom\n", "T56svLy8ZC8JIauoqNC+ffs0Y8YM5efnS+LvgSW7d+/Wb3/7W0WjUV133XW65JJL6G/I5s2bY2/j\n", "NnToUE2cOJH+RjQ0NOjf//3fdeedd/LPfmNefPHF2IPYV1xxhcaOHSuJ/pbs27dP27dvV1ZWloqK\n", "ilRfX097Ax5//HENHz5ckvTxxx9r/vz5khx/9gMPPP/887GP165dm8SVIJF2794dfPDBB7Fj/h7Y\n", "sXHjxtjHP//5z4MgoL9VL7/8chAE9Ldiw4YNwfbt2/lnv0GVlZXnvJ3+Nhw+fDiIRCKtbqO9DQ0N\n", "DbGPN2zYEPvYpb8XLznOycmJfZyZmZnElSCZ+Htgx4033njWbfS3Zf/+/XriiSc0bNgwSfS34PDh\n", "w8rJyVF2dnar22lvQ3Nzs9asWaPVq1e3ev9R+tvw1ltvqVevXlqzZo3effddSbS3ouWf+XV1dRo0\n", "aFDsdpf+Xgy0wWm/iDkjIyOJK0Ey8ffAnl/84heaNGmSJPpbU1BQoAULFmjbtm2S6G9BJBLRDTfc\n", "cNbttLehqKhIt912m2bOnBnbciDR34q6ujodOXJEt912m9577z1Fo1HaG1NTU9PqrV1d+nuxh/b0\n", "XwyUkpKSxJUgmfh7YMvGjRs1fPhwDRw4UBL9LcrOzlafPn0k0d+CgwcP6oUXXlBdXZ0KCgpie2hp\n", "b8/p//FKfztaXp01ZMgQ1dfX096YxsbGVq/QcenvxUDb0NAg6dSk3vIx7OHvgR2//OUvlZubq4KC\n", "gtht9Lejvr5eAwYMkPTXR2jp3/O1/CKQmpoa9e/fP3Y77W04cOCALr30Ukmn/sO2Bf1tGDFihPbt\n", "26dhw4bp8OHDGj16NO0NiUajSk1t/cJhl/4pwenP53ZTH374oTZu3KggCDRt2rRWr69Gz/TKK69o\n", "3759ys7OVkFBgW688Ub+HhhRV1enH//4x7ryyislSUePHlVpaSn9DXnxxRd1/PhxSdI111yjgoIC\n", "+htRX1+v5557TgUFBSosLJTEfwNYsWnTpthLja+++urYbz2lvx3PPfec0tLSdPHFF+uGG26gvSH7\n", "9+9XNBrV5ZdfHrvNpb8XAy0AAAAAAGfy4pdCAQAAAABwJgZaAAAAAICXGGgBAAAAAF5ioAUAAAAA\n", "eImBFgAAAADgJQZaAAAAAICXGGgBAKE5dOiQli9ffs7PvfTSS+1eu3z5ch06dCiMZXXK9u3b9dxz\n", "z+mll15SZWVlQu/75Zdf1urVq1vd1t739uTJk/rZz36mF154QT//+c914MCBVp8/3+/t9u3b9fTT\n", "T3f6+mT71a9+pcOHDyd7GQCALpCe7AUAAHquCy+8UMXFxef8XENDQ7vXFhcX68ILLwxjWZ2yb9++\n", "Nv8sYbv55pu1Zs2aVre197393e9+p7Fjx2rs2LHn/Pz5fm8nTpx41pDsk5MnT6qpqSnZywAAdAEG\n", "WgAw7M0339SmTZs0ePBg5eTk6OTJk+rfv7++8IUvSJIaGxv10ksvKSMjQ83NzerTp0/sc5K0du1a\n", "BUGgjIwMHTx4UDfddJOGDRsmSdq1a5f27t2rP//5z7rzzjtj1zQ1NWnDhg3as2eP1q1bJ0kaPny4\n", "Ro8eLUk6ceKEKioqtHfvXpWWluriiy9utebKykodO3ZMaWlpOnnypG655RZlZWXp97//vVatWqXP\n", "fOYz6t27t44fP64vfvGL6tu3b9zvQ3t/zpb1nL7ez372s8rNzW33a/785z/Xtm3bNHbsWB0+fFhZ\n", "WVk6fvy4vvzlL+viiy9u9z6bmpq0du1apaamKggC5eXltfrabX1vWz63efNmSacG2wsvvFCTJ0+O\n", "+71tamrSCy+8oNTUVKWkpCglJUXTp09XauqpF3O98sorqq+vV3p6utLS0hSNRuN+XyWpublZ69ev\n", "VxAEkqRPP/1UQ4cO1ec+9zlFo1GtXr1a6enpCoJAvXv3VmFhYezaiooK/f73v9f48eP1/vvvS5KK\n", "iorUt29f7dq1S7/5zW+UkZGhY8eOqaioSAMHDox7nzU1NdqxY4c++OAD9erVS6mpqfrSl76k9PRT\n", "/0m0adMm1dXVKTMzU42NjbH7k079vGzYsEGlpaXavHmzMjMzddVVV2n48OEd+l4AAEIQAABM+973\n", "vhccOnQodvzGG28Eu3fvDoIgCJ599tng2LFjsc+9++67wZYtW4IgCILm5ubgRz/6UXDy5MkgCILg\n", "T3/6U/DJJ5+c9fWfeeaZc95vW7e3eO2114K6urpWt/3qV78Kfvvb38aOjx49GqxevTp2XFZWFltP\n", "Q0ND8Pzzz7d7Hy3a+3N2dL1nqqurCyorK4MgCIKf/vSnsdteffXVuPf54osvntXk2WefPes+2lrT\n", "7t27Yw3P5Vzf2+effz6ora2NHR88eDB45ZVXYl/v9O/HoUOHgn/9139t8+ufbsOGDcGf/vSn2PHH\n", "H38c/OY3vznnueXl5Wfd9oMf/CDYuXNnu/dx4sSJYO3atR2+z9dee63V97fF7t27g1/+8petvu6Z\n", "3/dnnnkmqKioaHc9AIDE4RlaADBuyJAhsWe2JOnqq6/Wyy+/rFGjRikIAvXq1Sv2ueHDh+udd96R\n", "JKWmpuqWW27R66+/rqamJv3lL39p9exaGD744ANdf/31sePevXu3+nzfvn1jz7RlZ2d3+GWl7f05\n", "z0dGRkZsLZKUlpYWe9awvfs8duzYWU1anqEMS11dnbZs2XLO9b/33nu6+eabY7cPHDhQl1xySYe+\n", "7rFjxzRgwIDY8UUXXaSLLrpIknT8+HFVVlaqublZqamp+t3vfnfW9UOGDDnnS6f37NmjXbt2KSMj\n", "Q6mpqWpubu7QfbZo6XC6ffv2qbGxMfZMvHTq2d0znf69AAAkFwMtABj3wQcf6OOPP44NUG+99ZZG\n", "jhwp6dTQeuzYsdjg+O677yo/P1+S9Mc//lHZ2dmaNm2aJOnIkSPatGmTvvSlL4W21ksuuUTvvvuu\n", "RowYIenU4NIVzvXnPPNlvq7ONTDFu8+W722vXr1aNdmxY0fcr3fmfaekpDit9/LLL9eYMWM0aNCg\n", "2G0tDwgMHz5cb731lq677jpJp34h1R/+8IcOfd3s7GzV19fHBsxoNKp9+/Zp2LBhWr9+vaZOnRp7\n", "Se+5hsdzaWxs1Ntvv62SkhJJp15KffovGWvvPiUpPT291QDcYsyYMaqtrY39OU//HgAAuqeUwOXf\n", "kACAHmfVqlVKT0+PDUAXXXSRbrrpJkl/3Vuanp6uaDSqXr16xZ6d2rFjh2pqatS7d2+lpKTo008/\n", "1fTp09W3b9/YXs1oNKp33nlHY8eOVf/+/WNfVzq1V7G+vl6pqalqamrS9ddfr8GDB8f2h+7bt0+5\n", "ubnq1auXrrvuOg0ePFjSX/fQpqam6uTJk7r11luVlZWlXbt2ae3atZo5c6ZGjRqlN998U5WVlXrg\n", "gQfUp0+fdr8H7f05P/nkE7322mvauXOnxo4dq5SUFE2dOvWsZ4fPtH79eu3du1f333+/Vq1apQkT\n", "Jmjw4MH6yU9+ogceeEBNTU1t3mdTU5Oee+652LOPvXv31rZt2zR37lzl5eW1+73dunWr3nrrLUnS\n", "oEGDdMkll+iaa66RpA59bxsbGyWdevZ0yJAhsWfEf/GLX+jw4cPKzs5WY2Oj6urqdN1118W+dlua\n", "mpr0/PPPx/bdNjc362//9m81ePBg7d69WzU1NcrIyFBTU5Pee+89jR8/XkVFRef8vk+ZMiXWctWq\n", "VWNRCvkAAAC+SURBVMrOzlYQBAqCQL/5zW80d+5cFRQUtHufknT06FG9+OKLsYa9e/fWlClTJJ36\n", "e/3++++3etb3K1/5Sqzp9u3bY88YX3XVVbrsssva/fMDAMLFQAsAxj377LNJ++29AAAA54P3oQUA\n", "w958803t2bNHzz//vD755JNkLwcAAMAJz9ACAAAAALzEM7QAAAAAAC8x0AIAAAAAvMRACwAAAADw\n", "EgMtAAAAAMBLDLQAAAAAAC8x0AIAAAAAvPT/ActW+S28O4vzAAAAAElFTkSuQmCC\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def test_rep(k=1, n=128):\n", " s1 = string.letters[:k]*int(n/k*2)\n", " s1 = s1[:n]\n", " r = lambda x : ratio(x, s1)\n", " \n", " def modified(i):\n", " \"\"\" return the string s1, where the i-th is replaced by -\"\"\"\n", " return s1[:i-1]+u'-'+s1[i+1:]\n", " \n", " xx = range(1, n, step)\n", " distance = map( r, [modified(i) for i in xx])\n", " return xx,distance\n", "\n", "fig,ax = plt.subplots(1,1)\n", "fig.set_figwidth(16)\n", "fig.set_figheight(8)\n", "\n", "for k in [1,2,4,8,16,32]:\n", " xx, distance = test_rep(k, n=64)\n", " plt.step(xx, distance, where='post', label='k={k}'.format(k=k))\n", " \n", "\n", "plt.ylabel('similarity')\n", "plt.xlabel('position of modified caracter')\n", "plt.legend(loc=4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(bottom of the graph is at 0.5, not 0.0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Huummm... this definitively does not look at what I was expecting (mainly something constant), but looks more like a [Sierpinski triangle](http://en.wikipedia.org/wiki/Sierpinski_triangle) to me." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bottom line, even if difflib make some pretty looking diff, I cannot trust it for giving me proximity of two sequences." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Still Some good sides..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Anyway, I knew what [levenstein distance](http://en.wikipedia.org/wiki/Levenshtein_distance) was, but not really\n", "what the efficient algorithme where. I played around a little bit with them, and recoded them in pure python.\n", "I'll post the link soon, just time to clean things up im make them as pure python module. Below is how it looks like.\n", "\n", "Thing is, as far as I can tell, libdiff stays an order of magnitude faster in some cases, as well as computes the matches at the same time." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def lcs_len3(Seq1 , Seq2):\n", " \"\"\" Compute the LCS len 2 sequences\n", " \n", " Do not calculate the matrix and try to be as efficient as possible \n", " in storing only the minimal ammount of elelment in memory, mainly the previous\n", " matrix row + 1 element.\n", " \"\"\"\n", " LL1 = len(Seq1)+1\n", " LL2 = len(Seq2)+1\n", "\n", " ## we will do the big loop over the longest sequence (L1)\n", " ## and store the previous row of the matrix (L2+1)\n", " if LL2 > LL1 : \n", " Seq2, Seq1 = Seq1, Seq2\n", " LL2, LL1 = LL1, LL2\n", "\n", " \n", " previousrow = [0]*(LL2)\n", " cindex = 0\n", "\n", " for Seq1ii in Seq1:\n", " for jj in range(1,LL2):\n", " cindex = (cindex+1) % LL2\n", "\n", " if Seq1ii == Seq2[jj-1]:\n", " if jj == 1:\n", " previousrow[cindex] = 1\n", " else :\n", " previousrow[cindex]+=1\n", " if Seq1ii != Seq2[jj-1] :\n", " up = previousrow[(cindex+1) % LL2]\n", " \n", " if jj != 1 :\n", " left = previousrow[(cindex-1) % LL2]\n", " if left > up :\n", " previousrow[cindex] = left\n", " continue \n", " previousrow[cindex] = up\n", "\n", "\n", " return previousrow[cindex]" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import numpy as np\n", "import difflib" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "random x 4 8\n", "sorted \u221a 23 23\n", "random x 4 9\n", "sorted \u221a 26 26\n", "random x 6 10\n", "sorted \u221a 25 25\n", "random x 4 12\n", "sorted \u221a 27 27\n", "random x 5 7\n", "sorted \u221a 27 27\n", "random x 7 10\n", "sorted \u221a 30 30\n", "random x 6 13\n", "sorted \u221a 33 33\n", "random x 9 10\n", "sorted \u221a 25 25\n", "random x 2 7\n", "sorted \u221a 28 28\n", "random x 5 10\n", "sorted \u221a 27 27\n" ] } ], "source": [ "def compare(s1,s2):\n", " m0 = difflib.SequenceMatcher(None, s1, s2, autojunk=False).get_matching_blocks()\n", " m1 = lcs_len3(s1,s2)\n", " a,b = sum([x.size for x in m0]),m1\n", " return a,b \n", "\n", "for k in range(10):\n", " s1 = np.random.randint(0,250, 100)\n", " s2 = np.random.randint(0,250, 100)\n", " a,b = compare(s1,s2)\n", " print 'random',u'\u221a' if a == b else 'x',a,b\n", " a,b = compare(sorted(s1),sorted(s2))\n", " print 'sorted',u'\u221a' if a == b else 'x',a,b\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Except on the sorted case, SequenceMatcher from stdlib give the wrong matches length almost all the time (sometime it is right)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1000 loops, best of 3: 402 \u00b5s per loop\n", "100 loops, best of 3: 9.38 ms per loop\n", "--------- sorted ----------\n", "1000 loops, best of 3: 734 \u00b5s per loop\n", "100 loops, best of 3: 9.33 ms per loop\n" ] } ], "source": [ "%timeit difflib.SequenceMatcher(None, s1, s2, autojunk=False).get_matching_blocks()\n", "%timeit lcs_len3(s1,s2)\n", "print '--------- sorted ----------'\n", "s1.sort()\n", "s2.sort()\n", "%timeit difflib.SequenceMatcher(None, s1, s2, autojunk=False).get_matching_blocks()\n", "%timeit lcs_len3(s1,s2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On both sorted and unsorted arrays, SequenceMatcher is way faster (10 to 20 times) than I am, but wrong." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 26 ms per loop\n", "10 loops, best of 3: 30.8 ms per loop\n" ] } ], "source": [ "s1 = 'a'*251\n", "i = 124\n", "s2 = 'a'*(i)+'b'+'a'*(250-i)\n", "%timeit MySequenceMatcher(s1, s2).get_matching_blocks() \n", "%timeit lcs_len3(s1,s2)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "126" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(x.size for x in MySequenceMatcher(s1, s2).get_matching_blocks())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "But in the cases where `SequenceMatcher` is clearly wrong for the **optimal** sequence, we are around the same time to execute." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Not that I don't like current python libdiff, but I hope to be able to build a lower lever library (pure python of course) without any surprise behavior, on which maby one can rebuild the current libdiff and avoid to rely on [regular expression](http://hg.python.org/cpython/file/0872257752c2/Lib/difflib.py#l1371) to parse the output of another function. \n", "\n", "I'll be happy to get any tips to make it faster, of course it is not possible in all the cases but I'm sure we can figure it out." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "As usual comments, typo and PRs welcommed on the [repo that host thoses notebooks](https://github.com/Carreau/posts/issues). I should probably learn how to use [Pelican](http://docs.getpelican.com/en/3.2/) now that it [support notebooks](https://github.com/getpelican/pelican-plugins/pull/21).\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Edit**: At the request of some person, I opened a place to **[comment on this post](https://github.com/Carreau/posts/issues/2)** until I turn it into a real blogpost." ] } ], "metadata": { "kernelspec": { "display_name": "IPython (Python 3)", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3" } }, "nbformat": 4, "nbformat_minor": 0 }