Постройте быстрее

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

TREE
TRIE
TOO

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

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')

Ответ 5

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

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

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

Ответ 6

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

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

Patricia/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

Патрисия/Радикс (космическая эффективность): http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

Ответ 7

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

Ответ 8

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

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

Ответ 9

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

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

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

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

с 5-го уровня.