8
$\begingroup$

I have a long list of strings and I'm trying to find a more efficient way of removing those elements that are prefixes of another:

example = {"Clothing", "Clothing/Accessories", "Clothing/Accessories/Belts", 
   "Watches", "Watches/Accessories", "Watches/Accessories/Pocket Watch Chains"}

This is what I have, but it is not very optimized:

DeleteCases[example, a_ /; Or @@ Table[
     StringStartsQ[b, a], {b, DeleteCases[example, a]}]]
 {"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"} 

My real example has 13,732 strings and it takes 292.156 seconds to pare it down to 11,372.

$\endgroup$
  • 1
    $\begingroup$ You could try StringSplit and work with DeleteDuplicates or similar from there. $\endgroup$ – Yves Klett Jun 9 '16 at 19:15
  • 1
    $\begingroup$ What if there is a "Watch" string, should it be considered already included in "Watches" or should we only care about keys between / as a whole? $\endgroup$ – Kuba Jun 9 '16 at 19:45
10
$\begingroup$

Get the relation graph of your example

graph = SimpleGraph[RelationGraph[StringStartsQ, example], 
  VertexLabels -> "Name"]

Get the end of the vertex in every weaky connected graph

First@*TopologicalSort/@WeaklyConnectedGraphComponents[graph]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

Hope this can help. :)

$\endgroup$
  • 1
    $\begingroup$ +1 for pretty, but this will be deadly slow on a large list... $\endgroup$ – ciao Jun 10 '16 at 6:24
  • $\begingroup$ @ciao Good point out.Because of the RelationGraph is a bug function will result a ton wasteful computation.And I have reposted to Wolfram Research but get no response. $\endgroup$ – yode Jun 10 '16 at 6:27
9
$\begingroup$

Your solution doesn't seem to work when there are duplicates. Anyway, could you test the performance of the following method?

example =  RandomChoice[{"Clothing", "Clothing/Accessories", 
  "Clothing/Accessories/Belts", "Watch", "Watches/Accessories", 
  "Watches/Accessories/Pocket Watch Chains"
  },
  15000
];

Split[Sort@example,  StringStartsQ[#2, #] &][[;; , -1]] // AbsoluteTiming
{0.0562741, 
  {"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}}

In case where you want to care about keys between / as a whole, e.g. Watch to not be considered within Watches, you can use:

StringStartsQ[#2 <> "/", # <> "/"]

instead of

StringStartsQ[#2, #]
$\endgroup$
  • $\begingroup$ It's 2.43905 seconds, much much better! $\endgroup$ – user5601 Jun 9 '16 at 20:17
6
$\begingroup$

EDIT: My original answer, while quite a bit quicker than the current answer, dropped some words that should not be dropped, as does the other current answer, e.g.. {"pa","paperweight"} fails on both (unless that is the intent of the OP, which I doubt).

This led me to the following, which does not suffer from the problem and is also quite a bit quicker yet:

dumpPrefixes2 = DeleteCases[#, Alternatives @@ Flatten@StringCases[#, (a : __ ~~ "/" :> a)]] &;

Usage:

dumpPrefixes2@yourList

Using

wrds = WordList[];

example = 
 Flatten@Table[
   NestList[StringJoin[{#, "/", RandomSample[wrds, 1]}] &, 
    RandomChoice[wrds], RandomChoice[{3, 2, 1} -> {0, 1, 2}]], 20000]

to generate a test set, seemed to perform well on loungebook, perhaps @kuba or you can test with your data on a real machine...

$\endgroup$
  • $\begingroup$ You mean that pa should not be considered included in paperweight because it's not up to /? That's why I've asked OP in a comment. Untill I get the answer I'm going hard merging :) $\endgroup$ – Kuba Jun 10 '16 at 5:14
  • $\begingroup$ Yes, that's what I meant. Examples are like inventory items and categories, things like "watch" and "watchdog" then present a problem... $\endgroup$ – ciao Jun 10 '16 at 5:21
  • $\begingroup$ Yep. Added those cases handler too, can't test now but it seems that StringStartsQ[#2 <> "/", # <> "/"] should be enough. $\endgroup$ – Kuba Jun 10 '16 at 5:31
  • $\begingroup$ p.s. there seem to be a problem with handling duplicates by dumpPrefixes, this dumpPrefixes2@{"Watch", "Watch"} returns the input. Have I missed something? $\endgroup$ – Kuba Jun 10 '16 at 5:33
  • $\begingroup$ @Kuba - no, since OP did not specify behavior for duplicates, I did not remove them: goal was to be able to get result, and keep it stable (that is, in the order of the target list). Raises the question of what's to be done if duplicates are in list (they may not be), but trivially handled by a DeleteDuplicates pre/post operation. None of these may be issue for OP (and unless there are many lists or changing lists, who cares about performance?), I just found it an interesting tuning problem, posted idea. $\endgroup$ – ciao Jun 10 '16 at 6:16
5
$\begingroup$
Last /@ Gather[example, StringStartsQ[#2, #]&]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

FileNameJoin /@ Last /@ Gather[FileNameSplit /@ example, SubsetQ[#2, #] &]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

Also: slow but worth considering: a variation on @yode's approach

GraphComputation`SourceVertexList@SimpleGraph@RelationGraph[StringStartsQ, example]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

and

GeneralUtilities`GraphSources @ SimpleGraph @ RelationGraph[StringStartsQ, example]

{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

$\endgroup$
2
$\begingroup$
Clear[containerStrings]

containerStrings[stringList_] := Module[{TF, pos},
   TF = Outer[StringContainsQ, #, #]\[Transpose] &[stringList];
   pos = Position[Tally /@ TF, {{__}, {True, 1}}];
   Extract[stringList, pos]
]

containerStrings[example]
{"Clothing/Accessories/Belts", "Watches/Accessories/Pocket Watch Chains"}

It is yet to be tested whether Outer is efficient for a large list of strings.

$\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.