algorithm - 木を作らない木分け

Question

次のようなデータを取るものを書く必要があります。

そして、次のように並べ替えます。

データは、私が上に示したものとまったく同じように見えます (文字を除く)。これは複数行の文字列で、タブの数によってツリーの階層レベルが決まります。

階層の各レベルを独自にソートできるようにしたいと考えています。

まともなアルゴリズムを思いつくのに苦労していたので、ここで質問しています。

私はこれをPHPで行っていますが、疑似コードのアプローチは大歓迎です。

また、最初にツリーを構築し、そのツリーをソートして出力できることも認識していますが、より洗練されたソリューションを見つけようとしています。

ありがとう。

score 1 · Accepted Answer

質問の過程で実際にこれを解決したので、ここで他の誰かに役立つかもしれない自分の質問に答えます。おそらく他にも良い答えがあるでしょう...

class TreeLineSorter {
    function sort($tree_lines) {
        $sorted_line_groups = $this->group_and_sort_lines($tree_lines);

        return $this->get_sorted_lines($sorted_line_groups);
    }

    private function cmp_line_groups($a, $b) {
        return strcasecmp($a[0], $b[0]); 
    }

    private function get_line_level($line) {
        return strspn($line, "\t");
    }

    private function get_line_groups($lines) {
        $curr_level = $this->get_line_level($lines[0]);
        $line_groups = array();
        $idx = -1;

        foreach($lines as $line) {
            $level = $this->get_line_level($line);

            if ($level == $curr_level) {
                $idx++;
            }

            $line_groups[$idx][] = $line;
        }

        return $line_groups;
    }

    private function group_and_sort_lines($lines) {
        $line_groups = $this->get_line_groups($lines);

        usort($line_groups, array($this,'cmp_line_groups'));

        foreach($line_groups as $key=>$group) {
            if (sizeof($group) > 1) {
                $new_group = array(array_shift($group));
                $new_group = array_merge($new_group, $this->group_and_sort_lines($group));

                $line_groups[$key] = $new_group;
            }
        }

        return $line_groups;
    }

    private function get_sorted_lines($sorted_line_groups) {
        $lines = array();

        foreach($sorted_line_groups as $group) {
            if (is_array($group)) {
                if (sizeof($group) > 1) {
                    $lines = array_merge($lines, $this->get_sorted_lines($group));
                }
                else {
                    $lines[] = $group[0];
                }
            }
            else {
                $lines[] = $group;
            }
        }

        return $lines;
    }
}

そして、ここに使用例があります：

    $sample_text = <<<QES
B
\tb
\tc
\ta
A
\tb
\ta
D
\ta
\t\tb
\t\ta   
C
QES;

    $tree_lines = explode("\n",$sample_text);

    $tree_line_sorter = new TreeLineSorter();

    $sorted_tree_lines = $tree_line_sorter->sort($tree_lines);

    print_r($tree_lines);
    print_r($sorted_tree_lines);

algorithm - 木を作らない木分け

1 に答える 1

Related

Reference