1

背景：我正在研究用户代理字符串（Yuaaa）的分析器，作为此分析的一部分，我想对应该报告的设备品牌进行有根据的猜测。我有一个实现需要重写以提高效率。

因为我不想拥有所有设备的完整列表，所以我想根据模型的前缀进行检测。

所以我有一个带有前缀和相关品牌的数据集：

  • "GT-" --> "三星"
  • "LLD-" --> "华为"

然后我想做一个 .get("GT-1234124") 应该导致“三星”，因为那是“最长的匹配前缀”。

我查看了 Trie 结构，但这似乎是针对相反的情况。我的理解是，您从一组值开始，您可以有效地获取以提供的前缀开头的所有值。

如果我要从头开始实现它，我会使用类似于 Trie 的树，但会以不同的方式绕过它。我正在寻找的是一种尽可能快地完成我需要的数据结构。

您为此用例推荐什么数据结构？

我可以使用现有的（经过验证的）实现吗？

4

1 回答 1

0

我对数据结构进行了一些研究，发现基本上 Trie 结构是我所需要的，我需要一种不同的在结构中行走的方式。

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

见： https ://github.com/nielsbasjes/yauaa/blob/master/analyzer/src/main/java/nl/basjes/parse/useragent/utils/PrefixLookup.java

更新：

  1. 我写了一篇关于这个https://techlab.bol.com/finding-the-longest-matching-string-prefix-fast/的文章
  2. 我把我的实现放到了一个单独的库中，我开源了这个库，并且已经可以通过 maven Central 获得。见https://github.com/nielsbasjes/prefixmap
于 2018-11-21T16:16:17.217 回答