Return to Revisions

The “Suffix trie” provides a good way to think about the problem. However, the following implementation uses a more straightforward approach under the same principle. Given a list of directory name, we will produce the mapping {"dir" -> "label" ...}, where directories with distinctive last n components are labeled by their last n components concatenated, for smallest n.

We define labelRules[dirs, n] to give the list of rules {"dir" -> "label" ...} where each label consists of at least n components: we pick out from the directory list those distinguishable by last n components, then join them with labelRules[rest, n+1]. The recursion stops at labelRules[{}, _] which is just {}. The final result is given by labelRules[dirs, 1].

labelRules[{}, _Integer] := {}
labelRules[dirs : {__String}, n_Integer: 1] := Module[{s},
    s = Join @@
            Select[
                GatherBy[dirs, FileNameTake[#, {-n}] &],
                Length[#] == 1 &];
    Map[# -> StringReplace[
            FileNameTake[#, -n],
            $PathnameSeparator -> "."] &, s]
    ~Join~
    labelRules[Complement[dirs, s], n + 1]]


labelRules[{"common/a/b/c", "common/b/c", "common/x/y/z"}]

(*Out: {"common/x/y/z" -> "z", "common/a/b/c" -> "a.b.c", "common/b/c" -> "common.b.c"} *)

Note that the above does not always give the shortest possible label. For example it will give {"x/a/c" -> "a.c", "x/y/c" -> "y.c"} instead of e.g. {"x/a/c" -> "c", "x/y/c" -> "y.c"}.