Алгоритм для быстрого поиска вхождения слова

Здравствуйте!

Есть большая таблица 100млн записей.
В ней поле с английскими символами username.
Например:

tigertiger
mousemouse
vovarosema

Требуется найти слова, содержащие, допустим, фразу '%sem%' использую запрос select Username from Table where Username LIKE '%sem%'.
Этот Select делает полный скан по всем полям в таблице.

Возможно, придумать такой алгоритм, добавляем в таблицу численное поле (unsigned int) Frequency.

Для каждой УНИКАЛЬНОЙ буквы в UserName посчитать какое-то числовое значение, допустим для a=1 b=2 c=3 и записать сумму или битовую маску в поле Frequency.

Потом, для поисковой фразы "sem" подсчитать свою сумму букв или битовую маску.
И при поиске, сразу отсечь строки UserName, в которые не входит комбинация букв s+e+m.

Это все нужно для ускорения поиска.

Протестировал другой варинат, когда в таблице добавляется 26 колонок для каждой буквы A,B,C.. с признаком, сколько раз буква встречается в слове. Но это не дало ускорения из-за большого объема и низкой селективности индекса для буквы.

Хочется придумать вариант с одной колонкой Frequency.

0

a=1 b=2 c=4
по биту на букву - и искать по этому числу, используя битовые операции

0

Сообщение от Shamil1 a=1 b=2 c=4 по биту на букву - и искать по этому числу, используя битовые операции

Так на конкретный бит в поле Frequency индекс не построишь. Будет сначала full scan по Frequency.
Хочется что-то вида select * where Frequency >= (расчетное min число от Sem) and Frequency <= (расчетное max число от Sem), где для Frequency существует индекс.

0

Сообщение от vga1 where Frequency >= (расчетное min число от Sem) and Frequency <= (расчетное max число от Sem)

Так не получится.

0

Я бы попробовал для каждой буквы алфавита построить таблицу индексов слов, в которые эта буква входит. Затем по каждой букве запроса искать пересечения этих таблиц, ну и в конце запускать уже поиск по исходному шаблону.

И еще соображение. 100млн записей. Допустим все слова 16-буквенные. 1.6 гигабайт. Вкачать все в оперативку - и с бд не связываться.

0

Можно построить индекс всех слов в отдельной таблице и искать по нему (в связанной таблице хранить ключи строк исходной таблицы, в которых эти слова встречаются). Тоже скан, но там будет всего несколько тысяч строк, если в исходной таблице осмысленный текст. Либо попробовать полнотекстовый поиск прикрутить и сравнить время выполнения запросов.

0

Для поиска подстроки может помочь суффиксное дерево. Но это когда все данные помещаются в память.

В БД можно сделать что-то похожее (но менее эффективное по space). Сохранить все суффиксы слова в индекс.
Подстроку можно будет искать очень быстро. Но потребуется в K раз больше места, где K - средняя длина слова.

Т.е. для слова mouse записать в индекс слова
mouse
ouse
use
se
e

0