reverse prefix search

[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, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.

Comments

[juan-gandhi.livejournal.com]

Я думаю, что trie должен быть построен по базе, перед тем, как все это делать.

[109.livejournal.com]

can't parse

[juan-gandhi.livejournal.com]

I mean, you have random data in the db (ok, sorted maybe); what we need is a trie. Otoh, we may mock the trie, if it's sorted - binary search on string length.
E.g. do we have an entry for string/2? string/4? string*3/4?

Етпочя.

[109.livejournal.com]

извини, я плохо понимаю, что ты говоришь. например, я не понимаю, что будет результатом поиска "binary search on string length", да и вообще что ты под этим имеешь в виду. ты уверен, что внимательно прочитал условие? надо найти все [под]строки, являющиеся префиксом к данной.

[109.livejournal.com]

но ты меня натолкнул на оптимизацию. если в базе искать не точное совпадение (select ... where str = @str), a префиксное (select top 1 where str like @str + '%'), то поиск можно заканчивать, когда этот селект ничего не вернул. а скорость та же.

[juan-gandhi.livejournal.com]

Ну вот, об этом и речь была.

[109.livejournal.com]

точно об этом? :)

в моей оптимизации нету половинного деления, и не понятно, как оно может помочь.

[juan-gandhi.livejournal.com]

А, смотри. Делишь строку пополам, ищешь или ровно эту строку, или с процентом (limit 2). Потом или убавляешь длину, или прибавляешь. Максимум столько разов поиска, каков логарифм длины строки; ну и там затраты на поиск зависят от многого, типа как дерево устроено.

[109.livejournal.com]

ну перечитай же условие задачи уже! все подстроки надо найти.

[juan-gandhi.livejournal.com]

O, недопрочитал.

Тогда задача усложняется.


Вариант А. В твоей базе нужна структура trie, в смысле, длинный префикс должен содержать пойнтер на ближайший префикс. Я так думаю. Но найти самую длинную все равно надо.

Вариант Б. Сразу trie всандалить со ссылками сверху вниз.

[109.livejournal.com]

ну alter ego это и написал. но всё равно M log N, если прямо в базе. а если строить trie в памяти, то просто M (worst case).