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 componentlast 2 components, 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}]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"}
.