Pull to refresh

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

Reading time 4 min
Views 8.1K
Довольно давно на одной из презентаций выпускников одной из так называемых ИТ-академий докладчика спросили о деталях реализации поиска подстроки в строке толи в 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.

Удачи!:)
Tags:
Hubs:
+49
Comments 10
Comments Comments 10

Articles