Как я ускорял strstr

в 8:33, , рубрики: алгоритм, Алгоритмы, поиск подстроки в строке, Программирование, Си

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

График сравнения скорости работы моего алгоритма, с функцией strstr на 600 кб тексте русскоязычной книги, при поиске строк размером от 1 до 255 байт:

image

Идея лежащая в основе алгоритма следующая. Сперва обозначения:

S — Строка в которой будет производится поиск будет называться
P — строка, которую ищем будет называться
sl — длинна строки S
pl — длинна строки P
PInd — табличка составляемая на первом этапе.

Итак идея такая: Если в строке S выбирать элементы с индексами равными: pl1, pl2,..., plJ,..., pl(sl/pl), то если в отрезок pl(J-1)...pl(J+1) входит искомая строка P, то тогда выбранный элемент должен принадлежать принадлежать строке P. Иначе строка бы не вписывалась по длине.

Картинка, где нарисовано до куда дотягивается P, в pl*3.:

image

И ещё, так как выбранный элемент входит в строку P обычно маленькое число раз, то можно проверять только эти вхождения, а не весь диапазон.

Итого алгоритм такой:

Этап 1. Сортировка P

Для всех элементов(символов) строки P сортируем индексы этих элементов по значению этих элементов. То есть делаем так, что-бы все номера всех элементов равных какому-то значению, можно было быстро получить. Эта табличка будет дальше называться PInd:

image

Как видно из этой таблички, при поиске на этапе 2 при искомой строке P равной "сортировать индексы" нам понадобится проверять максимум 2 варианта подстрок в S.

Сначала я для составления этой таблички использовал быструю сортировку и какую-то ещё, а потом я сообразил, что так как элементы строки однобайтовые, то можно использовать поразрядную.

Этап 2. Поиск

Проходим по строке строке S скачками равными pl, выбирая соответствующие элементы. Для каждого выбранного элемента проверяем входит ли он в строку P.

Если входит, то для всех индексов из PInd соответствующего элемента, проверяем совпадает ли подстрока S с началом в соответствующим индексу из PInd смещением относительно выбранного элемента и искомая строка P.

Если совпало, то возвращаем результат, если нет то продолжаем.

Худший вариант для этого алгоритма, зависит от способа сравнения строк во втором этапе. Если простое сравнение, то sl*pl+pl, если какой-то ещё, то другой. Я использовал просто сравнение, как в обычном strstr.

За счёт того, что алгоритм скачет через pl элементов и проверяет только возможные строки он работает быстрее.

Лучший вариант, это когда алгоритм проскачет всю строку S и не найдёт текст или найдёт с первого раза, тогда потратит примерно sl/pl.
Среднюю скорость я не знаю как подсчитать.

Вот одна из моих реализаций этого алгоритма, по которой строился график на языке си. Здесь pl ограничено, то есть таблица PInd строится по префиксу P длинны max_len, а не по всей строке. Именно он использовался при построении графика:

Вот закодированный на си

char * my_strstr(const char * str1,  const char * str2,size_t slen){
    unsigned char max_len = 140;
    if ( !*str2 )
        return((char *)str1);
    //Очистка массивов
    unsigned char index_header_first[256];
    unsigned char index_header_end[256];
    unsigned char next_char[256];
    unsigned char sorted_index[256];
    memset(index_header_first,0x00,sizeof(unsigned char)*256);
    memset(index_header_end,0x00,sizeof(unsigned char)*256);
    memset(next_char,0x00,sizeof(unsigned char)*256);
    memset(sorted_index,0x00,sizeof(unsigned char)*256);
    //Этап 1.
    char *cp2 = (char*)str2;
    unsigned char v;
    unsigned int len =0;    
    unsigned char current_ind = 1;
    while((v=*cp2) && (len<max_len)){
        if(index_header_first[v] == 0){
            index_header_first[v] = current_ind;
            index_header_end[v] = current_ind;
            sorted_index[current_ind] = len;
        }
        else{
            unsigned char last_ind = index_header_end[v];
            next_char[last_ind] = current_ind;
            index_header_end[v] = current_ind;
            sorted_index[current_ind] = len;
        }
        current_ind++;
        len++;
        cp2++;
    }
    if(len > slen){
        return NULL;
    }
    //Этап 2.
    unsigned char *s1, *s2;
    //Начинаем проверку с элемента S+pl-1
    unsigned char *cp = (unsigned char *) str1+(len-1);
    unsigned char *cp_end= cp+slen;
    while (cp<cp_end){
        unsigned char ind = *cp;
        //Если выбранный элемент есть в строке P
        if( (ind = index_header_first[ind]) ) {
            do{
                //Тогда проверяем все возможные варианты с участием этой буквы
                unsigned char pos_in_len = sorted_index[ind];
                s1 = cp - pos_in_len;
                if((char*)s1>=str1)
                {
                    //Сравниваем строки
                    s2 = (unsigned char*)str2;
                    while ( *s2 && !(*s1^*s2) )
                        s1++, s2++;
                    if (!*s2)
                        return (char*)(cp-pos_in_len);
                }
            }
            while( (ind = next_char[ind]) );
        }
        //Прыгаем вперёд на pl
        cp+=len;
    }
    return(NULL);
}

Автор: MyNickFree

Источник

Поделиться новостью

* - обязательные к заполнению поля