 |
Поиск в строках, массивах, последовательностях:
Точный поиск подстроки в строке.
Турбо - обращенние сегмента.
Перевод с английского - Кантор И.
Этот алгоритм является улучшением 'алгоритма обращенного сегмента' уменьшающим наибольшее число сравнений до 2*n. В самом деле, достаточно запомнить префикс u (x), который совпал во время прошлой попытки. Тогда во время текущей попытки при достижении правого конца u, легко доказать, что достаточно прочитать заново не более, чем правую половину u. Это и заложено в алгоритме турбо-обращения сегмента.Пусть слово z - сегмент слова w.
Oпределим смещение disp( z, w) - от англ. displacement как положительное целое число, такое что
w [ m - d - |z| - 1 , m - d ] = z.
Типичная для TRF-алгоритма ( Turbo Reverse Factor - о чем мы говорим) ситуация возникает, когда префикс u был найден при прошлой попытке, а сейчас алгоритм пытается сравнить сегмент v длины m - |u| с текстом сразу справа за u. Точка между u и v называется 'точкой принятия решения'. Если v не является сегментом x, то сдвиг вычисляется, как в простом алгоритме обращенного сегмента.
Если v - суффикс x, тогда мы нашли x, а если v - не суффикс, но сегмент x, то достаточно просмотреть заново min( per( u ) , |u| / 2 ) правых символов u. Если u - периодичное ( т.е per( u ) <= |u| / 2 ), то пусть z - суффикс u длины per( u ). По определению периода, z - непериодичное слово, а значит следующее наложение невозможно:
Таким образом, z может появиться в u лишь на расстоянии, кратном per( u ), и следовательно, наименьший подходяший суффикс uv, являющийся префиксом x имеет длину |uv| - disp( zv , x ) = m - disp( zv , x ), значит, длину сдвига можно положить равной disp( zv , x ).
Если u - не периодичное: per( u ) > |u| / 2, то очевидно, что x не может появиться второй раз в левой части u длины per( u ). А значит, достаточно будет просмотреть правую часть u длины |u| - per( u ) < |u| / 2, чтобы найти неопределенный переход автомата. Функция disp реализована непосредственно в автомате S( x ) без увеличения сложности его построения.
Турбо алгоритм обращения сегмента производит в худшем случае 2*n сравнений и в среднем оптимален.
Реализация на Си
struct Arrow {
int target, shift;
};
struct State {
int length, suf, pos;
char terminal;
};
typedef struct Arrow ARROW;
typedef struct State STATE;
int state_counter;
int next[ XSIZE + 1 ];
/* Creates and returns a clone of state p. */
int COPY ( int p , STATE *states , ARROW trans[ XSIZE ][ ASIZE ])
{
int r;
r = state_counter++;
memcpy( trans[ r ] , trans[ p ] , ASIZE * sizeof( ARROW ));
states[ r ].suf = states[ p ].suf;
states[ r ].pos = states[ p ].pos;
return (r);
}
/* Creates the suffix automation for the reverse of the word x and */
/* returns its initial state. */
int SUFF( char *x, int m, STATE *states, ARROW trans[ XSIZE ][ ASIZE ])
{
int i, art, init, last, p, q, r;
char a;
art = state_counter++;
init = state_counter++;
states[ init ].suf = art;
last = init;
for ( i = m - 1; i >= 0; --i) {
a = x[ i ];
p = last;
q = state_counter++;
states[ q ].length = states[ p ].length + 1;
states[ q ].pos = states[ p ].pos + 1;
while ( p != init && trans[ p ][ a ].target == 0 ) {
trans[ p ][ a ].target = q;
trans[ p ][ a ].shift = states[ q ].pos - states[ p ].pos - 1;
p = states[ p ].suf;
}
if ( trans[ p ][ a ].target == 0 ) {
trans[ init ][ a ].target = q;
trans[ init ][ a ].shift = states[ q ].pos - states[ init ].pos - 1;
states[ q ].suf = init;
}
else
if ( states[ p ].length + 1 == states[ trans[ p ][ a ].target ].length)
states[ q ].suf = trans[ p ][ a ].target;
else {
r = COPY( trans[ p ][ a ].target , states, trans );
states[ r ].length = states[ p ].length + 1;
states[ trans[ p ][ a ].target ].suf = r;
states[ q ].suf = r;
while ( p != art && states[ trans[ p ][ a ].target ].length >= states[ r ].length) {
trans[ p ][ a ].shift = states[ trans[ p ][ a ].target ].pos - states[ p ].pos - 1;
trans[ p ][ a ].target = r;
p = states[ p ].suf;
}
}
last = q;
}
states[ last ].terminal = 1;
p = last;
while ( p != init ) {
p = states[ p ].suf;
states[ p ].terminal = 1;
}
return ( init );
}
/* Computation of the Morris and Pratt next function */
int MP( char *x, int m, int mp_next[])
{
int i, j;
i = 1;
j = 0;
mp_next[ 0 ]= -1;
while ( i < m )
if ( j > -1 && x[ i ] != x[ j ])
if ( j ) j = mp_next[ j-1 ] + 1;
else j = -1;
else mp_next[ i++ ] = j++;
for ( i = 0; i < m; ++i ) mp_next[ i ] = i - mp_next[ i ];
return 0;
}
/* Turbo Reverse Factor algorithm. */
void TRF( char *y, char *x, int n, int m)
{
int period, i, j, shift, u, period_of_u, disp, init, state, state_aux, mu;
STATE states[ 2 * XSIZE + 2 ];
ARROW trans[ XSIZE ][ ASIZE ];
/* Preprocessing */
memset( trans, 0, 2 * ( m + 2 ) * ASIZE * sizeof ( ARROW ) );
memset( states, 0, 2 * ( m + 2 ) * sizeof( STATE ) );
state_counter = 1;
init = SUFF( x , m , states , trans );
MP ( x, m, next );
period = next [ m - 1 ];
i = period_of_u = 0;
shift = m;
/* Searching */
while ( i <= n - m ) {
j = m - 1;
state = init;
u = m - 1 - shift;
shift = m;
disp = 0;
while ( j > u && ( state_aux = trans[ state ][ y[ i+j ] ].target) != 0 ) {
disp += trans[ state ][ y[ i+j ] ].shift;
state = state_aux;
if ( states[ state ].terminal ) shift = j;
j--;
}
if ( j > u ) period_of_u = ( shift != m ? next[ m - 1 - shift ] : 0 );
else if ( !disp ) {
OUTPUT (i);
shift = period;
period_of_u = ( shift != m ? next[ m - 1 - period ] : 0 );
}
else {
mu = ( u + 1 ) / 2;
if ( period_of_u <= mu ) {
u -= period_of_u;
while ( j > u && ( state_aux = trans[ state ][ y[ i+j ] ].target) != 0) {
disp += trans[ state ][ y[ i+j ] ].shift;
state = state_aux;
if ( states[ state ].terminal ) shift = j;
j--;
}
if ( j > u ) period_of_u = ( shift != m ? next[ m - 1 - shift ] : 0 );
else {
shift = disp;
period_of_u = next[ m - 1 - disp ];
}
}
else {
u -= mu;
--u;
while ( j > u && ( state_aux = trans[ state ][ y[ i+j] ].target) !=0 ) {
disp += trans[ state ][ y[ i+j ] ].shift;
state=state_aux;
if ( states[ state ].terminal ) shift = j;
j--;
}
period_of_u = ( shift != m ? next[ m - 1 - shift ] : 0 );
}
}
i+=shift;
}
}