Без разделения слов я не думаю, что желаемая задача выполнима (это было бы во многих механизмах работы с БД, если вообще не использовать индекс вообще, а производительность и масштабируемость не использовались бы, а App Engine просто не реализовывал) «функции», которые неизбежно разрушают масштабируемость и производительность). Если бы у вас было разделение слов, вы могли бы использовать элементарный полнотекстовый поиск, объясненный здесь , но, как говорится в этом блоге,
нет точного совпадения фразы,
совпадение подстроки, логические операторы,
stemming, или другой общий текст
особенности.
nonrel-search упоминается здесь как «альтернативный» и «похожий» на более старый, ныне прекращенный проект тех же авторов под названием gae-search (который был доступен в бесплатные и платные версии - может быть, вам может помочь платная версия, я никогда не исследовал ее подробно - и последняя ссылка, которую я дал, содержит контактную информацию для авторов, которые могут быть рады разработать что-то для вас если ваш бюджет достаточен для финансирования такого дорогостоящего проекта, как этот).
Проблема заключается в том, что число подстрок в каждой данной строке растет в квадрате с длиной строки, поэтому индексы, необходимые для достаточно быстрого поиска неограниченного вида, который вы хотите, также очень быстро растут очень сильно. Вы можете применить некоторые оптимизации, если у вас есть ограниченные длины для строк, которые вы храните, и строк, которые вы ищете, но это все еще довольно трудная задача для решения с любой допустимой на полпути эффективностью.
Может быть, вы можете точно объяснить, что вы пытаетесь получить с помощью этого гипотетического «произвольного поиска подстрок», чтобы можно было оценить числовые ограничения для строк (и искомых подстрок) как по длине, так и по числам. Возможно, точная проблема, которую вы хотите решить, если ваши численные пределы не являются жесткими (как вы в настоящее время выражали свою проблему, кажется, что никаких ограничений нет - но, надеюсь, это не совсем так!), Это может быть не совсем решаемо, но, возможно, какой-то вариант / подмножество этого может ... но вам нужно будет объяснить точную проблему, о которой идет речь, чтобы позволить потенциальным людям подумать о таких подмножествах и вариантах!
Редактировать : учитывая небольшое уточнение в редактировании OP своего Q, эвристика, которую я бы предложил, - это выбрать какой-нибудь разумный максимум и минимум "соответствующей длины подстроки" (скажем, 2 и 5, назовите их MINRSL и MAXRSL для определенности). Когда вводится строка (имя домена), разбивайте ее по точкам, если это необходимо (например, вы не хотите разрешать поиск «через» точки), возможно, отбрасываете некоторые части (вы не хотите явно записывать все .com, .org & c суффиксы, вы? В любом случае, это решение зависит от приложения), и для каждой из других частей, которые вы do хотите найти, выполните некоторое индексирование для подстрок длины От MINRSL до MAXRSL.
В частности, с указанными выше пределами 2 и 5 и допуская, что www. и .com могут быть удалены (так же, как обычно удаляются такие слова, как "и", "the", "of", ... in полнотекстовый поиск: такие «стоп-слова» слишком распространены, и их поиск - в обмен на огромные затраты на их индексацию - будет возвращать бесполезные тонны несвязанных документов), вы должны будете рассматривать их как индексируемые:
go oo og gl le
goo oog ogl gle
goog oogl ogle
googl oogle
Итак, вам нужно создать 5 + 4 + 3 + 2 = 14 экземпляров модели, индексируемой как одно поле, а в качестве другого поля - ссылка на экземпляр, где вы сохранили www.google.com. Как и во всех схемах индексации, это, конечно, делает обременительным «писать» (создавать новый объект или, что еще хуже, изменять проиндексированные части существующих! -), поскольку цену, которую вы платите за очень быстрое «чтение» (поиск) .
В качестве альтернативы, для более дешевого письма, но более дорогого чтения (поиска), вы можете записать только подстроки определенной единой длины, скажем, 4 - это было бы просто (идеальный упрощенный случай, см. Позже):
goog oogl ogle
т.е. три экземпляра упомянутой вспомогательной модели вместо четырнадцати. Но теперь, для поиска, вам нужно усечь искомую подстроку до четырех символов, получить все совпадения, которые будут включать в себя несколько ложных срабатываний, и использовать дополнительный код в вашем приложении, чтобы отфильтровать найденные таким образом «возможные попадания» для устранения ложных позитивы.
Когда пользователь ищет более короткую строку, скажем просто "oo", вы можете найти все совпадения, которые начинаются с "oo" (используя как >=, так и < в Ваш поиск: >= "oo", но также < "op", следующая возможная строка длиной два). Однако, и это упрощение в приведенных выше абзацах, это не работает для поиска с более короткими подстроками, которые не появляются в start подстрок длины четыре - поэтому вы должны добавить " трейлинг-индексы "
gle le
(всего 5, а не 14 с полной индексацией) по этой более сложной, но более сбалансированной схеме.
Обратите внимание, что в другой полной модели вам все еще нужен код для устранения ложных срабатываний при необходимости - если вы установили MAXRSL на 5, а пользователь ищет подстроку длины, скажем, семь, вы либо выдаете ошибку, либо сокращаете ее до пяти и применяете тот же код, который я упоминал выше.
Можете ли вы позволить себе более простую и быструю для поиска архитектуру «полного индексирования от MINRSL до MAXRSL»? Это зависит от вашего номера. Если у вас есть в общей сложности около 2000 проиндексированных URL-адресов с общим количеством, скажем, 4000 «слов» для индексации, все (для простоты) скажем длиной 8 символов, схемой MINRSL = 2, MAXRSL = 5 требуется 7 + 6 + 5 + 4 индексируемых на слово, т. е. 22 на слово, умноженное на 4000, составляет всего 88 000 записей, что было бы вполне доступно. Но если у вас есть еще много слов для индексации или существенно длинных слов, или вам нужны гораздо более широкие диапазоны от минимального до максимального RSL, тогда цифры могут стать тревожными (и это тот случай, когда экономия, скажем, фактора из трех, для более сложной схемы медленного поиска, может считаться стоящей). Вы не даете нам никаких цифр, поэтому, конечно, я не могу угадать.
Как видите, даже эта простая идея приводит к необходимости довольно сложного кода, который вряд ли вы найдете уже доступным в качестве открытого источника, поскольку требование довольно своеобразное (очень мало людей заботятся о "произвольных подстроках имен DNS" «как вам кажется) - отсюда мое предположение, что, если вы не уверены в том, чтобы разрабатывать и настраивать весь этот код у себя дома, вы можете обратиться к опытным специалистам, таким как упомянутые выше, чтобы получить расценки на разработку такого кода для вас (из Конечно, вам нужно будет дать им цифры, которые вы нам не указали, включая то, насколько большими могут стать вспомогательные индексы, чтобы они могли сделать предварительную оценку осуществимости перед началом торгов по вашим требованиям).