java - 如何在 Trie 数据结构中使用字符串频率列表？

Question

我正在对各种数据结构进行一些性能测试。在我的列表中，我有 HashMap 和 Trie 数据结构。我已经完成了 HashMap 但不确定如何使用 Trie 来解决以下问题 -

我有一个文本文件，其中包含 200 万个英语单词及其出现频率 -

hello 100
world 5000
good 2000
bad 9000
...

现在我逐行读取此文件并将其存储在 HashMap 中 - 第一个拆分字符串作为 HashMap 中的键，下一个拆分字符串作为 HashMap 中的值，所以我是能够使用以下代码测量插入性能。

Map<String, String> wordTest = new HashMap<String, String>();

try {
        fis = new FileInputStream(FILE_LOCATION);
        reader = new BufferedReader(new InputStreamReader(fis));

        String line = reader.readLine();
        while (line != null) {
        String[] splitString = line.split("\\s+");
        // now put it in HashMap as key value  pair
        wordTest.put(splitString[0].toLowerCase().trim(), splitString[1].trim());

        line = reader.readLine();
    }
}

现在我将如何实现 Trie 数据结构以在 Trie 中加载与我为 HashMap 所做的相同的内容？然后也对 String 进行查找？这是我第一次接触 Trie 数据结构，所以有点困惑。

更新:-

下面是我的 TrieImpl 类

public class TrieImpl {

    //root node
    private TrieNode r;

    public TrieImpl() {
        r = new TrieNode();
    }

    public boolean has(String word) {
        return r.has(word);
    }

    public void insert(String word){
        r.insert(word);
    }

    public String toString() {
        return r.toString();
    }

    public static void main(String[] args) {

        TrieImpl t = new TrieImpl();

        System.out.println("Testing some strings");
        t.insert("HELLO"); // how do I pass string and its count
        t.insert("WORLD"); // how do I pass string and its count

    }
}

下面是我的 TrieNode 类 -

public class TrieNode {

    // make child nodes
    private TrieNode[] c;
    // flag for end of word
    private boolean flag = false;

    public TrieNode() {
        c = new TrieNode[26]; // 1 for each letter in alphabet
    }

    protected void insert(String word) {
        int val = word.charAt(0) - 64;

        // if the value of the child node at val is null, make a new node
        // there to represent the letter
        if (c[val] == null) {
            c[val] = new TrieNode();
        }

        // if word length > 1, then word is not finished being added.
        // otherwise, set the flag to true so we know a word ends there.
        if (word.length() > 1) {
            c[val].insert(word.substring(1));
        } else {
            c[val].flag = true;
        }
    }

    public boolean has(String word) {
        int val = word.charAt(0) - 64;
        if (c[val] != null && word.length() > 1) {
            c[val].has(word.substring(1));
        } else if (c[val].flag == true && word.length() == 1) {
            return true;
        }

        return false;
    }

    public String toString() {
        return "";
    }
}

现在我如何扩展它来传递一个特定的字符串及其计数，然后在 String 上进行查找？

Answer 1

您只需将元素 frequency 添加到您的 TrieNode 类。

public class TrieNode {

    // make child nodes
    private TrieNode[] c;
    // flag for end of word
    private boolean flag = false;
    //stores frequency if flag is set
    private int frequency;

现在在插入方法中，在设置标志的同时添加频率..适当更改方法签名

protected void insert(String word, int frequency) {
    int val = word.charAt(0) - 64;
    ..........
    ..........
    // if the value of the child node at val is null, make a new nod
    if (word.length() > 1) {
        c[val].insert(word.substring(1),frequency);
    } else {
        c[val].flag = true;
        c[val].frequency = frequency;
    }
}

现在创建一个获取频率的新方法。它可以类似于 has 方法完成，在该方法中，您跟随分支直到结束，最后当您发现标志已设置时，返回频率。

public int getFreq(String word) {
    int val = word.charAt(0) - 64;
    if (word.length() > 1) {
        return c[val].getFreq(word.substring(1));
    } else if (c[val].flag == true && word.length() == 1) {
        return c[val].frequency;
    } else
        return -1;
}

----------------------------编辑---------------- ----------

首先使用has方法检查字符串，然后使用getFreq方法

    public int getFreq(String word) {
        if(has(word))
            return getFreqHelper(word);
        else
            return -1; //this indicates word is not present
    }

    private int getFreqHelper(String word) {
        int val = word.charAt(0) - 64;
        if (word.length() > 1) {
            return c[val].getFreq(word.substring(1));
        } else if (c[val].flag == true && word.length() == 1) {
            return c[val].frequency;
        } else
        return -1;
}