在模式匹配字符串时，Javascript/jQuery 比 $.inArray 更快

Question

我在 Javascript 中有大量单词(约 100,000 个)，我希望能够根据文本模式快速返回其中的一个子集。

例如，我想返回所有以某种模式开头的单词，所以键入 hap 应该给我 ["happy", "happiness", "happening", etc , etc], 结果。

如果可能的话，我希望不遍历整个数组。

像这样的东西运行速度不够快:

// data contains an array of beginnings of words e.g. 'hap'
$.each(data, function(key, possibleWord) {
 found = $.inArray(possibleWord, words);
 // do something if found
}

关于如何在不遍历整个词集的情况下快速将词集减少到可能的匹配项，有什么想法吗？如果有帮助，单词数组按字母顺序排列。

Answer 1

如果您只想搜索前缀，可以使用专门的数据结构，例如 Trie和三元搜索树

快速 Google search一些有前途的 Javascrit Trie 和自动完成实现出现了:

http://ejohn.org/blog/javascript-trie-performance-analysis/

Autocomplete using a trie

http://odhyan.com/blog/2010/11/trie-implementation-in-javascript/