blocks|key|2982632|text|sort+bigfile.txt+%7C+uniq+-d|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2982633|entityMap^0|0|Q|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

<code>sort bigfile.txt | uniq -d</code>

blocks|key|1756738|text|一种可能性是使用bloom+filter。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1756739|bloom过滤器速度很快(就像使用哈希码一样)，并且没有漏报。这也是非常节省空间的。可以调整各种参数(大小(m)和函数数量(k))，以以大小和时间为代价获得更好的假阳性率。|1756740|将所有字符串逐个添加到筛选器表示的集合中。在插入时，您可以确定是否存在重复项。因为它没有假阴性，所以你只需要仔细检查过滤器出现的“重复”字符串。|1756741|如果你想了解更多关于布隆过滤器的信息，请访问wikipedia|offset|length|1756742|到目前为止，这是解决这个问题的最佳方法。代理服务器使用Bloom过滤器来确定URL是否在其缓存中。代理服务器可以看到数十亿个URL，并且需要能够非常快速地判断URL是新的还是以前被它“看到”过的。如果URL是“新的”，代理服务器立即从原始URL获取网站，而不是在其缓存中查找它。|1756743|这里的所有其他答案，即使是远程使用"sort“，显然也是错误的。|1756744|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Bloom_filter^0|0|0|0|M|9|0|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Y|8|@]|9|@$H|Z|I|10|1|11]]|A|$]]|$1|J|3|K|5|6|7|12|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|13|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|O|$P|$5|Q|R|S|A|$T|U]]]]

One possibility is to use bloom filter.

A bloom filter is fast (like using hashcode) and has no false negatives. It is very space efficient too. The various parameters (Size (m) and number of functions (k)) can be tweaked to achieve a better false-positive rate at the cost of size and time. 

You add all the strings, one by one to the set represented by the filter. At the time of insertion you can determine if a duplicate could exist. Since it has no false negatives, you only have to double-check the strings that come up as "duplicates" by the filter.

If you want more information about Bloom filters go to <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer">wikipedia</a>

This is by far the best approach to solving this problem. Bloom filters are used by proxy servers to determine if a URL is or is not in their cache. A proxy server sees billions of URLs and need to be able to tell very quickly if a URL is new or has been "seen" by it before. If the URL is "new" the proxy server immediately fetches the website from the original URL rather than look it up in its cache. 

All other answers here that even remotely use "sort" are obviously wrong.

blocks|key|4392209|text|如果每行只有一个单词，为什么不直接将文本文件转储到具有以下列id、text等的数据库表中|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4392210|select+text,+count(text)+
from+table+
group+by+text
having+count(text)>1|code-block|syntax|javascript|4392211|那么你应该以一种非常简单的方式得到正确的答案。|4392212|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

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

<pre><code>select text, count(text) 
from table 
group by text
having count(text)&gt;1
</code></pre>

then you should get the right answers in a very easy way.

blocks|key|4392126|text|一种相当直接的方式，从我的头顶：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4392127|您可以合并排序(对于太大而不能放入主内存的数据，性能很好)文本文件。然后，您可以通过该文件在一次遍历中识别重复项。O(nlogn)。当然，这将修改原始的文本文件，或者您可以复制一份。|offset|length|style|CODE|4392128|entityMap^0|0|1L|8|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@$D|L|E|M|F|G]]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

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. <code>O(nlogn)</code>. Of course this will either modify the original text file, or you could make a copy.

blocks|key|1753697|text|如果你有足够的额外磁盘空间，这样的东西应该是可行的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1753698|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.|code-block|syntax|javascript|1753699|假设您的散列函数是相对平衡的，排序应该不会太繁琐。|1753700|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

If you've got plenty of extra disk space, something like this should be workable:

<pre><code>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.
</code></pre>

Assuming your hash function is relatively balanced, the sorts shouldn't be too onerous.

blocks|key|1756827|text|SELECT+String
FROM+TextFile
GROUP+BY+String
HAVING+COUNT(*)+>+1
ORDER+BY+String|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1756828|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>SELECT String
FROM TextFile
GROUP BY String
HAVING COUNT(*) &gt; 1
ORDER BY String
</code></pre>

blocks|key|4392008|text|速度算数吗？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4392009|我想到的最明显的解决方案是将前1000行加载到某种Set类中，然后一次读取剩下的一行，并检查它们是否包含在集合中。然后读下面1000行，然后重复。这样一来，你一次只能在内存中存储1000行代码。|offset|length|style|CODE|4392010|我不认为你会因为告诉面试官将那么多数据存储在文本文件中是个坏主意而得到很多分数。谁知道这个文本文件是怎么来的……也许它是某种遗留系统的结果，或者谁知道是什么。它的存在有完全合法的理由。|4392011|entityMap^0|0|P|3|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@$D|N|E|O|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Does speed count?

The obvious solution that comes to mind is to load up say, the first 1000 lines into some kind of <code>Set</code> 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.

blocks|key|4392245|text|对此文件进行排序，重复项将一起排序。或者，创建第二个文件和散列(md5+?)每一行，然后对其进行排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4392246|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Sort this file, duplicates will sort together. Alternatively, create a second file and hash (md5 ?) each line into it, then sort that.

blocks|key|4392297|text|我会提出两个解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4392298|第一种方法是将每一行放入集合中，然后在集合中查找具有多个元素的集合。我会让解决方案将集合写入磁盘以节省内存空间。|4392299|第二种方法是按照其他人的建议对文本文件进行排序。|4392300|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

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.

blocks|key|2982815|text|A概率解决方案|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|2982816|下面的技术尝试使用散列函数来识别被证明是唯一的字符串。在第一次传递之后，字符串将被分成(1)证明是唯一的和(2)可能是重复的。|2982817|由于哈希码冲突，将有许多唯一的字符串标记为可能重复。后续传递将仅处理可能重复的字符串，以降低冲突率。|2982818|此技术不能保证消除所有重复项(只消除其中的大部分)。|2982819|让|2982820|2982821|s1，s2，...，sn是输入字符串。|ordered-list-item|2982822|h1，h2，...，hm是大小为k的不同哈希函数。|2982823|a1，...n是值为0，1的位数组。|2982824|b1，...，m是值为0，1，2的标志数组。|2982825|2982826|然后|2982827|2982828|+i=1+to+k：|2982829|For+j=1+to+n：|2982830|if+aj==0+//此字符串可能//可能不是唯一的|2982831|让x是|2982832|aj==0|2982833|H124>else+if+bi==1+then+code|2982834|2982835|2982836|2982837|2982838|2982839|​|2982840|++++1.+else+if+a[j]==1,+this+string+has+been+proven+to+be+unique,+skip+it.|code-block|syntax|javascript|2982841|2982842|1.+For+j=1+to+n:++
++++1.+if+a[j]==0+//+this+string+may/+may+not+be+unique++
++++++++1.+Let+x+be+h[i]+(s[j])
++++++++2.+if+b[i][x]==1+then+set+a[j]=1+//+we+have+proven+the+string+to+be+unique
++++++++3.+else+if+b[i][x]==2+this+string+may/+may+not+be+unique
++++++++4.+else+if+b[i][x]==0+there+is+an+implementation+problem|2982843|2982844|++++1.+else+if+a[j]==1,+this+string+has+been+proven+to+be+unique,+skip+it|2982845|2982846|2982847|entityMap^0|0|7|0|0|0|0|0|0|0|0|0|0|0|0|0|1|2|3|3|4|4|3|2|1|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1Z|8|@$9|20|A|21|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|22|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|23|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|24|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|25|8|@]|D|@]|E|$]]|$1|N|3|-4|5|6|7|26|8|@]|D|@]|E|$]]|$1|O|3|P|5|Q|7|27|8|@]|D|@]|E|$]]|$1|R|3|S|5|Q|7|28|8|@]|D|@]|E|$]]|$1|T|3|U|5|Q|7|29|8|@]|D|@]|E|$]]|$1|V|3|W|5|Q|7|2A|8|@]|D|@]|E|$]]|$1|X|3|-4|5|6|7|2B|8|@]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|2C|8|@]|D|@]|E|$]]|$1|10|3|-4|5|6|7|2D|8|@]|D|@]|E|$]]|$1|11|3|12|5|Q|7|2E|8|@]|D|@]|E|$]]|$1|13|3|14|5|Q|7|2F|8|@]|D|@]|E|$]]|$1|15|3|16|5|Q|7|2G|8|@]|D|@]|E|$]]|$1|17|3|18|5|Q|7|2H|8|@]|D|@]|E|$]]|$1|19|3|1A|5|Q|7|2I|8|@]|D|@]|E|$]]|$1|1B|3|1C|5|Q|7|2J|8|@]|D|@]|E|$]]|$1|1D|3|-4|5|6|7|2K|8|@]|D|@]|E|$]]|$1|1E|3|-4|5|6|7|2L|8|@]|D|@]|E|$]]|$1|1F|3|-4|5|6|7|2M|8|@]|D|@]|E|$]]|$1|1G|3|-4|5|6|7|2N|8|@]|D|@]|E|$]]|$1|1H|3|-4|5|6|7|2O|8|@]|D|@]|E|$]]|$1|1I|3|1J|5|6|7|2P|8|@]|D|@]|E|$]]|$1|1K|3|1L|5|1M|7|2Q|8|@]|D|@]|E|$1N|1O]]|$1|1P|3|1J|5|6|7|2R|8|@]|D|@]|E|$]]|$1|1Q|3|1R|5|1M|7|2S|8|@]|D|@]|E|$1N|1O]]|$1|1S|3|1J|5|6|7|2T|8|@]|D|@]|E|$]]|$1|1T|3|1U|5|1M|7|2U|8|@]|D|@]|E|$1N|1O]]|$1|1V|3|1J|5|6|7|2V|8|@]|D|@]|E|$]]|$1|1W|3|1J|5|6|7|2W|8|@]|D|@]|E|$]]|$1|1X|3|-4|5|6|7|2X|8|@]|D|@]|E|$]]]|1Y|$]]

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

<ol>
<li>s[1], s[2], ..., s[n] be the input strings.</li>
<li>h[1], h[2], ..., h[m] be different hash functions of size k.</li>
<li>a[1,...n] be an array of bits having values 0, 1.</li>
<li>b[1,...,m][1,...,k] be an array of flags having values 0, 1, 2.</li>
</ol>

Then

<ol>
<li>For i=1 to k:

<ol>
<li>For j=1 to n:

<ol>
<li>if a[j]==0 // this string may/ may not be unique

<ol>
<li>Let x be h[i] (s[j]).</li>
<li>if b[i][x]==0 then b[i][x]==1</li>
<li>else if b[i][x]==1 then b[i][x]=2</li>
</ol></li>
<li>else if a[j]==1, this string has been proven to be unique, skip it.</li>
</ol></li>
<li>For j=1 to n:

<ol>
<li>if a[j]==0 // this string may/ may not be unique

<ol>
<li>Let x be h[i] (s[j])</li>
<li>if b[i][x]==1 then set a[j]=1 // we have proven the string to be unique</li>
<li>else if b[i][x]==2 this string may/ may not be unique</li>
<li>else if b[i][x]==0 there is an implementation problem</li>
</ol></li>
<li>else if a[j]==1, this string has been proven to be unique, skip it</li>
</ol></li>
</ol></li>
</ol>

blocks|key|2982916|text|我想使用perl会更好，因为它是用于文本处理的v.good|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2982917|在perl程序中编写以下代码：|2982918|my+%25dataHash+=+();#create你的哈希|2982919|而(@ARGV+){+#argv是命令行参数，它将是那个3TB的文件chomp($_)；#删除新行|2982920|如果(!exists($dataHash{$_}))+{|2982921|+++$dataHash{$\_}+=+$currentLine;++#increase+the+count+of+value+of+key+if+key+exist...to+deal+with+duplicate....|code-block|syntax|javascript|2982922|+};++++++$currentLine%2B%2B;|2982923|}；#end+while|2982924|现在我们可以做任何我们想要复制的want...for示例|2982925|所以我们能做的就是运行for循环，并检查所有值大于0的键是否为duplicate....thats+it|2982926|我认为为了更好的可读性，do...sorry应该不给程序增加色彩。|2982927|entityMap^0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|13|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|14|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|15|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|L|7|16|8|@]|9|@]|A|$M|N]]|$1|Q|3|R|5|6|7|17|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|18|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|19|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|Z|$]]

I guess its better to use perl, as it is v.good for text processing 

Write the following in the perl program: 


 

my %dataHash = ();#create your hash
 
while (@ARGV ) { #argv is command line arg which will be that 3TB file
 chomp($_); #remove the new line


if (!exists($dataHash{$_})) { 
 $dataHash{$_} = $currentLine; #increase the count of value of key if key exist...to deal with duplicate.... 
 };

 $currentLine++; 
 }; #end while 




Now we can do anything we want...for example we want duplicate 
So what we can do is run the for loop and check all the keys for which the value is greater than 0 is duplicate....thats it


 
I think that should do...sorry for not adding color to the program for better readability

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!

Duplicated strings in a 3TB TXT file

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

假设有一个3TB的TXT文件，其中每一行都是一个字符串，如何查找其中重复的字符串？这是我一个朋友的面试问题。我们最好在面试后把这些问题弄清楚，以防下次面试。PS:如果我是面试官，我会告诉面试官:你们怎么能在一个TXT文件中存储这么多字符串？这真是个坏主意！

问3TB TXT文件中的重复字符串
EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问3TB TXT文件中的重复字符串EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问3TB TXT文件中的重复字符串
EN