Термины не обязательно запоминать: будут в алгоритме - вернетесь.
Искомый образец - строка x = x [ 0 ... m - 1 ]; его длина m.
Текст - строка y = y [ 0 ... n - 1 ]; его длина n. Алфавит ( множество символов, из которых составлены текст и образец ) - S, в нем s символов.
Слово u - префикс cлова w, если существует слово v : w = uv.
Слово v - суффикс cлова w, если существует слово u : w = uv.
Слово z - подстрока слова w, если существуют u и v : w = uzv.
Слово u - период слова w, если w - префикс слова u(в степени k) для целого k. Наименьший период мы далее и будем называть периодом и обозначать per(w).
Cлово w длины l - периодичное, если длина per(w) <= l/2, в противном случае оно непериодичное.
Слово называется фундаментальным, если оно не может быть записано в виде степени другого слова, то есть не существует z : w = z (в степени 1).
Cлово z - граница слова w, если существуют u и w : w = uz = zv, z - одновременно префикс и суффикс w.
Обращение слова w длины l обозначается w(в степени R) - зеркальный образ w; w(в степени R) = w[ l-1 ]w[ l-2 ] ... w[1]w[0].
В программах будут использованы следующие функции и константы:
константа ASIZE - размер алфавита,
константа WORD - размер компьютерного слова в битах, обычно 16
константа XSIZE - размер образца,
функция ERROR сообщает об ошибке,
функции MIN / MAX - минимум / максимум,
функция OUTPUT возвращает позицию начала совпадения относительно начала текста.
Алгоритм грубой силы
Этот алгоритм заключается в проверке всех позиций текста с 0 по n - m на предмет совпадения с началом образца. Если совпадает - смотрим следующую букву и т.д.
Алгоритм грубой силы не нуждается в предварительной обработке и дополнительном пространстве.
Code
#define EOS '\0'
void BF(char *x, char *y, int m) {
int i;
/* Ищем до конца, вообще говоря можно до позиции n-m */
for(i=0; *y!=EOS; i++, y++) if(memcmp(y,x,m) == 0) OUTPUT(i);
}
Построение автомата
Cтроим автомат ( DFA ): A(x) = (Q, i, T, d).
1. Q - набор всех префиксов х, Q = { e, x0, x0,1, ... , x0,m - 2, x};
2. i = e
3. T = { x }
4. Для q из Q и a из S, (q, a, qa) принадлежит d, если qa - также префикс x. В противном случае (q, a, p) принадлежит d, такое, что p - длиннейший суффикс qa, являющийся префиксом x.
После построения автомата, процесс поиска состоит в проходе по тексту и изменению состояний автомата. Каждый раз, когда достигнуто конечное состояние, мы имеем местонахождение образца.
Code
void AUT(char *y, char *x, int n, int m)
{
int i, j, delta[XSIZE][ASIZE];
/* Preprocessing *.
memset(delta, 0, ASIZE*sizeof(int));
for (j=0; j < m; j++) {
i=delta[j][x[j]];
delta[j][x[j]]=j+1;
memcpy(delta[j+1], delta[i], ASIZE*sizeof(int));
}
/* Searching */
j=0;
for (i=0; i < n; i++) {
j=delta[j][y[i]];
if (j >= m) OUTPUT(i-m+1);
}
}
Алгоритм Карпа-Рабина
Хеширование может позволить нам избежать квадратичного количества сравнений символов в обычных ситуациях. Вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые 'напоминают' образец. Для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию хеширования. Она должна удовлетворять следующим требованиям:
1. Легко вычисляться.
2. Как можно лучше различать несовпадающие строки.
3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ] ):
hash( y[ i+1 , i+m ] ) = rehash( y[ i ], y[ i+m ], hash( y[ i , i+m-1]).
Пусть наша функция будет определена для слова w, например, следующим образом:
hash( w[ 0 , m-1 ] ) = ( w[0] * 2 (в степени m-1) + w[1] * 2(в степени m-2) + ... + w[m-1] ) mod q,
где q - большое число. Тогда
rehash( a, b, h ) = (( h - a * 2 m-1 ) * 2 + b) mod q.
Во время поиска х будем сравнивать hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно. Если обнаруживаем совпадение, то проверяем посимвольно.
Наихудший случай O( n * m ) встретится, например, при поиске a (в степени m) в a (в степени n).
Code
/*
Here all the modulo multiplications by 2 are made using shifts.
So q = max integer avianable
*/
#define REHASH( a, b, h ) ((( h - a * d ) << 1 ) + b )
void KR( char *y, char *x, int n, int m ) {
int hy, hx, d, i;
/*
Preprocessing
computes d = 2^( m-1 ) with the left-shift operator
*/
d = 1;
for ( i = 1; i < m; i++ ) d = ( d << 1 );
hy = hx = 0;
for ( i = 0; i < m; i++) {
hx = ( ( hx << 1 ) + x[i] );
hy = ( ( hy << 1 ) + y[i] );
}
/* Searching */
for ( i=m; i < n; i++ ) {
if ( hy == hx && memcmp( &y[ i-m-1 ], x, m ) == 0 ) OUTPUT( i-m );
hy = REHASH( y[i-m], y[i], hy );
}
}
Алгоритм Сдвига-Или
Code
void SO( char *y, char *x, int n, int m )
{
unsigned int j, state, lim, first, initial;
unsigned int T[ASIZE];
int i;
if ( m > WORD ) ERROR( "Use pattern size <= word size" );
/* Preprocessing */
for ( i=0; i < ASIZE; i++ ) T[i] =~0;
lim=0;
for ( i=0, j=1; i < m; i++, j <<=1 ) {
T[x[i]]&=~j;
lim|=j;
}
lim=~( lim >> 1 );
/* Searching */
state=~0;
for ( i=0; i < n; i++ ) {
state = ( state << 1 ) | T[y[i]];
if ( state < lim ) OUTPUT( i-m+1 );
}
}
Алгоритм Морриса-Пратта
Этот алгоритм появился в результате тщательного анализа алгоритма грубой силы. Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования ( алгоритм грубой силы ее просто выбрасывает ;-( ).
Итак, давайте и мы взглянем на него поближе. Оказывается, размер сдвига образца можно увеличить, одновремеменно запомнив части текста, совпадающие с образцом. Это позволит нам избежать ненужных сравнений и, тем самым, резко увеличить скорость поиска.
Рассмотрим сравнение на позиции i, где образец x[ 0, m - 1 ] сопоставляется с частью текста y[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между y[ i + j ] и x[ j ] , где 1 < j < m. Тогда y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u и a = y[ i + j ] =/= x[ j ] = b.
При сдвиге вполне можно ожидать, что префикс образца u сойдется с каким-нибудь суффиксом подслова текста u. Наиболее длинный такой префикс - граница u ( Он встречается на обоих концах u ). Это приводит нас к следующему алгоритму: пусть mp_next[ j ] - длина границы x[ 0, j - 1 ]. Тогда после сдвига мы можем возобновить сравнения с места y[ i + j ] и x[ j - mp_next[ j ] ] без потери возможного местонахождения образца. Таблица mp_next может быть вычислена за O( m ) перед самим поиском. Максимальное число сравнений на 1 символ - m
Code
/* Preprocessing */
void PRE_MP( char *x, int m, int mp_next[] ) {
int i, j;
i=0;
j=mp_next[0]=-1;
while ( i < m ) {
while ( j > - 1 && x[i] != x[j] ) j=mp_next[j];
mp_next[++i]=++j;
}
}
void MP( char *x, char *y, int n, int m ) {
int i, j, mp_next[XSIZE];
/* Preprocessing */
PRE_MP(x, m, mp_next );
/* Searching */
i=j=0;
while ( i < n ) {
while ( j > -1 && x[j] != y[i] ) j=mp_next[j];
i++;
j++;
if ( j >= m ) {
OUTPUT( i - j );
j = mp_next[ j ];
}
}
}
Алгоритм Кнута-Морриса-Пратта
Этот алгоритм был получен благодаря глубокому анализу алгоритма Морриса-Пратта. Итак, посмотрим, что еще можно сделать, чтобы увеличить размер сдвига.
Рассмотрим сравнение на позиции i, где образец x[ 0, m - 1 ] сопоставляется с частью текста y[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между y[ i + j ] и x[ j ] , где 1 < j < m. Тогда y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u и a = y[ i + j ] =/= x[ j ] = b.
При сдвиге вполне можно ожидать, что префикс образца u сойдется с каким-нибудь суффиксом подслова текста u. Более того, если мы хотим избежать выявления другого несовпадения ( то есть не тратить на это операцию сравнения ;-) ), буква, находящаяся за префиксом v в образце должна отличаться от b. Наиболее длинный такой префикс v называется границей u ( он встречается по обоим сторонам u ).
Это приводит к следующему алгоритму: пусть kmp_next[ j ] - длина длиннейшей границы x[ 0, j - 1 ], за которой следует символ c, отличающийся от x[ j ]. Тогда после сдвига мы можем возобновить сравнения между символами y[ i + j ] и x[ j - kmp_next[ j ] ] без возможной потери местонахождения образца. Таблица kmp_next может быть вычислена за O( m ) перед поиском через применение этого же алгоритма поиска к самому образцу ( т.е y = x ). При этом максимальное количество сравнений для одного символа текста - logФ( m ), где Ф - золотое сечение: ( корень из 5 + 1 ) / 2.
Code
/* Preprocessing */
void PRE_KMP( char *x, int m, int kmp_next[] ) {
int i, j;
i=0;
j=kmp_next[0]=-1;
while ( i < m ) {
while ( j > -1 && x[ i ] != x[ j ] ) j=kmp_next[ j ];
i++;
j++;
if ( x[ i ] == x[ j ] ) kmp_next[i]=kmp_next[j];
else kmp_next[ i ] = j;
}
}
void KMP( char *x, char *y, int n, int m ) {
int i, j, kmp_next[XSIZE];
/* Preprocessing */
PRE_KMP(x, m, kmp_next );
/* Searching */
i=j=0;
while ( i < n ) {
while ( j > -1 && x[ j ] != y[ i ] ) j = kmp_next[ j ];
i++;
j++;
if ( j >= m ) {
OUTPUT( i - j );
j = kmp_next[ j ];
}
}
}
Алгоритм Боуера-Мура
Code
/* 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 ) );
}
}
Алгоритм Хорспула
Code
void HORSPOOL( char *y , сhar *x ,int n , int m )
{
int a, i, j, bm_bc[ ASIZE ];
char ch, lastch;
/* Preprocessing */
for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m;
for ( j=0; j < m-1; j++ ) bm_bc[ x[ j ] ] = m - j - 1;
/* Searching */
lastch = x[ m-1 ];
i = 0;
while ( i <= n-m ) {
ch = y[ i + m - 1 ];
if ( ch == lastch )
if ( memcmp( &y[ i ], x, m-1 ) == 0 ) OUTPUT( i );
i += bm_bc[ ch ];
}
}
Быстрый поиск
Code
void QS( char *y, char *x, int n, int m)
{
int i, qs_bc[ ASIZE ];
/* Preprocessing */
for ( i = 0; i < ASIZE; i++ ) qs_bc[ i ] = m + 1;
for ( i = 0; i < m; i ++ ) qs_bc[ x[i] ] = m - i;
/* Searching */
i = 0;
while ( i <= n - m ) {
if ( memcmp( &y[ i ], x, m ) == 0 ) OUTPUT( i );
i += qs_bc[ y[ i + m ] ]; /* shift */
}
}