时间戳

首页 > 解决方案 > 在 Trie 中找到长度为 n 的最频繁前缀

java - 在 Trie 中找到长度为 n 的最频繁前缀

问题描述

我正在使用 Trie 数据结构并试图找到：

  1. 长度为 n 的最频繁前缀
  2. 长度为 n 或更多的最常见前缀

有一个类似的帖子，但没有提供代码。上述帖子中建议的可能解决方案，我无法正确实施：

为每个 trie 节点添加一个计数器，并在使用该节点时递增该值，然后扫描节点以检查最频繁的前缀在哪里。

我能够计算每个节点的使用情况，但我不知道如何检查哪个前缀是最常见的前缀，然后如何从节点中构建这个前缀。问题：如何根据计数器找到长度为 n（或 >= n）的最常见前缀以及如何打印这样的前缀？

我的 trie 有数千个单词，但出于演示目的，我们可以坚持一组单词：

Trie t = new Trie();

t.insert("test");
t.insert("testify");
t.insert("television");
t.insert("car");
t.insert("cat");
t.insert("cabin");
t.insert("cab");

findMostFrequentPrefix(t.getRoot(), 2);

// expected output for provided data set: 
// 1) returns "ca" for exact length of 2 // "ca" appears 4 times and "te" appears 3 times
// 2) (not exactly sure about this) returns "ca" (appears 4 times, the second most frequent "cab" appears only 2 times) for length 2 or more, however if there was an additional most frequent prefix e.g. "cad" (5 times appearance), the function should return this one, instead of "ca"

Trie、Trie 节点的代码：

public class TrieNode {
    TrieNode[] children;
    boolean isEnd;
    char value;
    int counter;

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

    public TrieNode getNode(char ch) {
        if (this.children.length == 0) {
            return null;
        }
        for (TrieNode child : this.children) {
            if (child != null)
                if (child.value == ch)
                    return child;
        }
        return null;
    }

    public TrieNode[] getChildren() {
        return children;
    }

    public char getValue() {
        return value;
    }
}

public class Trie {
    private TrieNode root;

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

    public TrieNode getRoot() {
        return this.root;
    }

// Inserts a word into the trie.
    public void insert(String word) {
    TrieNode p = root;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);        
        int index = c - 'a';
        // p.counter++ incrementing the value which later will be used to examine the frequency
        if (p.children[index] == null) {
            TrieNode temp = new TrieNode();
            p.children[index] = temp;
            p.children[index].value = c;
            p.counter++;
            System.out.println("Counter: " + p.counter + " - for " + p.value);
            p = temp;
        } else {
            p.counter++;
            System.out.println("Counter: " + p.counter + " - for " + p.value);
            p = p.children[index];
        }
    }
    p.isEnd = true;
}

// Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode p = searchNode(word);
        if (p == null) {
            return false;
        } else {
            if (p.isEnd)
                return true;
        }
        return false;
    }

// Returns if there is any word in the trie
// that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode p = searchNode(prefix);
        if (p == null) {
            return false;
        } else {
            return true;
        }
    }

    public TrieNode searchNode(String s) {
        TrieNode p = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - 'a';
            if (p.children[index] != null) {
                p = p.children[index];
            } else {
                return null;
            }
        }
        if (p == root)
            return null;
        return p;
    }
}

遍历trie并找到长度为n的前缀的方法（应该有一个额外的函数来查找长度> = n的前缀）：

public static void findMostFrequentPrefix(TrieNode current, int n) {
        for (TrieNode temp : current.children) {
            if(temp != null) {
                // logic to examine which counter value is the greatest  
                // and then (maybe?) follow the idea until the length of n of prefix is reached             
                System.out.println(temp.value);
                findMostFrequentPrefix(temp, n);
            }
        }
    }

更新：对第二种情况的更清晰解释（> = n）：

假设我们有一组数据：

test
testi
testif
testify

如果我想找到最常见的长度前缀n = 2，我可以调用第一个答案中提供的函数：findMostFrequentPrefix(t.getRoot(), 2);-它会返回te。

但是在第二种情况下，我想找到长度可以大于或等于 n 的最常见前缀(>= n)。使用上面提供的数据，如果我调用了一个新函数findMostFrequentPrefixGreaterEqual(t.getRoot(), 1);，那么最常见的前缀可以是：

 1. n = 1 - "t" - max frequency = 4
 2. n = 2 - "te" - max frequency = 4
 3. n = 3 - "tes" - max frequency = 4
 4. n = 4 - "test - max frequency = 4

这意味着频率是相同的。该函数可以指示存在相同的频率，但返回长度最大的前缀，在本例中为：test。

标签： javaalgorithmdata-structuresprefixtrie

解决方案

首先，我认为您在跟踪每个TrieNode. 如果您检查表示incounter的 TrieNode的值，您会发现它是 1，而它应该是 2，因为：bcab

cab
cabin

您需要通过将方法末尾的代码更新为：记录表示单词中最后一个字符的节点的使用情况insert：

p.counter++;
p.isEnd = true;

通过该更新，您可以获得最常见的前缀（可能不止一个），如下所示：

public static int findMostFrequentPrefix(TrieNode current, int n, int max, char[] curr, int depth,
        List<Prefix> result)
{
    if (n == 0)
    {
        if (current.counter >= max)
        {
            if (current.counter > max)
            {
                result.clear();
                max = current.counter;
            }
            result.add(new Prefix(max, String.valueOf(curr)));
        }
        return max;
    }

    for (TrieNode child : current.children)
    {
        if (child != null)
        {
            curr[depth] = child.value;
            max = Math.max(max, findMostFrequentPrefix(child, n - 1, max, curr, depth + 1, result));
        }
    }
    return max;
}

使用一个小的PrefIx帮助类：

static class Prefix
{
    int freq;
    String value;
    public Prefix(int freq, String value)
    {
        this.freq = freq;
        this.value = value;
    }
}

测试：

int len = 3;
List<Prefix> result = new ArrayList<>();
int max = findMostFrequentPrefix(t.getRoot(), len, 0, new char[len], 0, result);
System.out.format("max frequency: %d%n", max);
for(Prefix p : result)
    System.out.println(p.value);

输出：

max frequency: 2
cab
tes

这是实现您的第二种方法的尝试，findMostFrequentPrefixGreaterEqual. 您必须测试并确认它在所有情况下都返回预期结果：

public static int findMostFrequentPrefixGreaterEqual(TrieNode current, int n, int max, char[] curr, int depth,
        List<Prefix> result)
{
    if (n <= 0)
    {
        if (current.counter >= max)
        {
            result.clear();
            max = current.counter;
            result.add(new Prefix(max, String.valueOf(curr, 0, depth)));
        }
        else
        {
            return max;
        }
    }

    for (TrieNode child : current.children)
    {
        if (child != null)
        {
            curr[depth] = child.value;
            max = Math.max(max, findMostFrequentPrefixGreaterEqual(child, n - 1, max, curr, depth + 1, result));
        }
    }
    return max;
}

测试：

t.insert("test");
t.insert("testi");
t.insert("testif");
t.insert("testify");

int len = 2;
int maxLen = 7;
List<Prefix> result = new ArrayList<>();
int max = findMostFrequentPrefixGreaterEqual(t.getRoot(), len, 0, new char[maxLen], 0, result);
System.out.format("max frequency: %d%n", max);
for(Prefix p : result)
    System.out.println(p.value);

请注意，我们现在必须知道 中任何单词的最大长度，Trie以便在char数组中分配足够的空间。

输出：

max frequency: 4
test

推荐阅读