Сериализация и десериализация триподобной структуры данных - PullRequest
Новая
       44

Сериализация и десериализация триподобной структуры данных

0 голосов
/ 26 августа 2018

Я пытаюсь сериализовать и десериализовать Trie-подобную структуру данных, которая имеет данные / символ в каждом узле. Таким образом, для формирования целого слова требуется обход от корневого узла до конечного.

Сериализация и десериализация должны выполняться по предварительному заказу, т. Е. Обрабатывать дочерние элементы в DFS.

# отмечает конец обхода для этого узла, т. Е. У триподобного узла больше нет дочерних элементов.

Вот что я пробовал. 

public class SerializeDeserialize {

    public static void main(String[] args) {
        // prepare TrieNode Tree
        TrieNodeSD root = buildTrienodeTree();
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
        System.out.println();
        TrieNodeSD newRoot = deserialize(sb.toString().split(","), new int[] {0});
        StringBuilder newsb = new StringBuilder();
        serialize(newRoot, newsb);
        newsb.deleteCharAt(newsb.length()-1);
        System.out.println(newsb.toString());
    }

    private static void serialize(TrieNodeSD node, StringBuilder sb) {
        if (node == null) return;
        sb.append(node.character + ",");
        if (node.characters != null && node.characters.size() > 0) {
            for (Character c : node.characters.keySet()) {
                serialize(node.characters.get(c), sb);
            }
        }
        sb.append("#,");
    }

    // DOESN'T WORK!!
    private static TrieNodeSD deserialize(String[] data, int[] t) {
        if (t[0] >= (data.length-1) || data[t[0]].equals("#")) return null;
        TrieNodeSD node = new TrieNodeSD(data[t[0]].charAt(0));
        t[0] = t[0] + 1;
        TrieNodeSD child = deserialize(data, t);
        if (child != null) node.characters.put(child.character, child);
        return node;
    }

    private static TrieNodeSD buildTrienodeTree() {
        TrieNodeSD root = new TrieNodeSD('A');

        root.characters.put('B', new TrieNodeSD('B'));
        root.characters.get('B').characters.put('E', new TrieNodeSD('E'));
        root.characters.get('B').characters.put('F', new TrieNodeSD('F'));
        root.characters.get('B').characters.get('F').characters.put('K', new TrieNodeSD('K'));

        root.characters.put('C', new TrieNodeSD('C'));

        root.characters.put('D', new TrieNodeSD('D'));
        root.characters.get('D').characters.put('G', new TrieNodeSD('G'));
        root.characters.get('D').characters.put('H', new TrieNodeSD('H'));
        root.characters.get('D').characters.put('I', new TrieNodeSD('I'));
        root.characters.get('D').characters.put('J', new TrieNodeSD('J'));

        return root;
    }
}

class TrieNodeSD {
    Map<Character, TrieNodeSD> characters;
    char character;
    public TrieNodeSD(char c) {
        this.characters = new HashMap<Character, TrieNodeSD>();
        this.character = c;
    }
    @Override
    public String toString() { return this.character + "";  }
}

Сериализация дает вывод в формате предварительного заказа (например, A,B,E,#,F,K,#,#,#,C,#,D,G,#,H,#,I,#,J,#,#,#).

PROBLEM: во время десериализации код не обрабатывает все дочерние элементы правильно и не связывает их с правильным родителем.

Может кто-нибудь подсказать, как исправить обработку в методе deserialize или помочь мне с указателями, что мне не хватает?

Ответы [ 2 ]

0 голосов
/ 31 августа 2018

Наконец-то нашли способ десериализации сериализованной формы предварительного заказа структуры данных Trie-Like. 

import java.util.HashMap;
import java.util.Map;

/**
 *                              A<br>
 *                  /           |           \<br>
 *                  B           C           D<br>
 *              /       \           /   /       \   \<br>
 *              E       F           G   H       I   J<br>
 *                      |<br>
 *                      K<br>
 * 
 *
 */
public class SerializeDeserialize {

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        StringBuilder newsb = new StringBuilder();

        // prepare TrieNode Tree
        TrieNodeSD root = buildTrienodeTree();

        // serialize tree into string
        serialize(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
        System.out.println();

        // construct tree again from serialized string
        TrieNodeSD newRoot = deserialize(sb.toString().split(","), new int[] { 0 });

        // Verify : again serialize above de-serialized tree to match both
        // trees serialized format.
        serialize(newRoot, newsb);
        newsb.deleteCharAt(newsb.length() - 1);
        System.out.println(newsb.toString());
    }

    private static void serialize(TrieNodeSD node, StringBuilder sb) {
        if (node == null) return;
        sb.append(node.character + ",");
        if (node.characters != null && node.characters.size() > 0) {
            for (Character c : node.characters.keySet()) {
                serialize(node.characters.get(c), sb);
            }
        }
        sb.append("#,");
    }

    private static TrieNodeSD deserialize(String[] data, int[] t) {
        if (t[0] >= (data.length - 1) || data[t[0]].equals("#")) return null;
        TrieNodeSD node = new TrieNodeSD(data[t[0]].charAt(0));
        while (true) {
            t[0] = t[0] + 1;
            TrieNodeSD child = deserialize(data, t);
            if (child != null) node.characters.put(child.character, child);
            else break;
        }
        return node;
    }

    private static TrieNodeSD buildTrienodeTree() {
        TrieNodeSD root = new TrieNodeSD('A');

        root.characters.put('B', new TrieNodeSD('B'));
        root.characters.get('B').characters.put('E', new TrieNodeSD('E'));
        root.characters.get('B').characters.put('F', new TrieNodeSD('F'));
        root.characters.get('B').characters.get('F').characters.put('K', new TrieNodeSD('K'));

        root.characters.put('C', new TrieNodeSD('C'));

        root.characters.put('D', new TrieNodeSD('D'));
        root.characters.get('D').characters.put('G', new TrieNodeSD('G'));
        root.characters.get('D').characters.put('H', new TrieNodeSD('H'));
        root.characters.get('D').characters.put('I', new TrieNodeSD('I'));
        root.characters.get('D').characters.put('J', new TrieNodeSD('J'));

        return root;
    }
}

class TrieNodeSD {
    Map<Character, TrieNodeSD> characters;
    char character;

    public TrieNodeSD(char c) {
        this.characters = new HashMap<Character, TrieNodeSD>();
        this.character = c;
    }

    @Override
    public String toString() {
        return this.character + "";
    }
}

Пробный прогон: Сериализация заданной Trie-Like структуры данных при обходе по предварительному заказу, использование сериализованной строки для построения Trie-данных, подобных структуре данных, то есть десериализации и, наконец, сериализации еще раз, чтобы убедиться, что сериализованная форма соответствует фактическому дереву. 

A,B,E,#,F,K,#,#,#,C,#,D,G,#,H,#,I,#,J,#,#,#

A,B,E,#,F,K,#,#,#,C,#,D,G,#,H,#,I,#,J,#,#,#
0 голосов
/ 27 августа 2018

Не совсем уверен насчет вашего trie data structure, но если вы ссылаетесь на trie, то должны быть некоторые недоразумения.

В вики есть четкая спецификация для trie .

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

(содержание из вики, я только что добавил акцент)

ПРОБЛЕМА: во время десериализации код не обрабатывает все дочерние элементы правильно и не связывает ихс правильным родителем.

Даже для древовидной структуры с ключом в узле ваше решение не будет работать, так как вы игнорируете размер дочерних элементов, используя map вместо fixed-sized массива, который весьма важен для десериализации сериализованных данных.

Использование map делает невозможным определение, какой узел является родительским, а какие -дети.

Что касается binary search tree или действительного trie tree, то их структура предопределена, с помощью которой вы затем можете сериализовать и десериализовать дерево, поскольку оно детерминировано,

Возможно Дерево корней - это то, что вы действительно хотите.

Кстати, вы можете сериализовать и десериализовать непосредственно в *Node.

Например, сериализация может выглядеть примерно так: 

@Override
public String toString() {
    List<String> resultList = new ArrayList<>();
    for (TrieNode child : children) {
        if (child == null) resultList.add("#");
        else resultList.add(child.toString());
    }
    return resultList.stream().collect(Collectors.joining(","));
}
...