I have a list of long directory names. For each directory name, I need a label just long enough to distinguish itself from the rest. Each label should be a FileNameJoin of one or more components of the corresponding directory name.

You can assume that all the directories names have a common beginning and are unique. They tend to differ by the last one or two components.

Example list: {"common/a/b/c", "common/b/c", "common/x/y/z"}

Result: {"a/b/c", "common/b/c", "z"} or equivalent.

Failing to find any system function that does this directly, I'm thinking along the lines of a recursive GroupBy, e.g.

f[dirs_List] := If[Length[dirs] == 1,
    FileNameTake @@ dirs,
    Normal @ GroupBy[dirs, FileNameTake -> FileNameDrop, f]]

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

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

I'm stuck at how to collect from such a structure. Also I'd like to hear your ideas before going further :)

  • $\begingroup$ @Öskå I need minimal labels. "z" is long enough to distinguish from the rest. Your example only strips away the first component "common". $\endgroup$
    – asterix314
    Oct 7 '14 at 9:55
  • $\begingroup$ What is the application you have in mind? Why don't just assign a number to each different directory? $\endgroup$ Oct 7 '14 at 10:18
  • $\begingroup$ @belisarius Indeed my current implementation uses Hash on the directory name. But this label is part of the user interface so I want it to be meaningful. $\endgroup$
    – asterix314
    Oct 7 '14 at 10:29
  • $\begingroup$ Is this what you are after? Can a Trie be implemented efficiently? $\endgroup$
    – Kuba
    Oct 7 '14 at 10:31
  • $\begingroup$ But isn't enough to eliminate the common header? Something like dirs = {"\\\\server\\share\\path\\last", "\\\\server\\share\\path\\last1", "\\\\server\\share\\path\\notlast\\last"}; NestWhile[Rest /@ # &, FileNameSplit /@ dirs, Length@Union@#[[All, 1]] == 1 &] $\endgroup$ Oct 7 '14 at 10:38

I'm not quite sure if your proposed nomenclature will be clear enough for end users. Anyway, here is a non optimal way:

dirs = {"\\\\server\\share\\path\\last", 

(* remove the common header*)
rcp = NestWhile[Rest /@ # &, FileNameSplit /@ dirs, Length@Union@#[[All, 1]] == 1 &]

(* Reverse, so to get the shortest distinguishable cutoff *)
r = Reverse /@ rcp

(* Form all possible nomenclatures*)
allcombs = FoldList[Join[#1, #2] &, List /@ #] & /@ r

(* Select the shorter one  (should be improved) *)
FileNameJoin /@  Reverse /@ 
  First@SortBy[Select[Tuples@allcombs, Length@Union@# == Length@# &], Length@Flatten@# &]

(* {"last", "last1", "last\\last1"} *)
  • $\begingroup$ Directory names like "\\server\share\path" are completely removed from the result. Moreover, the Tuples@allcombs grows exponentially with the length of the directory list... $\endgroup$
    – asterix314
    Oct 9 '14 at 7:41
  • $\begingroup$ @asterix314 The removal of the common header was done on purpose at the first line. If you have files hanging directly on it, just don't do the removal. Your second consideration is the sad truth. $\endgroup$ Oct 9 '14 at 7:57

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 last 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 @@
                GatherBy[dirs, FileNameTake[#, -n] &],
                Length[#] == 1 &];
    Map[# -> StringReplace[
            FileNameTake[#, -n],
            $PathnameSeparator -> "."] &, s]
    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"}.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.