Say there is a 3TB TXT file, in which every line is a string, how to find those duplicated strings in them? It's an interview question from a friend of mine. We'd better make those questions clear enough after an interview, in case of the next one.
PS: If I'm the interviewee, I will tell the interviewer: How can you guys store so many strings in a TXT file? It's really a bad idea!
Does speed count?
The obvious solution that comes to mind is to load up say, the first 1000 lines into some kind of Set class, and then read the remaining lines one at a time and check if they're contained in the set. Then read the next 1000 lines, and repeat. That way you're only storing 1000 lines in memory at any one time.
I don't think you'll score many brownie points for telling the interviewer that storing that much data in a text file is bad idea. Who knows how this text file came to be... maybe it's the result of some legacy system, or who knows what. There's perfectly legitimate reasons for its existence.
One possibility is to use bloom filter.
According to wikipedia
The Bloom filter, conceived by Burton Howard Bloom in 1970,[1] is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.the probability of false positives.
This way, you can store the duplicates much more efficient, but at the cost of precisness.
A fairly straightforward way off the top of my head:
You could merge sort (good performance for data too large to fit into main memory) the text file. Then you can identify duplicates in a single pass through the file. O(nlogn). Of course this will either modify the original text file, or you could make a copy.
If you've got plenty of extra disk space, something like this should be workable:
for every line in the file:
calculate a hash function for that line.
append to a file named based on that hash (create if new).
for every file created:
sort it.
for every line in sorted file:
if first line in file:
set count to 0.
set lastline to line.
else
if line identical to lastline:
add 1 to count.
if count is 1:
Output line.
else:
set count to 0.
set lastline to line.
Assuming your hash function is relatively balanced, the sorts shouldn't be too onerous.
hi
if there is just one word per line, why you don't just dump the text file in a database table with following columns id, text and do some
select text, count(text)
from table
group by text
having count(text)>1
then you should get the right answers in a very easy way.
Sort this file, duplicates will sort together. Alternatively, create a second file and hash (md5 ?) each line into it, then sort that.
SELECT String
FROM TextFile
GROUP BY String
HAVING COUNT(*) > 1
ORDER BY String
I'd propose 2 solutions.
The first would be to place each of the lines into sets then look though the sets looking for ones with more than one element. I'd have the solution write the sets to disk to save on memory space.
The second would be to sort the text file like others have been suggesting.
A Probabilistic Solution
The below technique tries to use hash functions to identify string which are proven unique. After the first pass, the strings will be divided into (1) proven unique and (2) possibly duplicate.
There will be many unique strings labelled possibly duplicate because of hash code collision. Subsequent passes will only work with the possibly duplicate strings to reduce the rate of collision.
This technique does not guarantee to get rid of all duplicates (just most of them).
Let
Then