How to search for a specific string in a file?
-
So what you want to do, is to find only 1 string once? Because then you could just stream the file, no buffers needed. [almost] To visualize this (in case anyone needs the explanation); you can look at it like a state machine, with a state for every character in the string you are searching for (lets call it X). The state machine will keep reading 1 character at a time until it exits. It starts in state 0, and will change to state 1 if it reads a character that matches X[0]. State n will transition to state n+1 if it reads X[n] or to state 0 if it reads anything else. The last state will return the position in the file if it reads X[last]. Every state will return "not found" if it runs out of characters to read. [/but not quite] Solution: use the Knuth-Morris-Pratt algorithm, at worst it has to evaluate the same character multiple times, but it never needs to go back (only forward, but skipping characters in a stream is trivial) Essentially it's doing the same as what I described, but it jumps back to the right state instead of always 0. That way you only need a constant amount of memory plus the string X.
modified on Sunday, March 7, 2010 9:38 AM
It is a great idea. How come I've never thought it. Thanks. :)
-
100 bytes is just fine. Search once with a stride of 100 bytes starting at zero-indexed byte 0, then search with a stride of 100 bytes starting at zero-indexed byte 50. This works with strings up to 50 bytes in length.
Thanks.
-
It is a great idea. How come I've never thought it. Thanks. :)
-
So what you want to do, is to find only 1 string once? Because then you could just stream the file, no buffers needed. [almost] To visualize this (in case anyone needs the explanation); you can look at it like a state machine, with a state for every character in the string you are searching for (lets call it X). The state machine will keep reading 1 character at a time until it exits. It starts in state 0, and will change to state 1 if it reads a character that matches X[0]. State n will transition to state n+1 if it reads X[n] or to state 0 if it reads anything else. The last state will return the position in the file if it reads X[last]. Every state will return "not found" if it runs out of characters to read. [/but not quite] Solution: use the Knuth-Morris-Pratt algorithm, at worst it has to evaluate the same character multiple times, but it never needs to go back (only forward, but skipping characters in a stream is trivial) Essentially it's doing the same as what I described, but it jumps back to the right state instead of always 0. That way you only need a constant amount of memory plus the string X.
modified on Sunday, March 7, 2010 9:38 AM
You do know it gets a little bit more complex when the characters in the search string aren't all different, as in: find "anas" in "a long text containing ananas and other stuff"; returning to state 0 isn't always right. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that.
-
You do know it gets a little bit more complex when the characters in the search string aren't all different, as in: find "anas" in "a long text containing ananas and other stuff"; returning to state 0 isn't always right. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that.
Ok fine, spoil the fun :) So maybe it isn't 0 but more like X.LastIndexOf(char that was read) (or 0 if it wasn't found) - or if it isn't that I might actually have to think and it's the weekend so no thanks (exercise for the reader?) My brain got unlazy for a second and remembered the solution - see the edit..
modified on Saturday, March 6, 2010 9:56 PM
-
Hi, Let's say that I've a file and I would like to find a specific string's location inside it. It is logical to load my file into a byte array and then parse it into a string or a StringBuilder byte by byte, right? It is an easy issue if the file is small. If the file is huge (like 400megabytes), it is not that easy. The application demands lots of RAM and it is annoying. I thought about copying the file into the byte array by 100 bytes, step by step. But this brings another problem, if the half of my string is inside the first 100 bytes, and the rest in the next 100 bytes; my application is not able to identify my string and therefore give its location to me. How can I solve this, any ideas? If there is anything unclear, feel free to ask. Thanks.
Similar to StarBP: use 2 rolling buffers which are the size of the search terms. initialize by loading data into buffer 1 repeat the following steps: clear buffer 2 dump buffer 1 into buffer 2 load fresh data into buffer 1 combine the buffers search the combination If the buffers are the correct size your search terms will always be in one combination. The overhead is that you will be searching each buffer twice though. hope it helps Shane
-
You do know it gets a little bit more complex when the characters in the search string aren't all different, as in: find "anas" in "a long text containing ananas and other stuff"; returning to state 0 isn't always right. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that.
Yes, but I think that is not a problem for me. I am looking for a string in the file, no matter where it is. I think code can express everything, in a better way. Here is my code:
private long DigBinary(string file, string strToDig)
{
FileStream fs = null;char\[\] chAim = strToDig.ToCharArray(); char chTemp = '0'; long latestHitBeginningLocation = 0; int locationInArray = 0; try { fs = new FileStream(file, FileMode.Open, FileAccess.Read); } catch { throw new Exception("An error occured while creating the stream."); } try { while (locationInArray < chAim.Length) { chTemp = (char)fs.ReadByte(); if( chTemp != chAim\[locationInArray\] ) locationInArray = 0; if (chTemp == chAim\[locationInArray\]) { if (locationInArray == 0) latestHitBeginningLocation = fs.Position - 1; if (locationInArray == chAim.Length) break; locationInArray++; } else { locationInArray = 0; latestHitBeginningLocation = 0; } } } catch { throw new Exception("An error occured while reading the file."); } finally { if (fs != null) { fs.Close(); fs.Dispose(); } } return latestHitBeginningLocation; }And yes, I know that my try-catch is useless. :D
-
Yes, but I think that is not a problem for me. I am looking for a string in the file, no matter where it is. I think code can express everything, in a better way. Here is my code:
private long DigBinary(string file, string strToDig)
{
FileStream fs = null;char\[\] chAim = strToDig.ToCharArray(); char chTemp = '0'; long latestHitBeginningLocation = 0; int locationInArray = 0; try { fs = new FileStream(file, FileMode.Open, FileAccess.Read); } catch { throw new Exception("An error occured while creating the stream."); } try { while (locationInArray < chAim.Length) { chTemp = (char)fs.ReadByte(); if( chTemp != chAim\[locationInArray\] ) locationInArray = 0; if (chTemp == chAim\[locationInArray\]) { if (locationInArray == 0) latestHitBeginningLocation = fs.Position - 1; if (locationInArray == chAim.Length) break; locationInArray++; } else { locationInArray = 0; latestHitBeginningLocation = 0; } } } catch { throw new Exception("An error occured while reading the file."); } finally { if (fs != null) { fs.Close(); fs.Dispose(); } } return latestHitBeginningLocation; }And yes, I know that my try-catch is useless. :D
that is a horrible piece of "code". X| X| X|
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that.
-
that is a horrible piece of "code". X| X| X|
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that.
I am open to suggestions.
-
I am open to suggestions.
Here are some: - unspecified catch = deadly sin - store actual exception as inner exception in functional exception - user-generated exceptions should inherit from ApplicationException - two try blocks where one would suffice - redundant chTemp initialization - should use using statement - char[] chAim = strToDig.ToCharArray(); is redundant; use strToDig[index] And the algorithm is wrong, as I reported earlier. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that.
-
Here are some: - unspecified catch = deadly sin - store actual exception as inner exception in functional exception - user-generated exceptions should inherit from ApplicationException - two try blocks where one would suffice - redundant chTemp initialization - should use using statement - char[] chAim = strToDig.ToCharArray(); is redundant; use strToDig[index] And the algorithm is wrong, as I reported earlier. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that.
Thanks for the advices. I will change the code accordingly. This algorithm covers my needs. It works, it is fast and it doesn't consume much RAM. :)