3

我有一个问题问你。我必须实现一个包含 30000 个名称的业务通讯簿。所有名称都包含名字和姓氏。我必须实现一个自动完成文本框，它不仅可以搜索输入名字，还可以搜索姓氏。在 google 上搜索我发现这个问题是使用 patricia trie 解决的，但它只做前缀搜索，所以如果我用 firstname+lastname 创建一个 trie，我如何不仅可以按名字搜索，而且可以按姓氏搜索？

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

请帮我！！！

搜索必须非常有效。

谢谢。

4

2 回答 2

2

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

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

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

IE 如果 John Doe 是主菜：

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

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

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

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

请注意，一旦您有了指向该$节点的指针，就可以简单地返回 trie，直到您到达根以获取该$符号所代表的单词。（需要每个节点指向父节点的指针）

另请注意：我解释了简单的尝试，但实际上没有理由不使用帕特里夏尝试，使用相同的方法。

于 2012-06-06T21:22:17.240 回答
0

是的，最简单的解决方案是插入两个变体。但是，这应该只复制搜索字符串，而不是条目。您可能希望以某种方式规范名字和姓氏之间的分隔（=删除地址簿和用户输入的标点符号），因此您将在所有情况下找到输入条目，例如“John Doe”、“Doe ，约翰”，“约翰”等。

我不会使用部分 trie，而只是使用平衡树。在许多语言中，您会发现平衡树作为库中的排序映射实现（至少 Java 和 C++）。

于 2012-06-06T21:20:57.467 回答