使用python在GAE中进行子串搜索？

Question

我有一个看起来像这样的模型:

class Search (db.Model) :

 word = db.StringProperty()

一个例子"单词"看起来像word ="thisisaword"

我想搜索搜索子字符串中的所有实体,如"this""isa"等.

我怎么能在使用python的App引擎中做到这一点？

更新:

这里的单词将是域名.所以有一些限制,我猜这个词的大小.例如google.com,facebook.com

当有人搜索"gle"时,我想显示"google.com"

Answer 1

没有单词分离,我不认为你想要的任务是可行的(它将在许多数据库引擎中隐含地不使用索引并破坏性能和可伸缩性,但App Engine只是没有实现"功能"这不可避免地破坏了可扩展性和性能).如果你有单词分离,你可以使用这里解释的基本全文搜索,但正如该博客所说,

它没有精确的短语匹配,子串匹配,布尔运算符,词干或其他常见的全文功能.

nonrel-search在这里被称为"替代"和"类似",由同一作者称之为旧的,现已停止的项目gae-search(可在免费和付费版本中使用 - 也许付费版本可以帮助你,我从来没有深入调查过 - 我给的最后一个链接有作者的联系信息,如果您的预算足以资助像这样的昂贵项目,他可能很乐意为您开发一些东西.

问题是每个给定字符串的子串数量随着字符串的长度呈二次方式增长,因此合理快速搜索所需的无界字符所需的索引也会非常快速地增长.如果你存储的字符串和你正在搜索的字符串的长度有限,你可以应用一些优化,但要解决任何中途容忍效率仍然是一个非常难的问题.

也许你可以用这个假设的"任意子串搜索"来准确解释你想要获得的东西,这样就可以评估字符串(和被搜索的子字符串)的数字限制,包括长度和数字.你想要解决的确切问题,如果你的数值限制不紧张(正如你现在表达的问题,似乎没有任何限制 - 但希望事实并非如此! - ),可能实际上并非如此可以解决,但也许它的某些变体/子集可能......但你需要解释有问题的确切问题,以便考虑这些子集和变体!

编辑:在OP编辑他的Q时稍微澄清一下,我建议的启发式是选择一些合理的最大和最小"相关子串长度"(比如说2和5,称其为明确的MINRSL和MAXRSL).输入字符串(域名)时,如果合适,可以用点分解(例如,您不希望允许搜索"点"),可能会丢弃一些部分(您不想明确记录所有部分.com,.org&C后缀是吗？反正,这个决定是应用特定的),并且对于每个你其他部分的不希望搜索,做一些索引;长度MINRSL到MAXRSL的子串.

具体来说,使用上面给出的限制2和5,并假设www.并且.com可以删除(很像通常在全文搜索中删除诸如"和","the","of"之类的单词:这样的"停止词" "只是过于普遍并且对它们进行搜索 - 以换取索引它们的巨大成本 - 将返回无用的大量无关文档),您将不得不考虑作为索引:

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" 开头的所有匹配项(在搜索中使用a >=和a <:>="oo",还有<"op",下一个可能的长度 - 两个字符串).但是,这是上面段落中的过度简化,这对于没有出现在长度为4的子串的开头的短子串搜索不起作用- 所以你必须添加"尾随索引"

gle le

(对于这个更复杂但更平衡的方案,总共5个,而不是14个完全索引).

请注意,在另一个完整的模型中,您仍然需要代码以在需要时消除误报 - 如果您将MAXRSL设置为5,并且用户查找长度为6的子字符串,则您要么给出错误,或将其截断为五并应用我上面提到的相同代码.

您能负担得起更简单,更快速的搜索"从MINRSL到MAXRSL的完整索引"架构吗？这取决于你的号码.如果你总共有大约2,000个索引URL,总共有4,000个"单词"要编入索引,所有(为简单起见)我们都会说长度为8个字符,MINRSL = 2,MAXRSL = 5方案每个单词需要7 + 6 + 5 + 4个索引,即每个单词22个,乘以4,000只有88,000个条目,这是非常实惠的.但是,如果你有更多的单词要索引,或者说长得多的单词,或者需要更大范围的最小到最大RSL,那么这些数字会变得令人担忧(这就是节省一个因素的情况)三,对于更复杂的慢速搜索方案,可能被认为是值得的).你没有给我们任何数字,所以我当然不能猜测.

正如你所看到的,即使是这个简单的想法也会导致需要相当复杂的代码 - 你不可能找到它作为开源代码,因为这个要求非常特殊(很少有人关心"DNS名称的任意子串")似乎) - 我的建议是,除非你对内部开发和调整所有这些代码有信心,否则你可以考虑联系上面提到的专业专业人士来获得为你开发这些代码的报价(当然,你我们必须向他们提供你没有给我们的数字,包括允许的辅助指数有多大,以便他们在竞标你的要求之前进行初步的可行性评估.