Efficient way to search a stream for a string

Question

Let's suppose that have a stream of text (or Reader in Java) that I'd like to check for a particular string. The stream of text might be very large so as soon as the search string is found I'd like to return true and also try to avoid storing the entire input in memory.

Naively, I might try to do something like this (in Java):

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

Of course this fails to detect the given search string if it occurs on the boundary of the 1k buffer:

Search text: "stackoverflow"
Stream buffer 1: "abc.........stack"
Stream buffer 2: "overflow.......xyz"

How can I modify this code so that it correctly finds the given search string across the boundary of the buffer but without loading the entire stream into memory?

Edit: Note when searching a stream for a string, we're trying to minimise the number of reads from the stream (to avoid latency in a network/disk) and to keep memory usage constant regardless of the amount of data in the stream. Actual efficiency of the string matching algorithm is secondary but obviously, it would be nice to find a solution that used one of the more efficient of those algorithms.

Ahl

Answer 1

I did a few changes to the Knuth Morris Pratt algorithm for partial searches. Since the actual comparison position is always less or equal than the next one there is no need for extra memory. The code with a Makefile is also available on github and it is written in Haxe to target multiple programming languages at once, including Java.

I also wrote a related article: searching for substrings in streams: a slight modification of the Knuth-Morris-Pratt algorithm in Haxe. The article mentions the Jakarta RegExp, now retired and resting in the Apache Attic. The Jakarta Regexp library “match” method in the RE class uses a CharacterIterator as a parameter.

class StreamOrientedKnuthMorrisPratt {
    var m: Int;
    var i: Int;
    var ss:
    var table: Array<Int>;

    public function new(ss: String) {
        this.ss = ss;
        this.buildTable(this.ss);
    }

    public function begin() : Void {
        this.m = 0;
        this.i = 0;
    }

    public function partialSearch(s: String) : Int {
        var offset = this.m + this.i;

        while(this.m + this.i - offset < s.length) {
            if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {
                if(this.i == this.ss.length - 1) {
                    return this.m;
                }
                this.i += 1;
            } else {
                this.m += this.i - this.table[this.i];
                if(this.table[this.i] > -1)
                    this.i = this.table[this.i];
                else
                    this.i = 0;
            }
        }

        return -1;
    }

    private function buildTable(ss: String) : Void {
        var pos = 2;
        var cnd = 0;

        this.table = new Array<Int>();
        if(ss.length > 2)
            this.table.insert(ss.length, 0);
        else
            this.table.insert(2, 0);

        this.table[0] = -1;
        this.table[1] = 0;

        while(pos < ss.length) {
            if(ss.substr(pos-1,1) == ss.substr(cnd, 1))
            {
                cnd += 1;
                this.table[pos] = cnd;
                pos += 1;
            } else if(cnd > 0) {
                cnd = this.table[cnd];
            } else {
                this.table[pos] = 0;
                pos += 1;
            }
        }
    }

    public static function main() {
        var KMP = new StreamOrientedKnuthMorrisPratt("aa");
        KMP.begin();
        trace(KMP.partialSearch("ccaabb"));

        KMP.begin();
        trace(KMP.partialSearch("ccarbb"));
        trace(KMP.partialSearch("fgaabb"));

    }
}

Burnette

Is the last trace supposed to return 10 or is it the fact you haven't called KMP begin meanwhile. And do you need to if all you're searching is for presence? Haxe needs to generate javadocs :) – Coverlet

@Coverlet what is the result in your run? it is supposed to return 8 since "aa" appears in the 8th position at: "ccarbbfgaabb" – Burnette

@sw: Thanks for your contribution, it's super!! But it's not clear, what is the license for your code? Is it public domain? – Northwesterly

@Sorin Postelnicu it is public domain. – Burnette

Answer 2

There are three good solutions here:

1. If you want something that is easy and reasonably fast, go with no buffer, and instead implement a simple nondeterminstic finite-state machine. Your state will be a list of indices into the string you are searching, and your logic looks something like this (pseudocode):

   String needle;
   n = needle.length();
   
   for every input character c do
     add index 0 to the list
     for every index i in the list do
       if c == needle[i] then
         if i + 1 == n then
           return true
         else
           replace i in the list with i + 1
         end
       else
         remove i from the list
       end
     end
   end
   

   This will find the string if it exists and you will never need a buffer.

2. Slightly more work but also faster: do an NFA-to-DFA conversion that figures out in advance what lists of indices are possible, and assign each one to a small integer. (If you read about string search on Wikipedia, this is called the powerset construction.) Then you have a single state and you make a state-to-state transition on each incoming character. The NFA you want is just the DFA for the string preceded with a state that nondeterministically either drops a character or tries to consume the current character. You'll want an explicit error state as well.

3. If you want something faster, create a buffer whose size is at least twice n, and user Boyer-Moore to compile a state machine from needle. You'll have a lot of extra hassle because Boyer-Moore is not trivial to implement (although you'll find code online) and because you'll have to arrange to slide the string through the buffer. You'll have to build or find a circular buffer that can 'slide' without copying; otherwise you're likely to give back any performance gains you might get from Boyer-Moore.

Roadblock

Boyer Moore seems to require a complete search space given that it works backwards, starting from the last character of the pattern string. In this case, half of the problem is that the buffer may be incomplete, and yes, using a buffer that is twice the size of pattern string reduces the probability of a partial read, but the case where a portion of the pattern is read is not eliminated. – Deontology

I didn't pay close attention and missed the circular buffer bit. I think Norman's option 3 is the most efficient solution. +1. – Deontology

Why not use a buffered stream in-between to minimize reads from the external stream; then the penalty for reading a single character at a time is at a minimum? – Shortlived

I feel bad down voting this answer as I like solution 1 - super simple and good enough performance wise for most people (I guess it's obvious, but maybe it's worth noting that the length of the list used will grow to at most the length of the pattern). However I'm down voting as I'm unconvinced Boyer-Moore (with its right-left behavior), even with a sliding circular buffer, makes sense for stream searching. I'm voting for KMP for this. – Nimwegen

Also for solution 1 when you write that your "state will be a list of indices into the string you are searching" shouldn't you write "searching for", i.e. the indices are into needle not into the text being searched. – Nimwegen

Answer 3

The Knuth-Morris-Pratt search algorithm never backs up; this is just the property you want for your stream search. I've used it before for this problem, though there may be easier ways using available Java libraries. (When this came up for me I was working in C in the 90s.)

KMP in essence is a fast way to build a string-matching DFA, like Norman Ramsey's suggestion #2.

Fritillary

This question is specifically about searching a stream so I agree with @DariusBacon that KMP is a very good match for this (left to right behavior, i.e. never backs up). And it's easy to implement which is always good :) – Nimwegen

Answer 4

This answer applied to the initial version of the question where the key was to read the stream only as far as necessary to match on a String, if that String was present. This solution would not meet the requirement to guarantee fixed memory utilisation, but may be worth considering if you have found this question and are not bound by that constraint.

If you are bound by the constant memory usage constraint, Java stores arrays of any type on the heap, and as such nulling the reference does not deallocate memory in any way; I think any solution involving arrays in a loop will consume memory on the heap and require GC.

---

For simple implementation, maybe Java 5's Scanner which can accept an InputStream and use a java.util.regex.Pattern to search the input for might save you worrying about the implementation details.

Here's an example of a potential implementation:

public boolean streamContainsString(Reader reader, String searchString)
            throws IOException {
      Scanner streamScanner = new Scanner(reader);
      if (streamScanner.findWithinHorizon(searchString, 0) != null) {
        return true;
      } else {
        return false;
      }
}

I'm thinking regex because it sounds like a job for a Finite State Automaton, something that starts in an initial state, changing state character by character until it either rejects the string (no match) or gets to an accept state.

I think this is probably the most efficient matching logic you could use, and how you organize the reading of the information can be divorced from the matching logic for performance tuning.

It's also how regexes work.

Frostbitten

java.util.regex (and most mainstream regex engines) use a backtracking scheme that would actually be extremely inefficient for something like this. Imagine a pattern that starts with ".*" (and remember that '*' is greedy). Of course this can be done much more efficiently, but for this specific question where it looks like no metacharacters are to be supported, regular expressions are probably not the way to go. – Spikelet

If you use a regex that starts with .* it's your own fault if it's too slow. But you can avoid any regex-related complications escaping the search string, i.e.: "\\Q"+searchString+"\\E" – Andersen

@AlanM, that's a bit dangerous in the case that the search string has a "\\E" in it. And the ".*" example was just that, an example. There are lots of ways that regexes don't fit this problem well. @safetydan, I don't see Pattern.escape() in the javadocs. Am I missing something? – Spikelet

The method is called quote(), not escape(), and it works by wrapping the string in \Q and \E. It also deals with any \E that might already be in the string. I didn't mention it because I thought it was only available in JDK 1.6+, but it's been there since JDK 1.5. – Andersen

The Scanner is a nice solution but unfortunately, it doesn't meet the requirement of being memory efficient. The javadocs for findWithinHorizon state: "[with a horizon of 0] In this case it may buffer all of the input searching for the pattern." and in fact debugging the class, you can see this is exactly what it does. So close, but no cigar... :p – Ahl

Answer 5

Instead of having your buffer be an array, use an abstraction that implements a circular buffer. Your index calculation will be buf[(next+i) % sizeof(buf)], and you'll have to be careful to full the buffer one-half at a time. But as long as the search string fits in half the buffer, you'll find it.

Roadblock

Answer 6

I believe the best solution to this problem is to try to keep it simple. Remember, beacause I'm reading from a stream, I want to keep the number of reads from the stream to a minimum (as network or disk latency may be an issue) while keeping the amount of memory used constant (as the stream may be very large in size). Actual efficiency of the string matching is not the number one goal (as that has been studied to death already).

Based on AlbertoPL's suggestion, here's a simple solution that compares the buffer against the search string character by character. The key is that because the search is only done one character at a time, no back tracking is needed and therefore no circular buffers, or buffers of a particular size are needed.

Now, if someone can come up with a similar implementation based on Knuth-Morris-Pratt search algorithm then we'd have a nice efficient solution ;)

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    int count = 0;
    while((numCharsRead = reader.read(buffer)) > 0) {
        for (int c = 0; c < numCharsRead; c++) {
            if (buffer[c] == searchString.charAt(count))
                count++;
            else
                count = 0;
            if (count == searchString.length()) return true;
        }
    }
    return false;
}

Ahl

I don't get it: what if the needle string in the stream falls on the boundaries of buffers, say first part is at indices 1021, 1022, 1023 and second part at indices 1024, 1025 1026 this would not work in that situation. – Franctireur

@Franctireur It should still work; the variable count keeps track of the index in the needle string that has successfully been matched. If you cross the boundary of the buffer, it remains unchanged, you simply begin matching agains the start of the new buffer. Note that count is only reset when a character is found that does not match the needle string. – Ahl

Ahh I completely missed that, genius. I would change my downvote to upvote but the post needs editing before I can do that :) – Franctireur

I just posted an answer with a link to my Knuth Morris Pratt implementation for partial searches. Hope it helps! – Burnette

Won't this fail on some search strings? Consider "abac" against "ababac": count gets incremented on the partial match up to 'c' against 'b', then reset to 0 where c = 3, and the search never considers the match starting at c = 2. – Fritillary

I agree with @DariusBacon - this code will fail for finding "AB" in "AAB" - so I'm down voting this answer. Humanity has spent untold time on string search so if an algo doesn't already have a known name, e.g. KMP or whatever, there's probably a good reason for this. See Charras and Lecroq's "Handbook of Exact String-Matching Algorithms" for more than you probably ever wanted to know on the subject :) – Nimwegen

Answer 7

If you're not tied to using a Reader, then you can use Java's NIO API to efficiently load the file. For example (untested, but should be close to working):

public boolean streamContainsString(File input, String searchString) throws IOException {
    Pattern pattern = Pattern.compile(Pattern.quote(searchString));

    FileInputStream fis = new FileInputStream(input);
    FileChannel fc = fis.getChannel();

    int sz = (int) fc.size();
    MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz);

    CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder();
    CharBuffer cb = decoder.decode(bb);

    Matcher matcher = pattern.matcher(cb);

    return matcher.matches();
}

This basically mmap()'s the file to search and relies on the operating system to do the right thing regarding cache and memory usage. Note however that map() is more expensive the just reading the file in to a large buffer for files less than around 10 KiB.

Bagel

Answer 8

A very fast searching of a stream is implemented in the RingBuffer class from the Ujorm framework. See the sample:

 Reader reader = RingBuffer.createReader("xxx ${abc} ${def} zzz");

 String word1 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("abc", word1);

 String word2 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("def", word2);

 String word3 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("", word3);

The single class implementation is available on the SourceForge: For more information see the link.

Tennessee

Answer 9

Implement a sliding window. Have your buffer around, move all elements in the buffer one forward and enter a single new character in the buffer at the end. If the buffer is equal to your searched word, it is contained.

Of course, if you want to make this more efficient, you can look at a way to prevent moving all elements in the buffer around, for example by having a cyclic buffer and a representation of the strings which 'cycles' the same way the buffer does, so you only need to check for content-equality. This saves moving all elements in the buffer.

Silverplate

Answer 10

I think you need to buffer a small amount at the boundary between buffers.

For example if your buffer size is 1024 and the length of the SearchString is 10, then as well as searching each 1024-byte buffer you also need to search each 18-byte transition between two buffers (9 bytes from the end of the previous buffer concatenated with 9 bytes from the start of the next buffer).

Sacramentalism

Answer 11

I'd say switch to a character by character solution, in which case you'd scan for the first character in your target text, then when you find that character increment a counter and look for the next character. Every time you don't find the next consecutive character restart the counter. It would work like this:

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
int count = 0;
while((numCharsRead = reader.read(buffer)) > 0) {
    if (buffer[numCharsRead -1] == searchString.charAt(count))
        count++;
    else
        count = 0;

    if (count == searchString.size())    
     return true;
}
return false; 
}

The only problem is when you're in the middle of looking through characters... in which case there needs to be a way of remembering your count variable. I don't see an easy way of doing so except as a private variable for the whole class. In which case you would not instantiate count inside this method.

Braided

Answer 12

You might be able to implement a very fast solution using Fast Fourier Transforms, which, if implemented properly, allow you to do string matching in times O(nlog(m)), where n is the length of the longer string to be matched, and m is the length of the shorter string. You could, for example, perform FFT as soon as you receive an stream input of length m, and if it matches, you can return, and if it doesn't match, you can throw away the first character in the stream input, wait for a new character to appear through the stream, and then perform FFT again.

Sharanshard

Answer 13

You can increase the speed of search for very large strings by using some string search algorithm

Laellaertes

Those don't really apply since he has a stream of char's coming in. He doesn't have access to the entire String. So he's only going to be able to scan sequentially. And he specifically says he doesn't want to load the entire string into memory. – Campus

some algorithms does not require loading of full text at one time. For example Boyer-Moor algorithm applies indexing to search string but not to full text – Laellaertes

Answer 14

If you're looking for a constant substring rather than a regex, I'd recommend Boyer-Moore. There's plenty of source code on the internet.

Also, use a circular buffer, to avoid think too hard about buffer boundaries.

Mike.

Horace

Boyer-Moore is fast, but wants to look ahead. – Roadblock

Answer 15

I also had a similar problem: skip bytes from the InputStream until specified string (or byte array). This is the simple code based on circular buffer. It is not very efficient but works for my needs:

  private static boolean matches(int[] buffer, int offset, byte[] search) {
    final int len = buffer.length;
    for (int i = 0; i < len; ++i) {
      if (search[i] != buffer[(offset + i) % len]) {
        return false;
      }
    }
    return true;
  }

  public static void skipBytes(InputStream stream, byte[] search) throws IOException {
    final int[] buffer = new int[search.length];
    for (int i = 0; i < search.length; ++i) {
      buffer[i] = stream.read();
    }

    int offset = 0;
    while (true) {
      if (matches(buffer, offset, search)) {
        break;
      }
      buffer[offset] = stream.read();
      offset = (offset + 1) % buffer.length;
    }
  }

Fredericfrederica

Answer 16

Here is my implementation:

static boolean containsKeywordInStream( Reader ir, String keyword, int bufferSize ) throws IOException{
    SlidingContainsBuffer sb = new SlidingContainsBuffer( keyword );
    char[] buffer = new char[ bufferSize ];
    int read;
    while( ( read = ir.read( buffer ) ) != -1 ){
        if( sb.checkIfContains( buffer, read ) ){
            return true;
        }
    }
    return false;
}

SlidingContainsBuffer class:

class SlidingContainsBuffer{

    private final char[] keyword;
    private int keywordIndexToCheck = 0;
    private boolean keywordFound = false;

    SlidingContainsBuffer( String keyword ){
        this.keyword = keyword.toCharArray();
    }

    boolean checkIfContains( char[] buffer, int read ){
        for( int i = 0; i < read; i++ ){
            if( keywordFound == false ){
                if( keyword[ keywordIndexToCheck ] == buffer[ i ] ){
                    keywordIndexToCheck++;
                    if( keywordIndexToCheck == keyword.length ){
                        keywordFound = true;
                    }
                } else {
                    keywordIndexToCheck = 0;
                }
            } else {
                break;
            }
        }
        return keywordFound;
    }
}

This answer fully qualifies the task:

1. The implementation is able to find the searched keyword even if it was split between buffers
2. Minimum memory usage defined by the buffer size
3. Number of reads will be minimized by using bigger buffer

Unkempt