Searching for multiple strings in multiple files

Question

I have a text file containing 21000 strings (one line each) and 500 MB of other text files (maily source codes). For each string I need to determine if it is contained in any of those files. I wrote program that does the job but its performance is terrible (it would do that in couple of days, I need to have the job done in 5-6 hours max).
I'm writing using C#, Visual Studio 2010

I have couple of questions regarding my problem:
a) Which approach is better?

foreach(string s in StringsToSearch)
{
    //scan all files and break when string is found
}

or

foreach(string f in Files)
{
    //search that file for each string that is not already found
}

b) Is it better to scan one file line by line

StreamReader r = new StreamReader(file);
while(!r.EndOfStream)
{
    string s = r.ReadLine();
    //... if(s.Contains(xxx));
}

or

StreamReader r = new StreamReader(file);
string s = r.ReadToEnd();
//if(s.Contains(xxx));

c) Would threading improve performance and how to do that?
d) Is there any software that can do that so I don't have to write my own code?

Answer 1

You want to minimize of File I/O, so your first idea is very bad because you would be opening the 'other' files up to 21.000 times. You want to use something based on the second one (a1). And when those other files aren't overly big, load them into memory once with readAllText.

List<string> keys = ...;    // load all strings

foreach(string f in Files)
{
    //search for each string that is not already found
    string text = System.IO.File.ReadAllText(f);  //easy version of ReadToEnd


    // brute force
    foreach(string key in keyes)
    {
        if (text.IndexOf(key) >= 0) ....
    }

}

The brute force part can be improved upon but I think you will find it acceptable.

Answer 2

You might want to look at the Windows Search SDK here

http://msdn.microsoft.com/en-us/library/aa965362%28VS.85%29.aspx

Answer 3

1. In both a) and b), second option is efficient
2. threading may not improve the performance coz each thread would read the file from your disk, so you disk will become bottleneck.
3. sry i have no idea about s/w for your purpose

thread snippet

      foreach (FileInfo file in FileList)
      {
         Thread t  = new Thread(new ParameterizedThreadStart(ProcessFileData));
         t.Start(file.FullName);  
       }//where processFileData is the method that process the files

General I/O Guidelines

What follows are some basic recommendations for reducing the I/O activity of your program, and thus enhancing its performance. As with all recommendations, it is important to measure the performance of the code being optimized before and after optimization to ensure that it actually gets faster.

1. Minimize the number of file operations you perform
2. Group several small I/O transfers into one large transfer. A single write of eight pages is faster than eight separate single-page writes, primarily because it allows the hard disk to write the data in one pass over the disk surface. For more information,
3. Perform sequential reads instead of seeking and reading small blocks of data. The kernel transparently clusters I/O operations, which makes sequential reads much faster.
4. Avoid skipping ahead in an empty file before writing data. The system must write zeroes into the intervening space to fill the gap. For more information, see Reading is typically cheaper than writing data.
5. Defer any I/O operations until the point that your application actually needs the data.
6. Use the preferences system to capture only user preferences (such as window positions and view settings) and not data that can be inexpensively recomputed.
7. Do not assume that caching file data in memory will speed up your application. Storing file data in memory improves speed until that memory gets swapped out to disk, at which point you pay the price for accessing the disk once again. Strive to find an appropriate balance between reading from disk and caching in memory

Answer 4

If you are just wanting to know if the string is found or not found, and don't need to do any further processing, then I'd suggest you just use grep. Grep is extremely fast and designed for exactly this kind of problem.

grep -f strings-file other-files...

should do the trick. I'm sure there is a Windows implementation out there somewhere. At worst, Cygwin will have it.

EDIT: This answers question d)

Answer 5

Does the search have to be real time on current 500 MB of text? The reason I ask is because you could build a search index on the text files and perform search. It would be much faster...Take a look at Lucene

Lucene.Net

C# and Lucene to index and search