Поиск подстрок с помощью дерева цифрового поиска

Теория

Задача: имеется два больших (100 000+) списка строк, и требуется отфильтровать первый список (Source List) таким образом, чтобы в нем остались только строки, содержащие подстроки из второго списка (Search List).

Решать эту задачу будем следующим образом: для каждой строки Z из Source List будем искать строку S из Search List, такую, что S является подстрокой Z.

Примитивный алгоритм

Можно решить задачу нахождения подстроки из списка Search List при помощи следующего очевидного (примитивного), но крайне медленного алгоритма: будем последовательно перебирать все строки S из Search List до тех пор, пока не окажется, что S является подстрокой Z. При этом, алгоритм поиска подстроки в строке можно использовать либо примитивный, либо один из более продвинутых (например, Бойера-Мура, см. https://ru.wikipedia.org/wiki/Поиск_подстроки). Однако, использование более быстрого алгоритма поиска подстроки в строке не сильно ускоряет поиск подстроки из списка, т.к. все-равно требуется перебрать в среднем N/2 строк (здесь N - количество строк в Search List).

Дерево цифрового поиска

Дерево цифрового поиска (также бор, Trie, Префиксное дерево) - структура данных, которая используется для осуществления поразрядного поиска. Каждый узел дерева содержит значение одного “разряда” (в нашем случае - строковый символ). Вся строка представлена последовательностью узлов от корня до листа дерева. Пример - дерево цифрового поиска для строк A, ABA, ABB, ABBA, ABC, BAC, BC: 

    [ROOT NODE]
    /         \
   A           B
  / \         / \
{0}  B       A   C
   / | \    /
  A  B  C  C
    / \
  {0}  A

Почитать про эту структуру можно, например, тут: https://en.wikipedia.org/wiki/Trie.

Алгоритм A1 поиска префикса строки S по дереву:

1. Пусть L = длина строки S.
2. Если L = 0 (“пустая” строка), то выход: префикс не найден.
3. Если дерево не содержит узлов (“пустое” дерево), то выход: префикс не найден.
4. Терминальный узел T = NULL.
5. Текущий узел P = корень дерева ( [ROOT NODE] ).
6. Цикл по K = 1..L:
7.   Если у текущего узла нет дочернего, соответствующего символу S[K], то выход из цикла.
8.   Текущий узел P = дочерний, узел, соответствующий символу S[K].
9.   Если у узла P есть дочерний узел с терминальным символом {0}, то присваиваем его T.
10. Конец цикла.
11. Если узел P - лист, то выход: префикс найден.
12. Если T не равно NULL, то выход: префикс найден.
13. Префикс не найден.

В качестве терминального символа {0} как правило используется символ NUL с ASCII-кодом 0, который не может встретиться в строке.

Алгоритм A2 поиска подстроки строки S по дереву.

1. Пусть L = длина строки S.
2. Если L = 0 (“пустая” строка), то выход: подстрока не найдена.
3. Если дерево не содержит узлов (“пустое” дерево), то выход: подстрока не найдена.
4. Цикл по K = 1..L:
5.  Пусть Sk - суффикс строки S, начиная с K-го символа (суффикс длины L-K+1).
6.  Используем алгоритм A1 для поиска префикса строки Sk по дереву; если префикс найден, то выход: подстрока найдена.
7. Конец цикла.
8. Подстрока не найдена.

В алгоритмах A1 и A2 использованы определения префикса и суффикса строки из статьи: https://ru.wikipedia.org/wiki/Подстрока. По-простому: префикс строки длины X - это первые X символов строки, суффикс строки длины Y - последние Y символов строки.

Построение дерева цифрового поиска

Обозначения:

N - количество строк.
Si - i-я строка, i = 1..N.
Li - длина i-ой строки.
[ROOT NODE] - корневой узел.

Построение дерева цифрового поиска:

1. Сортировка списка строк по возрастанию, удаление дубликатов.
2. Вызов рекурсивной процедуры R( [ROOT NODE], 1, 1, N).

Рекурсивная процедура R (параметры: P - узел-родитель, K - позиция текущего символа, I0, J0 - индексы строк; I0<=J0):

1. Индекс i = I0.
2. Если K > Li и i = J0, то выход из процедуры R.
3. Если K <= Li, то символ C = Si[K], иначе C = {0}.
4. Создать X = узел (C, P).
5. Индекс j = i.
6. Цикл:
7.      Если j = J0 или S(j+1)[K] не равно C, то:
8.        Вызвать R (X, K+1, i, j)
9.        Если j = J0, то выход из цикла.
10.      i = j+1.
10.      C = Si[K].
11.      Создать X = узел (C, P).
12.    Конец если.
13.    j = j + 1.
14. Конец цикла.

См. иллюстрацию на Python: http://blog.coolsoftware.ru/2016/03/blog-post_23.html.

Оптимизация (сжатие)

Под-деревья, узлы которых содержат не более одного потомка, можно объединить в один узел - см. узел (AC) в примере ниже. 

    [ROOT NODE]
    /         \
   A           B
  / \         / \
{0}  B      (AC) C
   / | \
  A  B  C
    / \
  {0}  A

Реализация на Delphi: https://github.com/optinsoft/SearchStrings

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru