Найти наиболее частый префикс длины n в трие

Question

Я работаю со структурой данных Tr ie и пытаюсь найти:

1. самый частый префикс длины n
2. самый частый префикс длины n или более

Существует аналогичная запись , но код предоставлен не был. Возможное решение, которое было предложено в упомянутом посте, которое я не могу правильно реализовать:

Добавление счетчика для каждого узла tr ie и увеличение значения при использовании узла, затем сканирование узлы, чтобы проверить, где находится наиболее частый префикс.

Я могу подсчитать использование каждого узла, но я не знаю, как проверить, какой префикс является наиболее частым, а затем как построить этот префикс из узлов. Вопрос: Как найти наиболее часто встречающийся префикс длины n (или> = n) на основе счетчика и как напечатать такой префикс?

В моем tr ie есть тысячи слов, но для демонстрационной цели мы можем придерживаться набора слов:

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"

Код для узла Tr ie, Tr ie:

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;
    }
}

Метод обхода tr ie и поиск префикс длины 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.

Answer 1

Во-первых, я думаю, что у вас есть небольшая, но существенная ошибка в вашем коде, отслеживающая использование каждого TrieNode. Если вы изучите значение counter для TrieNode, представляющего b в cab, вы увидите, что это 1, когда должно быть 2, для:

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;
}

Test:

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