Поиск наибольшей общей подстроки двух строк с использованием хеширования — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Псевдокод)
(не показаны 43 промежуточные версии 7 участников)
Строка 1: Строка 1:
==Постановка задачи==
+
{{Задача
Имеются строки <tex>s</tex> и <tex>t</tex> такие, что элементы этих строк  <tex>-</tex> символы из конечного алфавита <tex> \Sigma </tex>. Говорят, что строка <tex>z[1 .. m]</tex> является подстрокой строки <tex>s[1 .. n]</tex>, если существует такой индекс <tex>k \in [0 .. n - m]</tex>, что для любого <tex>i \in [1 .. m]</tex> справедливо <tex>s[k + i] = z[i]</tex>. Требуется найти такую строку <tex>z</tex> максимальной длины, что <tex>z</tex> является и подстрокой <tex>s</tex>, и подстрокой <tex>t</tex>.
+
|definition = Имеются строки <tex>s</tex> и <tex>t</tex> такие, что элементы этих строк  <tex>-</tex> символы из конечного алфавита <tex> \Sigma </tex>. Требуется найти такую строку <tex>z</tex> максимальной длины, что <tex>z</tex> является и подстрокой <tex>s</tex>, и подстрокой <tex>t</tex>.
 +
}}
 +
{{Определение
 +
|definition = Будем говорить, что строка <tex>z[0 \, \ldots \, m-1]</tex> является подстрокой строки <tex>s[0 \, \ldots \, n-1]</tex>, если существует такой индекс <tex>k \in [0\,  \ldots \, n - m]</tex>, что для любого <tex>i \in [0 \, \ldots \, m-1]</tex> справедливо <tex>s[k + i] = z[i]</tex>.
 +
}}
  
==Алгоритм==
+
== Алгоритм ==
Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>s</tex> и <tex>t</tex> обязательно найдется общая подстрока длины <tex>y \in [0 .. x]</tex>, так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию <tex>f : [0 .. \min(|s|, |t|)] \rightarrow \{0, 1\}</tex>, которая для <tex>i</tex> из области определения равна 1, если у строк <tex>s</tex> и <tex>t</tex> есть общая подстрока длины <tex>i</tex>, иначе она равна 0. Согласно замечанию, функция <tex>f</tex> должна по мере возрастания <tex>i</tex> быть равной 1 до некоторого момента, а затем обращаться в 0. Собственно, максимальное значение, при котором функция принимает значение 1, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью бинарного поиска найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует равенство строк. Поэтому нужно выполнить проверку нескольких случайных символов подстрок на совпадение, проиграв при этом по времени работы. Алгоритм работает следующим образом:
+
Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>s</tex> и <tex>t</tex> обязательно найдется общая подстрока длины <tex>y \in [0 \ldots x]</tex>, так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим предикат <tex>f \colon [0 \ldots \min(|s|, |t|)] \rightarrow \{0, 1\}</tex>, который для <tex>i</tex> из области определения истинен, если у строк <tex>s</tex> и <tex>t</tex> есть общая подстрока длины <tex>i</tex>, иначе ложен. Согласно замечанию, предикат <tex>f</tex> должен по мере возрастания <tex>i</tex> быть истинным до некоторого момента, а затем обращаться в ложь. Собственно, максимальное значение, при котором предикат истинен, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью [[Целочисленный двоичный поиск|двоичного поиска]] найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует равенство строк. Поэтому нужно выполнить проверку нескольких случайных символов подстрок на совпадение, проиграв при этом по времени работы. Алгоритм работает следующим образом:
  
1) У строки <tex>s</tex> хешируем подстроки заданной длины и полученные хеши записываем в Set.
+
* у строки <tex>s</tex> хешируем подстроки заданной длины и полученные хеши записываем в Set,
  
2) У строки <tex>t</tex> хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set проверяем несколько случайных символов подстрок на совпадение.
+
* у строки <tex>t</tex> хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set проверяем несколько случайных символов подстрок на совпадение.
  
 
Хеширование будем производить так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].
 
Хеширование будем производить так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].
Строка 13: Строка 17:
 
== Псевдокод ==
 
== Псевдокод ==
  
<tex>f</tex> — функция, описанная в алгоритме.
+
<tex>i</tex> — длина подстроки, найденная с помощью [[Целочисленный двоичный поиск|двоичного поиска]].
  
'''findGCS'''(s, t)
+
<tex>f(i)</tex> — предикат, описанный в алгоритме.
    n = min(|s|, |t|)
 
    left = 0
 
    right = n + 1
 
    '''while''' (right - left > 1):
 
        val = (left + right) / 2
 
        '''if''' ('''f'''(val) == 1)
 
            left = val
 
        '''else'''
 
            right = val
 
    '''return''' left
 
  
==Время работы==
+
'''bool''' f(i: '''int'''):
Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки <tex>s</tex> и запись их в Set требует <tex>O(|s|)</tex> шагов. Во-вторых, хеширование подстрок строки <tex>t</tex> и проверка их наличия в Set требует <tex>O(|t|)</tex>. Проверка на совпадение нескольких символов подстрок требует константное время. Значит,на каждый шаг бинарного поиска требуется <tex>O(max(|s|, |t|))</tex> действий. Заметим, что всего для завершения бинарного поиска потребуется <tex>O(\log(\min(|s|, |t|)))</tex> шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(|s|, |t|)) \cdot \max(|s|, |t|))</tex> действий.
+
  hashes = хеши подстрок строки <tex>s</tex> длины <tex>i</tex>
 +
  '''for''' j = 0 '''to''' |t| − i
 +
    hash = hash(t[j ... j + i − 1])
 +
    '''if''' hash '''in''' hashes
 +
      '''if''' совпали несколько случайных символов подстрок
 +
        '''return''' ''true''
 +
      '''else'''
 +
        '''continue'''
 +
  '''return''' ''false''
  
== Литература ==
+
== Время работы ==
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
+
Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим, сколько нам потребуется действий на каждом шаге двоичного поиска. Во-первых, хеширование подстрок строки <tex>s</tex> и запись их в Set требует <tex>O(|s|)</tex> шагов. Во-вторых, хеширование подстрок строки <tex>t</tex> и проверка их наличия в Set требует <tex>O(|t|)</tex>. Проверка на совпадение нескольких символов подстрок требует константное время. Значит, на каждый шаг двоичного поиска требуется <tex>O(\max(|s|, |t|))</tex> действий. Заметим, что всего для завершения двоичного поиска потребуется <tex>O(\log(\min(|s|, |t|)))</tex> шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(|s|, |t|)) \cdot \max(|s|, |t|))</tex> действий.
 +
 
 +
== См. также ==
 +
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 +
* [[Задача о наибольшей общей подпоследовательности]]
 +
 
 +
== Источники информации ==
 +
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Поиск подстроки в строке]]
 
[[Категория:Поиск подстроки в строке]]
 +
[[Категория:Точный поиск]]
 +
[[Категория:Хеширование]]

Версия 20:58, 28 октября 2018

Задача:
Имеются строки [math]s[/math] и [math]t[/math] такие, что элементы этих строк [math]-[/math] символы из конечного алфавита [math] \Sigma [/math]. Требуется найти такую строку [math]z[/math] максимальной длины, что [math]z[/math] является и подстрокой [math]s[/math], и подстрокой [math]t[/math].


Определение:
Будем говорить, что строка [math]z[0 \, \ldots \, m-1][/math] является подстрокой строки [math]s[0 \, \ldots \, n-1][/math], если существует такой индекс [math]k \in [0\, \ldots \, n - m][/math], что для любого [math]i \in [0 \, \ldots \, m-1][/math] справедливо [math]s[k + i] = z[i][/math].


Алгоритм

Пусть длина наибольшей общей подстроки будет [math]x[/math]. Заметим, что у строк [math]s[/math] и [math]t[/math] обязательно найдется общая подстрока длины [math]y \in [0 \ldots x][/math], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим предикат [math]f \colon [0 \ldots \min(|s|, |t|)] \rightarrow \{0, 1\}[/math], который для [math]i[/math] из области определения истинен, если у строк [math]s[/math] и [math]t[/math] есть общая подстрока длины [math]i[/math], иначе ложен. Согласно замечанию, предикат [math]f[/math] должен по мере возрастания [math]i[/math] быть истинным до некоторого момента, а затем обращаться в ложь. Собственно, максимальное значение, при котором предикат истинен, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью двоичного поиска найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует равенство строк. Поэтому нужно выполнить проверку нескольких случайных символов подстрок на совпадение, проиграв при этом по времени работы. Алгоритм работает следующим образом:

  • у строки [math]s[/math] хешируем подстроки заданной длины и полученные хеши записываем в Set,
  • у строки [math]t[/math] хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set проверяем несколько случайных символов подстрок на совпадение.

Хеширование будем производить так же, как и в алгоритме Рабина-Карпа.

Псевдокод

[math]i[/math] — длина подстроки, найденная с помощью двоичного поиска.

[math]f(i)[/math] — предикат, описанный в алгоритме.

bool f(i: int):
  hashes = хеши подстрок строки [math]s[/math] длины [math]i[/math]
  for j = 0 to |t| − i
    hash = hash(t[j ... j + i − 1])
    if hash in hashes
      if совпали несколько случайных символов подстрок
        return true
      else
        continue
  return false

Время работы

Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим, сколько нам потребуется действий на каждом шаге двоичного поиска. Во-первых, хеширование подстрок строки [math]s[/math] и запись их в Set требует [math]O(|s|)[/math] шагов. Во-вторых, хеширование подстрок строки [math]t[/math] и проверка их наличия в Set требует [math]O(|t|)[/math]. Проверка на совпадение нескольких символов подстрок требует константное время. Значит, на каждый шаг двоичного поиска требуется [math]O(\max(|s|, |t|))[/math] действий. Заметим, что всего для завершения двоичного поиска потребуется [math]O(\log(\min(|s|, |t|)))[/math] шагов. Следовательно, суммарное время работы алгоритма будет [math]O(\log(\min(|s|, |t|)) \cdot \max(|s|, |t|))[/math] действий.

См. также

Источники информации

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.