https://wikicshse.ru/index.php?action=history&feed=atom&title=%D0%A3%D0%BC%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BE%D0%B1%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B8_%D1%81%D1%82%D1%80%D0%BE%D0%BA_%D0%B2_ClickHouse 2026-06-06T16:01:09Z История изменений этой страницы в вики MediaWiki 1.45.3 https://wikicshse.ru/index.php?title=%D0%A3%D0%BC%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BE%D0%B1%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B8_%D1%81%D1%82%D1%80%D0%BE%D0%BA_%D0%B2_ClickHouse&diff=1018&oldid=prev 2018-10-15T11:54:39Z

<p>Новая страница: «{{Карточка_командного_проекта |name=Умные алгоритмы обработки строк в ClickHouse |company=Яндекс |seme…»</p> <p><b>Новая страница</b></p><div>{{Карточка_командного_проекта<br /> |name=Умные алгоритмы обработки строк в ClickHouse<br /> |company=Яндекс<br /> |semester=Осень 2018<br /> |course=3-4<br /> |number_of_students=?<br /> |categorize=yes<br /> }}<br /> <br /> <br /> ClickHouse как правило используется в сценариях, когда построение полноценного обратного индекса для текстового поиска, нецелесообразно. Это - большое количество мелких строк. В этом случае, объём полноценного индекса может быть больше объёма исходных данных, и в случаях, когда объём данных существенно превышает объём оперативки, его поддержка становится непрактичной.<br /> <br /> Не смотря не это, ClickHouse часто используется в сценариях, предполагающих поиск по тексту. Например, для этого в ClickHouse реализован эффективный (brute-force) поиск подстроки в строке. Но многих алгоритмов не хватает.<br /> <br /> 1. Для начала, сделаем эффективную проверку наличия любой из (явно заданного) множества подстрок. Как вы уже знаете, для этого есть такие алгоритмы как Aho-Corasick, Rabin-Karp. Но мы попробуем сделать кое что ещё лучше, и использовать алгоритм multi-Volnitsky, который ещё никто не реализовывал.<br /> <br /> 2. Для brute-force поиска подстроки в строке, нужно по крайней мере прочитать те строки (haystack), в которых мы хотим искать. А можно ли сделать какую-нибудь выжимку из haystack, чтобы проверять гипотезу наличия подстроки быстрее? Мы попробуем добавить в ClickHouse функцию, которая построит для строки триграмный bloom filter. Полученную выжимку можно будет записать в отдельный столбец, чтобы быстрее его сканировать, и исключать сканирование исходных строк в большинстве случаев. А может быть, вы сможете придумать трюки с суффиксными массивами.<br /> <br /> 3. Для одной из задач нам нужно locality-sensitive хэширование строк. Это такая хэш-функция, которая при небольших изменениях аргумента, как правило, не меняется. Для этого реализуем хорошо оптимизированный алгоритм min-hash. https://en.wikipedia.org/wiki/MinHash</div>

imported>Aapoludnitsin