Довольно давно на одной из презентаций выпускников одной из так называемых ИТ-академий докладчика спросили о деталях реализации поиска подстроки в строке толи в 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) миксом алгоритмов Бойера — Мура и Хорспула с несколькими усовершенствованиями и упрощениями. Алгоритм также использует фильтр Блума.
И так, поехали. Заголовок функции:
Всё вроде ясно. Посмотрим на define операторы:
Как работает эта реализация блум-фильтров. Каждому символу на основание его последних log(STRINGLIB_BLOOM_WIDTH) битов ставится в соответствие некоторое число. Например, для a это 1:
Для q — 17:
С помощью логического «ИЛИ» STRINGLIB_BLOOM_ADD накапливает информацию об увиденных символах в фильтре mask. Позже с помощью STRINGLIB_BLOOM можно проверить, добавлялся ли символ к фильтру. Конечно, у этой проверки могут быть false positives (STRINGLIB_BLOOM возвращает не 0, но символа на самом деле нет в строке\фильтре):
Но она довольно дешёвая и помогает сократить число сравнений.
Теперь можно перейти к самому алгоритму. Очевидная логика для случаев m > n и m <= 1:
и (часть кода опущена, что бы не рвать статью):
После у нас появляются несколько новых переменных и заполняется маска для искомой подстроки:
skip — некоторое число, по умолчанию равно индексу последнего символа искомой строки минус 1. Если же в строке есть символы, равны последнему, то skip равен разнице между индексами последнего с них и последнего символа строки.
Описание идеи основного алгоритма с Википедии:
Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.
Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.
Собственно реализация этого описания (выше w = n — m):
Немного визуализации. Пусть работаем со строкой «барабан» и ищем подстроку «аба»:
Ну вот и всё.
Если Вам понравилось, в исходниках Python есть ещё куча мест, в которых интересно покопатся. Например — реализация list.sort в Objects/listobject.c или dict.get в Objects/dictobject.c.
Удачи!:)
Прошло время, 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
Для q — 17:
>>> 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.
Удачи!:)
