Умные алгоритмы обработки строк в ClickHouse

Компания	Яндекс
Учебный семестр	Осень 2018
Учебный курс	3-4-й курс
Максимальное количество студентов, выбравших проект: ?

ClickHouse как правило используется в сценариях, когда построение полноценного обратного индекса для текстового поиска, нецелесообразно. Это - большое количество мелких строк. В этом случае, объём полноценного индекса может быть больше объёма исходных данных, и в случаях, когда объём данных существенно превышает объём оперативки, его поддержка становится непрактичной.

Не смотря не это, ClickHouse часто используется в сценариях, предполагающих поиск по тексту. Например, для этого в ClickHouse реализован эффективный (brute-force) поиск подстроки в строке. Но многих алгоритмов не хватает.

1. Для начала, сделаем эффективную проверку наличия любой из (явно заданного) множества подстрок. Как вы уже знаете, для этого есть такие алгоритмы как Aho-Corasick, Rabin-Karp. Но мы попробуем сделать кое что ещё лучше, и использовать алгоритм multi-Volnitsky, который ещё никто не реализовывал.

2. Для brute-force поиска подстроки в строке, нужно по крайней мере прочитать те строки (haystack), в которых мы хотим искать. А можно ли сделать какую-нибудь выжимку из haystack, чтобы проверять гипотезу наличия подстроки быстрее? Мы попробуем добавить в ClickHouse функцию, которая построит для строки триграмный bloom filter. Полученную выжимку можно будет записать в отдельный столбец, чтобы быстрее его сканировать, и исключать сканирование исходных строк в большинстве случаев. А может быть, вы сможете придумать трюки с суффиксными массивами.

3. Для одной из задач нам нужно locality-sensitive хэширование строк. Это такая хэш-функция, которая при небольших изменениях аргумента, как правило, не меняется. Для этого реализуем хорошо оптимизированный алгоритм min-hash. https://en.wikipedia.org/wiki/MinHash