2

因此，我意识到这涵盖了广泛的主题，并且之前在 StackOverflow 上已经涵盖了其中的一部分，例如这个问题。同样，部分字符串匹配和近似字符串匹配似乎是流行的算法讨论。然而，结合使用这些想法来解决需要讨论两者的问题似乎效率很低。我正在寻找一种将这两个问题有效地组合成一个解决方案的方法。

现在，我将 AppEngine 与 Java 和 Persistent DataStore 一起使用。这有点烦人，因为它似乎在查询中没有任何算术用法以使事情变得更容易，所以我目前正在考虑进行一些预先计算并将其作为额外字段存储在数据库中。本质上，这是我和一个朋友关于如何实现匹配系统的想法，我或多或少地希望就如何提高效率提出建议。如果需要废弃它以支持已经存在的更好的东西，我也可以处理。

让我们从一个我想要搜索的基本示例开始。考虑以下无意义的句子：

隔离层在你虚伪的垃圾下面敲响了校长。

如果用户搜索

isalatig pri

我认为这将是字符串的一个相当好的起始匹配，并且应该返回该值。我们正在考虑使用的当前方法基本上是分配一个值来测试可分性。本质上，有一个包含以下数据的表

A: 2        B: 3        C: 5
D: 7        E: 11       F: 13
...

每个字符都映射到一个素数（多个字符没有区别，只需要一个字符）。如果查询字符串除以数据库中的字符串，则返回值作为可能的匹配项。

在此之后，从搜索字符串中比较未列为停用词的关键字，以查看它们是否是在给定的编辑距离阈值（当前使用 Levenshtein 距离）下可能匹配的单词的起始子字符串。

distance("isalatig", "isolating") == 2
distance("pri", "principal") == 0 // since principal has a starting 
                                  // substring of pri it passes

然后按升序排列每个查询的总距离，然后将最高n值返回给进行查询的人。

这是算法背后的基本思想，虽然这是我第一次处理这种情况，但我意识到我可能遗漏了一些非常重要的东西（或者我的整个想法可能是错误的）。处理我正在尝试实施的当前情况的最佳方法是什么。同样，如果 AppEngine 目前提供任何实用程序来对抗我正在尝试做的事情，请告诉我。

4

1 回答 1

0

首先，澄清一下：App Engine 不允许在查询中进行算术运算，因为没有有效的方法来查询任意算术表达式的结果。当您在 SQL 数据库中执行此操作时，计划程序被迫选择一个效率低下的查询计划，这通常涉及将所有候选记录一一扫描。

由于同样的原因，您的方案将不起作用：没有办法索引整数，以便您可以有效地查询可被目标数字整除的所有数字。其他潜在问题包括转换成数字太大而无法存储在固定长度整数中的单词，以及无法区分“出租”、“学习”和“鹿角”。

如果我们暂时放弃您对匹配任意字符串前缀的要求，那么您要搜索的是全文索引，这通常使用倒排索引和词干提取来实现。对全文搜索的支持已在 App Engine 路线图中，但尚未发布；与此同时，您最好的选择似乎是SearchableModel，或者使用外部搜索引擎，例如 Google Site Search。

于 2011-10-17T03:40:39.550 回答