Поиск в строке. Реализация в CPython

    Довольно давно на одной из презентаций выпускников одной из так называемых ИТ-академий докладчика спросили о деталях реализации поиска подстроки в строке толи в Java, толи в .Net. Выпускник конечно не смог ничего вразумительного ответить, а я отложил вопрос в и без того длинный todo-лист.

    Прошло время, Python стал для меня актуальней enterprise платформ, так что вашему вниманию разбор алгоритма поиска подстроки в Python.

    Реализацию объекта string можно найти здесь — Objects/stringobject.c . Определение функций, которые отвечают за разные виды поиска (find, rfind, __contains__) — Objects/stringlib/find.h. Все эти функции (вместе с split, replace и т.п.) используют поиск, реализованный в Objects/stringlib/fastsearch.h. Им мы и займёмся.

    Собственно сам алгоритм назван (The stringlib Library) автором (Fredrik Lundh) миксом алгоритмов Бойера — Мура и Хорспула с несколькими усовершенствованиями и упрощениями. Алгоритм также использует фильтр Блума.

    И так, поехали. Заголовок функции:
    fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n,
               const STRINGLIB_CHAR* p, Py_ssize_t m,
               Py_ssize_t maxcount, int mode)
    
        /* s - строка, в которой ищем,
           n - её длина,
           p - подстрока, которою ищем (часто называемая шаблоном),
           m - её длина,
           maxcount - максимальное значения для счетчика, если просто считаем сколько раз встречается подстрока,
           mode - просто поиск/поиск с конца/подсчет количества вхождений подстроки */
    

    Всё вроде ясно. Посмотрим на define операторы:
    /* Вот и определения для параметра mode */
    #define FAST_COUNT 0
    #define FAST_SEARCH 1
    #define FAST_RSEARCH 2
    
    /* STRINGLIB_BLOOM_WIDTH в зависимости от платформы\(обычная строка или юникод) 
    может принимать значения 32, 64, 128 */
    
    #define STRINGLIB_BLOOM_ADD(mask, ch)   ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
    
    #define STRINGLIB_BLOOM(mask, ch)   ((mask &  (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
    

    Как работает эта реализация блум-фильтров. Каждому символу на основание его последних log(STRINGLIB_BLOOM_WIDTH) битов ставится в соответствие некоторое число. Например, для a это 1:
    >>> ord('a') & 31
    1
    

    Для q17:
    >>> ord('q') & 31
    17
    

    С помощью логического «ИЛИ» STRINGLIB_BLOOM_ADD накапливает информацию об увиденных символах в фильтре mask. Позже с помощью STRINGLIB_BLOOM можно проверить, добавлялся ли символ к фильтру. Конечно, у этой проверки могут быть false positives (STRINGLIB_BLOOM возвращает не 0, но символа на самом деле нет в строке\фильтре):
    >>> ord(']') & 31
    29
    >>> ord('}') & 31
    29
    

    Но она довольно дешёвая и помогает сократить число сравнений.

    Теперь можно перейти к самому алгоритму. Очевидная логика для случаев m > n и m <= 1:
        w = n - m;
    
        if (w < 0 || (mode == FAST_COUNT && maxcount == 0))
            return -1;
    

    и (часть кода опущена, что бы не рвать статью):
        if (m <= 1) {
            if (m <= 0)
                return -1;
            if (mode == FAST_COUNT) {
                /* ... */
            } else if (mode == FAST_SEARCH) {
                for (i = 0; i < n; i++)
                    if (s[i] == p[0])
                        return i;
            } else {    /* FAST_RSEARCH */
                /* ... */
            }
            return -1;
        }
    

    После у нас появляются несколько новых переменных и заполняется маска для искомой подстроки:
        mlast = m - 1;
        skip = mlast - 1;
        mask = 0;
    
        for (i = 0; i < mlast; i++) {
            STRINGLIB_BLOOM_ADD(mask, p[i]);
            if (p[i] == p[mlast])
                skip = mlast - i - 1;
        }
        STRINGLIB_BLOOM_ADD(mask, p[mlast]);
    

    skip — некоторое число, по умолчанию равно индексу последнего символа искомой строки минус 1. Если же в строке есть символы, равны последнему, то skip равен разнице между индексами последнего с них и последнего символа строки.

    Описание идеи основного алгоритма с Википедии:

    Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

    Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.


    Собственно реализация этого описания (выше w = n — m):
            for (i = 0; i <= w; i++) {
                if (s[i+m-1] == p[m-1]) {
                    /* Возможно, мы нашли конец нашей подстроки */
                    for (j = 0; j < mlast; j++)
                        if (s[i+j] != p[j])
                            break;
                    if (j == mlast) {
                        /* Нашли совпадение! */
                        if (mode != FAST_COUNT)
                            /* Если надо было найти одно совпадение - конец,
                            возвращаем индекс начала совпадения */
                            return i;
                        /*Иначе дальше считаем количество совпадений */
                        count++;
                        if (count == maxcount)
                            return maxcount;
                        i = i + mlast;
                        continue;
                    }
                    /* Хотя один или несколько символов в обоих строках равны,
                    полного совпадения ми не нашли  */
                    /* Используем уже заполнений фильтр и проверяем,
                    находиться ли следующий символ в искомой подстроке */
                    if (!STRINGLIB_BLOOM(mask, s[i+m]))
                        /* Если нет, то мы можем передвинутся вправо на длину всей искомой строки */
                        i = i + m;
                    else
                        /* Если да, то мы можем передвинутся только на шаг 'skip' */
                        i = i + skip;
                } else {
                    /* Не нашли ни одного совпадения. Используем уже заполнений фильтр 
                    и проверяем, находиться ли следующий символ в искомой подстроке */
                    if (!STRINGLIB_BLOOM(mask, s[i+m]))
                        /* Если нет, то мы можем передвинутся вправо на длину всей искомой строки */
                        i = i + m;
                    /* Иначе следующая итерация, i++ */
                }
            }
    

    Немного визуализации. Пусть работаем со строкой «барабан» и ищем подстроку «аба»:
    заполняем фильтр и считаем skip = 1
    
    i = 0:
        ______________
        |б|а|р|а|б|а|н|
             |           - нет совпадения, i++
        _______
        |а|б|а|
    
    i = 1:
        ______________
        |б|а|р|а|б|а|н|
               |         - есть совпадение, смотрим далее
          _______
          |а|б|а|
    
        ______________
        |б|а|р|а|б|а|н|
             |             - нет совпадения. поскольку следующий после "а" символ "б" принадлежит искомой подстроке, используем шаг skip, инкремент с for и получаем i += 2
          _______
          |а|б|а|
    
    i = 3:
        ______________
        |б|а|р|а|б|а|н|
                   |       - есть совпадение, смотрим далее
              _______
              |а|б|а|
    
        ______________
        |б|а|р|а|б|а|н|
                 |         - есть совпадение, смотрим далее
              _______
              |а|б|а|
    
        ______________
        |б|а|р|а|б|а|н|
               |           - есть совпадение, подстрока найдена
              _______
              |а|б|а|
    
    

    Ну вот и всё.

    Если Вам понравилось, в исходниках Python есть ещё куча мест, в которых интересно покопатся. Например — реализация list.sort в Objects/listobject.c или dict.get в Objects/dictobject.c.

    Удачи!:)
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 10
    • –5
      а чему будут равны O(n) и o(n)?
      Спасибо за статью.
      • 0
        — sublinear search behaviour in good cases (O(n/m))
        — no worse than the current algorithm in worst case (O(nm))


        отсюда — effbot.org/zone/stringlib.htm
        • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Немного визуализации....
          а вот за это, отдельное спасибо. Сразу понял как работает.
          • 0
            Отличная статья.
            • +1
              Как насчет utf8 и многбайтных символов?
              • 0
                Я не нашел других реализаций поиска специально для неоднобайтовых кодировок, так что могу предположить что они сравниваются побайтово.
                • 0
                  Слова «STRINGLIB_BLOOM_WIDTH может принимать значения 32, 64, 128» как бы намекают нам, что речь идёт о UCS-4/8/16. UTF можно предварительно преобразовать в UCS, это всего лишь добавит O(n).
                • 0
                  Визуализация отличная. Спасибо.
                  • 0
                    а почему бы не использовать difflib?
                    Пример велосипеда по поиску общей подстроки для двух строк
                    def get_subline(str_first, srt_second):
                        s = difflib.SequenceMatcher(None, str_first, srt_second)
                        match = s.find_longest_match(0, len(str_first), 0, len(srt_second))
                        return str_first[match[0]:match[0]+match[2]].strip()
                    </python>

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.