代码之家 › 专栏 › 技术社区 › DSlomer64

如何加快搜索按字母顺序排列的单词列表以查找前导通配符匹配

wildcard search android

DSlomer64 · 技术社区 · 10 年前

我在业余时间是一个单词拼图迷,所以我花了很多其他业余时间研究一个帮助程序,该程序允许在搜索模式中使用通配符。它工作得很好。在我的戴尔笔记本电脑(i5,8GB RAM)上,搜索140000个单词的“字典”以查找单词的通配符匹配有一个几乎无法察觉且绝对可接受的延迟,只有在返回数万个单词时才会出现这种延迟。Java规则。它的实施也是如此 regex 和 match() .

我希望将其移植到Android。我花了一整天的时间来编译一个差不多相当的应用程序。对于给定的代码架构,没有机会。

问题是可以(必须)使用前导通配符。例如。, ???ENE 返回15个匹配项--来自 achENE 到 xylENE 和 *RAT 返回22个匹配项--来自 aristocRAT 通过`zikuRAT--即,所有140000个单词必须(?)被搜索,哪一个会在大多数情况下(全部?)Android设备。(在我的笔记本电脑上,每一个都用了不到一秒钟的时间。)

由于某些单词拼图允许单词中的字母数量可变,因此不允许使用前导通配符会让此类拼图的应用程序陷入困境。但如果搜索模式必须以字母开头,那么进行二进制搜索(或更快的搜索)就足够容易了。(而且速度可能仍然慢得令人无法接受。)

无论如何,我想知道是否有人知道一些算法,或者可以想出一些方法来加快使用前导通配符的搜索速度。

2 回复 | 直到 10 年前

GreyBeardedGeek 10 年前

我相信,您正在尝试的优化版本被广泛称为Unix/Linux实用程序“grep”,如果我没有记错的话,它使用了Boyer-Moore搜索算法。

在封面下,Java的Pattern类使用Boyer-Moore。而且它支持正则表达式,所以如果您可以编写一些东西来将通配符搜索模式转换为正则表达式,则可以使用Pattern。

这里有一个有趣的grep Java实现 http://www.java2s.com/Code/Java/Regular-Expressions/AnotherGrep.htm

它使用内存映射文件。我猜你无法将整个单词列表放入内存,但你可以将其拆分为一堆较小的文件——内存上面的实现一次映射一个文件。您必须进行一些测试以找到文件的最佳大小。

DSlomer64 10 年前

我刚刚在谷歌上搜索了一下,发现将第二个列表按字母顺序倒排可能是一种方法,然后将前导通配符变为尾随通配符,从而为模式开始的二进制搜索打开了大门。有趣的但是 *a???ene* 也是程序中的合法搜索模式。然后呢?(是的。你需要多久进行一次这样的搜索?)

我刚刚发现了Apache Lucene:

Leading wildcards (e.g. *ook) are not supported by the QueryParser by default. 从Lucene 2.1开始,可以通过调用 QueryParser.setAllowLeadingWildcard( true ) 请注意,这可能是一个昂贵的操作:它需要扫描索引中的令牌列表以查找与模式匹配的令牌。