ФЭНДОМ


Общая постановка задачи Править

Пусть дан образец Needle длиной n и строка Haystack. Требуется найти такой индекс i, что:

$ \forall l \in \overline {0, n-1}\ haystack_{i+l} = needle_l $

Либо, если такого индекса не существует, вернуть число, которое не может быть интерпретировано как индекс, например, отрицательное.

Наивный алгоритм Править

Идём вперёд по строке и на каждой итерации проверяем, совпадают ли следующие n символов с Needle.

 let naive_search haystack needle =
  let needle_len = String.length needle in
  let search_end = String.length haystack - needle_len in
  let rec search i =
   if i > search_end then -1 else
   if (String.sub haystack i needle_len) = needle then i else
   search (succ i) in
  search 0

Как нетрудно заметить, в худшем случае на каждой итерации нужно $ |needle| - 1 $ сравнений, всего производится $ |haystack|-|needle| $ итераций, поэтому наибольшее количество сравнений, которое, возможно, придётся произвести - это $ (|haystack|-|needle|)*(|needle|-1) $, что соответствует $ O(|haystack|*|needle|) $.

Алгоритм Рабина-Карпа Править

Хэш-функции Править

Вообще говоря, хэш-функцией называется функция $ [hash\colon 'a \to int] $, дающая более-менее равномерное распределение результатов. Кстати, такая функция представлена в библеотеке OCaml'а. Но в сейчас нас интересует более узкое понятие: хэш-функция строки. Самый простой способ её реализовать - это просто просуммировать коды всех символов.

Описание алгоритма Править

Вычислим хэш-функцию от needle и от первых n символов haystack и сравним их. Если совпали, произведём обыкновенное сравнение. Если нет, сдвинем позицию проверки вправо на единицу, вычтем из значения хэш-функции хэш первого символа и прибавим хэш n+1-го. Повторить...

 let hash s =
  let sum = ref 0 in
  for i = 0 to pred (String.length s) do
   sum := !sum + (int_of_char s.[i]);
  done; !sum
 
 let rabin_karp haystack needle =
  let haystack_len = String.length haystack
  and needle_len = String.length needle in
  let search_end = haystack_len - needle_len in
  if search_end < 0 then -1 else
  let needle_hash = hash needle in
  let rec search i h =
   if (i > search_end) then -1 else
   if (h = needle_hash) && ((String.sub haystack i needle_len) = needle) then i else
   if (i = search_end) then -1 else search (succ i)
    (h - (int_of_char haystack.[i]) + (int_of_char haystack.[i + needle_len])) in
  search 0 (hash (String.sub haystack 0 needle_len))

Алгоритм Кнута-Морриса-Пратта Править

Общее описание Править

Рассмотрим сравнение строк на позиции i, где образец $ Needle [0, m - 1] $ сопоставляется с частью текста $ Haystack [ i, i + m - 1 ] $. Предположим, что первое несовпадение произошло между $ Haystack[ i + j ] $ и $ Needle[ j ] $, где $ 1 < j < m $. Тогда $ Haystack[ i, i + j - 1 ] = Needle[ 0, j - 1 ] = P $ и $ a = Haystack[ i + j ] \ne Needle[ j ] = b $.

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца P сойдется с каким-нибудь суффиксом (подсловом) текста P. Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки P.

 let self_repeat s =
  let len = String.length s in
  let rec sr i =
   if (String.sub s 0 i) = (String.sub s (len - i) i) then i else sr (pred i) in
  if len = 0 then 0 else sr (pred (String.length s))

Таким образом, если при сравнении несовпадение произошло в позиции i, можно сдвигать текущий указатель начала сравнения вперёд не на единицу, а на префикс-функцию от подстроки $ Needle [0, i - 1] $.

Классический вариант Править

 let kmp haystack needle =
  let build_backw s =
   Array.init (String.length s) (fun i -> self_repeat (String.sub s 0 i)) in
  let backw = build_backw needle
  and needle_len = String.length needle
  and haystack_len = String.length haystack in
  let rec apply i n =
   if n = needle_len then (i - needle_len) else
   if i = haystack_len then (-1) else
   if haystack.[i] <> needle.[n] then
    if n = 0 then apply (succ i) 0 else
                  apply i backw.(n) else
    apply (succ i) (succ n) in
  apply 0 0

Автоматный вариант Править

 let build_fsm needle =
  let needle_len = String.length needle in
  Array.init 256 (fun ch -> Array.init needle_len (fun len ->
   let c = char_of_int ch in
   if needle.[len] = c then succ len else
   self_repeat ((String.sub needle 0 len) ^ (String.make 1 c))))
 
 let automation haystack needle =
  let needle_len = String.length needle
  and haystack_len = String.length haystack
  and auto = build_fsm needle in
  let rec apply i n =
   if n = needle_len then (i - needle_len) else
   if i = haystack_len then (-1) else
   find (succ i) (auto.(int_of_char haystack.[i]).(n)) in
  apply 0 0

Разница между этими двумя вариантами заключается лишь в том, что автомат строится дольше, чем массив откатов (причём в 256 раз), зато его применение несколько эффективнее, так как массив откатов учитывает все совпавшие символы, а автомат, кроме них, ещё один - тот, на котором произошло несоответствие.