Строить дерево быстрее

Сохранение / загрузка двойного массива выполняется очень быстро, поскольку все данные хранятся в линейных массивах. Их также очень быстро искать, но вставки могут быть дорогостоящими. Бьюсь об заклад, где-то есть реализация Java.

Кроме того, если ваши данные статичны (т.е. вы не обновляете их на телефоне), рассмотрите для своей задачи DAFSA. Это одна из наиболее эффективных структур данных для хранения слов (должно быть лучше, чем "стандартные" попытки и попытки счисления как по размеру, так и по скорости, лучше, чем сжатые попытки по скорости, часто лучше, чем сжатые попытки по размеру). Существует хорошая реализация C ++: dawgdic - вы можете использовать его для создания DAFSA из командной строки, а затем использовать программу чтения Java для результирующей структуры данных (пример реализации: здесь).

Вы можете сохранить свое дерево в виде массива узлов, заменив ссылки на дочерние узлы на индексы массива. Ваш корневой узел будет первым элементом. Таким образом, вы можете легко сохранить / загрузить свое дерево из простого двоичного или текстового формата.

public class SimpleTrie {
    public class TrieNode {
        boolean valid;
        int[] children;
    }
    private TrieNode[] nodes;
    private int numberOfNodes;

    private TrieNode getNode() {
        TrieNode t = nodes[++numberOnNodes];
        return t;
    }
}

Просто создайте большой String [] и отсортируйте его. Затем вы можете использовать двоичный поиск, чтобы найти местоположение строки. Вы также можете выполнить запрос на основе префиксов без особых усилий.

Пример поиска префикса:

Метод сравнения:

private static int compare(String string, String prefix) {
    if (prefix.length()>string.length()) return Integer.MIN_VALUE;

    for (int i=0; i<prefix.length(); i++) {
        char s = string.charAt(i);
        char p = prefix.charAt(i);
        if (s!=p) {
            if (p<s) {
                // prefix is before string
                return -1;
            }
            // prefix is after string
            return 1;
        }
    }
    return 0;
}

Находит вхождение префикса в массиве и возвращает его местоположение (MIN или MAX означают, что не найдено)

private static int recursiveFind(String[] strings, String prefix, int start, int end) {
    if (start == end) {
        String lastValue = strings[start]; // start==end
        if (compare(lastValue,prefix)==0)
            return start; // start==end
        return Integer.MAX_VALUE;
    }

    int low = start;
    int high = end + 1; // zero indexed, so add one.
    int middle = low + ((high - low) / 2);

    String middleValue = strings[middle];
    int comp = compare(middleValue,prefix);
    if (comp == Integer.MIN_VALUE) return comp;
    if (comp==0)
        return middle;
    if (comp>0)
        return recursiveFind(strings, prefix, middle + 1, end);
    return recursiveFind(strings, prefix, start, middle - 1);
}

Получает массив String и префикс, распечатывает вхождения префикса в массиве

private static boolean testPrefix(String[] strings, String prefix) {
    int i = recursiveFind(strings, prefix, 0, strings.length-1);
    if (i==Integer.MAX_VALUE || i==Integer.MIN_VALUE) {
        // not found
        return false;
    }
    // Found an occurrence, now search up and down for other occurrences
    int up = i+1;
    int down = i;
    while (down>=0) {
        String string = strings[down];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        down--;
    }
    while (up<strings.length) {
        String string = strings[up];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        up++;
    }
    return true;
}

Вот достаточно компактный формат для хранения дерева на диске. Я укажу его по (эффективному) алгоритму десериализации. Инициализируйте стек, исходным содержимым которого является корневой узел дерева. Прочтите символы по одному и интерпретируйте их следующим образом. Значение буквы A-Z - «выделить новый узел, сделать его дочерним по отношению к текущей вершине стека и поместить вновь выделенный узел в стек». Буква указывает, в какой позиции находится дочерний элемент. Значение пробела - «установить действительный флаг узла на вершине стека в значение true». Значение символа возврата (\ b) - «вытолкнуть стек».

Например, вход

TREE \b\bIE \b\b\bOO \b\b\b

дает список слов

TREE
TRIE
TOO

. На рабочем столе создайте дерево, используя любой метод, а затем сериализуйте его с помощью следующего рекурсивного алгоритма (псевдокода).

serialize(node):
    if node is valid: put(' ')
    for letter in A-Z:
        if node has a child under letter:
            put(letter)
            serialize(child)
            put('\b')

Это не волшебная палочка, но вы, вероятно, можете немного сократить время выполнения, выполнив одно большое выделение памяти вместо нескольких маленьких.

Я увидел ускорение примерно на 10% в приведенном ниже тестовом коде (C ++, а не Java, извините), когда я использовал «пул узлов» вместо того, чтобы полагаться на отдельные распределения:

#include <string>
#include <fstream>

#define USE_NODE_POOL

#ifdef USE_NODE_POOL
struct Node;
Node *node_pool;
int node_pool_idx = 0;
#endif

struct Node {
    void insert(const std::string &s) { insert_helper(s, 0); }
    void insert_helper(const std::string &s, int idx) {
        if (idx >= s.length()) return;
        int char_idx = s[idx] - 'A';
        if (children[char_idx] == nullptr) {
#ifdef USE_NODE_POOL
            children[char_idx] = &node_pool[node_pool_idx++];
#else
            children[char_idx] = new Node();
#endif
        }
        children[char_idx]->insert_helper(s, idx + 1);
    }
    Node *children[26] = {};
};

int main() {
#ifdef USE_NODE_POOL
    node_pool = new Node[400000];
#endif
    Node n;
    std::ifstream fin("TWL06.txt");
    std::string word;
    while (fin >> word) n.insert(word);
}

Попытки выделить пространство всем возможным дочерним элементам (256) имеют огромное количество потраченного впустую пространства. Вы заставляете свой кеш плакать. Сохраните эти указатели на дочерние элементы в структуре данных с изменяемым размером.

Некоторые попытки оптимизируются за счет того, что один узел представляет длинную строку и разбивает эту строку только при необходимости.

Вместо простого файла вы можете использовать базу данных, такую ​​как sqlite и вложенный набор или дерево celko, для хранения дерева, а также можете построить более быстрое и короткое (с меньшим количеством узлов) дерево с троичным деревом поиска.

Мне не нравится идея адресации узлов по индексу в массиве, но только потому, что это требует еще одного добавления (индекса к указателю). Но с массивом предварительно выделенных узлов вы, возможно, сэкономите время на выделении и инициализации. И вы также можете сэкономить много места, зарезервировав первые 26 индексов для листовых узлов. Таким образом, вам не нужно выделять и инициализировать 180000 листовых узлов.

Также с помощью индексов вы сможете прочитать подготовленный массив узлов с диска в двоичном формате. Это должно быть в несколько раз быстрее. Но я не знаю, как это сделать на вашем языке. Это Ява?

Если вы проверили, что ваш исходный словарь отсортирован, вы также можете сэкономить время, сравнив некоторый префикс текущей строки с предыдущим. Например. первые 4 символа. Если они равны, вы можете начать свой

for (int level = 0; level ‹key.length (); level ++) {

петля с 5-го уровня.

Это неэффективное пространство или неэффективное время? Если вы катите обычное дерево, то место может быть частью проблемы при работе с мобильным устройством. Ознакомьтесь с попытками patricia / radix, особенно если вы используете его в качестве средства поиска по префиксу.

Trie: http://en.wikipedia.org/wiki/Trie

Патрисия / Radix trie: http://en.wikipedia.org/wiki/Radix_tree

Вы не упомянули язык, но вот две реализации попытки префикса в Java.

Обычное дерево: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/Trie.java

Patricia / Radix (эффективное пространство) trie: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

Вообще говоря, избегайте создания большого количества объектов с нуля в Java, поскольку это одновременно и медленно, и имеет огромные накладные расходы. Лучше реализовать свой собственный класс пула для управления памятью, который выделяет, например, полмиллиона записей за один раз.

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