reverse prefix search
Nov. 16th, 2015 01:53 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109столкнулся с проблемой, из которой, кажется, получится хороший вопрос для интервью на продвинутого девелопера.
проблема такая: есть относительно длинная строка, например "lasdkfbvaouvyaou". и есть в базе таблица с миллиардом записей, в которой хранятся потенциальные подстроки, например "la", "las", "lasdk". надо их все найти как можно быстрее.
поверхностное гуглование нашло только кошмарное решение, гордо опубликованное на http://www.loganbibby.com/2011/03/reverse-pattern-matching-in-mysql
это решение сканирует всю таблицу, весь миллиард, вне зависимости от существования индексов.
чисто датабазное решение, которое приходит в голову, это поиск по индексу для каждой подстроки типа "l", "la", "las", и так далее. это даёт O(M log N), где M - количество букв в строке, а N - количество записей в таблице.
если надо лучше, то придётся в памяти строить trie, и делать по нему лукап. для дополнительного ускорения, вместо традиционного trie, где дети лежат в списке, можно держать детей в Dictionary, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.
проблема такая: есть относительно длинная строка, например "lasdkfbvaouvyaou". и есть в базе таблица с миллиардом записей, в которой хранятся потенциальные подстроки, например "la", "las", "lasdk". надо их все найти как можно быстрее.
поверхностное гуглование нашло только кошмарное решение, гордо опубликованное на http://www.loganbibby.com/2011/03/reverse-pattern-matching-in-mysql
это решение сканирует всю таблицу, весь миллиард, вне зависимости от существования индексов.
чисто датабазное решение, которое приходит в голову, это поиск по индексу для каждой подстроки типа "l", "la", "las", и так далее. это даёт O(M log N), где M - количество букв в строке, а N - количество записей в таблице.
если надо лучше, то придётся в памяти строить trie, и делать по нему лукап. для дополнительного ускорения, вместо традиционного trie, где дети лежат в списке, можно держать детей в Dictionary, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2015-11-17 11:10 pm (UTC)(no subject)
Date: 2015-11-18 12:37 am (UTC)Тогда задача усложняется.
Вариант А. В твоей базе нужна структура trie, в смысле, длинный префикс должен содержать пойнтер на ближайший префикс. Я так думаю. Но найти самую длинную все равно надо.
Вариант Б. Сразу trie всандалить со ссылками сверху вниз.
(no subject)
Date: 2015-11-18 01:05 am (UTC)