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"}`.