Splitting up delimited data in lists

One task that I frequently find myself doing in Mathematica is splitting lists into lists of sublists, using specific elements to define the break-points. This is particularly useful with imported files which often have a structure like this:

section 1
a
b
c
section 2
d
e
f


Upon import, this turns into

{"section 1", "a", "b", "c", "section 2", "d", "e", "f"}


I'd like to split this into sublists at the strings that mark sections, like so:

{{"a", "b", "c"}, {"d", "e", "f"}}


Doing this with Mathematica's library functions is pretty awkward. First, you want a predicate that tells you where the delimiting elements are:

delimiterQ[s_String] := StringMatchQ[s, "section "~~__]
delimiterQ[_]        := False


In cases like this, rule replacement seems like an elegant solution:

In[1]:= delimitingRule = {before___, _?delimiterQ,
Longest[run : Except[_?delimiterQ] ...],
after___} :> {before, {run}, after};
{"section 1", "a", "b", "c", "section 2", "d", "e", "f"} //. delimitingRule
Out[1]= {{"a", "b", "c"}, {"d", "e", "f"}}


However, the performance of this kind of solution is truly atrocious, as you might expect (I got bored of waiting with a test list of 1000 elements after a couple minutes). The alternative I usually use is:

In[2]:= splitAtDelimiters[l_List, test_] :=
With[{delimIndices = Flatten@Position[l, _?test, {1}],
len = Length@l},
With[{first = First@delimIndices, last = Last@delimIndices},
Take[l, #] & /@ Join[
If[1 < first, {{1, first - 1}}, {}],
# + {1, -1} & /@ Partition[delimIndices, 2, 1],
If[last < len, {{last + 1, len}}, {}]]]];
In[3]:= splitAtDelimiters[
{"section 1", "a", "b", "c", "section 2", "d", "e", "f"},
delimiterQ]
Out[3]= {{"a", "b", "c"}, {"d", "e", "f"}}


This works OK, but I always think there must be a better way to do things whenever I generate a list of indices into a list just to immediately extract them all again. That sort of round trip is a Mathematica "code smell", IMO, and in this particular case there's a lot of extra work done to deal with corner cases involving delimiters at the begining or end of the list.

Any other suggestions? I think that there must be a way to do it with Split, but after trying a few obvious things I'm not sure what it is.

EDIT to add: My approach using Position has an annoying bug in cases where you are interested in splitting a list of lists (which is common when processing, say, Excel imports). The corrected version requires use of the Heads -> False option for Position:

splitAtDelimiters[l_List, test_] :=
With[{delimIndices =
Flatten@Position[l, _?test, {1}, Heads -> False], len = Length@l},
With[{first = First@delimIndices, last = Last@delimIndices},
Take[l, #] & /@ Join[
If[1 < first, {{1, first - 1}}, {}],
# + {1, -1} & /@ Partition[delimIndices, 2, 1],
If[last < len, {{last + 1, len}}, {}]]]]


Bugs like this make me think my unease with this approach is justified.

EDIT the second: rcollyer suggested I move this from StackOverflow.

-

The first thing that comes to mind is:

list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

delimiterQ[s_String] := StringMatchQ[s, "section " ~~ __]
delimiterQ[_] := False

SplitBy[list, delimiterQ][[2 ;; ;; 2]]

{{"a", "b", "c"}, {"d", "e", "f"}}


Szabolcs raised the concern that if the first element of list is not a delimiter this breaks. If you know in advance that the first element is not a delimiter you can use [[;; ;; 2]] -- if it is uncertain you might use this rather ugly blob of code:

#[[If[delimiterQ@#[[1, 1]], 2, 1] ;; All ;; 2]] & @ SplitBy[list, delimiterQ]


If you can create a list of all separators another option would be using Import. With your data in splitdat.txt:

Rest@Import["splitdat.txt", "Table",
"LineSeparators" -> {"section 1", "section 2"},
"FieldSeparators" -> "\n"]

{{"a", "b", "c"}, {"d", "e", "f"}}


Likewise ReadList, which is probably faster:

ReadList["splitdat.txt",
Word,
WordSeparators -> "\n",
RecordLists -> True,
RecordSeparators -> {"section 1", "section 2"}
]

-
This is perfect, and it leaves the option of keeping the delimiters should I need them (which I sometimes do). –  Pillsy Feb 22 '12 at 16:49
@Pillsy okay, great! But you should wait to Accept an answer until you have seen what everyone else has to offer. :-) –  Mr.Wizard Feb 22 '12 at 16:51
This Split approach won't work if the list does not start with a delimiter. –  Szabolcs Feb 22 '12 at 17:02
@Szabolcs if the list doesn't start with a delimiter just use [[;; ;; 2]] instead. It is not hard to test if the list starts with a delimiter. –  Mr.Wizard Feb 22 '12 at 17:04
I think the SplitBy solution is superior as you may not know the number of "LineSeparators" or RecordSeparators present. It somewhat irks me that you can't pass something a little more dynamic to those like a StringExpression (e.g. "section " ~~ __) or a RegularExpression to allow for more variation in importing. –  rcollyer Feb 22 '12 at 17:10

If you import your sample file as text, then do a StringSplit you have more control:

test="section 1\na\nb\nc\nsection 2\nd\ne\nf"
Rest/@StringSplit@StringSplit[test, "section "]


This outputs {{"a", "b", "c"}, {"d", "e", "f"}}

Edit In a comment, rcollyer complained about the inability to use RegularExpression. Using this approach you can:

StringSplit@StringSplit[test, "section " ~~ RegularExpression["\\d"]]


which has the same output as above.

-
An excellent alternative. –  Mr.Wizard Feb 22 '12 at 16:55

Here is a solution based on a combination of rules and recursion, but not very efficient (the inefficiency spotted by @Pillsy, see below for the explanation):

Clear[splitAtDelimeters];
splitAtDelimeters[l_List, test_] :=
Module[{split, h},
h[{}] := h[];
h[h[x___], h[y___]] := h[x, y];
split[ls_] :=
First@ReplaceList[
ls,
{{x___, el_?test, y___} :> h[h[{x}], split[{y}]], x_List :> h[x]},
1];
List @@ split[l]];


For example:

list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

delimiterQ[s_String] := StringMatchQ[s, "section " ~~ __]
delimiterQ[_] := False

splitAtDelimeters[list,delimiterQ]

(*
==> {{a,b,c},{d,e,f}}
*)


EDIT

As rightly noted by @Pillsy, the above solution is still quadratic complexity in the size of the list. I missed this point initially, but this is clearly due to massive list/ sequence copying in patterns like

{x___, el_?test, y___} :> h[h[{x}], split[{y}]]


(y is the culprit here).

Here is a linear time solution, based entirely on linked lists:

Clear[splitAtDelimetersLL];
splitAtDelimetersLL[l_List, test_] :=
Module[{split, ll, llist, hh},
SetAttributes[{ll, hh}, HoldAllComplete];
llist = Fold[ll[#2, #1] &, ll[], Reverse@l];
split[acc_, ll[_?test, t_], r_] := split[hh[], t, ll[r, acc]];
split[acc_, ll[h_, t_], r_] := split[hh[acc, h], t, r];
split[acc_, ll[], r_] := ll[r, acc];
Map[
Flatten[#, Infinity, hh] /. {hh[] :> Sequence[], hh[x__] :> {x}} &,
List @@ Flatten[split[hh[], llist, hh[]], Infinity, ll]
]
];


It may be somewhat less elegant, but it avoids excessive copying characteristic for the previous one. It also is tail-recursive, so it affects $IterationLimit rather than $RecursionLimit, which is good. This solution is just as efficient as the one based on SplitBy, proposed by @Mr.Wizard, at least for this predicate / problem.

-
Leonid, I realize I hold you to a higher standard, but what is the benefit of this over SplitBy? Or are you showing how one can implement such a function himself? –  Mr.Wizard Feb 22 '12 at 16:54
@Mr.Wizard I just think this is an interesting code pattern, based entirely on rules (and recursion) and still being efficient. I can imagine other cases when this can be useful and no simple function like Split or SplitBy will exist. For this particular case, I don't claim any superiority of my code. Also, the OP wished to have some rule-based solution for this, that was part of my motivation. So, yes, if you wish, this illustrates how to efficiently implement a version of SplitBy with only the replacement rules. –  Leonid Shifrin Feb 22 '12 at 17:00
Good enough for me. +1 –  Mr.Wizard Feb 22 '12 at 17:05
@Leonid This is more efficient than my rule-based solution, but it's still O(n^2). Using rule-replacement with sequence-based patterns in lists is really hard to do efficiently. –  Pillsy Feb 22 '12 at 17:21
@Pillsy Actually, you are right, I was not careful enough. Please see my edit for a linear-time solution. –  Leonid Shifrin Feb 22 '12 at 17:52

Inspired by rcollyer's state machine answer, I realized that with a little change you can generate index pairs to pass to Take, as in my original solution. The advantage of doing things this way is that, with a little help from Boole, you can easily recast the state machine as something that works in Compile.

compiledIndexer =
Compile[{{tests, _Integer, 1}},
With[{n = Length@tests},
Module[{
j = 1,
fill = 0,
result = ConstantArray[0, {2*Count[tests, 0], 2}],
state = tests[[1]]},
Do[
If[BitXor[tests[[i]], state] == 1,
result[[++fill]] = {j, i - 1};
state = tests[[i]];
j = i],
{i, 2, n}];
result[[++fill]] = {j, n};
Take[result, fill]]]];


The rest of the function is just a one-liner. Well, a two-liner, because Compile can't return a zero-length list, so you need to specially handle an empty list:

splitWithCompile[{}, _] = {};
splitWithCompile[list_List, test_] :=
With[{tests = Boole[test /@ list]},
Take[list, #] & /@ compiledIndexer[tests]]


On my machine, this goes about 50% slower than Heike's SplitBy solution, but that's using Mathematica's bytecode compiler. I don't have a C compiler on this machine, so I can't really take full advantage of the Mathematica 8 compiler.

-
Pretty cool, +1. I'd recommend to replace ConstantArray (which is not compilable), with Table. –  Leonid Shifrin Feb 22 '12 at 19:08
@LeonidShifrin I tried that, and it didn't make a discernible difference in performance. It's just one external call, and there's no reason ConstantArray can't really fly here. –  Pillsy Feb 23 '12 at 0:26
Agree - when it is not in a loop, there isn't much of a difference. I just like it when everything inside Compile is compiled, and usually bring pieces which can not be compiled outside of Compile, but this is a matter of personal preference :) –  Leonid Shifrin Feb 23 '12 at 0:29

This is a variation of Mr.Wizard's answer:

list = {"section 1", "a", "b", "c", "section 2", "d", "e", "f"};

delimiterQ[s_String] := StringMatchQ[s, "section " ~~ __]
delimiterQ[_] := False

Rest /@ Split[list, (Not[delimiterQ[#2]] &)]


Here, I'm specifying a test function to Split to decide where the list should be split. For a test function test, say, the list will be split between consecutive elements e1 and e2 if test[e1, e2] returns False. The next sublist will then start with e2. In this case the list will be split between e1 and e2 if Not[delimiterQ[e2]] == False, i.e. when delimiterQ[e2] == True.

-
To my surprise this appears to be faster than SplitBy. +1 ! –  Mr.Wizard Feb 22 '12 at 17:03
This won't work correctly if the list doesn't start with a delimiter . –  Szabolcs Feb 22 '12 at 17:10
@Szabolcs I guess you could do something like Split[list, (Not[delimiterQ[#2]] &)] /. a_String /; delimiterQ[a] :> Sequence[] instead –  Heike Feb 22 '12 at 17:11

I know, late to the party, but after my answer for the Brainf*** parser, I have been thinking in terms of state machines. In this case, each instance of the pattern "section " ~~ __ signals a change in state from one section to the next, so it seems like a solution based upon Sow and Reap should be doable with a cached section delimiter, as follows

splitAtDelimeters[l_List, test_, out_:Rule]:=
Module[{del = ""},
Reap[If[
test@#,
del = #,
Sow[#, del]
] & /@ l, _, out][[2]]
]

splitAtDelimeters[list, StringMatchQ[#, "section " ~~ __] &]
(*
{"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
*)


Incidentally, this works "out of the box" for lists without a starting delimiter:

 splitAtDelimeters[Rest@list, StringMatchQ[#, "section " ~~ __] &]
(*
{"" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
*)


Edit: As pointed out, the above code does not work for non-unique delimiters. An alternative is to track them separately, and recombine them at the end, as follows:

Clear[splitAtDelimeters2]
splitAtDelimeters2[l_List, test_, out_: Rule] :=
Module[{del = {}, section = 1},
Reap[If[test@#,
del = {del, #}; section++,
Sow[#, section]
] & /@ l, _, #2 &
With[{lstdels = Flatten[del], terms = #1},
{If[Length@lstdels != Length@terms, {""}, {}]~Join~lstdels,
terms}]
] &
]

longList = Flatten@ConstantArray[list, {3}];
splitAtDelimeters[longList, StringMatchQ[#, "section " ~~ __] &]
(*
{"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"},
"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"},
"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
*)


splitAtDelimeters[Rest@longList, StringMatchQ[#, "section " ~~ __] &]
(*
{"" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"},
"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"},
"section 1" -> {"a", "b", "c"}, "section 2" -> {"d", "e", "f"}}
*)


This works by tagging each entry with a unique section number (section), and then using MapThread with the accumulated delimiters (del). The If is in there to ensure that the list of delimiters has the same length as the number of terms which will occur if the leading section is missing a delimiter.

-
This won't work when some delimeters are repeated several times, like e.g. in Flatten@ ConstantArray[list, {3}]. –  Leonid Shifrin Feb 22 '12 at 18:01
@LeonidShifrin you're right, I had assumed (incorrectly) that the delimiters would be unique. –  rcollyer Feb 22 '12 at 18:06
@LeonidShifrin I added something that will work for non-unique delimiters. –  rcollyer Feb 22 '12 at 18:25
@rcollyer Another trick for making the state machine work is to detect edges; this has the advantage that you can just use the value of test as your state. –  Pillsy Feb 22 '12 at 18:37
@Pillsy that's what I did with the BF parser. Here, I thought I could do something a little simpler. –  rcollyer Feb 22 '12 at 18:43