4
$\begingroup$

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 :)

$\endgroup$
  • $\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$ – Dr. belisarius 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$ – Dr. belisarius Oct 7 '14 at 10:38
3
$\begingroup$

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", 
        "\\\\server\\share\\path\\last2\\last1", 
        "\\\\server\\share\\path\\last2\\last\\last1"};

(* 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"} *)
| improve this answer | |
$\endgroup$
  • $\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$ – Dr. belisarius Oct 9 '14 at 7:57
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.