在GAE中用Python进行子串搜索？

Question

我有一个模型，长得像这样：

class Search (db.Model) :

 word = db.StringProperty()

比如说，一个例子“单词”可以是 word = "thisisaword"

我想在搜索中查找所有的实体，找出像“this”、“isa”等这样的子字符串。

我该如何在App引擎中用python来实现这个呢？

更新：

这里的单词将是域名。所以我想这些单词的长度应该是有限制的，比如 google.com、facebook.com。

当有人搜索“gle”时，我想显示“google.com”。

Answer 1

没有单词分隔的话，我觉得你想要的这个任务是不可行的（在很多数据库引擎中，这样做会隐式地不使用索引，从而影响性能和可扩展性，但应用引擎并没有实现那些必然会破坏可扩展性和性能的“功能”）。如果你有单词分隔的话，你可以使用这里解释的基本全文搜索方法这里，但是，正如那篇博客所说，

它没有精确的短语匹配、子字符串匹配、布尔运算符、词干提取或其他常见的全文搜索功能。

nonrel-search在这里被提到，作为一种“替代方案”，与一个旧的、现在已经停止的项目相似，这个项目叫做gae-search（它有免费和付费版本——也许付费版本能帮到你，我从未深入研究过——我给的最后一个链接有作者的联系信息，如果你的预算足够，他们可能会乐意为你开发这样的项目）。

问题在于，每个给定字符串的子字符串数量随着字符串长度的增加而呈平方增长，因此，为了实现你想要的那种无限制的快速搜索，所需的索引也会非常迅速地变得庞大。如果你存储的字符串和要搜索的字符串长度是有限的，你可以进行一些优化，但这仍然是一个相当难以用任何可接受的效率解决的问题。

也许你可以详细说明一下你想要实现的这个假设的“任意子字符串搜索”，这样我们就可以评估字符串（以及要搜索的子字符串）的长度和数量的具体限制。你想解决的确切问题，可能如果你的数字限制不紧（就像你目前表达的问题那样，似乎没有任何限制——但希望事实并非如此！），可能在实际操作中是无法解决的，但也许它的某些变体或子集是可以的……不过你需要详细解释一下具体问题，以便有意帮助的人能够考虑这些子集和变体！

编辑：根据提问者对其问题的稍微澄清，我建议的启发式方法是选择一些合理的最大和最小“相关子字符串长度”（比如2和5，称它们为MINRSL和MAXRSL以便明确）。当输入一个字符串（域名）时，如果合适的话，可以通过点来拆分它（例如，你不想允许“跨越”点进行搜索），可能还要丢弃一些部分（你不想明确记录所有的.com、.org等后缀，对吧？无论如何，这个决定是特定于应用的），对于你确实想要可搜索的其他部分，进行长度在MINRSL到MAXRSL之间的子字符串索引。

具体来说，假设给定的限制是2和5，并假设可以去掉www.和.com（就像在全文搜索中通常去掉“和”、“的”、“在”等词一样：这些“停用词”太常见了，搜索它们的代价巨大，而返回的结果却是无用的无关文档），你需要考虑的可索引内容是：

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”，下一个可能的长度为2的字符串）。然而，正如上面段落中的过于简化，这对于不出现在长度为四的子字符串开头的较短子字符串搜索是行不通的——所以你必须添加“尾部可索引项”

gle le

（总共5个，而不是完整索引的14个）到这个更复杂但更平衡的方案中。

请注意，在另一个完整模型中，当需要时，你仍然需要代码来消除误报——如果你将MAXRSL设置为5，而用户查找的子字符串长度为七，你要么给出错误，要么将其截断为5，并应用我上面提到的相同代码。

你能承担“从MINRSL到MAXRSL的完整索引”架构的简单、快速搜索吗？这取决于你的数字。如果你总共有大约2000个索引的URL，总共大约4000个“单词”需要索引，假设所有单词长度为8个字符，MINRSL=2，MAXRSL=5的方案每个单词需要7+6+5+4个可索引项，即每个单词22个，乘以4000总共只有88000个条目，这相当可承受。但是如果你有更多的单词需要索引，或者单词长度大得多，或者需要更大的最小到最大RSL范围，那么这些数字可能会迅速增长（在这种情况下，复杂的、搜索较慢的方案节省的，比如三倍的成本，可能会被认为是值得的）。你没有给我们任何数字，所以我当然无法做出猜测。

如你所见，即使这个简单的想法也需要相当复杂的代码——你不太可能找到现成的开源代码，因为这个需求相当特殊（很少有人关心“DNS名称的任意子字符串”，而你似乎就是其中之一）——因此我建议，除非你对开发和调试所有这些代码有信心，否则考虑联系上述提到的专业人士，获取开发此类代码的报价（当然，你需要提供他们没有给出的数字，包括允许辅助索引变得多大的数字，以便他们能够在对你的需求进行初步可行性评估之前进行报价）。