从 csv 生成树结构

我已经为这个问题摸不着头脑有一段时间了。我基本上试图从一组 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 ) {
    ...
}

我只是想启动我的编码大脑。

有什么想法吗？

基本思想并不困难：按第一条记录分组，然后按第二条记录分组，依此类推，直到得到如下所示的结果：

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

现在您必须考虑要使用的具体数据结构，但希望如果您了解算法，这应该不会太困难（正如您提到的，我认为尽早决定数据结构可能会阻碍您的想法） 。