Sparse Ngrams Devlog. Part 1
Следующие несколько постов, дней, недель я буду много постить о сайд проекте, а именно о GitHub Indexing Codesearch, а именно Sparse Ngrams solutions. Мне надоели Russ Cox trigram индекс и Zoekt. Посмотрим куда приведёт:
https://github.com/danlark1/sparse_ngrams
Основную идею я уже писал в блоге выше, а именно мы должны взять все ngrams, хеши биграм которых на концах больше, чем в середине. Так как хеши не зависят от input, то подстроки будут иметь подмножество такого разбиения. А всего таких ngram не более 2n.
Понятно, что при запросе не надо разбивать таким алгоритмом и в статье GitHub сказано, что
У меня в тесте для
А covering ngrams меньше, они более репрезентативны и должны быстрее отвечать на запрос из-за ngram
Как строятся такие ngrams и coverage? Сначала добавляем все триграмы как мельчайшие единицы. Потом алгоритм в точности является sliding min/max window (LeetCode полезно решать вообще). Когда мы добавляем следующий хеш в стек, надо выкинуть все элементы, которые меньше по хешу из конца. В итоге в первом случае мы когда убираем из стека, мы добавляем этот range ngrams, а во втором случае добавляем все убывающие последовательности. На картинке в статье, к сожалению, ошибка (пропущена "ste"). Covering ngrams в строке "chester " (с пробелом) в этом случае будут "chester ". Потому что пока все значение после девятки меньше девяти, то мы будем добавлять в стек (один раз уберем из стека по ходу, но эту ngram не добавим пока не дойдём до конца), а когда наткнёмся на 7, надо будет всё убрать до начала и в итоге мы найдём очень большую ngram. А для подстроки "chester" (без пробела) covering ngrams будут "che", "hes", "este", "ter". Потому что когда мы дойдём до нулевого хеша, у нас sliding window закончится, и надо обработать хвост. Единственная возрастающая последовательность это "1 2", поэтому добавляем "este", остальное -- обычные триграмы как мельчайшие единицы. Асимптотика -- линейная, потому что добавляем и убираем из стека каждый элемент суммарно не более двух раз.
Алгоритм весь получился на 70 строк кода.
Понятное дело дальше будет интересно, потому что надо будет доводить до инженерного решения. А там шардирование, большие ngram не нужны, фаззинг, тестирование и тд. 70 строк ещё можно математически доказать, дальше не очень.
Мораль: за 70 строк кода написали ядро, нашли ошибку в статье github (не все подстроки имеют разбиение, что все ngrams содержатся в надстроках -- забыли рассказать о деталях), и алгоритмы тоже пригождаются.
Следующие несколько постов, дней, недель я буду много постить о сайд проекте, а именно о GitHub Indexing Codesearch, а именно Sparse Ngrams solutions. Мне надоели Russ Cox trigram индекс и Zoekt. Посмотрим куда приведёт:
https://github.com/danlark1/sparse_ngrams
Основную идею я уже писал в блоге выше, а именно мы должны взять все ngrams, хеши биграм которых на концах больше, чем в середине. Так как хеши не зависят от input, то подстроки будут иметь подмножество такого разбиения. А всего таких ngram не более 2n.
Понятно, что при запросе не надо разбивать таким алгоритмом и в статье GitHub сказано, что
At query time, we use the exact same algorithm, but keep only the covering ngrams, as the others are redundant. Covering ngrams -- такой же алгоритм, только надо удостовериться, нет никакой подстроки другой в множестве.У меня в тесте для
for(int i=42 как раз получается интересная история: всяких ngram много:
"for", "or(", "for(", "r(i", "for(i", "(in", "int", "(int", "nt ", "t i", " i=", "t i=", "i=4", "t i=4", "nt i=4", "(int i=4", "=42"А covering ngrams меньше, они более репрезентативны и должны быстрее отвечать на запрос из-за ngram
=42 и (int i=4."for(i", "(int i=4", "=42"Как строятся такие ngrams и coverage? Сначала добавляем все триграмы как мельчайшие единицы. Потом алгоритм в точности является sliding min/max window (LeetCode полезно решать вообще). Когда мы добавляем следующий хеш в стек, надо выкинуть все элементы, которые меньше по хешу из конца. В итоге в первом случае мы когда убираем из стека, мы добавляем этот range ngrams, а во втором случае добавляем все убывающие последовательности. На картинке в статье, к сожалению, ошибка (пропущена "ste"). Covering ngrams в строке "chester " (с пробелом) в этом случае будут "chester ". Потому что пока все значение после девятки меньше девяти, то мы будем добавлять в стек (один раз уберем из стека по ходу, но эту ngram не добавим пока не дойдём до конца), а когда наткнёмся на 7, надо будет всё убрать до начала и в итоге мы найдём очень большую ngram. А для подстроки "chester" (без пробела) covering ngrams будут "che", "hes", "este", "ter". Потому что когда мы дойдём до нулевого хеша, у нас sliding window закончится, и надо обработать хвост. Единственная возрастающая последовательность это "1 2", поэтому добавляем "este", остальное -- обычные триграмы как мельчайшие единицы. Асимптотика -- линейная, потому что добавляем и убираем из стека каждый элемент суммарно не более двух раз.
Алгоритм весь получился на 70 строк кода.
Понятное дело дальше будет интересно, потому что надо будет доводить до инженерного решения. А там шардирование, большие ngram не нужны, фаззинг, тестирование и тд. 70 строк ещё можно математически доказать, дальше не очень.
Мораль: за 70 строк кода написали ядро, нашли ошибку в статье github (не все подстроки имеют разбиение, что все ngrams содержатся в надстроках -- забыли рассказать о деталях), и алгоритмы тоже пригождаются.