[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: Ledi_Gaga  
Форум » Программирование » С++/С# » Алгоритмы поиска (примеры реализации на с++)
Алгоритмы поиска
_Hz_Дата: Пятница, 26.02.2010, 22:37 | Сообщение # 1
Генералиссимус
Группа: Администраторы
Сообщений: 179
Награды: 11
Репутация: 7
Статус: Offline
Термины не обязательно запоминать: будут в алгоритме - вернетесь.
Искомый образец - строка 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 */
   }
}


 
_Hz_Дата: Среда, 17.03.2010, 22:09 | Сообщение # 2
Генералиссимус
Группа: Администраторы
Сообщений: 179
Награды: 11
Репутация: 7
Статус: Offline
Программа на C# с реализацией нескольких алгоритмов поиска

Доступно только для пользователей


 
_Hz_Дата: Суббота, 24.04.2010, 13:28 | Сообщение # 3
Генералиссимус
Группа: Администраторы
Сообщений: 179
Награды: 11
Репутация: 7
Статус: Offline
Поиск подстроки в строке (простой поиск, метод Боейра-Мура, метод Кнута-Морриса-Пратта)

Доступно только для пользователей


 
Форум » Программирование » С++/С# » Алгоритмы поиска (примеры реализации на с++)
  • Страница 1 из 1
  • 1
Поиск: