时间戳

首页 > 解决方案 > 如何修改前缀 trie 数据结构以处理中间的单词？

algorithm - 如何修改前缀 trie 数据结构以处理中间的单词？

问题描述

我想为网站实现简单的自动完成功能。我首先想为此使用前缀 trie 数据结构，这就是自动完成通常的工作方式，您输入一个前缀，您可以在 trie 中搜索可能的后缀，但是产品所有者希望将中间的单词处理为出色地。

让我解释一下我的意思。想象一下，我有这些产品名称：

用户搜索“tile”，如果我使用前缀 trie，他们只会看到前 2 个结果，但我希望弹出所有这些结果，但是我不知道任何有效的数据结构来处理这个问题。你能建议点什么吗？可以修改前缀树来处理这个问题吗？

我考虑过一些修改，比如插入所有的后缀等，但是它们会给出错误的结果，例如，我插入了后缀

并将前缀保留在每个后缀的第一个节点中（有点像笛卡尔积），这样我就可以获得不存在的“其他一些瓷砖，黑色”的结果。所以这个解决方案很糟糕。此外，此解决方案将使用大量内存...

标签： algorithmdata-structures

解决方案

trie 数据结构确实适用于前缀匹配操作，不适用于中间文本搜索

中间文本搜索支持的常用数据结构是后缀树：https ://en.wikipedia.org/wiki/Suffix_tree

它需要足够的空间来存储大约 20 倍于你的单词列表的内存，所以是的，它需要更多的内存

后缀数组是一种节省空间的替代方案：https ://en.wikipedia.org/wiki/Suffix_array

推荐阅读