Эффективный поиск по адресной книге

Question

Допустим, у меня есть имя, фамилия и адрес электронной почты на объекте (вызов AddressBook). Какую структуру данных я использую (в Java) для хранения этого объекта, так что мне нужно искать по фамилии, которая начинается с определенных букв. Например, если фамилия Джон или Джонсон, и я запрашиваю у Джона, он должен вернуть все объекты AddressBook с фамилиями, начинающимися с Джона.

Какой самый эффективный способ для этого?

Допустим, есть 10 человек с фамилией X, тогда я могу поставить этот X как ключ к карте со значением списка, содержащего 10 объектов AddressBook.

Здесь фамилия может быть X, X1, X12, X13, XA. Нужна помощь в этом.

Answer 1

Возьмите три : каждый узел будет связан с набором лиц, чья фамилия начинается со строки, содержащейся в этом узле.

[ОБНОВЛЕНИЕ] Еще лучше взглянуть на Патриция Три . Или даже лучше взять этот код в качестве примера trie, который позволяет помечать узлы подстановочным знаком «*» в конце префикса, чтобы вы могли искать такие вещи, как «John *»:

<code>/**
 * Tatiana trie -- variant of Patricia trie
 * (http://en.wikipedia.org/wiki/Patricia_tree, http://en.wikipedia.org/wiki/Trie)
 * in which edge associated not with substring, but with regular expressions.
 * <b>Every child node RE defines match-set which is proper subset of parent node ER's match-set.</b>
 * <b>Null keys aren't permitted</b>
 * <p/>
 * Following wildcards <b>at the end</b> of RE are accepted:
 * * -- any string of length >= 0
 * <p/>
 * Examples of valid RE: <pre>a, abra*, 

* Пример неверного RE:

a*a

*

* / открытый класс TatianaTree { закрытый конечный узел root; / ** * Создает дерево с null, связанным с корневым узлом. * / public TatianaTree () { это (нуль); } / ** * Создает дерево с данным элементом, связанным с корневым узлом. * * @param el элемент для связи с root * / public TatianaTree (T el) { root = новый узел (ноль, el); } общедоступное TatianaTree add (узел узел) { if (null == node.key) бросить новое IllegalArgumentException («Не могу добавить узел с нулевым ключом»); root.add (узел); верни это; } public Node findNode (Строковый ключ) { вернуть root.findNode (Node.normalize (key)); } / ** * Удаляет наиболее специфичный узел, который соответствует данному ключу. * Элемент * @return типа T, связанный с удаленным узлом или null. * Единственный случай, когда будет возвращено null, это когда корневой узел соответствует данному ключу. * / public T удалить (строковый ключ) { Node node = findNode (ключ); if (root == узел) вернуть ноль; node.removeSelf (); return node.el; } public Node getRoot () { вернуть корень; } общедоступный статический класс Node { приватная статическая final String INTERNAL_ROOT_KEY = ". *"; приватная статическая final String ROOT_KEY = "*"; частный статический окончательный шаблон KEY_WRONG_FORMAT_PATTERN = Pattern.compile ("\\ *. +"); private static final String ROOT_KEY_IN_NODE_MSG = "Невозможно добавить некорневой узел с корневым ключом"; private static final String WRONG_KEY_FORMAT_MSG = "Допустимый формат: ^ [A-Za-z0-9 _] + (\\ *) {0,1} $"; закрытый финальный строковый ключ; закрытый финал T el; закрытый финальный список > children = new ArrayList > (); закрытый узел parent; public Node (Строковый ключ) { это (ключ, ноль); } public Node (Строковый ключ, T el) { Строка k = INTERNAL_ROOT_KEY; if (null! = key) { k = нормализовать (ключ); } this.key = k; this.el = el; this.parent = null; } / ** * Функция проверки подмножества. * * @param s строка для проверки * @param base string для проверки * @return true если база - это расширенный набор s, false в противном случае * / приватный логический isSubset (String s, String base) { String shorttestS = s.replaceFirst ("\\ * $", ""); Строка baseRE = "^" + base; Pattern p = Pattern.compile (baseRE); return p.matcher (shorttestS) .matches (); } public T getEl () { вернуть эл; } частное добавление void (узел узел) { логическое addHere = true; для (Узел ребенок: дети) { if (isSubset (child.key, node.key)) { insertAbove (узел); addHere = false; перерыв; } else if (isSubset (node.key, child.key)) { child.add (узел); addHere = false; перерыв; } } if (addHere) { children.add (узел); node.parent = this; } } private void insertAbove (Node newSibling) { List > thisChildren = new ArrayList > (),newNodeChildren = new ArrayList > (); для (Узел ребенок: дети) { if (isSubset (child.key, newSibling.key)) { newNodeChildren.add (ребенок); child.parent = newSibling; } еще { thisChildren.add (ребенок); } } newSibling.children.clear (); newSibling.children.addAll (newNodeChildren); this.children.clear (); this.children.addAll (thisChildren); this.children.add (newSibling); newSibling.parent = this; } закрытый узел findNode (строковый ключ) { для (Узел ребенок: дети) { if (isSubset (key, child.key)) return child.findNode (key); } верни это; } public int getChildrenCount () { вернуть children.size (); } приватная статическая строка нормализует (строка k) { если (ROOT_KEY.equals (k)) бросить новое IllegalArgumentException (ROOT_KEY_IN_NODE_MSG); k = k.replaceFirst ("\\ * $", ". *"). replaceAll ("\\ [", "\\\\ ["). replaceAll ("\\]", "\\\\] «); Matcher m = KEY_WRONG_FORMAT_PATTERN.matcher (k); if (m.find ()) бросить новое IllegalArgumentException (WRONG_KEY_FORMAT_MSG); возврат к; } private void removeSelf () { parent.children.remove (это); для (TatianaTree.Node ребенок: дети) child.parent = parent; parent.children.addAll (детей); } } }

Answer 2

Если вы собираетесь искать только по фамилии, когда пишете вопрос (или любое другое отдельное поле), вы можете использовать TreeMap <> в качестве структуры данных с эффективным поиском префиксов.

public class Phonebook {
    NavigableMap<String, Collection<Record>> map = new TreeMap<>();

    public void add(String name, String phone) {
        map.computeIfAbsent(name, k -> new ArrayList<>()).add(new Record(name, phone));
    }

    public Collection<Record> lookup(String prefix) {
        if (prefix.length() == 0) {
            return Collections.emptyList(); // or all values if needed
        }

        String from = prefix;

        char[] chars = prefix.toCharArray();
        chars[chars.length - 1]++;

        String to = new String(chars);

        Collection<Record> result = new ArrayList<>();

        map.subMap(from, to).values().forEach(result::addAll);

        return result;
    }

    private static class Record {
        private final String name;
        private final String phone;

        public Record(String name, String phone) {
            this.name = name;
            this.phone = phone;
        }

        @Override
        public String toString() {
            return "Record{" +
                    "name='" + name + '\'' +
                    ", phone='" + phone + '\'' +
                    '}';
        }
    }

    public static void main(String... args) {
        // example
        Phonebook book = new Phonebook();
        book.add("john", "1");
        book.add("john", "2");
        book.add("johnny", "3");
        book.add("joho", "4"); // joho will be computed as a value of 'to' parameter.

        Collection<Record> records = book.lookup("john");
        System.out.println("records = " + records);
    }
}

Answer 3

Это классическое древовидное решение.вы строите дерево следующим образом:

             root
             x / \y 
             1/\2
            2/\3

Когда вы начинаете поиск, вы идете по дереву. Если у вас есть x, то вы идете по x, и все имена являются поддеревом этого узла...так далее.Вы можете исправить простой метод рекурсии для сбора имен.

Я думаю, что наиболее простая реализация - это HashMap для узлов, то есть каждый узел построен с помощью хэш-карты, которая содержит соответствующий узел на символ.Это дерево также динамично, его легко добавлять, добавлять, удалять ... и т. Д.

Answer 4

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

Если это так, хэш-карта не будет работать, потому чтоне содержит понятия префикса.Вы хэшируете полное значение ключа, и только потому, что Джон

Если вы загружаете список один раз, а затем удерживаете его, и он не меняется, я думаю, что наиболее практичным решением будет создание объекта для каждого имени, затемсоздать массив указателей на эти объекты и отсортировать массив по фамилии.Затем используйте Arrays.binarySearch, чтобы найти первую запись с заданным префиксом и цикл, пока не найдете последнюю.

Если список очень динамичный, моей первой мыслью было бы создать связанный список и создать набор«указатели указателя» на выбранные точки в связанном списке, такие как первый A, первый B и т. д. Последовательный поиск оттуда.

Если список является одновременно динамическим и слишком большим для «вкладки индекса»подход к работе, тогда я думаю, что вы на практике выберете либо сохранить ее в базе данных и использовать возможности извлечения индекса из базы данных, либо проделать целую кучу работы, чтобы написать полную схему индексации в памяти.Честно говоря, это звучит как слишком много работы для меня.(Возможно, для этого есть какой-то пакет с открытым исходным кодом, который вы могли бы просто взять.) Если вы действительно поддерживаете большие объемы данных в памяти, а не в базе данных, возможно, вам следует спросить себя, почему.Для этого и нужны базы данных.