Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Imagine I have file called strings.dat. Inside this file there is alot of string, for example: one million. String are sorted. Now I want to find specified string, so I can write method like this:

public long FindByName (string text)
{
  // ...
}

This method can return to me a position within a file where this string occurs. But iterating through lots of data is not efficient. I can do some indexing system, like an Dictionary<char, long> which tells about at what position within file is placed first string with its value starting from given char.

Example: if I got 5 strings: hello
hello2
world
world2
Zzz

So my dictionary will be like:
h 0
w 2
z 4

But it's not efficient if I will have 1000 string with "d" char as first letter, and 10 million with "r" letter.

Do you know any good algorithms do ahieve what Im asking for?

share|improve this question
5  
No need to reinvent the wheel. Databases do this better than you could hope to accomplish in a reasonable time frame. –  Karl Bielefeldt Apr 28 at 12:38
    
Well, I want to dump entire database into one read-only file because I don't want to use DBMS anymore. –  zgnilec Apr 28 at 12:46
1  
What made you decide not to use a DBMS anymore? –  MetaFight Apr 28 at 12:47
7  
Good look getting better performance with smaller file size than a DBMS. Maybe you should look into things like sqlite. –  MetaFight Apr 28 at 13:49
4  
sqlite 1) does not require any license fee, 2) has simple clients and APIs for any serious major OS platforms, 3) provides you with ready made indexing capabilities for high performance, 4) has only a small size overhead, and any self-made persistent indexes will need additional storage, too. Of course, you loose the ability to open the text file in a standard text editor (but for a 5GB text file I would not recommend this either). –  Doc Brown Apr 28 at 14:30

4 Answers 4

Because your data is sorted, I would use a Binary Search algorithm on it.

Since this is a text file (i.e., string lengths / record sizes are not all equal) you'll have a little adjusting to do.

As an example, say your file is 1GB in size - (average string length including end of line is around 1,024 bytes.

Open the file and start reading bytes at position 512 MB. Chances are you've hit the middle of a string. No problem, just keep reading bytes until you get to the end of the line, then read the next line and use that as your pivot.

It will be a little bit messier than if all the strings were the same length, but not terribly so.

If your search target comes before the pivot string, your next random access read would begin around 256 MB.

share|improve this answer
    
Good option, I will read this link after work. –  zgnilec Apr 28 at 13:44
    
The point about string length is crucial: if each string were the same length this would be a lot simpler. Also do not forget about EOL differences across platforms. –  Snowman Apr 28 at 16:58

You mention in the comments to your question that you used to use a DBMS but are moving away in order to save money and make your project more portable.

There are free and portable DBMS alternatives. I highly recommend looking into those instead of writing your own.

Existing products will have been designed by better devs than you or me, and will already have hundreds of testing hours on them. In other words: They will be faster and more stable.

Try looking into sqlite.

share|improve this answer
    
I think my own "DB" will be smaller and faster, because it will be read only and will be designed for concrete data types. For example is use alot of strings with 4 char length. So I can optimize my db for it. Other DB are not intelligent to do that. –  zgnilec Apr 28 at 16:27
    
Assuming you are correct, another advantage of using something like sqlite is that it instantly reduces the overall complexity of your project, and also reduces the amount of code you have to maintain. This alone can save you loads of time (read: money). –  MetaFight Apr 28 at 16:35
1  
For something as simple as finding the position of a string in a file I wouldn't bother with a DBMS. Overkill and less portable. –  Will Calderwood Apr 28 at 21:22
    
@up Agree. My "DB" file structure is just a file filled with different size records. Each recors has a dictionary attr_name : attr_value. Thats all. I can query these records via ID (special number) and Name (string). So this file will be so simple. No need a entire DBMS. –  zgnilec Apr 29 at 10:27
    
@MetaFight: some people (like me) just like to write own implementations of things. It's fun, and you can learn much. –  zgnilec Apr 29 at 10:41

I would use a bucket sort to help optimize this.

Since strings are different lengths in your example, and there is a lot of data considering this is a flat file, I would simply split the file into multiple pieces based on the string prefix.

So instead of having strings.dat I would have the following:

  • a.dat
  • b.dat
    ...
  • z.dat

If any particular file is still too large, for example, a common letter such as r or t is disproportionately larger, split that into smaller buckets:

  • r.dat
  • ra.dat
  • re.dat
    ...

This can continue with rab.dat and so on.

To find a string, simply start with the full string and look for a file matching its name. If not found, look for a file matching the string minus the last character. Do this until a match is found or the string is zero length (e.g. maybe there is no x.dat so no word starting with x will ever be found).

Example: here are some files, and a string that could be located in each one.

  • r.dat - rhombus (no rh.dat)
  • ra.dat - rat (no rat.dat)
  • rab.dat - rabid (no rabi.dat)

Each file should be small enough for efficient searching either using a full scan or a binary search, whatever you believe is appropriate given the amount of data.

Benefits

  • Smaller text files are easier to manage in a text editor if you need to modify them.
  • Seeking through text files can be inefficient depending on your language, library, and file mode. By reducing the amount of data in each file, this may alleviate that.
  • From an algorithmic complexity perspective this does not buy you much if anything. However, from a practical perspective it does. File I/O is expensive, easily one of the most expensive operations a computer can perform (unless you have an SSD). By minimizing file seeks/reads, you mitigate the real-world performance impact of searching 500 MB of data each time. How much? Profile it to say for sure, but I would feel comfortable sticking my neck out and saying it would be a measurable amount.
share|improve this answer
    
I considering this (algorithm). But I would stay in one file instead of many. –  zgnilec Apr 29 at 10:39
1  
If you want to use a single file, I would recommend either a binary format with a table of contents or keep the text file but store a second file with metadata. This metadata would include offsets to different buckets. This is important because strings in a natural language tend to be skewed toward certain letters (buckets). A binary search is efficient, but you have a priori knowledge which can make it better: hence, the bucket sort. –  Snowman Apr 29 at 14:38

Use a hash table. The hash table would include a reasonably unique key generated from the string and pointers to the strings that match that hash key.

A simple, fast hash with a small hash table (256 entries), but lots of key collisions, would be the xor of all bytes in the string. A slower, more complicated hash with a much larger hash table (as many entries as strings), but where key collisions are unlikely, would be AES encryption.

I realize you're using C#, but here's a little perl script to help you investigate what hash table size you'd like to use. This version of the keyify() function just sums the string into a 16 bit integer.

# keyspace.pl
sub keyify {
    use constant HASH_KEY_SIZE_IN_BITS => 16;
    return unpack( '%' . HASH_KEY_SIZE_IN_BITS . 'A*', $_ );
}

$/ = "\r\n"; # Windows EOL
$offset = 0;
while(<>) {
    $newoffset = $offset + length($_);
    $key = keyify($_);
    if (defined $myhash{$key}) {
        # key collision, add to the list of offsets
        push @{ $myhash {$key} }, $offset;
    } else {
        # new key, create the list of offsets
        $myhash { $key } = [$offset];
    }
    $offset = $newoffset;
}
printf "%d keys generated\n", scalar (keys %myhash);
$max = 0;
foreach (keys%myhash) {
    $collisions = scalar @{ $myhash{$_} };
    $max = $collisions      if ( $collisions > $max );
}
print "maximum # of string offsets in a hash = $max\n";
exit;

# dump hash table
foreach (keys%myhash) {
    print "key = $_:";
    foreach my $offset ( @{ $myhash{$_} } ) {
        print " $offset";
    }
    print "\n";
}

Use it like so:

perl keyspace.pl <strings.dat

The same thing in PowerShell, with a much simpler hashing function. You'll have to put in some effort if you want this to be useful.

# keyspace.ps1
# Don't use "gc -Encoding Byte -Raw" because it reads the ENTIRE file into memory.
function keyify {
    return $args[0].Substring(0,1);
}

$myHash = @{};
$offset = 0;
$file = New-Object System.IO.StreamReader($args[0]);
while ($line = $file.ReadLine()) {
    $newoffset = $offset + $line.Length + 2;    # adjust by 2 for Windows EOL (CRLF)
    $key = keyify($line);
    if ($myHash.ContainsKey($key)) {
        # key collision, add to the list of offsets
        $myHash.Set_Item($key, $myHash.Get_Item($key)+$offset);
    } else {
        # new key, create the list of offsets
        $myHash.Add($key, @($offset));
    }
    $offset = $newoffset;
}
$file.close()
echo "$($myHash.Count) keys generated";
$max = 0;
foreach ($i in $myHash.KEYS.GetEnumerator()) {
    $collisionList = $myHash.Get_Item($i);
    if ($collisionList.Count -gt $max) { $max = $collisionList.Count; }
}
echo "maximum # of string offsets in a hash = $max";

# echo $myHash;

Use it like so:

.\keyspace.ps1 strings.dat
share|improve this answer
    
Idk why someone downvoted you, but has table is one of the best solution. I will generate hash for each string, and I will build dictionarz hash-position?in?file, then I will sort hashes. But 16 bit hash would be better fo mz solution i think=. –  zgnilec Apr 28 at 16:29
2  
C# already has a hash table class. Unless it's too slow, let it do the work. –  Scott Leadley Apr 28 at 17:15
1  
A quick thought about performance. If the hash table contains a lot of collisions, you may want to (A) reorder the file by hash key in order to take advantage of locality of reference (caching) speedups or (B) modify the hashing algorithm to take advantage of locality of reference in the lexically sorted file. –  Scott Leadley Apr 29 at 6:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.