Турбо-алгоритм Бойера-Мура — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Псевдокод)
(→‎Псевдокод)
Строка 31: Строка 31:
 
   
 
   
 
     '''while''' (i <= n - m)  
 
     '''while''' (i <= n - m)  
−
         '''int''' j = m - 1;
+
         '''int''' j = m - 1
−
         '''while''' (j >= 0 && x[j] == y[i + j])
+
         '''while''' (j >= 0 '''and''' x[j] == y[i + j])
 
             --j;
 
             --j;
−
             '''if''' (u != 0 && j == m - 1 - shift)  
+
             '''if''' (u != 0 '''and''' j == m - 1 - shift)  
 
                 j -= u
 
                 j -= u
 
         '''if''' (j < 0)  
 
         '''if''' (j < 0)  
−
             OUTPUT(i);
+
             OUTPUT(i)
−
             shift = bm_gs[0];
+
             shift = bm_gs[0]
−
             u = m - shift;
+
             u = m - shift
 
         '''else'''  
 
         '''else'''  
−
             '''int''' v = m - 1 - j;
+
             '''int''' v = m - 1 - j
−
             '''int''' turbo_shift = u - v;
+
             '''int''' turbo_shift = u - v
−
             '''int''' bc_shift = bm_bc[y[i+j]] - m + j + 1;
+
             '''int''' bc_shift = bm_bc[y[i+j]] - m + j + 1
−
             shift = MAX (turbo_shift, bc_shift);
+
             shift = MAX (turbo_shift, bc_shift)
−
             shift = MAX ( shift, bm_gs[j+1]);
+
             shift = MAX (shift, bm_gs[j+1])
 
             '''if''' (shift == bm_gs[j+1])
 
             '''if''' (shift == bm_gs[j+1])
−
                 u = MIN((m - shift), v);
+
                 u = MIN((m - shift), v)
 
             '''else'''  
 
             '''else'''  
−
                 '''if''' (turbo_shift < bc_shift) shift = MAX (shift, (u+1));
+
                 '''if''' (turbo_shift < bc_shift)  
−
                    u = 0;
+
                    shift = MAX (shift, (u+1))
 +
                u = 0;
 
         i += shift;
 
         i += shift;
  

Версия 20:40, 3 апреля 2016

Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм) является улучшением алгоритма Бойера-Мура. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.

Алгоритм

Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффикс шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:

  1. можно перепрыгнуть через этот сегмент;
  2. она может позволить выполнение 'турбо-сдвига'.

Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.

Пусть [math]u[/math] - запомненный сегмент, а [math]v[/math] - cуффикс, совпавший во время текущей попытки, такой что [math]uzv[/math] - суффикс [math]x[/math]. Тогда [math]av[/math] - суффикс [math]x[/math], два символа [math]a[/math] и [math]b[/math] встречаются на расстоянии [math]p[/math] в тексте, и суффикс [math]x[/math] длины [math]|uzv|[/math] имеет период длины [math]p[/math], а значит не может перекрыть оба появления символов [math]a[/math] и [math]b[/math] в тексте. Наименьший возможный сдвиг имеет длину [math]|u| - |v|[/math] ( его мы и называем турбо - сдвигом ).

Применение турбо-сдвига в случае [math]|v| \lt |u|[/math]

При [math]|v| \lt |u|[/math], если сдвиг плохого символа больше, то совершаемый сдвиг будет больше либо равен [math]|u| - 1[/math]. В этом случае символы [math]c[/math] и [math]d[/math] различны, так как мы предположили, что предыдущий сдвиг был сдвигом хорошего суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший [math]|u| + 1[/math] совместит [math]c[/math] и [math]d[/math] с одним и тем же символом [math]v[/math]. Значит, если сдвиг плохого символа больше, то мы можем применить сдвиг больший, либо равный [math]|u| + 1[/math]. Нельзя совместить символы [math]c \neq d[/math] с одним и тем же символом v.

Псевдокод

Стадия репроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура.

В сам алгоритм добавляется обработка турбо-сдвигов. 

function TBM(char[] x, char[] y, int n, int m)
   int n = length(y)
   int m = length(x)
   int i = 0
   int u = 0
   int shift = m

   if m == 0
        return
        
   //Предварительные вычисления
   int bmBc[] = preBmBc(x, m)
   int bmGs[] = preBmGs(x, m)

   while (i <= n - m) 
       int j = m - 1
       while (j >= 0 and x[j] == y[i + j])
           --j;
           if (u != 0 and j == m - 1 - shift) 
               j -= u
       if (j < 0) 
           OUTPUT(i)
           shift = bm_gs[0]
           u = m - shift
       else 
           int v = m - 1 - j
           int turbo_shift = u - v
           int bc_shift = bm_bc[y[i+j]] - m + j + 1
           shift = MAX (turbo_shift, bc_shift)
           shift = MAX (shift, bm_gs[j+1])
           if (shift == bm_gs[j+1])
               u = MIN((m - shift), v)
           else 
               if (turbo_shift < bc_shift) 
                   shift = MAX (shift, (u+1))
               u = 0;
       i += shift;

Асимптотика

  • Фаза препроцессинга требует [math]O(m + \sigma)[/math] времени и памяти, где [math]\sigma[/math] — размер алфавита.
  • Фаза поиска требует [math]O(n)[/math] времени.
  • В худшем случае поиск требует [math]O(2 \cdot n)[/math] сравнений.

См. также

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Турбо-алгоритм_Бойера-Мура&oldid=53012»