search with wildcard* (using inverted index)

1. Смотря что считать быстро.

2. Какой размер оперативной памяти.

3. Какие требования к wildcard, типичные, итд. Знаете ли, ни один алгоритм

по wildcard а.*б.*в.*г.*...я где все буквы русского алфавита и 33 звездочек быстро искать не будут.

4. Ну и потом, посчитайте, что если на реализацию такого алгоритма затратить 2 недели, неделю-другую на отладку довдоку (а может даже больше) Ваша цена в 500 баксов выглядит совсем смешной.

5. подумал, дописал, кстати, если это какое-то критичное приложение, то можно написать распределенную искалку.

.

.......................

ну скажем 20ms на Dual Opteron c 4Gb

если больше двух * - можно во время не вписываться.

да там чуть выше спецы такой алгоритм тривиальным обозвали :)

и уже реализованным во всех поисковиках

а как до дела дошло - ёк :)

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

Если это намек на меня, то я попросил бы читать внимательнее. Привожу фрагмент своего постинга:

Более ничего я не говорил. По сути дела я полностью согласен с itman по поводу реализации в общем виде :) и об этом тоже писал. Можно попробовать другой метод, может Вы опишите (хотя бы в общем) зачем и где (в каких условиях) эта штуковина должна работать. Возможно тогда что-то будет можно сказать или предложить.

нет, я о том что обсуждали в этом топике до меня

за такое время на такой железке, с такой памятью стандартные инвертированный файл не справится, или справится едва-едва.

к тому же, имхо, здесь важно не сколько там есть звездочек, а какая длина подстрок без wildcard. сами, посудите какова фильтруаящая способность, скажем, триграммы относительно массива слов длинной 128 символов количеством 13 млн. я думаю, что будет очень хорошо, если на такой железке вам удастся уложить поиск в несколько секунд.

tano, а какова примерно средняя длина слова? И каков допустимый максимальный объем всего индекса?

сейчас 15, может со временем расти, до 20-30

128 - это максимально возможная длина

Желательно - данные+индекс уложить в 2 размера данных в plain формате, можно превысить. Решения с 128*размер данных не проходят.

Ууупс... Вы путаетесь в показаниях, если максимальная длина слова 15, то размер данных ну уж никак не 13 гигов. Опять-таки, какая средня длина, порядка 10 я думаю?