Java Pattern.split() with overlapping delimiters

Question

Firstly, I'm aware of similar questions that have been asked such as here:

How to split a string, but also keep the delimiters?

However, I'm having issue implementing a split of a string using Pattern.split() where the pattern is based on a list of delimiters, but where they can sometimes appear to overlap. Here is the example:

The goal is to split a string based on a set of known codewords which are surrounded by slashes, where I need to keep both the delimiter (codeword) itself and the value after it (which may be empty string).

For this example, the codewords are:

/ABC/
/DEF/
/GHI/

Based on the thread referenced above, the pattern is built as follows using look-ahead and look-behind to tokenise the string into codewords AND values:

((?<=/ABC/)|(?=/ABC/))|((?<=/DEF/)|(?=/DEF/))|((?<=/GHI/)|(?=/GHI/))

Working string:

"123/ABC//DEF/456/GHI/789"

Using split, this tokenises nicely to:

"123","/ABC/","/DEF/","456","/GHI/","789"

Problem string (note single slash between "ABC" and "DEF"):

"123/ABC/DEF/456/GHI/789"

Here the expectation is that "DEF/456" is the value after "/ABC/" codeword because the "DEF/" bit is not actually a codeword, but just happens to look like one!

Desired outcome is:

"123","/ABC/","DEF/456","/GHI/","789"

Actual outcome is:

"123","/ABC","/","DEF/","456","/GHI/","789"

As you can see, the slash between "ABC" and "DEF" is getting isolated as a token itself.

I've tried solutions as per the other thread using only look-ahead OR look-behind, but they all seem to suffer from the same issue. Any help appreciated!

Answer 1

If you are OK with find rather than split, using some non-greedy matches, try this:

public class SampleJava {
static final String[] CODEWORDS = {
    "ABC",
    "DEF",
    "GHI"};
static public void main(String[] args) {
    String input = "/ABC/DEF/456/GHI/789";
    String codewords = Arrays.stream(CODEWORDS)
            .collect(Collectors.joining("|", "/(", ")/"));
    //     codewords = "/(ABC|DEF|GHI)/";
    Pattern p = Pattern.compile(
/* codewords */ ("(DELIM)"
/* pre-delim */ + "|(.+?(?=DELIM))"
/* final bit */ + "|(.+?$)").replace("DELIM", codewords));
    Matcher m = p.matcher(input);
    while(m.find()) {
        System.out.print(m.group(0));
        if(m.group(1) != null) {
            System.out.print(" ← code word");
        }
        System.out.println();
    }
}
}

Output:

/ABC/ ← code word

DEF/456

/GHI/ ← code word

789

Answer 2

Use a combination of positive and negative look arounds:

String[] parts = s.split("(?<=/(ABC|DEF|GHI)/)(?<!/(ABC|DEF|GHI)/....)|(?=/(ABC|DEF|GHI)/)(?<!/(ABC|DEF|GHI))");

There's also a considerable simplification by using alternations inside single look ahead/behind.

See live demo.

Answer 3

Following some TDD principles (Red-Green-Refactor), here is how I would implement such behaviour:

Write specs (Red)

I defined a set of unit tests that explain how I understood your "tokenization process". If any test is not correct according to what you expect, feel free to tell me and I'll edit my answer accordingly.

import static org.assertj.core.api.Assertions.assertThat;

import java.util.List;

import org.junit.Test;

public class TokenizerSpec {

    Tokenizer tokenizer = new Tokenizer("/ABC/", "/DEF/", "/GHI/");

    @Test
    public void itShouldTokenizeTwoConsecutiveCodewords() {
        String input = "123/ABC//DEF/456";

        List<String> tokens = tokenizer.splitPreservingCodewords(input);

        assertThat(tokens).containsExactly("123", "/ABC/", "/DEF/", "456");
    }

    @Test
    public void itShouldTokenizeMisleadingCodeword() {
        String input = "123/ABC/DEF/456/GHI/789";

        List<String> tokens = tokenizer.splitPreservingCodewords(input);

        assertThat(tokens).containsExactly("123", "/ABC/", "DEF/456", "/GHI/", "789");
    }

    @Test
    public void itShouldTokenizeWhenValueContainsSlash() {
        String input = "1/23/ABC/456";

        List<String> tokens = tokenizer.splitPreservingCodewords(input);

        assertThat(tokens).containsExactly("1/23", "/ABC/", "456");
    }

    @Test
    public void itShouldTokenizeWithoutCodewords() {
        String input = "123/456/789";

        List<String> tokens = tokenizer.splitPreservingCodewords(input);

        assertThat(tokens).containsExactly("123/456/789");
    }

    @Test
    public void itShouldTokenizeWhenEndingWithCodeword() {
        String input = "123/ABC/";

        List<String> tokens = tokenizer.splitPreservingCodewords(input);

        assertThat(tokens).containsExactly("123", "/ABC/");
    }

    @Test
    public void itShouldTokenizeWhenStartingWithCodeword() {
        String input = "/ABC/123";

        List<String> tokens = tokenizer.splitPreservingCodewords(input);

        assertThat(tokens).containsExactly("/ABC/", "123");
    }

    @Test
    public void itShouldTokenizeWhenOnlyCodeword() {
        String input = "/ABC//DEF//GHI/";

        List<String> tokens = tokenizer.splitPreservingCodewords(input);

        assertThat(tokens).containsExactly("/ABC/", "/DEF/", "/GHI/");
    }
}

Implement according to the specs (Green)

This class make all the tests above pass

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;

public final class Tokenizer {

    private final List<String> codewords;

    public Tokenizer(String... codewords) {
        this.codewords = Arrays.asList(codewords);
    }

    public List<String> splitPreservingCodewords(String input) {
        List<String> tokens = new ArrayList<>();

        int lastIndex = 0;
        int i = 0;
        while (i < input.length()) {
            final int idx = i;
            Optional<String> codeword = codewords.stream()
                                                 .filter(cw -> input.substring(idx).indexOf(cw) == 0)
                                                 .findFirst();
            if (codeword.isPresent()) {
                if (i > lastIndex) {
                    tokens.add(input.substring(lastIndex, i));
                }
                tokens.add(codeword.get());
                i += codeword.get().length();
                lastIndex = i;
            } else {
                i++;
            }
        }

        if (i > lastIndex) {
            tokens.add(input.substring(lastIndex, i));
        }

        return tokens;
    }
}

Improve implementation (Refactor)

Not done at the moment (not enough time that I can spend on that answer now). I'll do some refactor on Tokenizer with pleasure if you request me to (but later). :-) Or you can do it yourself quite securely since you have the unit tests to avoid regressions.