实施电话地址簿 - 反向指标

现在我想拿出用于实现电话adreess书的数据结构。假设有两个信息：姓名，电话号码。同名可以有多个号码。现在我想想出一个数据结构，它将帮助我获取给定名称的数字并获取给定名称的数字。我必须在尽可能短的时间内做到这一点。我正在考虑维护一个地图（名字到数字），然后给定的数字以某种方式反向索引到这张地图中，然后找到名字。我不确定最好的方法来做到这一点。你能提出一个理想的数据结构吗？将使用一些反向索引的帮助。如果是的话，我如何在这种情况下使用它。实施电话地址簿 - 反向指标

来源

2009-09-22 AMM

你需要做部分匹配吗？即如果Bob Williams和Bobby Thomas的条目存在，数据结构是否需要支持对'Bob'的有效查找以产生两个结果？ – ejspencer 2009-09-22 18:11:41

您可以使用一对词典（又名地图）：一个用于查找使用名称（name -> List<number>）的数字和一个用数字查找名称（number -> name）。

来源

2009-09-22 18:04:58 Brian

因此，如果单个联系人有多个号码，那么您会有多个地图？ – user183037 2011-02-22 03:39:08

@ user183037：不，在这种情况下，您的“列表”将具有多个号码。但我确实认为每个号码只有一个联系人。如果不是这种情况，你可以使用'number - > List '。我相信[instanceofTom的答案]（http://stackoverflow.com/questions/1461571/implement-a-telephone-address-book-reverse-index/1467206#1467206）与我的一样，但更详细。他使用'Set '而不是'List '，这可能会更好。 – Brian 2011-02-22 03:56:13

假设前缀匹配的需要，我建议使用Patricia线索。假设一个姓名和一个电话号码永远不会发生冲突 - 即你的目录中没有任何人命名为435-9876 - 那么你可以插入带有索引的电话号码对以及按姓名索引的配对。如果出于某种奇怪的原因可能发生名字 - 数字冲突，那么您可以添加一个特殊字符来为电话号码添加前缀，以便它们更有可能发生冲突。

的插入将花费O（S）
查找将花费O（S）
其中s是搜索串/插入的钥匙的长度。

该解决方案还允许你支持Linux shell风格的自动完成功能，您可以在确定有多少项有相匹配的特定名称作为其类型化，甚至按需要显示的所有比赛。

编辑：

一个帕特里夏特里结构相似，但只有当至少有两个不同的密钥共享还没有被前面的分支分离前缀的帕特里夏·特里分支出现正则树。

内部节点指示键不同的索引，而叶节点存储实际键。
节点共享父的前缀的所有儿童。从一个节点
分行都“标记”与发生在由父指定的位置处的字符。
孩子不能指定比其父一个小的索引。

因此，如果Jane和Jamie是唯一存储在trie中的密钥，它有三个节点 - 父代表共享前缀'Ja'，一个分支导致包含所有以'Jan'开始的字符串的子树， - 由于只有一个存储在叶节点'Jane'中，而另一个分支导向包含以'Jam'开头的所有字符串的子树，同样它们只有一个。

  [2] 
    n    m 
'Jane'   'Jamie'

如果你加入詹姆斯，你会得到

  [2] 
    n    m 
'Jane'    [3] 
       e    i 
      'James'  'Jamie'

，然后加入Jamelia的

  [2] 
    n    m 
'Jane'    [3] 
       e    i 
       [4]   'Jamie' 
      l  s 
     'Jamelia' 'James'

搜索非常简单。从根开始，检查指定的索引。如果没有孩子被标记为指定的实际值，则在我们的示例中，例如如果正在搜索Jasper，则由于位置2中的字符是s而不是n或m，所以搜索返回该值不存在。否则，遵循适当的分支，直到找到该值，证明它不在那里，或保留多个匹配。例如。搜索Jam会停在标有[3]的节点上。有几个节点匹配，但关键字Jam不存在。在这种情况下，您可以遍历以[3]为根的子树来构建部分匹配的列表。请注意，这仅适用于进行部分匹配时，如果指定了整个键，搜索'Jam'的结果将不匹配。

搜索的成本在密钥的长度，小号的顺序，因为你可以看到最多有小号之前的水平，关键是无论是发现或证明不应该存在。类似地，插入的代价也是按照要插入的键的长度的顺序进行的，插入是通过执行搜索来执行的，然后添加树中最长前缀分支的节点。

你可以找到一个java实现here和似乎是一个C++实现here。

我从来没有真正使用过我指出过的任何实现，所以不能担保他们的准确性。如果你决定自己实现数据结构，我建议你使用一个二进制字母表，这样就容易一些！ Here是一篇描述该算法的文章。

来源

2009-09-22 19:18:02 ejspencer

您能否更详细地解释您的解决方案？我能够在某种程度上得到它，但没有看到数据结构如何看起来像 – AMM 2009-09-23 07:58:06

这是一个非常复杂的数据结构，用于简单的问题。另外，它会有一个log（n）的复杂性，对吗？ – 2009-09-23 17:14:15

我不认为它比你的典型树更复杂。在我看来，平衡木的实现当然是AVL，红黑等等。我也指出了一些现有的实现。至于复杂性，假设n是存储在数据结构中的元素的数量，那么没有。这与密钥的长度有关。当然，键的长度决定了可以存储多少数据。 :) – ejspencer 2009-09-23 17:39:11

我会维护两个（散列）地图。

第一张地图将有名称作为关键字，并将套（或列表或向量）作为值，此列表将包含特定人员的所有电话号码。

Map<String,Set<String>> NamesToNumbers;

第二张地图将有电话号码的按键，和名称作为值。

Map<String,String> NumbersToNames;

此外，我将创建与这两个地图作为私有成员一个简单的类，这个类的目的是保持两个同步对应，并通过所有的put（），删除（）等。以正确的键/值格式调用两个地图。

为ID如何写在简单类put（）方法

的伪代码：

public void put(String Name,String PhoneNumber) 
{ 

Set NumbersForName = NamesToNumbers.get(Name); 
if (NumbersForName == null) 
    { 
    NumbersForName = new Set(); 
    NamesToNumbers.put(Name,NumbersForName); 
    } 

NumbersForName.put(PhoneNumber); 
NumbersToNames.put(PhoneNumber,Name); 

}

一个查找的成本将是O（1），和插入的费用将是O（ 1）除非有散列冲突。

如果你正在使用Java 5+，你应该检查出Google Collections，他们有一个漂亮的双映射类，这本质上是我想描述的。

来源

2009-09-23 16:37:57

请确实使用我们的BiMap课程，因为确实很难让这些东西完全正确，而且我们已经放了血汗和泪水。 – 2009-11-04 18:09:22

因此，如果单个联系人有多个号码，您会有多个地图？ – user183037 2011-02-22 03:41:22

我会设置一个概念数据库与名称x号码对。每一对都有一个ID。除非你能保证约翰史密斯不会住在两个不同的地方，否则你需要一个独特的身份证。

所以你必须（在Perl）

$db{$id} = [name, number]

然后覆盖与两个散列返回套IDS的。

$name_index[$name] = [$id1, $id2, $id3] 
$number_index[$number] = #as above

这将需要一定的费力更新，但会快速返回结果。

您可以使用具有散列/映射构造的语言来执行此操作。

来源

2009-09-23 17:01:51

实施电话地址簿 - 反向指标

回答

相关问题