algorithm - 地址簿和树状结构

我有一个问题问你。我必须实现一个包含 30000 个姓名的企业通讯录。所有的名字都包含名字和姓氏。
我必须实现一个自动完成文本框，不仅可以输入名字，还可以通过姓氏进行搜索。
在 google 上搜索我已经看到这个问题是使用 patricia trie 解决的，但它只进行前缀搜索，所以如果我创建一个带有名字+姓氏的 trie，我如何不仅按名字搜索，还按姓氏搜索？

我是否必须重复插入这样的两个字符串的条目？
名字+姓氏
和
姓+名

请帮我!!!

搜索必须非常有效。

谢谢。

最佳答案

另一种可能性是创建两次尝试。

第一个(让它成为 T1 )用于名字，第二个(让它成为 T2 )用于姓氏。

当您构造 trie 时，从 T1 中的每个单词终止符(通常表示为 $ 符号)，添加指向 T2 中相关条目的指针列表，反之亦然。

IE。如果 John Doe 是主菜:

T1:
     J
     |
     O
     |
     H
     |
     N
     |
     $1
T2:
     D
     |
     O
     |
     E
     |
     $2

$1 将保存一个包含指向 $2 的指针的列表，而 $2 将保存一个包含 $1 的列表。

每个前缀搜索都会在两次尝试中搜索，让您自动完成，然后使用指针获取全名(部分搜索只给您名字/姓氏，您使用指针获得第二个)。

搜索全名是通过在两次尝试中搜索来完成的(在 T1 中查找名字，在 T2 中查找姓氏，并分别获取相关的 $1 和 $2)，然后您需要检查指针是否匹配(列表 l1 $1 中包含 $2 并且 l2 中的列表 $2 包含 $1 )。如果他们这样做 - 名字在字典里。

请注意，一旦您有了指向 $ 节点的指针，您就可以简单地返回树状结构树，直到到达根节点以获取此 $ 符号所代表的单词。 (需要从每个节点指向父节点的指针)

另请注意:我解释了简单的尝试，但确实没有理由不使用 patricia 尝试代替，使用相同的方法。

关于algorithm - 地址簿和树状结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10922442/