Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Точный поиск подстроки в строке /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Алгоритм Боуера-Мура - Программирование от RIN.RU
Алгоритм Боуера-Мура

Ну вот мы и пришли к этому, одному из наиболее известных и, эффективных ( Это особенно касается его дальнейших улучшений ) для ОБЫЧНЫХ ПРИЛОЖЕНИЙ ( то есть редакторов текста, например ) алгоритму.


Он совершает 3n сравнений в худшем случае при поиске первого совпадения с непериодничным образцом и O( n*m ) при поиске всех вхождений.


Он производит сравнения справа налево, начиная с самого правого символа. В случае несовпадения ( или, наоборот, полного попадания ) используются две заранее вычисляемые функции: функция плохого символа и функция хорошего суффикса.


Предположим, что несовпадение произошло между символом образца x[j] = b и символом текста y[ i+j ] = a на позиции i.


Тогда y[ i+j+1, i+m-1 ] = x[ j+1, m-1 ] = u и y[ i+j ] =/= x[j]. Функция хорошего суффикса состоит в 'выравнивании' сегмента y[ i+j+1, i+m-1 ] = x[ j+1, m-1 ] = u по его самому правому появлению в x, так чтобы ему предшествовал символ, несовпадающий с x[ j ] ( см Рис.1 ).


Если такого сегмента нет, то сдвиг выравнивает наибольший суффикс v отрезка y[i+j+1,i+m-1] по совпадающему префиксу x ( см Рис.2 ).



Рис.1  Сдвиг хорошего суффикса, u появляется с символом, отличным от b, в начале.




Рис.2  Сдвиг хорошего суффикса. Вновь появляется в x лишь префикс u.




Рис.3  Сдвиг плохого суффикса, a вновь появляется в x.




Рис.4  Сдвиг плохого суффикса, а не появляется в x еще раз.




Функция плохого символа выравнивает символ текста y[ i + j ] по его самому правому появлению в x[ 0 ... m - 2] ( см Рис.3 ). Если его там нет - сдвигаем на всю длину образца: левый конец теперь - y[ i + j + 1 ] ( см Рис.4 ).


Для сдвига образца мы берем минимум этих двух функций.


Это приводит нас к следующему алгоритму:

сдвиг функции плохого символа хранится в таблице bc размера s, а сдвиг функции хорошего суффикса - в таблице gs размера m + 1.


Для a из S:


bm_bc[ a ] = min{ j | 1 <= j < m и x[ m - 1 - j ] = a }, если a появляется в x и bm_bc[ a ] = m в противоположном случае.


Определим два условия:


cond 1 ( j, s ) : для каждого k, такого что j < k < m, s >= k или x[ k-s ] = x[k]


cond 2 ( j, s ) : если s < j то x[ j-s ] =/= x[ j ].


Тогда для 0 <= i < m имеем:


bm_gs[ i+1 ] = min{ s > 0 | cond 1 ( i, s ) AND cond 2 ( i, s ) hold}


А bm_gs[0] - длина наименьшего периода x.


Реализация на Си



/* Preprocessing of the Bad Character function shift */
PRE_BC( char *x, int m, int bm_bc[] ) {
int a, j;


for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m;
for ( j=0; j < m-1; j++ ) bm_bc[ (unsigned char)x[ j ] ] = m - j - 1;
}


/* Preprocessing of the Good Suffix function shift */
PRE_GS( char *x, int m, int bm_gs[] ) {
int i, j, p, f[XSIZE];


memset( bm_gs, 0, ( m + 1 ) * sizeof( int ) );
f[ m ] = j = m + 1;
for (i=m; i > 0; i-- ) {
while ( j <= m && x[ i - 1 ] != x[ j - 1 ] ) {
if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = j - i;
j = f[ j ];
}
f[ i - 1 ] = --j;
}
p=f[ 0 ];
for ( j=0; j <= m; ++j ) {
if ( bm_gs[ j ] == 0 ) bm_gs[ j ] = p;
if ( j == p ) p = f[ p ];
}
}


/* Boyer-Moore string matching algorithm */
void BM( char *x, char *y, int n, int m ) {
int i, j, bm_gs[XSIZE], bm_bc[ASIZE];


/* Preprocessing */
PRE_GS( x, m, bm_gs );
PRE_BC( x, m, bm_bc );
i=0;
while ( i <= n-m ) {
for ( j=m-1; j >= 0 && x[j] == y[ i+j ]; --j );
if ( j < 0 ) {
OUTPUT(i);
i += bm_gs[ j+1 ];
}
else i += MAX(( bm_gs[ j+1 ]), ( bm_bc[ (unsigned char)y[ i+j ] ] - m + j + 1 ) );
}
}




 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
по выгодной цене купить чай улун .ЧаоЧай - настоящий чай из Китая!