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

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