Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Точный поиск подстроки в строке /
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
Турбо - обращенние сегмента

Этот алгоритм является улучшением 'алгоритма обращенного сегмента' уменьшающим наибольшее число сравнений до 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 - непериодичное слово, а значит следующее наложение невозможно:


Иллюстрация 1




Таким образом, 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;
int 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;
}
}




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

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь