高效搜索大型字符串列表

我有大量的字符串需要由iPhone/Android应用程序的用户搜索。这些字符串按字母顺序排序，但实际上并没有那么有用，因为如果搜索查询落在字符串内的任何位置，而不仅仅是开头，则字符串应该包含在结果中。当用户输入他们的搜索查询时，应该更新搜索以反映他们当前输入的结果。（例如，如果他们键入“猫”，则应该在键入它时显示“c”，“ca”和“cat”的结果）。高效搜索大型字符串列表

我目前的做法是：

我有一个堆栈的“搜索结果”，它开始是空的。如果用户输入某些内容来延长搜索查询时间，我会将当前搜索结果推送到堆栈中，然后仅搜索当前搜索结果（对于新搜索结果，这是不可能的）结果在这种情况下）。

如果用户点击退格，我只需要将搜索结果从堆栈中弹出并恢复。这可以几乎立即完成。

此方法适用于“向后”搜索（使搜索查询更短）以及搜索查询已足够长以使结果数量较少的情况。但是，它仍然需要在O（n）时间内搜索用户输入的前几个字母中的每个字母的完整列表，这很慢。

我考虑过的一种方法是对2或3个字母的所有可能的搜索查询的结果进行预编译的列表。这种方法的问题是它需要26^2或26^3这样的列表，并占用相当大的空间。

您可以想到的任何其他优化或替代方法？

来源

2012-05-02 numegil

的可能重复[一个字符串集合的子串过滤速度快？（http://stackoverflow.com/questions/1299168/fast-filtering-of-a-按字符串收集字符串） –

您是否在询问有关查询预测的内容？即如果用户键入'c'，你应该如何预测*'cat'将成为查询？或者你是否要搜索所有'c'，'ca'，'cat'，作为用户类型？将查询预测视为“替代方法”吗？或者它是太离谱你想要实现的？ – amit

我注意到，Google和我想象的其他人在按下1或2个字符时没有提供完整列表。在你的情况下，或许一个好的起点是只有当用户键入至少3个字符时才开始填充搜索查询结果。

对于以后的版本，如果它很重要，可以从Google的工作方式中获得提示，并进行更复杂的处理：跟踪以前用户选择的实际条目，并按频率排序。然后，在您的服务器上每天运行一个cron作业，以填充每个字母开头的前10个条目的小型数据库表，如果只有1或2个字母被按下，则使用此小表中的结果而不是扫描完整名单。

来源

2012-05-02 21:19:40

我没有一个中央服务器，所有东西都在本地人的手机上运行。而且我已经限制为至少3个字符。 – numegil

您应该考虑使用prefix tree (trie)来预先计算列表。我不确定在子字符的基础上显示'c'，'ca'和'cat'的结果是个不错的主意。例如，假设用户正在搜索“吃”这个词。你的算法必须找到所有包含'e'，然后'ea'，最后'吃'的单词;其中大部分将对用户无用。对于手机应用程序，如果你是以单词为基础的话，它可能会更好。多字符串可以被标记化，因此在'大股权'中搜索'股权'可以正常工作，但不会搜索'采取'。

来源

2012-05-02 21:49:26 user845279

你可以使用压缩后缀树

来源

2012-05-03 00:35:49

这会占用指数量的空间，这是我在iPhone或Android上无法承受的。 – numegil

高效搜索大型字符串列表

回答

相关问题