marathon_day8.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "marathon_day8.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyN5v3Q0On8bTc5xiuYB0J27",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sweetpand/Algorithms/blob/master/marathon_day8.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iGykki-pvakp",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "1. Определение количества различных подстрок с использованием хеш-функции. Пусть дана строка S длиной N. \n",
        "Например, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке. \n",
        "Для решения задачи рекомендую воспользоваться алгоритмом sha1 из модуля hashlib или встроенную функцию hash()\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tXmtx1OKvMqb",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "0a71cce3-aa64-4b1c-9ab4-b4b2f38e436e"
      },
      "source": [
        "from collections import defaultdict\n",
        "\n",
        "\n",
        "def find_substr(s):\n",
        "    hash_dict = defaultdict(int)\n",
        "    str_len = len(s)\n",
        "    summ = 0\n",
        "    for n in range(1, str_len): # последовательное увеличение длинны подстроки\n",
        "        for i in range(str_len - n + 1):  # сдвиг каретки для взятия подстроки\n",
        "            sub = hash(s[i:i+n])\n",
        "            if sub not in hash_dict:  # Если подстрока встретилась первый раз\n",
        "                for j in range(str_len - n + 1):  # сдвиг каретки для поиска подстроки\n",
        "                    if sub == hash(s[j:j+n]):\n",
        "                        hash_dict[sub] += 1\n",
        "                        summ += 1\n",
        "    return len(hash_dict), summ\n",
        "\n",
        "\n",
        "my_string = 'beep boop beer'\n",
        "res = find_substr(my_string)\n",
        "print(f'Кол-во уникальных подстрок {res[0]}, кол-во найденных подстрок {res[1]}')"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Кол-во уникальных подстрок 90, кол-во найденных подстрок 104\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kII8lgtVvn50",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "2. Закодируйте любую строку (хотя бы из трех слов) по алгоритму Хаффмана.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9KFmn7Wzvv5F",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        },
        "outputId": "fba44b22-2281-4b74-95c0-0de5d04d5bdc"
      },
      "source": [
        "from collections import defaultdict\n",
        "\n",
        "def my_huffman(input_str):\n",
        "    def _make_dict_list(s):  # модификация из прошлой задачи\n",
        "        hash_dict = defaultdict(int)\n",
        "\n",
        "        str_len = len(s)\n",
        "        for i in range(str_len):  # сдвиг каретки для взятия подстроки\n",
        "            sub = s[i:i + 1]\n",
        "            if sub not in hash_dict:  # Если подстрока встретилась первый раз\n",
        "                for j in range(str_len):  # сдвиг каретки для поиска подстроки\n",
        "                    if sub == s[j:j + 1]:\n",
        "                        hash_dict[sub] += 1 #посчет сколько раз встречается\n",
        "        return hash_dict\n",
        "\n",
        "\n",
        "    def _make_tree_nodes(nodes, label, result, prefix = ''):\n",
        "        childs = nodes[label]\n",
        "        tree = {}\n",
        "        if len(childs) == 2:\n",
        "            tree['0'] = _make_tree_nodes(nodes, childs[0], result, prefix+'0')\n",
        "            tree['1'] = _make_tree_nodes(nodes, childs[1], result, prefix+'1')\n",
        "            return tree\n",
        "        else:\n",
        "            result[label] = prefix\n",
        "            return label\n",
        "\n",
        "\n",
        "    def _bin_code(_vals):\n",
        "        vals = _vals.copy()\n",
        "        nodes = {}\n",
        "        for n in vals.keys():\n",
        "            nodes[n] = []\n",
        "\n",
        "        while len(vals) > 1:\n",
        "            s_vals = sorted(vals.items(), key=lambda x:x[1])\n",
        "            a1 = s_vals[0][0]\n",
        "            a2 = s_vals[1][0]\n",
        "            vals[a1+a2] = vals.pop(a1) + vals.pop(a2)\n",
        "            nodes[a1+a2] = [a1, a2]\n",
        "        code = {}\n",
        "        root = a1+a2\n",
        "        tree = _make_tree_nodes(nodes, root, code)\n",
        "        return code, tree\n",
        "\n",
        "\n",
        "    def _encode(s, code):\n",
        "        res = []\n",
        "        for t in s:\n",
        "            res.append(code[t])\n",
        "        return res\n",
        "\n",
        "\n",
        "    code, tree = _bin_code(_make_dict_list(input_str))\n",
        "\n",
        "    return _encode(input_str, code), code, tree\n",
        "\n",
        "\n",
        "result = my_huffman('beep boop beer!')\n",
        "print(f'encoded str {result[0]}, \\ncode_dict: {result[1]}, \\ncodetree: {result[2]}')"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "encoded str ['00', '01', '01', '100', '101', '00', '110', '110', '100', '101', '00', '01', '01', '1110', '1111'], \n",
            "code_dict: {'b': '00', 'e': '01', 'p': '100', ' ': '101', 'o': '110', 'r': '1110', '!': '1111'}, \n",
            "codetree: {'0': {'0': 'b', '1': 'e'}, '1': {'0': {'0': 'p', '1': ' '}, '1': {'0': 'o', '1': {'0': 'r', '1': '!'}}}}\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}