внедрить телефонную адресную книгу - обратный индекс

Question

Теперь я пытаюсь придумать структуру данных для реализации телефонной адресной книги. Скажем, есть две информации: имя, номера телефонов. Одно и то же имя может иметь более одного номера. Теперь я хотел бы придумать структуру данных, которая поможет мне выбрать число, данное имя, и имя, заданное число. Я должен сделать это в кратчайшие сроки. Я думал о сохранении карты (имя к номеру), а затем для заданного числа каким-то образом перевернуть индекс на эту карту и затем найду имя. Я не совсем уверен, что лучший способ сделать это. Можете ли вы предложить идеальную структуру данных. Будет ли использовать некоторую справку обратного индекса. Если да, то как мне использовать это в этом контексте.

Answer 1

Я бы создал концептуальную базу данных с парами Имя х Число. Каждая пара получает идентификатор. Если вы не можете гарантировать, что Джон Смит не будет жить в двух разных местах, вам нужен уникальный идентификатор.

так что у вас есть (в perl)

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

Затем наложите это на два хэша, которые возвращают наборы идентификаторов.

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

Для обновления потребуется определенная осторожность, но результаты будут быстро возвращаться.

Вы можете сделать это на любом языке, который имеет конструкцию hash / map.

Answer 2

Предполагая, что совпадения префиксов желательны, я бы предложил использовать три Патриции. Предполагая, что имя и номер телефона никогда не могут совпадать - т.е. у вас не будет никого с именем 435-9876 в вашем каталоге - тогда вы можете вставить пары с номером телефона, индексируемым с помощью дерева, а также пары, проиндексированные по имени. Если по какой-то странной причине возможны коллизии имен и имен, вы можете добавить специальный символ в префикс телефонных номеров, чтобы они могли дольше сталкиваться.

Вставки будут стоить O (s)
Поиски будут стоить O (s)
где s - длина строки поиска / вставленного ключа.

Это решение также позволит вам поддерживать автозаполнение в стиле оболочки Linux, где вы можете определить количество записей, которые соответствуют определенному имени, как его набрано, или даже отобразить все совпадения по требованию.

EDIT:

Патриция-дерево похожа на обычное дерево, за исключением того, что ветви в патриции-дерево появляются только тогда, когда есть по крайней мере два разных ключа с общим префиксом, которые не были разделены предыдущей ветвью.

1. Внутренние узлы указывают индекс, по которому ключи различаются, а конечные узлы хранят фактические ключи.
   
2. Все дочерние узлы имеют общий префикс родителя.
   
3. Ветви от узла «помечены» символом, который находится в положении, указанном родителем.
   
4. Ребенок не может указать меньший индекс, чем его родитель.

Таким образом, если Jane и Jamie являются единственными ключами, хранящимися в дереве, у него есть три узла - родительский элемент представляет общий префикс «Ja», одна ветвь ведет к поддереву, содержащему все строки, начинающиеся с «Jan», - и так как в листовом узле «Jane» хранится только один, в то время как другая ветвь ведет к поддереву, содержащему все строки, начинающиеся с «Jam», опять же, при этом они являются единственными.

           [2]
   n                m
'Jane'            'Jamie'

Если вы добавите Джеймса, вы получите

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

А потом добавляем Джамелию

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

Поиск прост. Начиная с корня, указанный индекс проверяется. Если ни один из потомков не помечен с указанным фактическим значением, в нашем примере, например, если ищется Джаспер, так как символ в позиции 2 - это s, а не n или m, поиск возвращает, что значение не существует. В противном случае выполняется соответствующая ветвь, пока не будет найдено значение, не будет доказано, что его нет, или останется несколько совпадений. Например. поиск Jam останавливается на узле с меткой [3]. Есть несколько совпадающих узлов, но ключа Jam нет. В этом случае вы можете пройти по поддереву с корнем в [3], чтобы создать список частичных совпадений. Обратите внимание, что это применимо только в том случае, если вы выполняете частичное совпадение, если указан весь ключ, результат поиска 'Jam' не будет совпадать.

Стоимость поиска в порядке длины ключа, s , потому что, как вы можете видеть, существует не более s уровней до того, как ключ найден или показан не быть там. Точно так же стоимость вставки также находится в порядке длины ключа, который будет вставлен, поскольку вставка выполняется путем поиска, а затем добавления ветвления узла по самому длинному префиксу в дереве.

Вы можете найти реализацию Java здесь и то, что выглядит реализацией C ++ здесь .

На самом деле я никогда не использовал ни одну из реализаций, на которые я вам указывал, поэтому не могу ручаться за их правдивость. Если вы решите реализовать структуру данных самостоятельно, я бы посоветовал вам использовать двоичный алфавит, так будет немного проще! Здесь - статья, описывающая алгоритм.

Answer 3

Я бы сохранил две (хэш) карты.

Первая карта будет иметь Имена в качестве ключей, а Наборы (или списки или векторы) в качестве значений, этот список будет содержать все телефонные номера для конкретного человека.

Map<String,Set<String>> NamesToNumbers;

Вторая карта будет иметь номера телефонов в качестве ключей и имена в качестве значений.

Map<String,String> NumbersToNames;

Кроме того, я бы создал простой класс с этими двумя картами в качестве закрытых членов, целью этого класса было бы синхронизировать две карты и передавать все вызовы put (), remove () и т. Д. На обе карты в правильном формате ключ / значение.

Psuedo-код для того, как 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 , у них есть отличный класс Bi-map, который, по сути, я и пытаюсь описать.

Answer 4

Вы можете использовать пару словарей (или карт): один для поиска номеров по именам (name -> List<number>) и один для поиска имен по номерам (number -> name).