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 names, we are to produce the mapping {"dir" -> "label" ...}, where directories with distinctive last n components are labeled by these components concatenated, for smallest n.

Algorithm: first pick out from the directory list those distinguishable by the last component. For the rest, pick by the second-to-last component, and so on.

Recursive implemention: let's define labelRules[dirs, n] to give the list of rules {"dir" -> "label" ...} where each label consists of at least n components: pick out from the dirs those distinguishable by exactly n components, augmented by labelRules[rest, n+1]. The recursion stops at labelRules[{}, _] = {}. 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. 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"}.