{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "# Наивный (очень) алгоритм сравнения строк\n", "\n", "
\n",
    "\n",
    "\n",
    "1  StrCmpNaive(text, pattern):\n",
    "2     lp = length(pattern)\n",
    "3     lt = length(text)\n",
    "4     matches = new List\n",
    "5     for i in range 0..lt exclusively  // что здесь не так?\n",
    "6         for j in range 0..lp exclusively   \n",
    "7             if text[i+j] != pattern[j]\n",
    "8                 break\n",
    "9             if j == lp - 1\n",
    "10                matches.append(i)\n",
    "11    return matches\n",
    "\n",
    "\n",
    "
\n", "> Ассимптотическая сложность в наихудшем случае = $O(?)$\n", "\n", "> Какой паттерн (и для какого текста) будет приводить к максимально неэффективной работе алгоритма? (* в случае, если совпавшие строки _не перекрываются_)\n", " \n", "> Например, поиск `'aaaaaaab'` в `'aaaaaaaaaaaaaaaaaaaaaa'` и тому подобное. Или поиск паттернов из повторяющихся символов, если допускается частичное пересечение разных выравниваний. К примеру, поиск `'aaaa'` в `'aaaaaaaaaaaaaaaaa'`\n", " \n", "# Мы можем лучше\n", "\n", "Мы будем предполагать следующее:\n", "* Паттерн (в большинстве случаев) значительно меньше, чем сам текст\n", "* Алфавит ограничен, и его мы тоже знаем, естественно. Алфавит - множество символов, из которых состоят текст и паттерн\n", "\n", "Одна из (относительно) простых идей, которую можно использовать для ускорения поиска:\n", "> Если встреченный в тексте не совпадающий с паттерном символ вообще не встречается в паттерне, можно смело \"проматывать\" начало паттерна и располагать его сразу за этим символом\n", "\n", "
\n",
    "1  StrCmpLessNaive(text, pattern):\n",
    "2     lp = Length(pattern)\n",
    "3     lt = Length(text)\n",
    "4     matches = new List\n",
    "5     preprocessed = Preprocess(pattern)\n",
    "6     \n",
    "7     shift = 0\n",
    "8     while shift < lt - lp + 1:\n",
    "9         j = 0\n",
    "10        while j < lp and text[shift+j] == pattern[j]:\n",
    "11            j += 1\n",
    "12        if j == lp:\n",
    "13            matches.append(shift)\n",
    "14            shift += 1\n",
    "15        else:\n",
    "16            shift += UsePreprocessed(text[shift+j], shift, preprocessed)\n",
    "17     return matches\n",
    "
\n", "\n", "Возникают следующие вопросы:\n", "* Как выглядит применение эвристики \"перемотки\"? \n", "* Как улучшить эвристику?\n", "\n", "\n", "\n", "\n", " \n", " \n", "`shift = 0`\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "EXAMPLE\n",
    "^\n",
    "
\n", " \n", "`j = 0; shift = shift + j + 1` \n", "`shift = 1`\n", "\n", "
HERE IS A SIMPLE EXAMPLE \n",
    " EXAMPLE\n",
    "  ^\n",
    "
\n", "`j = 1; shift = shift + j + 1` \n", "`shift = 3`\n", "\n", "
HERE IS A SIMPLE EXAMPLE \n",
    "   EXAMPLE\n",
    "    ^\n",
    "
\n", "`j = 1; shift = shift + j + 1` \n", "`shift = 5`\n", "\n", "\n", "\n", "\n", "> И так далее. Пока решение выглядит очень сырым. Как можно _существенно_ улучшить его?\n", "\n", "\n", "Чтобы ускорить обработку последовательностей еще сильнее, нам придется взглянуть на проблему с другой стороны - буквально. \n", "\n", "Правда, для этого придется немного переписать основной алгоритм.\n", "\n", "## Сравнение строк с (правого) конца паттерна\n", "\n", "
\n",
    "1  StrCmpReversed(text, pattern):\n",
    "2     lp = Length(pattern)\n",
    "3     lt = Length(text)\n",
    "4     matches = new List\n",
    "5     preprocessed = Preprocess(pattern)\n",
    "6     \n",
    "7     shift = 0\n",
    "8     while shift < lt - lp + 1:\n",
    "9         j = lp - 1\n",
    "10        while j >= 0 and text[shift+j] == pattern[j]:\n",
    "11            j -= 1\n",
    "12        if j <= 0:\n",
    "13            matches.append(shift)\n",
    "14            shift += 1\n",
    "15        else:\n",
    "16            if text[j+shift] not in preprocessed == 0:\n",
    "17                shift += (j + 1)\n",
    "18            else:\n",
    "19                shift += 1\n",
    "20     return matches\n",
    "
\n", "\n", "\n", "\n", " \n", " \n", "`shift = 0`\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "EXAMPLE\n",
    "      ^\n",
    "
\n", " \n", "`j = 6; shift = shift + j + 1` \n", "`shift = 7`\n", "\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "       EXAMPLE\n",
    "             ^\n",
    "
\n", "`shift = shift + 1` \n", "`shift = 8`\n", "\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "        EXAMPLE\n",
    "              ^\n",
    "
\n", "`shift = shift + 1` \n", "`shift = 9`\n", "\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "         EXAMPLE\n",
    "           ^\n",
    "
\n", "`j = 2; shift = shift + j + 1` \n", "`shift = 12`\n", "\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "            EXAMPLE\n",
    "                  ^\n",
    "
\n", "\n", "`shift = shift + 1` \n", "`shift = 13`\n", "\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "             EXAMPLE\n",
    "                   ^\n",
    "
\n", "\n", "`shift = ?` \n", "Можно ли улучшить эвристику \"сдвиг на 1\" в данном случае?\n", "\n", "\n", "\n", "\n", "В случае, если символа, встреченного в тексте, нет в паттерне, весь паттерн сдвигается правее этого символа.\n", "\n", "А если есть? Предположим, что мы искали бы не весь паттерн, а только его часть - т.е. брали бы _суффикс_ паттерна до встречи с символом `A`: \n", "\n", "> 
MPLE
\n", "\n", "тода решение было бы простым - сдвинуть паттерн правее символа. Иначе говоря, сдвигать его до тех пора, пока можно с уверенностью сказать, что \"плохого\" символа в паттерне нет.\n", "\n", "Теперь вспомним, что у паттерна есть вторая часть (то есть просто его начало):\n", "\n", "> 
EXAMPLE
\n", "\n", "До этой части можно спокойно проматывать. Если мы сделаем так, то окажется, что эвристика сдвигает последний (самый правый) символ `A` паттерна как раз до совпадения с таким же символом в тексте.\n", "\n", "\n", "
HERE IS A SIMPLE EXAMPLE   \n",
    "                 EXAMPLE\n",
    "                       ^\n",
    "
\n", "\n", "\n", "> (нам повезло, и поиск закончился, но это не всегда так)\n", "\n", "Как расчитать сдвиг? Ведь \"плохой\" символ может встретиться не только в конце паттерна, но и во время проверки \"в середине\" паттерна. Препроцессинг должен покрывать все эти случаи. \n", "\n", "\n", "# Подготовка символов\n", "\n", "Нам потребуется функция `AlphabetIndex(char)`, которая переводит символ в целое чисо: $f: Char \\rightarrow Int$. При помощи этой функции будем получать фиксированные числовые индексы для символов из алфавита.\n", "\n", "\n", "Вторая функция, более важная - это функция, которая подготовит таблицу для работы эвристики \"плохого символа\".\n", "\n", "\n", "
\n",
    "1  BadCharacterTable(pattern):\n",
    "2      if Length(pattern) == 0: \n",
    "3          return new Array[Int] of shape (0, |Alphabet|)\n",
    "4      support = new Array[Int] of -1 of length |Alphabet|\n",
    "5      table = new Array[Int] of shape (1 + Length(pattern), |Alphabet|)\n",
    "6      for i in 0..Length(pattern) exclusively:\n",
    "7          support[AlphabetIndex(pattern[i])] = i\n",
    "8          for j in 0..Length(pattern) exclusively:\n",
    "9              table[j][j+1] = support[j]\n",
    "10     return table\n",
    "
\n", "\n", "Есть и более простой подход, который создает одномерную таблицу, в которой записаны для каждого символа алфавита расстояние от последнего символа до _самого правого_ вхождения в строку. Если символа вообще нет, записывается длина строки: \n", "\n", "
\n",
    "1 BadCharacterVariant(pattern):\n",
    "2     lp = Lentgh(pattern);\n",
    "3     table = new Table of size |Alphabet|\n",
    "4     for i in 0..|Alphabet| exclusively:\n",
    "5         table[i] = lp;\n",
    "6     for i in 0..(|lp| - 1) exclusively:\n",
    "7         table[pattern[i]] = lp - 1 - i\n",
    "8     return table\n",
    "
\n", "\n", "\\- но она несовместима с дальнейшей версией кода (из-за разных вовзращаемых значений)\n", "\n", "\n", "## Пример работы функции с небольшим алфавитом\n", "\n", "Алфавит: $\\{A, C, G, T\\}$\n", "\n", "Паттерн: $GATTACA$\n", "\n", "Таблица:\n", "\n", "
\n",
    "        G   A   T   T   A   C   A\n",
    "A| -1, -1,  1,  1,  1,  4,  4,  6\n",
    "C| -1, -1, -1, -1, -1, -1,  5,  5\n",
    "G| -1,  0,  0,  0,  0,  0,  0,  0\n",
    "T| -1, -1, -1,  2,  3,  3,  3,  3\n",
    "
\n", "\n", "\n", "Применяя подобную таблицу, можно гарантированно перемотать до \"самого правого\" относительно сравниваемого в данный момент \"плохого\" символа. Этот алгоритм является упрощением алгоритма Бойера-Мура и называется **алгоритмом Бойера-Мура-Хорспула**.\n", "\n", "Чуть позже сравним его с \"полной\" версией.\n", "\n", "
\n",
    "1  BoyerMooreHorspool(text, pattern):\n",
    "2     lp = Length(pattern)\n",
    "3     lt = Length(text)\n",
    "4     matches = new List\n",
    "5     preprocessed = BadCharacterTable(pattern)\n",
    "6     \n",
    "7     shift = 0\n",
    "8     while shift < lt - lp + 1:\n",
    "9         j = lp - 1\n",
    "10        while j >= 0 and text[shift+j] == pattern[j]:\n",
    "11            j -= 1\n",
    "12        if j <= 0:\n",
    "13            matches.append(shift)\n",
    "14            shift += 1\n",
    "15        else:\n",
    "16            shift += (j - prepocessed[alphabet_index(text[shift+j])][j])\n",
    "17            // Альтернативный вариант с \"одномерной\" таблицей\n",
    "18            // shift += prepocessed[alphabet_index(text[shift+j])]) - j\n",
    "19     return matches\n",
    "
\n", "\n", "\n", "# Эвристика \"хорошего суффикса\"\n", "\n", "То, что мы только что рассмотрели выше, называется _\"эвристикой плохого символа\"_.\n", "\n", "**Алгоритм Бойера-Мура** использует дополнительную эвристику, называемую эвристикой _\"хорошего суффикса\"_. При каждом несовпадении этот алгоритм вычисляет _обе_ эвристики, и затем выбирает сдвиг по наилучшей (то есть мсаксимальный сдвиг).\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "## Описание эвристики \"хорошего суффикса\" с примерами\n", "\n", "Для начала - как эвристика вообще работает.\n", "\n", "Пусть для данного выравнивания паттерна P и текста T подстрока t текста T совпадает с суффиксом P, но левее t происходит несовпадение. \n", "\n", "
\n",
    "\n",
    "SAGGTAGACTAAGACTTACCCAT\n",
    "     GAAGCAAG\n",
    "     \n",
    "t = AAG\n",
    "\n",
    "
\n", "\n", "Тогда, если существует, найдем самое правое вхождение t' == t в паттерн P, такое, что символ левее P отличается от символа левее t в паттерне P.\n", "\n", "
\n",
    "\n",
    "SAGGTAGACTAAGACTTACCCAT\n",
    "     GAAGCAAG\n",
    "     \n",
    "t = AAG после C\n",
    "t' = AAG после G\n",
    "\n",
    "
\n", "\n", "Сдвинем паттерн P вправо так, чтобы t' из паттерна совпадало с t из текста.\n", "\n", "
\n",
    "\n",
    "SAGGTAGACTAAGACTTACCCAT\n",
    "         GAAGCAAG\n",
    "\n",
    "
\n", "\n", "Если же t' в паттерне P не существует, до сдвинем левый край P левее t из текста T как можно _меньше_, чтобы _префикс_ P совпадал с суффиксом t, если такой префикс существует.\n", "\n", "
\n",
    "\n",
    "паттерн изменен на AGAGCAAG с целью демонстрации\n",
    "\n",
    "SAGGTAGACTAAGACTTACCCAT\n",
    "          |AGAGCAAG\n",
    "          |||\n",
    "          |||\n",
    "          AAGAGCAAG\n",
    "\n",
    "
\n", "\n", "Если префикса нет, сдвинем паттерн левее подстроки t из текста.\n", "\n", "
\n",
    "\n",
    "SAGGTAGACTAAGACTTACCCAT\n",
    "             TCAGCAAG\n",
    "\n",
    "
\n", "\n", "### На примере фразы\n", "Как работает эвристика \"хорошего суффикса\". Синим обозначен суффикс, размещенный в начале паттерна, в том числе его \"воображаемая\" часть.\n", "\n", "
HERE IS A SIMPLE EXAMPLE -> HERE IS A SIMPLE EXAMPLE   \n",
    "      MPLEXAMPLE         ->             MPLEXAMPLE\n",
    "           ^\n",
    "
\n", "\n", "Для сравнения, \"плохой символ\" в той же ситуации дает меньший сдвиг:\n", "\n", "
HERE IS A SIMPLE EXAMPLE -> HERE IS A SIMPLE EXAMPLE\n",
    "        IEXAMPLE         ->            IEXAMPLE\n",
    "
\n", "\n", "\n", "> В алгоритме Бойера-Мура после вычисления выбирается лучшая эвристика \n", "\n", "\n", " \n", "## Расчет эвристики \"хорошего суффикса\"\n", "\n", "Для того, чтобы воспользвоаться перечисленными выше правилами, нам нужно составить таблицы сдвигов для того, чтобы усрорить процесс сдвига. Таблицы составляются за счет предобработки _только_ паттерна. \n", "\n", "Расчет таблиц для эвристики - сложный процесс, поэтому мы разберем его по частям, \"снизу вверх\". \n", "Первая функция, которая потребуется, ищет повторения строки в самой себе по заданным индексам, и возвращает длину совпавшей подстроки:\n", "\n", "\n", "
\n",
    "1  MatchLength(string, i, j):\n",
    "2      if i == j:\n",
    "3          return Length(string) - i\n",
    "4       match_length = 0 \n",
    "5       ls = Length(s)\n",
    "6       while i < ls and j < ls and string[i] == string[j]\n",
    "7            match_length += 1\n",
    "8            i += 1\n",
    "9            j += 1\n",
    "10      return match_length\n",
    "
\n", "\n", "Если вернуться к примеру выше, эта функция дала бы примерно такие результаты:\n", "\n", "
\n",
    "MatchLength(GAAGCAAG, 1, 5) == 3\n",
    "
\n", " \n", "Т.е. следующие три символа после 1-го и 5-го включительно совпадают:\n", "\n", "
GAAGCAAG
\n", "\n", "\n", "## Какие таблицы понадобятся для работы алгоритма\n", "\n", "Для работы алгоритма используются две одномерные таблицы: `L` и `F`. Таблица `F` используется только в случае, если `L[i]` содержит \"пустое\" значение, или найдено совпадение паттерна и подстроки.\n", "\n", "В таблице L содержится следующая информация:\n", "\n", "Для всех `i`, `L[i]` содержит наибольшую (самую правую) позицию меньше `n`, такую, что строка `P[i..n]` совпадает с суффиксом `P[1..L[i]]`, и символ, предшествующий этому суффиксу, не равен `P[i-1]` (то есть символу до `P`). Если такой позиции нет, `L[i]` равен 0.\n", "\n", "\n", "Таблица `F` описывает величину наибольшего суффикса `P[i..n]` для `F[i]`, который также является префиксом `P`. если такого суффикса нет, `P[i] = 0`\n", "\n", "> Пока становится только запутанее. Давайте посмотрим на примеры\n", "\n", "\n", "### Предобработка\n", "\n", "Функция FindPrefixes(string) возвращает массив `Z` такой, что `Z[i]` содержит число, равное длине подстроки `S[i]`, котороая при этом является и префиксом `S`. Если такого префикса нет, то `Z[i]` будет 0.\n", "\n", "Пример:\n", "
\n",
    "FindPrefixes(\"coconut\")\n",
    "--\n",
    "[7, 0, 2, 0, 0, 0, 0]\n",
    "\n",
    "FindPrefixes(\"aaaaaaa\")\n",
    "--\n",
    "[7, 6, 5, 4, 3, 2, 1]\n",
    "
\n", "\n", "> Домашнее задание - реализовать данную функцию.\n", "\n", "Как вы уже могли преположить, данная функция используется для создания таблиц `L` и `H`. \n", "\n", "Однако, поскольку мы ведем сравнение \"с конца\" паттерна, то и функцию будем применять к развернутой строке (или сама функция пишется так, чтобы искать суффиксы - в принципе, разницы нет)\n", "\n", "
\n",
    "\n",
    "FindPrefixes(Reversed(\"EXAMPLE\"))\n",
    "--\n",
    "[7, 0, 0, 0, 0, 0, 1]\n",
    "\n",
    "FindPrefixes(\"ELMAXE\")\n",
    "--\n",
    "[7, 0, 0, 0, 0, 0, 1]\n",
    "\n",
    "\n",
    "
\n", "\n", "### Создание таблицы сдвигов L\n", "\n", "По умолчанию используется эта таблица. Что она содержит?\n", "\n", "При помощи этой таблицы можно вычислить сдвиг, если не совпал `i-1` элемент, по следующей формуле:\n", "\n", "> `shift = Length(pattern) - L[i] - 1`\n", "\n", "\n", "
\n",
    "GoodSuffixTable(\"EXAMPLE\")\n",
    "--\n",
    "  E   X   A   M   P   L   E\n",
    "[-1, -1, -1, -1, -1, -1,  0]\n",
    "-- Сдвиг\n",
    "[ -,  -,  -,  -,  -,  -,  -,  7]\n",
    "
\n", "\n", "\\- здесь единственный совпадающий суффикс - это последняя `'E'`\n", "\n", "
\n",
    "GoodSuffixTable(\"GAAGCAAG\")\n",
    "--\n",
    "  G   A   A   G   C   A   A   G\n",
    "[-1, -1, -1, -1, -1,  3, -1,  0]\n",
    "-- Сдвиг\n",
    "[ -,  -,  -,  -,  -,  4,  -,  7]\n",
    "
\n", "\n", "`\"G\"` в центре паттерна игнорируется, так как сдвигаться до суффикса `'G'` перед которым идет `'A'`, когда алгоритм \"споткнулся\" об `\"AG\"`, бессмысленно. Получается, что \"сдвиг\" нужен до первой `'G'`.\n", "\n", "
\n",
    "GoodSuffixTable(\"GATGCAAG\")\n",
    "--\n",
    "  G   A   T   G   C   A   A   G\n",
    "[-1, -1, -1, -1, -1, -1, -1,  3]\n",
    "-- Сдвиг\n",
    "[ -,  -,  -,  -,  -,  -,  -,  4]\n",
    "
\n", "\n", "А теперь все нормально, потому что в центре перед `'G'` расположено `'T'`, а не `'A'`.\n", "\n", "\n", "Таблица используется для того, чтобы правильно свидгать паттерн относительно текста так, чтобы на совпавший в прошлый раз суффикс накладывалась самая правая часть, содержащая ту же подстроку:\n", "\n", "\n", "
\n",
    "\n",
    "SAGGTAGACTAAGACTTACCCAT\n",
    "     GAAGCAAG\n",
    "\n",
    "После сдвига:\n",
    "\n",
    "SAGGTAGACTAAGACTTACCCAT\n",
    "         GAAGCAAG\n",
    "\n",
    "
\n", "\n", "Совпадение строки с самой собой не важно, поэтому `L[0] = -1`. Если `L[i]` сожержит `-1` (подходящего суффикса нет), осуществляется переход к следуюущей таблице, \"таблице полного сдивга\" `H` (\"full shift table\"). В случае, если произошло несовпадение символов текста и паттерна на `i-1`-м символе, выполняется сдвиг на `Length(pattern) - L[i]`.\n", "\n", "`L[i] = k`, где `S[i:]` совпадает с `S[:k]`. Несовпадающие суффиксы равны `-1`. Например, для `EXAMPLE` будет: \n", "\n", "\n", "**Псевдокод алгоритма**:\n", "
\n",
    "GoodSuffixTable(string):\n",
    "    L = new Array[Int] of -1 of size Length(string)\n",
    "    Z = FindPrefixes(Reversed(S)) \n",
    "    Z = Reverse(Z)\n",
    "    for j in 0..Length(S)-1 exclusively:\n",
    "        i = Length(S) - Z[j]\n",
    "        if i != Length(S):\n",
    "            L[i] = j\n",
    "    return L\n",
    "    \n",
    "
\n", "\n", "\n", "### Создание таблицы полного сдвига H\n", "\n", "Это таблица частично совпадающих префиксов. Переходим к ней в ситуации, если совпадающего суффикса не существует.\n", "\n", "Используется схожим с таблицей `L` образом: если `i-1`-й элемент паттерна не совпал, то паттерн перемещается на `Length(P) - F[i]` вправо.\n", "\n", "По сути, это таблица, содержащую размеры следующей вещи: самого длинного суффикса строки `S[i:]` (можно сказать, что это _суффикс суффикса_ паттерна), который одновременно является и префиксом S.\n", "\n", "На примере `\"EXAMPLE\"`:\n", "\n", "\n", "\n", "
\n",
    "FullShiftTable(\"BONOBO\")\n",
    "--\n",
    "               'O'\n",
    "            'B  O'\n",
    "         'O  B  O'\n",
    "      'N  O  B  O'\n",
    "   'O  N  O  B  O'\n",
    "'N  O  N  O  B  O'\n",
    "--\n",
    "[6, 2, 2, 2, 2, 0]\n",
    "-- Сдвиг\n",
    "[0, 4, 4, 4, 4, 6]\n",
    "
\n", "\n", "\\- Другой пример:\n", "\n", "\n", "
\n",
    "FullShiftTable(\"EXAMPLE\")\n",
    "--\n",
    "[7, 1, 1, 1, 1, 1, 1]\n",
    "-- Сдвиг\n",
    "[0, 6, 6, 6, 6, 6, 6]\n",
    "
\n", "\n", "\n", "**Псевдокод функции**\n", "\n", "
\n",
    "FullShiftTable(string):\n",
    "    F = new Array[Int] of 0 of size Length(string)\n",
    "    Z = FindPrefixes(string)\n",
    "    Z = Reversed(Z)\n",
    "    longest = 0\n",
    "    for i in Length(Z):\n",
    "        if Z[i] == i+1:\n",
    "            longest = max(Z[i], longest)\n",
    "        else:\n",
    "            longest\n",
    "        F[-i-1] = longest\n",
    "    return F\n",
    "
\n", "\n", "\n", "# Алгоритм Бойера-Мура\n", "\n", "Теперь мы (надеюсь) готовы к тому, чтобы добавить эвристику \"хорошего суффикса\" к основному алгоритму.\n", "\n", "Добавим новую эвристику в алгоритм Бойера-Мура-Хорспула:\n", "\n", "\n", "
\n",
    "BoyerMoore(pattern, text):\n",
    "    lp = Length(pattern)\n",
    "    lt = length(text)\n",
    "\n",
    "    if lp == 0 or lt == 0 or lt < lp:\n",
    "        return []\n",
    "        \n",
    "    matches = new List\n",
    "    \n",
    "    bad_character = BadCharacterTable(pattern)\n",
    "    L = GoodSuffixTable(pattern)\n",
    "    F = FullShiftTable(pattern) \n",
    "    \n",
    "    previous_k = -1\n",
    "    shift = 0\n",
    "    \n",
    "    while i >= 0 and shift + i > previous_k and pattern[i] = text[shift+i]:\n",
    "        i -= 1\n",
    "        \n",
    "    if i == -1 or shift + i == previous_k:\n",
    "        matches.append(shift)\n",
    "    else:\n",
    "        char_shift = i - bad_character[AlphabetIndex(text[shift + i])][i]\n",
    "        if i + 1 == lp:\n",
    "            suffix_shift = 1\n",
    "        else if L[i+1] == -1:\n",
    "            suffix_shift = lp - F[i+1]\n",
    "        else:\n",
    "            suffix_shift = lp - L[i+1] - 1\n",
    "        max_shift = Max(char_shift, suffix_shift)\n",
    "        if max_shift == i+1:\n",
    "            previous_k = matches[-1] if matches is not empty else -1\n",
    "        shift += max_shift\n",
    "        \n",
    "    return matches\n",
    "        \n",
    "    \n",
    "
\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "# Сложность алгоритма\n", "\n", "* O(n) с учетом соблюдения правила Галила.\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "# Домашняя работа\n", "\n", "* Реализовать функцию `FindPrefixes`, которая создает таблицу префиксов (примеры работы есть в материале):\n", " * Функция `FindPrefixes(string)` возвращает массив `Z` такой, что `Z[i]` содержит число, равное длине подстроки `S[i]`, котороая при этом является и префиксом `S`. Если такого префикса нет, то `Z[i]` будет 0.\n", "\n", " * Есть тест-кейсы: файл `preprocess_test_cases.txt`. Традиционно, первая строка - количество записей, первый столбец - строка, далее через пробел - записанные последовательно значения из таблицы префиксов для данной строки. \n", "* Реализовать алгоритм Бойера-Мура-Хорспула. \n", " * Для проверки есть тест-кейсы: `string_matching_test_cases.tsv`. Это .tsv без заголовка, но в первой строчке общее число записей. Первый столбец - текст (содержит пробелы), после первого таба - столбец с паттерном (также может содержать пробелы), в последнем столбце через пробел _все_ вхождения паттерна в текст, в том числе, перекрывающиеся частично. Если вхождений нет, столбец пуст.\n", "* (для тех, кто пишет на C): проверить работу алгоритма Бойера-Мура, реализация на С, [из википедии](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Implementations). Можно на предложенных тест-кесах, можно на своих.\n", "\n", "\n", "* [Реализация на Go](https://golang.org/src/strings/search.go)\n", "\n", "" ] }, { "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.7" } }, "nbformat": 4, "nbformat_minor": 2 }