Реализация Radix (Trie) Tree для поиска Cutomer в Java

Question

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

Класс клиента:

public class Customer {

    String name;
    String mobileNumer;


    public Customer (String name, String phoneNumer) {
        this.name = name;
        this.mobileNumer = phoneNumer;
    }

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getPhoneNumer() {
        return mobileNumer;
    }
    public void setPhoneNumer(String phoneNumer) {
        this.mobileNumer = phoneNumer;
    }



}

Класс RadixNode:

import java.util.HashMap;
import java.util.Map;

class RadixNode {
    private final Map<Character, RadixNode> child = new HashMap<>();
    private final Map<Customer, RadixNode> mobileNum = new HashMap<>();
    private boolean endOfWord;

    Map<Character, RadixNode> getChild() {
        return child;
    }

    Map<Customer, RadixNode> getChildPhoneDir() {
        return mobileNum;
    }

    boolean isEndOfWord() {
        return endOfWord;
    }

    void setEndOfWord(boolean endOfWord) {
        this.endOfWord = endOfWord;
    }
}

Класс Radix:

class Radix {
    private RadixNode root;

    Radix() {
        root = new RadixNode();
    }

    void insert(String word) {
        RadixNode current = root;

        for (int i = 0; i < word.length(); i++) {
            current = current.getChild().computeIfAbsent(word.charAt(i), c -> new RadixNode());
        }
        current.setEndOfWord(true);
    }

    void insert(Customer word) {
        RadixNode current = root;
        System.out.println("==========================================");
        System.out.println(word.mobileNumer.length());
        for (int i = 0; i < word.mobileNumer.length(); i++) {
            current = current.getChildPhoneDir().computeIfAbsent(word.mobileNumer.charAt(i), c -> new RadixNode());
            System.out.println(current);
        }
        current.setEndOfWord(true);
    }

    boolean delete(String word) {
        return delete(root, word, 0);
    }

    boolean containsNode(String word) {
        RadixNode current = root;

        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            RadixNode node = current.getChild().get(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return current.isEndOfWord();
    }

    boolean isEmpty() {
        return root == null;
    }

    private boolean delete(RadixNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord()) {
                return false;
            }
            current.setEndOfWord(false);
            return current.getChild().isEmpty();
        }
        char ch = word.charAt(index);
        RadixNode node = current.getChild().get(ch);
        if (node == null) {
            return false;
        }
        boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord();

        if (shouldDeleteCurrentNode) {
            current.getChild().remove(ch);
            return current.getChild().isEmpty();
        }
        return false;
    }

    public void displayContactsUtil(RadixNode curNode, String prefix) 
    { 

        // Check if the string 'prefix' ends at this Node 
        // If yes then display the string found so far 
        if (curNode.isEndOfWord()) 
            System.out.println(prefix); 

        // Find all the adjacent Nodes to the current 
        // Node and then call the function recursively 
        // This is similar to performing DFS on a graph 
        for (char i = 'a'; i <= 'z'; i++) 
        { 
            RadixNode nextNode = curNode.getChild().get(i); 
            if (nextNode != null) 
            { 
                    displayContactsUtil(nextNode, prefix + i); 
            } 
        } 
    }


    public boolean displayContacts(String str) 
    { 
        RadixNode prevNode = root; 

        // 'flag' denotes whether the string entered 
        // so far is present in the Contact List 

        String prefix = ""; 
        int len = str.length(); 

        // Display the contact List for string formed 
        // after entering every character 
        int i; 
        for (i = 0; i < len; i++) 
        { 
            // 'str' stores the string entered so far 
            prefix += str.charAt(i); 

            // Get the last character entered 
            char lastChar = prefix.charAt(i); 

            // Find the Node corresponding to the last 
            // character of 'str' which is pointed by 
            // prevNode of the Trie 
            RadixNode curNode = prevNode.getChild().get(lastChar); 

            // If nothing found, then break the loop as 
            // no more prefixes are going to be present. 
            if (curNode == null) 
            { 
                System.out.println("No Results Found for \"" + prefix + "\""); 
                i++; 
                break; 
            } 

            // If present in trie then display all 
            // the contacts with given prefix. 
            System.out.println("Suggestions based on \"" + prefix + "\" are"); 
            displayContactsUtil(curNode, prefix); 

            // Change prevNode for next prefix 
            prevNode = curNode; 
        } 

        for ( ; i < len; i++) 
        { 
            prefix += str.charAt(i); 
            System.out.println("No Results Found for \""  + prefix + "\""); 
        }

        return true;
    }


    public void displayContactsUtil(RadixNode curNode, String prefix, boolean isPhoneNumber) 
    { 

        // Check if the string 'prefix' ends at this Node 
        // If yes then display the string found so far 
        if (curNode.isEndOfWord()) 
            System.out.println(prefix); 

        // Find all the adjacent Nodes to the current 
        // Node and then call the function recursively 
        // This is similar to performing DFS on a graph 
        for (char i = '0'; i <= '9'; i++) 
        { 
            RadixNode nextNode = curNode.getChildPhoneDir().get(i); 
            if (nextNode != null) 
            { 
                    displayContactsUtil(nextNode, prefix + i); 
            } 
        } 
    }

    public boolean displayContacts(String str, boolean isPhoneNumber) 
    { 
        RadixNode prevNode = root; 

        // 'flag' denotes whether the string entered 
        // so far is present in the Contact List 

        String prefix = ""; 
        int len = str.length(); 

        // Display the contact List for string formed 
        // after entering every character 
        int i; 
        for (i = 0; i < len; i++) 
        { 
            // 'str' stores the string entered so far 
            prefix += str.charAt(i); 

            // Get the last character entered 
            char lastChar = prefix.charAt(i); 

            // Find the Node corresponding to the last 
            // character of 'str' which is pointed by 
            // prevNode of the Trie 
            RadixNode curNode = prevNode.getChildPhoneDir().get(lastChar); 

            // If nothing found, then break the loop as 
            // no more prefixes are going to be present. 
            if (curNode == null) 
            { 
                System.out.println("No Results Found for \"" + prefix + "\""); 
                i++; 
                break; 
            } 

            // If present in trie then display all 
            // the contacts with given prefix. 
            System.out.println("Suggestions based on \"" + prefix + "\" are"); 
            displayContactsUtil(curNode, prefix, isPhoneNumber); 

            // Change prevNode for next prefix 
            prevNode = curNode; 
        } 

        for ( ; i < len; i++) 
        { 
            prefix += str.charAt(i); 
            System.out.println("No Results Found for \""  + prefix + "\""); 
        }

        return true;
    } 


}

Я пытался искать в коллекции, но застрял. Буду признателен за любую помощь / предложение.

Answer 1

Я предлагаю вам 2 способа сделать это.

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

import java.util.HashMap;
import java.util.Map;

class RadixNode {
    private Map<Character, RadixNode> children;
    private Customer customer;

    public RadixNode(){
        this.children = new Map<Character, RadixNode>();
        this.Customer = NULL;
    }
    Map<Character, RadixNode> getChildren() {
        return children;
    }
    boolean hasCustomer() {
        return this.customer != NULL;
    }
    Customer getCustomer() {
        return customer;
    }
    void setCustomer(Customer customer) {
        this.customer = customer;
    }
}

Как видите, существует только одна карта, хранящая дочерние элементы узла.Это потому, что мы можем видеть номер телефона в виде цепочки цифр, поэтому этот файл будет хранить всех клиентов ... дважды.Один раз для имени, один раз для номера телефона.
Теперь давайте посмотрим функцию вставки.Вашему трию понадобится рут, и давайте назовем его root.

public void insert(RadixNode root, Customer customer){
    insert_with_name(root, customer, 0);
    insert_with_phone_nb(root, customer, 0);
}

public void insert_with_name(RadixNode node, Customer customer, int idx){
    if (idx == customer.getName().length()){
        node.setCustomer(customer);
    } else {
        Character current_char = customer.getName().chatAt(idx);
        if (! node.getChlidren().containsKey(current_char){
            RadixNode new_child = new RadixNode();
            node.getChildren().put(current_char, new_child);
        }
        insert_with_name(node.getChildren().get(current_char), customer, idx+1);
    }
}

Метод insert_with_phone_nb() аналогичен.Это будет работать до тех пор, пока у людей есть уникальные имена, уникальные номера телефонов и если чье-то имя не может быть чьим-либо номером.
Как видите, метод рекурсивный.Я советую вам рекурсивно строить свою структуру трия (и, как правило, все, что основано на древовидных структурах), так как это упрощает и упрощает очистку кода.
Функция поиска является почти копией-вставкой функции вставки:

public void search_by_name(RadixNode node, String name, int idx){
    // returns NULL if there is no user going by that name
    if (idx == name.length()){
        return node.getCustomer();
    } else {
        Character current_char =  name.chatAt(idx);
        if (! node.getChlidren().containsKey(current_char){
            return NULL;
        } else {
            return search_by_name(node.getChildren().get(current_char), name, idx+1);
        }
    }
}

Второй способ: с 2 попытками
Принцип тот же, все, что вам нужно сделать, это повторно использовать приведенный выше код, но сохранить два отдельных узла root, каждый из которыхони построят три (один для имен, один для телефонных номеров).Единственным отличием будет функция insert (так как она будет вызывать insert_with_name и insert_with_phone_nb с двумя разными корнями) и функция поиска, которая также должна будет искать в нужном дереве.

public void insert(RadixNode root_name_trie, RadixNode root_phone_trie, Customer customer){
    insert_with_name(root_name_trie, customer, 0);
    insert_with_phone_nb(root_phone_trie, customer, 0);
}

Редактировать : После уточнения комментариев могут быть клиенты с одинаковыми именами, вот альтернативная реализация, позволяющая RadixNode содержать ссылки на несколько Customer.
Заменить *Атрибут 1038 * в RadixNode, например, Vector<Customer>.Конечно, методы должны быть изменены соответствующим образом, и поиск по имени вернет вам вектор покупателей (возможно, пустой), поскольку этот поиск может привести к нескольким результатам.
В вашем случае, я быперейти на одну Trie, содержащую векторы клиентов.Таким образом, вы можете иметь как поиск по имени, так и по телефону (приведите число как String), а также одну структуру данных для обслуживания.