{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "# MLClass. \"Прикладной анализ данных\"\n", "# Модуль \"Инструментарий Data Science\"\n", "\n", "\n", "## Автор материала: Юрий Кашницкий, ФКН НИУ ВШЭ\n", "
\n", "Материал распространяется на условиях лицензии Ms-RL. Можно использовать в любых целях, кроме коммерческих, но с обязательным упоминанием автора материала." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Урок 3. Структуры данных I" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть 3. Алгоритмы на строках" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Python 2 and 3 compatibility\n", "# pip install future\n", "from __future__ import (absolute_import, division,\n", " print_function, unicode_literals)\n", "from builtins import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах и т.д." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Точное соответствие (Naive exact matching)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Дан текст t и образец p (считаем, что |p| < |t|).\n", "\n", "**Задача**: найти все вхождения образца p в текст t\n", "\n", "**Алгоритм**:\n", "1. i=0,\n", "2. сравнить i-й символ t с первым символом p,\n", "3. совпадение -> сравнить вторые символы и так далее,\n", "4. несовпадение -> i += 1 и переход ко второму пункту" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Сложность в худшем случае**: O ( |t| * |p| )" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def naive_match(p, t):\n", " assert len(p) <= len(t) # assume text at least as long as pattern\n", " occurrences = []\n", " for i in range(0, len(t)-len(p)+1): # for each alignment of p to t\n", " match = True # assume we match until proven wrong\n", " for j in range(0, len(p)): # for each position of p\n", " if t[i+j] != p[j]:\n", " match = False # at least 1 char mismatches\n", " break\n", " if match:\n", " occurrences.append(i)\n", " return occurrences" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[9]" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t = 'I need a needle in a haystack' # \"text\" - thing we search in\n", "p = 'needle' # \"pattern\" - thing we search for\n", "naive_match(p, t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Убедимся, что `needle` действительно найдено" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'needle'" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t[9: 9 + len(p)]" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0, 6, 12]" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "naive_match('needle', 'needleneedleneedle')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "Такая сложность алгоритма - непозволительная роскошь для поиска в больших текстах.\n", "\n", "Посмотрим, как замена строки на некоторый вектор может помочь в таких задачах как поиск подстроки и сжатие строки. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Z-функция" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Пусть дана строка s длины n. Тогда Z-функция (\"зет-функция\") от этой строки — это массив длины n, i-ый элемент которого равен наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Пример: Z(abcdabscabcdabia)=[16,0,0,0,2,0,0,0,6,0,0,0,2,0,0,1]. Еще примеры и описание алгоритма на сайте e-maxx.\n", "\n", "Ниже приведен код (опционально)." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def z_func(s):\n", " \n", " Z = [len(s)] + [0] * len(s)\n", " assert len(s) > 1\n", " \n", " # Initial comparison of s[1:] with prefix\n", " for i in range(1, len(s)):\n", " if s[i] == s[i-1]:\n", " Z[1] += 1\n", " else:\n", " break\n", " \n", " r, l = 0, 0\n", " if Z[1] > 0:\n", " r, l = Z[1], 1\n", " \n", " for k in range(2, len(s)):\n", " assert Z[k] == 0\n", " if k > r:\n", " # Case 1\n", " for i in range(k, len(s)):\n", " if s[i] == s[i-k]:\n", " Z[k] += 1\n", " else:\n", " break\n", " r, l = k + Z[k] - 1, k\n", " else:\n", " # Case 2\n", " # Calculate length of beta\n", " nbeta = r - k + 1\n", " Zkp = Z[k - l]\n", " if nbeta > Zkp:\n", " # Case 2a: Zkp wins\n", " Z[k] = Zkp\n", " else:\n", " # Case 2b: Compare characters just past r\n", " nmatch = 0\n", " for i in range(r+1, len(s)):\n", " if s[i] == s[i - k]:\n", " nmatch += 1\n", " else:\n", " break\n", " l, r = k, r + nmatch\n", " Z[k] = r - k + 1\n", " return Z" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[11, 0, 0, 1, 0, 1, 0, 4, 0, 0, 1, 0]" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z_func('abracadabra')\n", "# abracadabra (11)\n", "# a (1)\n", "# a (1)\n", "# abra (4)\n", "# a (1)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[5, 4, 3, 2, 1, 0]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z_func('aaaaa')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Применения Z-функции:\n", "- Поиск подстроки в строке\n", "- Количество различных подстрок в строке\n", "- Сжатие строки" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Поиск подстроки в строке" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Пусть t - текст, p - образец. \n", "\n", "**Задача**: найти все вхождения образца p в текст t.\n", "\n", "**Решение**: \n", "- Образуем строку s = p + $ + t, т.е. к образцу припишем текст через символ-разделитель (который не встречается нигде в самих строках).\n", "- Посчитаем для полученной строки Z-функцию\n", "- Тогда для любого i в отрезке [0; length(t)-1] по соответствующему значению z[i + len(p) + 1] можно понять, входит ли образец p в текст t, начиная с позиции i: если это значение Z-функции равно length(p), то да, входит, иначе — нет.\n", "\n", "Сложность: O(len(p) + len(t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Код**" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def zMatch(p, t):\n", " s = p + \"$\" + t\n", " Z = z_func(s)\n", " occurrences = []\n", " for i in range(len(p) + 1, len(s)):\n", " if Z[i] == len(p):\n", " occurrences.append(i - (len(p) + 1))\n", " return occurrences" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Иллюстрация**:\n", "Текст \"lambalambalam\", ищем в нем \"lamb\"" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[18, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4, 0, 0, 0, 0, 3, 0, 0, 0]\n" ] } ], "source": [ "t, p = \"lambalambalam\", \"lamb\"\n", "calculated_z = z_func(\"lamb$lambalambalam\")\n", "print(calculated_z)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Для первого индекса есть вхождение:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "4 4\n" ] } ], "source": [ "print(len(p), calculated_z[0 + len(p) + 1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Для второго - нет:" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "4 0\n" ] } ], "source": [ "print(len(p), calculated_z[1 + len(p) + 1])" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0, 5]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "zMatch(\"lamb\", \"lambalambalam\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Еще примеры**" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n" ] }, { "data": { "text/plain": [ "[9]" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t, p = 'haystack needle haystack', 'needle'\n", "print(z_func(p + '$' + t))\n", "zMatch('needle', 'haystack needle haystack')" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0]\n" ] }, { "data": { "text/plain": [ "[9, 16]" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t, p = 'haystack needle needle', 'needle'\n", "print(z_func(p + '$' + t))\n", "zMatch('needle', 'haystack needle needle')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Сжатие строки" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Дана строка s длины n. \n", "\n", "**Задача**: найти самое короткое её \"сжатое\" представление, т.е. найти такую строку t наименьшей длины, что s можно представить в виде конкатенации одной или нескольких копий t.\n", "\n" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def compress_with_z(s):\n", " z_vec = z_func(s)\n", " for i in range(1, len(s)):\n", " if (i + z_vec[i] == len(s)) and (z_vec[i] % i == 0):\n", " return s[:i]\n", " else:\n", " return s" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[20, 0, 0, 0, 16, 0, 0, 0, 12, 0, 0, 0, 8, 0, 0, 0, 4, 0, 0, 0, 0]\n", "foot\n" ] } ], "source": [ "s = \"footfootfootfootfoot\"\n", "print(z_func(s))\n", "print(compress_with_z(s))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Полезные ссылки\n", "- Список алгоритмов на Википедии\n", "- Про Z-функцию\n", "- Задача на Z-функцию на MCCME.\n", "- Алгоритмы поиска в строке на Хабрахабре" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" }, "name": "seminar2_part1_variables_strings_numbers.ipynb" }, "nbformat": 4, "nbformat_minor": 0 }