Довольно давно на одной из презентаций выпускников одной из так называемых ИТ-академий докладчика спросили о деталях реализации поиска подстроки в строке толи в 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.
Удачи!:)