Найти все ключи в patricia trie, которые являются префиксом строки

Я пытаюсь найти все ключи, хранящиеся в дереве, которые являются допустимыми префиксами строки.

Пример: задано дерево, содержащее «ab», «abc», «abcd», «bc» и «bcd». Поиск строки "abcdefg" в дереве должен дать "abcd", "abc", "ab".

Я хотел бы использовать реализацию appache commons patricia trie для java, но, похоже, она не поддерживает такой поиск. Есть ли альтернативная реализация или простое решение этой проблемы?


java trie apache-commons patricia-trie
person user9457782    schedule 10.02.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я сам не использовал Apache Commons PatriciaTrie, но, насколько я проверял, вы можете легко получить только карту слов с префиксом некоторой строки. Большинство примеров, которые я нашел, также предоставляют базовые операции, такие как вставка, поиск. Я также столкнулся с некоторыми обсуждениями реализации Trie в гуаве, но ничего особенного.

Итак, вот мое простое предложение пользовательской реализации (но должно быть покрыто хорошим набором тестов, когда используется пользовательская реализация).

public class SimpleTrie {

    private static final int ALPHABET_COUNT = 26;

    class TrieNode {
        char value;
        TrieNode[] children;
        boolean isValidWord;

        TrieNode() {
            this(' ');
        }

        TrieNode(char value) {
            this.value = value;
            children = new TrieNode[ALPHABET_COUNT];
            isValidWord = false;
        }
    }

    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode current = root;

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);

            if (current.children[c - 'a'] == null) {
                current.children[c - 'a'] = new TrieNode(c);
            }

            current = current.children[c - 'a'];
        }

        current.isValidWord = true;
    }

    public List<String> findValidPrefixes(String word) {
        List<String> prefixes = new ArrayList<>();
        TrieNode current = root;

        StringBuilder traversedPrefix = new StringBuilder();

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);

            if (current.children[c - 'a'] != null) {
                current = current.children[c - 'a'];
                traversedPrefix.append(c);

                if (current.isValidWord) {
                    prefixes.add(traversedPrefix.toString());
                }
            }
        }

        return prefixes;
    }

    public static void main(String[] args) {
       SimpleTrie trie = new SimpleTrie();

        // insert "ab", "abc", "abcd", "bc" and "bcd"
        trie.insert("ab");
        trie.insert("abc");
        trie.insert("abcd");
        trie.insert("bc");
        trie.insert("bcd");

        List<String> validPrefixes = trie.findValidPrefixes("abcdefg");

        System.out.println(validPrefixes);
    }
}
person FVY    schedule 10.02.2019
comment
Спасибо за ответ! Я бы, вероятно, добавил этот метод в реализацию общих ресурсов вместо того, чтобы переопределять trie с нуля. Просто хотел спросить сначала, прежде чем начинать какие-либо приключения. - person user9457782; 11.02.2019