logo标签列表

从csv生成树状结构

javaalgorithmcsvparsinggrouping
7

我已经为这个问题苦恼了一段时间。我基本上是尝试从一组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

我试图使分组的方式尽可能灵活。最简单的分组方式是将记录1和记录2与值1和值2一起存储在记录2下，以便我们获得以下输出：

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 ) {
    ...
}

我只是想启动我的编程思维。

有什么想法吗？

1
大局是什么？对于行A,XX,12,34，你怎么知道12和34属于A还是XX？ - palacsint
6个回答
3
基本思路并不难：按照第一条记录，然后是第二条记录，以此类推进行分组，直到得到如下结果：
(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)

现在您需要考虑使用特定的数据结构，但是如果您理解算法（正如您提到的那样），这应该不会太困难。我认为，如果您能早些确定使用的数据结构，可能会有助于您的思考。

感谢您提供的伪代码思路。 - Andez
@Andez 对不起，我没有真正的Java代码，我认为在这个阶段草图更合适，以便专注于算法。请注意，这是目前唯一处理任意级别记录的解决方案。如果您想将代码翻译成Java（或任何人想根据我发布的内容发布Java答案），我很乐意提供帮助。 - Jong Bor Lee
3

这里是一个基本的工作解决方案，以junit的形式呈现（虽然没有断言），使用google-guava collections简化。代码是自说明的，而且你可以使用csv库来读取csv文件，而不是使用文件io。这应该能给你一个基本的思路。

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

}
谢谢，看起来很有趣。我会研究一下。 - Andez
1

如果你知道只会有两个层级的记录，我建议使用类似这样的代码：

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

当你读取新行时，查看外部映射以检查是否已存在该值为Record1的值，如果不存在，则为其创建新的空内部Map。然后检查内部映射是否存在该Record2的值。如果不存在，则创建新的List。然后读取这些值并将它们添加到列表中。
这就是问题所在，我将会有更多的列依赖于我处理的csv文件。一开始我确实考虑过使用Maps。谢谢Andez。 - Andez
1
    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;
}
1
我最近也有同样的需求，编写了tree-builder.com来完成任务。唯一的区别是，由于您的CSV布局不同，最后两个参数将分别为父项和子项，而不是对等项。此外，我的版本不接受标题行。
代码全部使用JavaScript编写；它使用jstree构建树形结构。您可以使用Firebug或仅查看页面源代码来了解其工作原理。很可能很容易将其调整为转义CSV中的逗号，以便将最后两个参数保留为单个子项。
0

根据问题的提出方式，我会采取以下步骤：

  1. 定义最终数据结构以包含树。
  2. 为原始文本中的每一行定义一个表示（例如链表以实现灵活性）。
  3. 编写一个方法，将表示的行插入到树数据结构中。对于每个不存在的分支，创建它；对于每个现有的分支，在遍历“行”链接列表结构时进行遍历。
  4. 从空树开始。
  5. 将文件的每一行读入您的行项目结构，并调用步骤3中定义的方法。

这有帮助吗？

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接