blocks|key|1518545|text|用单词建立一个哈希表，扫描文本，在词表中查找每个单词，并填充所需的信息(递增计数，添加到位置列表，等等)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1518546|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|$]]

build a hashtable with the words, and scan throuhgt the text, for each word lookup in the wordtable and stuff the needed info (increment count, add to a position list, whatever).

blocks|key|1518622|text|Bloom+Filter可能是你最好的选择。你用你的搜索词初始化你的过滤器，然后在阅读你的语料库时，你可以快速检查每个作品是否都在过滤器中。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1518623|它非常节省空间，比简单地对每个单词进行散列要好得多:在1%25的误报率下，每个元素应该只需要9.6位。对于每个元素每增加4.8比特，假阳性率降低10倍。相比之下，普通散列通常需要每个元素32位的sizeof(int)+==。|1518624|我在这里有一个C#实现：http://www.codeplex.com/bloomfilter|1518625|下面是一个示例，演示它在字符串中的用法：|1518626|int+capacity+=+2000000;+//+the+number+of+items+you+expect+to+add+to+the+filter
Filter<string>+filter+=+new+Filter<string>(capacity);
filter.Add("Lorem");
filter.Add("Ipsum");
if+(filter.Contains("Lorem"))
++++Console.WriteLine("Match!");|code-block|syntax|javascript|1518627|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Bloom_filter|1|http://www.codeplex.com/bloomfilter^0|0|C|0|0|0|C|Z|1|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@$A|Z|B|10|1|11]]|C|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|13|8|@]|9|@$A|14|B|15|1|16]]|C|$]]|$1|H|3|I|5|6|7|17|8|@]|9|@]|C|$]]|$1|J|3|K|5|L|7|18|8|@]|9|@]|C|$M|N]]|$1|O|3|-4|5|6|7|19|8|@]|9|@]|C|$]]]|P|$Q|$5|R|S|T|C|$U|V]]|W|$5|R|S|T|C|$U|X]]]]

A <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer">Bloom Filter</a> may be your best bet. You initialize your filter with your search terms, then while reading your corpus can quickly check if each work is in the filter.

It is very space efficient, much better than simply hashing each word: with a 1% false-positive rate it should require only 9.6 bits per element. The false-positive rate is reduced by a factor of 10 for each additional 4.8 bits per element. Contrast this to plain hashing, which usually requires sizeof(int) == 32 bits per element. 

I have an implementation in C# here: <a href="http://www.codeplex.com/bloomfilter" rel="nofollow noreferrer">http://www.codeplex.com/bloomfilter</a>

Here's an example, demonstrating its use with strings:

<pre><code>int capacity = 2000000; // the number of items you expect to add to the filter
Filter&lt;string&gt; filter = new Filter&lt;string&gt;(capacity);
filter.Add("Lorem");
filter.Add("Ipsum");
if (filter.Contains("Lorem"))
 Console.WriteLine("Match!");
</code></pre>

blocks|key|1518693|text|正如Javier所说，最简单的解决方案可能是哈希表。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1518694|在C%2B%2B中，这可以使用STL来实现。首先将25,000个测试单词添加到集合中，然后使用set.find(current_word)扫描文本中的每个单词，以评估该单词是否在25,000个测试单词中。|1518695|set.find的对数速度很快，所以25,000个测试字应该不会太大。该算法在文本中的单词数量上明显是线性的。|1518696|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|$]]

As Javier says, the simplest solution is probably a hash table.

In C++, this can be implemented using an STL set. First add the 25,000 test words to the set, and then scan through each word in the text, using set.find(current_word) to evaluate whether the word is among the 25,000 test words.

set.find is logarithmically fast, so 25,000 test words shouldn't be too large. The algorithm is obviously linear in the number of words in the text.

blocks|key|1733749|text|可能将初始字典(+25000个单词)存储在磁盘上的berkeley+db哈希表中，您可能可以直接从c/c%2B%2B中使用(我知道您可以在perl中使用)，并且对于文本中的每个单词，查询它是否存在于数据库中。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1733750|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|$]]

May be storing your initial dictionnary (the 25000 words) in a berkeley db hash table on disk, that you can probably use directly from c/c++ (i know you can do it from perl), and for each word in the text, query if it's present in the database.

blocks|key|1518926|text|如果语料库如此之大，试着这样优化它：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1518927|计算需要检查的每个单词的散列，为每个字符分配一个整数质数，然后将每个数字相乘；将每个数字->单词存储在multimap中(您需要允许在单个键上有多个值)|1518928|在扫描单词列表时，以相同的方式计算每个单词的散列，然后在hashmap上获得与计算出的键相关联的单词。使用整数作为键，您可以检索O(1)；这样，如果处理的单词在映射中有一些字形(您乘以字符)，您就可以非常快速地找到它。|1518929|记住:您在multimap中存储了具有相同散列的单词集合，因此您现在需要在这个大大减少的集合中查找匹配。你需要这个额外的检查，因为整数在map上的存在并不等于单词在相关集合中的存在:我们在这里使用散列来减少问题的计算空间，但这会引入冲突，需要对每个识别的元词进行检查以消除歧义。|1518930|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

if the corpus is so large, try to optimize it in this way:

compute an hash of each word you need to check, assigning to each char an integer prime number and then multiplying each number together;store each number->word in a multimap (you need to allow for multiple value on single key)

while scanning the wordlist, compute the hash in the same way for each word, then get the word(s) associated with the computed key on the hashmap. using integers as key, you have a retrieval of O(1); this way you could find in a really quick way if the processed word has some anagram (you multiplied characters) inside the map. 

remember: you stored in the multimap the set of the word having that same hash, so you now need to find a match in this greatly reduced set. you need this additional check as the simply existence of the integer on the map does not equate to the existence of the word in the associated set: we are using hashing here to reduce the computational space of the problem, but this introduces collision which need to be disambiguated checking on each identified anagram.

blocks|key|1518988|text|您也可以按字母顺序对文本和单词列表进行排序。当你有两个排序的数组时，你可以很容易地在线性时间内找到匹配。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1518989|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|$]]

You may also sort the text and the word-list alphabetically. When you have two sorted arraysyou can easily find the matches in linear time.

blocks|key|1519047|text|你想要一个Ternary+Search+Tree。可以在here中找到一个很好的实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1519048|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Ternary_search_tree|1|http://www.cs.princeton.edu/~rs/strings/^0|5|J|0|S|4|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

You want a <a href="http://en.wikipedia.org/wiki/Ternary_search_tree" rel="nofollow noreferrer">Ternary Search Tree</a>. A good implementation can be found <a href="http://www.cs.princeton.edu/~rs/strings/" rel="nofollow noreferrer">here</a>.

blocks|key|1519100|text|如果你搜索的文本很大，那么做一些预处理可能是值得的:把你的25,000个单词组合成一个TRIE。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1519101|扫描到文本中第一个单词的开头，并在遍历单词的字母时开始遍历TRIE。如果TRIE中没有转换，请跳到下一个单词的开头，然后返回TRIE的词根。如果到达单词的末尾，并且位于TRIE中的单词结尾节点，则表示找到了匹配项。对文本中的每个单词重复上述步骤。|1519102|如果您的文本只是很大(而不是很大)，那么简单地在哈希表中查找每个单词可能就足够了。|1519103|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|$]]

If the text you're searching is huge, then it might be worth doing some preprocessing: assemble your 25,000 words into a TRIE.

Scan to the start of the first word in the text, and start walking the TRIE as you walk through the letters of the word. If there's no transition in your TRIE, skip to the start of the next word and go back to the root of the TRIE. If you reach the end of the word, and you're at a word-ending node in the TRIE, you've found a match. Repeat for each word in the text.

If your text is merely large (rather than huge), then simply looking up each word in a hash table is probably sufficient.

blocks|key|1519136|text|使用Aho-Corasick+algorithm。它是为这个应用程序制作的。您只需阅读搜索文本中的每个字母一次。我最近实现并使用了它，并取得了很好的效果。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1519137|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Aho-Corasick_algorithm^0|2|M|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Use the <a href="http://en.wikipedia.org/wiki/Aho-Corasick_algorithm" rel="nofollow noreferrer">Aho-Corasick algorithm</a>. It was made for this application. You'll only need to read each letter in your search text once. I've recently implemented and used it with great results.

blocks|key|1734162|text|Aho-Corasick算法是专门为此目的而构建的:一次搜索多个单词。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1734163|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|$]]

Aho-Corasick algorithm is built specifically for that purpose: searching for many words at once.

I need to find occurrences of ~ 25 000 words within a text. What is the most suitable algorithm/library for this purpose?

target language is C++

search 25 000 words within a text

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

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

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

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

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

我需要在一个文本中找到大约25000个单词的匹配项。最适合此目的的算法/库是什么？目标语言是C++

问在文本中搜索25000个单词
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在文本中搜索25000个单词EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在文本中搜索25000个单词
EN