search with wildcard* (using inverted index)

Наверное кроме как полным перебором никак не получится.

Т.е. по шаблону (поиск* запрос*) находятся все слова из словаря, затем для каждого слова извлекается постлист из индекса, после чего полученные постлисты объединяются по OR.

Какие-же тогда должны быть вычислительные/дисковые мощности для того, чтобы такое позволять делать... Ведь как-то же реализуется такое, или именно поэтому крупных поисковиков разрешающих такие запросы и нет?

Если кто-то будет задаваться таким же дурацким вопросом (как и я), то ответ на него можно найти в "классике" (документе об архитектуре Гугла): все (/большинство) имеющихся слов словаря держатся в оперативной памяти, доступ к которой не так уж и дорог даже при условии полного перебора.

Правильно ли я понимаю, что трудности вызывает именно применение шаблона (поиск*, поиск? и т.д.)?

Если так, то здесь все достаточно просто:

1. Получаем диапазон подходящих слов;

2. Объединяем соответствующие списки.

Время выполнения операции (1) пренебрежимо мало - одно обращение к словарю. Основное время операции (2) занимает чтение соответствующих списков, что также невелико.

Такие вещи реализовывались еще в поисковиках, работавших на 386-486 машинах, если кто помнит такие.

Так что проблемы, вроде, нет.

Правильно.

Вопрос в том, по какому принципу получить диапазон подходящих слов (если слова могут быть на разных языках и методы описанные на http://linguist.nm.ru/ и заточенные под один язык не подходят)?

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

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

В данном случае подойдет простой словарь словоформ без всяких "заточенных под язык" методов (любое дерево здесь подойдет). Вот тогда получение диапазона для шаблона превращается в тривиальную задачу.

Спасибо за справку!

тривиальную..

Дам $500 за реализацию такого алгоритма.

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

Нужен быстрый поиск с wildcards по словарю из примерно 100-150 миллионов слов.

Набор символов [\x21-\xFF], максимальная длина слова 128 байт, на разбивку на более простые и короткие слова по каким-то границам внутри слова (пробелы,запятые,...) расчитывать не стоит.

Найти нужно все слова в словаре, подходящие под шаблон, желательно (но не обязательно) в отсортированном порядке.

В словарь могут добавляться слова, удаляться не могут - нужно апдейтить индекс без перестройки его с нуля по всему словарю.

Размер индекса критичен, желательно уложиться не более чем еще один размер словаря, время создания индекса - не очень критично.

Очень критично - время поиска и "время поиска первых n результатов подходящих под шаблон"

За 3000 сделаю... За меньше лениво...

Аналогично