實施電話地址簿 - 反向指標

現在我想拿出用於實現電話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

實施電話地址簿 - 反向指標

回答

相關問題