java - 从 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 中的每一行都表示为一个元组。每个元组都有“记录”和“值”，使用您在问题中使用的相同术语。 “记录”是必须放入层级结构中的东西。 “值(value)观”将是树的叶子。当我使用这些具有这些特定含义的术语时，我会使用引号。

我还假设所有“记录”都在所有“值”之前。

废话不多说，上代码:

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

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