代码之家 › 专栏 › 技术社区 › Niels Basjes

哪种数据结构最快找到最佳匹配前缀?

prefix-tree prefix binary-search-tree data-structures

1

Niels Basjes · 技术社区 · 7 年前

Yauaa )作为这个分析的一部分,我想做一个有根据的猜测,应该报告什么品牌的设备。我有一个实现,我需要重写以提高效率。

因此,我有一个带有前缀和相关品牌的数据集:

然后我想做一个.get(“GT-1234124”),结果应该是“Samsung”,因为这是“最长匹配前缀”。

我看了一下Trie结构,但似乎情况正好相反。我的理解是,从一组值开始,可以有效地获得以提供的前缀开始的所有值。

对于这个用例,您推荐什么样的数据结构?

我是否可以使用现有的(经验证的)实现?

1 回复 | 直到 7 年前

1

0

Niels Basjes 7 年前

我对数据结构做了一些深入的研究,发现本质上Trie结构是我所需要的,它采用了一种不同的方式来遍历结构。

由于这个结构非常简单,我创建了自己的实现,效果非常好。

更新:

我写了一篇关于这个的文章 https://techlab.bol.com/finding-the-longest-matching-string-prefix-fast/
我将我的实现放在一个单独的库中,该库是我开源的,并且已经通过maven central提供。看见 https://github.com/nielsbasjes/prefixmap