Генерация древовидной структуры из CSV

Question

Я почесал голову над этой проблемой некоторое время. Я в основном пытаюсь сгенерировать древовидную иерархию из набора данных CSV. Данные CSV не обязательно упорядочены. Это примерно так:

Header: Record1,Record2,Value1,Value2
Row: A,XX,22,33
Row: A,XX,777,888
Row: A,YY,33,11
Row: B,XX,12,0
Row: A,YY,13,23
Row: B,YY,44,98

Я пытаюсь сделать группировку максимально гибкой. Самым простым для группировки было бы сделать это для Record1 и Record2 со значениями Value1 и Value2, хранящимися в Record2, чтобы мы получили следующий вывод:

Record1
    Record2
        Value1 Value2

Что будет:

A
    XX
        22,33
        777,888
    YY
        33,11
        13,23
B
    XX
        12,0
    YY
        44,98 

В настоящее время я храню настройки моей группы в Списке, который я не знаю, мешает ли это моим мыслям. Этот список содержит иерархию групп, например:

Record1 (SchemaGroup)
    .column = Record1
    .columns = null
    .childGroups =
        Record2 (SchemaGroup)
            .column = Record1
            .columns = Value1 (CSVColumnInformation), Value2 (CSVColumnInformation)
            .childGroups = null

Код для этого выглядит следующим образом:

private class SchemaGroup {
    private SchemaGroupType type = SchemaGroupType.StaticText;  // default to text
    private String text;
    private CSVColumnInformation column = null;
    private List<SchemaGroup> childGroups = new ArrayList<SchemaGroup>();
    private List<CSVColumnInformation> columns = new ArrayList<CSVColumnInformation>();
}


private enum SchemaGroupType {
    /** Allow fixed text groups to be added */
    StaticText,
    /** Related to a column with common value */
    ColumnGroup
}

Я изо всех сил пытаюсь разработать алгоритм для этого, пытаясь придумать, какую структуру использовать. В настоящее время я анализирую CSV сверху вниз, используя свой собственный класс-обертку:

CSVParser csv = new CSVParser(content);
String[] line;
while((line = csv.readLine()) != null ) {
    ...
}

Я просто пытаюсь запустить мой мозг кодирования.

Есть мысли?

Answer 1

Основная идея не сложна: группируйте по первой записи, затем по второй записи и т. Д., Пока не получите что-то вроде этого:

(A,XX,22,33)
(A,XX,777,888)
-------------------------
(A,YY,33,11)
(A,YY,13,23)
=============
(B,XX,12,0)
-------------------------
(B,YY,44,98)

, а затем работайте задом наперед, чтобы построить деревья.

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

Я предполагаю, что каждая строка в вашем CSV представлена ​​как кортеж. Каждый кортеж имеет «записи» и «значения», используя те же термины, которые вы используете в своем вопросе. «Записи» - это вещи, которые необходимо поместить в иерархическую структуру. «Ценностями» будут листья дерева. Я буду использовать цитаты, когда я использую эти термины с этими конкретными значениями.

Я также предполагаю, что все «записи» предшествуют всем «значениям».

Без лишних слов, код:

// builds tree and returns a list of root nodes
// list_of_tuples: a list of tuples read from your csv
// curr_position: used to keep track of recursive calls
// number_of_records: assuming each csv row has n records and then m values, number_of_records equals n
function build_tree(list_of_tuples, curr_position, number_of_records) {
    // check if we have already reached the "values" (which shouldn't get converted into trees)
    if (curr_position == number_of_records) {
        return list of nodes, each containing a "value" (i.e. everything from position number_of_records on)
    }

    grouped = group tuples in list_of_tuples that have the same value in position curr_position, and store these groups indexed by such common value
    unique_values = get unique values in curr_position

    list_of_nodes = empty list

   // create the nodes and (recursively) their children
    for each val in unique_values {
        the_node = create tree node containing val
        the_children = build_tree(grouped[val], curr_position+1, number_of_records)
        the_node.set_children(the_children)

        list_of_nodes.append(the_node)
    }

    return list_of_nodes
}

// in your example, this returns a node with "A" and a node with "B"
// third parameter is 2 because you have 2 "records"
build_tree(list_parsed_from_csv, 0, 2)

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

Answer 2

Вот основное рабочее решение в форме junit (без каких-либо утверждений), упрощенное с помощью google-guava collection * . Код не требует пояснений, и вместо файла io вы используете библиотеки csv для чтения csv. Это должно дать вам основную идею.

import java.io.File;
import java.io.IOException;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Set;

import org.junit.Test;

import com.google.common.base.Charsets;
import com.google.common.base.Splitter;
import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;
import com.google.common.io.Files;

public class MyTest
{
    @Test
    public void test1()
    {
        List<String> rows = getAllDataRows();

        Multimap<Records, Values> table = indexData(rows);

        printTree(table);

    }

    private void printTree(Multimap<Records, Values> table)
    {
        Set<String> alreadyPrintedRecord1s = Sets.newHashSet();

        for (Records r : table.keySet())
        {
            if (!alreadyPrintedRecord1s.contains(r.r1))
            {
                System.err.println(r.r1);
                alreadyPrintedRecord1s.add(r.r1);
            }

            System.err.println("\t" + r.r2);

            Collection<Values> allValues = table.get(r);

            for (Values v : allValues)
            {
                System.err.println("\t\t" + v.v1 + " , " + v.v2);
            }
        }
    }

    private Multimap<Records, Values> indexData(List<String> lines)
    {
        Multimap<Records, Values> table = ArrayListMultimap.create();

        for (String row : lines)
        {
            Iterable<String> split = Splitter.on(",").split(row);
            String[] data = Iterables.toArray(split, String.class);

            table.put(new Records(data[0], data[1]), new Values(data[2], data[3]));
        }
        return table;
    }

    private List<String> getAllDataRows()
    {
        List<String> lines = Collections.emptyList();

        try
        {
            lines = Files.readLines(new File("C:/test.csv"), Charsets.US_ASCII);
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }

        lines.remove(0);// remove header

        return lines;
    }
}



public class Records
{
    public final String r1, r2;

    public Records(final String r1, final String r2)
    {
        this.r1 = r1;
        this.r2 = r2;
    }

    @Override
    public int hashCode()
    {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((r1 == null) ? 0 : r1.hashCode());
        result = prime * result + ((r2 == null) ? 0 : r2.hashCode());
        return result;
    }

    @Override
    public boolean equals(final Object obj)
    {
        if (this == obj)
        {
            return true;
        }
        if (obj == null)
        {
            return false;
        }
        if (!(obj instanceof Records))
        {
            return false;
        }
        Records other = (Records) obj;
        if (r1 == null)
        {
            if (other.r1 != null)
            {
                return false;
            }
        }
        else if (!r1.equals(other.r1))
        {
            return false;
        }
        if (r2 == null)
        {
            if (other.r2 != null)
            {
                return false;
            }
        }
        else if (!r2.equals(other.r2))
        {
            return false;
        }
        return true;
    }

    @Override
    public String toString()
    {
        StringBuilder builder = new StringBuilder();
        builder.append("Records1and2 [r1=").append(r1).append(", r2=").append(r2).append("]");
        return builder.toString();
    }

}


public class Values
{
    public final String v1, v2;

    public Values(final String v1, final String v2)
    {
        this.v1 = v1;
        this.v2 = v2;
    }

    @Override
    public int hashCode()
    {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((v1 == null) ? 0 : v1.hashCode());
        result = prime * result + ((v2 == null) ? 0 : v2.hashCode());
        return result;
    }

    @Override
    public boolean equals(final Object obj)
    {
        if (this == obj)
        {
            return true;
        }
        if (obj == null)
        {
            return false;
        }
        if (!(obj instanceof Values))
        {
            return false;
        }
        Values other = (Values) obj;
        if (v1 == null)
        {
            if (other.v1 != null)
            {
                return false;
            }
        }
        else if (!v1.equals(other.v1))
        {
            return false;
        }
        if (v2 == null)
        {
            if (other.v2 != null)
            {
                return false;
            }
        }
        else if (!v2.equals(other.v2))
        {
            return false;
        }
        return true;
    }

    @Override
    public String toString()
    {
        StringBuilder builder = new StringBuilder();
        builder.append("Values1and2 [v1=").append(v1).append(", v2=").append(v2).append("]");
        return builder.toString();
    }

}

Answer 3

Недавно мне нужно было сделать почти то же самое, и я написал tree-builder.com для выполнения этой задачи.Разница лишь в том, что, поскольку у вас есть CSV, последние два параметра будут родительскими и дочерними, а не одноранговыми.Кроме того, моя версия не принимает строку заголовка.

Код полностью на JavaScript;он использует jstree для построения дерева.Вы можете использовать firebug или просто просмотреть источник на странице, чтобы увидеть, как это делается.Вероятно, было бы довольно легко настроить его, чтобы экранировать запятую в CSV, чтобы последние два параметра оставались для одного ребенка.

Answer 4

Если вы знаете, что у вас будет только два уровня Record с, я бы использовал что-то вроде

Map<string, Map<string, List<Values>>>

Когда вы читаете новую строку, вы смотрите на внешнюю карту, чтобы проверить, существует ли уже это значение для Record1, и если нет, создайте для него новый пустой внутренний Map.

Затем проверьте внутреннюю карту, существует ли значение для этого Record2. Если нет, создайте новый List.

Затем прочитайте значения и добавьте их в список.

Answer 5

    public static void main (String arg[]) throws Exception
{
    ArrayList<String> arRows = new ArrayList<String>();
    arRows.add("A,XX,22,33");
    arRows.add("A,XX,777,888");
    arRows.add("A,YY,33,11");
    arRows.add("B,XX,12,0");
    arRows.add("A,YY,13,23");
    arRows.add("B,YY,44,98");
    for(String sTreeRow:createTree(arRows,",")) //or use //// or whatever applicable
        System.out.println(sTreeRow);
}
    public static ArrayList<String> createTree (ArrayList<String> arRows, String sSeperator) throws Exception
{
    ArrayList<String> arReturnNodes = new ArrayList<String>();
    Collections.sort(arRows);
    String sLastPath = "";
    int iFolderLength = 0;
    for(int iRow=0;iRow<arRows.size();iRow++)
    {
        String sRow = arRows.get(iRow);
        String[] sFolders = sRow.split(sSeperator);
        iFolderLength = sFolders.length;
        String sTab = "";
        String[] sLastFolders = sLastPath.split(sSeperator);
        for(int i=0;i<iFolderLength;i++)
        {
            if(i>0)
                sTab = sTab+"    ";
            if(!sLastPath.equals(sRow))
            {

                if(sLastFolders!=null && sLastFolders.length>i)
                {
                    if(!sLastFolders[i].equals(sFolders[i]))
                    {
                        arReturnNodes.add(sTab+sFolders[i]+"");
                        sLastFolders = null;
                    }
                }
                else
                {
                    arReturnNodes.add(sTab+sFolders[i]+"");
                }
            }
        }
        sLastPath = sRow;
    }
    return arReturnNodes;
}

Answer 6

Исходя из того, как ставится эта проблема, я бы сделал следующее:

1. Определите, как будет выглядеть ваша окончательная структура данных, чтобы содержать дерево.
2. Определить представление длякаждая строка в исходном тексте (возможно, связанный список для гибкости)
3. Напишите метод, который берет представленную строку и вставляет ее в древовидную структуру данных.Для каждой несуществующей ветви создайте ее;для каждой существующей ветви пройдите по ней, пройдя по структуре списка ссылок «строка».
4. Начните с пустого дерева.
5. Считайте каждую строку файла в структуру элемента строки ивызовите метод, определенный в шаге 3.

Помогает ли это?