我需要一个 trie 样式的数据结构来存储自定义 class 的附加信息

Question

我目前有 2 次尝试，一次存储姓名，一次存储 ID 号，从 5,000 到 300,000 不等，具体取决于用户运行程序的方式。当我比较这两种类型的数据时，它的工作效率很高。所以我的问题：

这些名称和数字是我编写的自定义 class 的一部分，我需要能够通过与 trie 的比较来访问其他节点信息。

例如，"Record" 包含身份证号码、名字、中间名和姓氏、工作组织和职位、布尔值、居住状态以及更多 int 值。 (名字 + 姓氏) 或 (身份证号码) 字符是尝试中的节点。

一个比较列表中有其他"Records"要比较（名字 + 姓氏）。
另一个比较列表有"Records"可以按（身份证号）进行比较。

如果在相应的比较列表中找到匹配项，我需要能够更改尝试中 "Records" 的字段。

我需要不同数据结构的编辑或建议，以便我可以访问 trie 中的键记录的其余部分。我对其他数据结构进行了广泛的研究，并且尝试了 AVL 树的实现，但没有取得最佳成功。有没有办法在 trie 中存储 HashTable 或 HashMap？我查看了 HAT Tries，但我不确定如何实施或者它是否是我正在寻找的。

这是记录的代码 class：

public class Record { //the is the general record form, all records imported are put in this form

    public int cnum; //constituent number
    public String nm;
    public String fn; //first name
    public String ln; //last name
    public String mn; //middle name
    public String maid; //maiden name
    public String su; //suffix
    public boolean FOTL; //front of the line status
    public String state; //state
    public String jobOrg; //job organization
    public String jobPos; //job position
    public int fblikes; //facebook likes
    public int fbcom; //facebook comments

    public Record(int cnum, String nm, String fn, String ln, String mn, String maid, String su, boolean FOTL, String state,
        String jobOrg, String jobPos, boolean fb, int fblikes, int fbcom) { //full class declaration
        this.cnum = cnum;
        this.nm = nm;
        this.fn = fn;
        this.ln = ln;
        this.mn = mn;
        this.maid = maid;
        this.su = su;
        this.FOTL = FOTL;
        this.state = state;
        this.jobOrg = jobOrg;
        this.jobPos = jobPos;
        this.fblikes = fblikes;
        this.fbcom = fbcom;
    }

    //getters and setters for class members are included, but not seen

这是按 ID 或 Cnum 比较的 Trie 代码：

class ReTrieNode {
    ReTrieNode[] arr;
    boolean isEnd;

    public ReTrieNode() {
        this.arr = new ReTrieNode[10];
    }
}

public class ReTrie {
    private ReTrieNode root;
    public Record w;

    public ReTrie() {
        root = new ReTrieNode();
    }

    public void insert(Record word) {
        try {
            w = word;
            ReTrieNode p = root;
            String con = Integer.toString(w.getCnum());
            for (int i = 0; i < con.length(); i++){
                char c = con.charAt(i);
                int index = c-'0';
                if (p.arr[index] == null) {
                    ReTrieNode temp = new ReTrieNode();
                    p.arr[index] = temp;
                    p = temp;
                }
                else {
                    p = p.arr[index];
                }
            }
            p.isEnd=true;
        }
        catch (ArrayIndexOutOfBoundsException a) {
            System.out.print("ArrayIndexOutOfBoundsException ReTrie.insert(" + word.getNm() + ")");
            System.out.println();
        }
    }

    ArrayList<Record> matches = new ArrayList<>();
    ArrayList<Record> nonmatch = new ArrayList<>();
    PrintWriter found;
    PrintWriter notFound;
    File dir = new File("DataReports");


    public void search(Record word) throws IOException, FileNotFoundException {
        if (!dir.exists()) {
            try {
                dir.mkdir();
            }
            catch (SecurityException se) {
                System.out.println("trie make dir");
            }
        }
        notFound = new PrintWriter(new FileWriter(dir + File.separator + "ReferNotFound." + FileDate.date + ".csv", true));
        found = new PrintWriter(new FileWriter(dir + File.separator + "ReferFound." + FileDate.date + ".csv", true));
        ReTrieNode p = searchNode(word);
            if (p == null) {
                String t = word.toString() + "," + "\n";
                notFound.append(t);
                found.close();
                notFound.close();
                return;
            }
            else {
                if (p.isEnd) {

                    String f = w.toString() + "," + "\n";
                    found.append(f);
                    found.close();
                    notFound.close();
                    return;
                }
            }
            found.close();
            notFound.close();
    }

    public ArrayList<Record> getFind() {
        return matches;
    }

    public ArrayList<Record> getNotFound() {
        return nonmatch;
    }

    public ReTrieNode searchNode(Record s){
        try {
            ReTrieNode p = root;
            String con = Integer.toString(s.getCnum());
            for(int i = 0; i < con.length(); i++){
                char c = con.charAt(i);
                int index = c-'0';
                if (p.arr[index] != null) {
                    p = p.arr[index];
                }
                else {
                    return null;
                }
            }
            if (p == root)
                return null;
            return p;
        }
        catch (ArrayIndexOutOfBoundsException a) {
            System.out.print("ArrayIndexOutOfBoundsException Trie.searchNode(" + s.getNm() + ")");
            System.out.println();
            return null;
        }
    }

    public String printHeader() {
        String COMMA = ",";
        return ("Constituent Number" + COMMA  + "First Name" + COMMA + "Middle Name" + COMMA 
                + "Last Name"  + COMMA + "Suffix" + COMMA + "FOTL" + COMMA
                + "State" + COMMA + "Organization" + COMMA + "Position" + COMMA
                + "FB Active" + COMMA + "FB Likes" + COMMA + "FB Comments");
    }

}

这是按（名字+姓氏）或 Nm 进行比较的 Trie 代码：

class TrieNode {
    TrieNode[] arr;
    boolean isEnd;

    public TrieNode() {
        this.arr = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;
    public Record w;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(Record word) {
        try {
            w = word;
            TrieNode p = root;
            for (int i = 0; i < w.getNm().length(); i++){
                char c = w.getNm().charAt(i);
                int index = c-'a';
                if (p.arr[index] == null) {
                    TrieNode temp = new TrieNode();
                    p.arr[index] = temp;
                    p = temp;
                }
                else {
                    p = p.arr[index];
                }
            }
            p.isEnd=true;
        }
        catch (ArrayIndexOutOfBoundsException a) {
            System.out.print("ArrayIndexOutOfBoundsException Trie.insert(" + word.getNm() + ")");
            System.out.println();
        }
    }

    ArrayList<Record> matches = new ArrayList<>();
    ArrayList<Record> nonmatch = new ArrayList<>();
    public Hashtable<String,ArrayList<String>> nam = new Names().getNames();
    PrintWriter found;
    PrintWriter notFound;
    File dir = new File("DataReports");


    public void search(Record word) throws IOException, FileNotFoundException {
        if (!dir.exists()) {
            try {
                dir.mkdir();
            }
            catch (SecurityException se) {
                System.out.println("trie make dir");
            }
        }
        notFound = new PrintWriter(new FileWriter(dir + File.separator + "ReviewNotFound." + FileDate.date + ".csv", true));
        found = new PrintWriter(new FileWriter(dir + File.separator + "ReviewFound." + FileDate.date + ".csv", true));
        TrieNode p = searchNode(word);
            if (p == null) {
                if (nam.containsKey(word.getFn())) {
                    ArrayList<String> n = new ArrayList<String>(nam.get(word.getFn()));
                    for (int j = 0; j < n.size(); j++) {
                        word.setFn(n.get(j));
                        word.setNm(word.getFn() + word.getLn());
                        if (searchR(word) == false) {
                            String t = word.toString() + "," + "\n";
                            notFound.append(t);
                            continue;
                        }
                        else {

                            String s = w.toString() + "," + "\n";
                            found.append(s);
                            found.close();
                            notFound.close();
                            return;
                        }
                    }
                }
                else {
                    String u = word.toString() + "," + "\n";
                    notFound.append(u);
                }
                found.close();
                notFound.close();
                return;
            }
            else {
                if (p.isEnd) {
                    String f = word.toString() + "," + "\n";
                    found.append(f);
                    found.close();
                    notFound.close();
                    return;
                }
            }
            found.close();
            notFound.close();
    }


    public boolean searchR(Record word) {
        TrieNode p = searchNode(word);
        if (p == null) {
            return false;
        }
        else {
            if (p.isEnd) {
                return true;
            }
        }
        return false;
    }

    public ArrayList<Record> getFind() {
        return matches;
    }

    public ArrayList<Record> getNotFound() {
        return nonmatch;
    }

    public TrieNode searchNode(Record s){
        try {
            TrieNode p = root;
            for(int i = 0; i < s.getNm().length(); i++){
                char c = s.getNm().charAt(i);
                int index = c-'a';
                if (p.arr[index] != null) {
                    p = p.arr[index];
                }
                else {
                    return null;
                }
            }
            if (p == root)
                return null;
            return p;
        }
        catch (ArrayIndexOutOfBoundsException a) {
            System.out.print("ArrayIndexOutOfBoundsException Trie.searchNode(" + s.getNm() + ")");
            System.out.println();
            return null;
        }
    }

    public String printHeader() {
        String COMMA = ",";
        return ("Constituent Number" + COMMA  + "First Name" + COMMA + "Middle Name" + COMMA 
                + "Last Name"  + COMMA + "Suffix" + COMMA + "FOTL" + COMMA
                + "State" + COMMA + "Organization" + COMMA + "Position" + COMMA
                + "FB Active" + COMMA + "FB Likes" + COMMA + "FB Comments");
    }

}

我知道这是一个相当复杂和具体的问题。感谢任何帮助。

Answer 1

Essentially the same information is being put into two different tries, and I need a way to access the additional information pertaining to the Records in both tries.

// create record
Record record = new Record()

// do the parsing
record.setNm(""); //sets full name field
record.setFn(""); //sets first name
record.setLn(""); //sets last name

// add to both, so that they share both the record reference
RETree.insert(record);
RETrie.insert(record);

Answer 2

我最终在保存记录实例的 trie 节点中添加了一个变量 class 并且可以在 trie 分支的末尾访问。

我需要一个 trie 样式的数据结构来存储自定义 class 的附加信息

I need a trie style data structure that will store additional information of a custom class

java

data-structures

hashmap

hashtable

trie