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).

[zaharchenko]

Надо конечно на предметную область смотреть, и что там за строки, но мне часто хватало битовой маски наличия буквы строке, это если без юникода можно жить.

[109.livejournal.com]

и что делать с этой битовой маской?

[zaharchenko]

использовать как индекс

[109.livejournal.com]

каким образом? битовой маски нашей строки в базе нет. битовые маски подходящих строк - другие. дальше что? или вы думаете, что краткость - это непременный признак таланта? :)

[zaharchenko]

Не, просто ночь и ожидание что мы таки на одной волне :-)

Из условий которые не в заголовке не уловил что всё таки надо только префиксы, я про все подстроки писал. А в чём тут реверс то возникает тогда и зачем?

[109.livejournal.com]

прямая задача - это найти все строки, префиксом которых является данная. это очень легко и быстро. а тут - наоборот.

[sergey_cheban]

Лучше искать не l - la - las - lasd, а l - lasdkfbvaouvyaou, а потом уже в диапазоне между ними - lasdkfbv.

[109.livejournal.com]

в смысле, между ними? сканировать от l до lasdkfbv? а если у нас lzsdkfbv? много миллионов придётся сканировать.

[sergey_cheban]

Нет, разумеется, тоже методом половинного деления (ну или интерполяционным поиском). Просто делить придётся меньший диапазон, не миллиарды от l до zzzzzzzzzz, а миллионы от l до lzsdkfbv. Что даст нам экономию в ~8 сравнений уже на третьей итерации.
Навскидку, должно получиться что-нибудь вроде O(log M log N), но, возможно, я ошибаюсь.

[109.livejournal.com]

половинное деление - такой же log N для каждой префиксной подстроки, как и поиск по индексу. кроме того, если это не в базе, то trie быстрее, а если в базе, то вообще непонятно, как половинное деление делать.

[sergey_cheban]

> половинное деление - такой же log N для каждой префиксной подстроки
Нет. Он, конечно, log, но не N, а (N/2^i).

Trie - надо ещё создать, это O(N).

[allter-ego.livejournal.com]

Условия задачи допускают изменение формата хранения данных в БД?
Если да, то можно таблицу с потенциальными подстроками переформатировать в формат, максимально совместимый с trie.

Что-то типа такого:
| ID | Character | ParentID | Value |

Тогда для строки C1-C2-C3-...-Cn

Потребуется выполнить не более N запросов.
Первый - "SELECT ID FROM TABLE WHERE Character = 'C1' AND ParentID IS NULL"
Остальные - "SELECT ID FROM TABLE WHERE Character = 'Ck' AND ParentID = <ID_FROM_PREV_QUERY>"

> если надо лучше, то придётся в памяти строить trie, и делать по нему лукап.
А разве для этого не потребуется просканировать всю таблицу?

[109.livejournal.com]

> Тогда для строки C1-C2-C3-...-Cn
> Потребуется выполнить не более N запросов.

о, отлично. это тоже M log N в моей терминологии, но основание логарифма побольше, потому что индекс уже.

> А разве для этого не потребуется просканировать всю таблицу?

ну имеется в виду, что трие строится один раз в начале, и потом отвечает на много запросов, так что это не считается.