logo标签列表

C++需要将一个字符串与20万个单词进行比较。

c++comparewords
6
在我的C++程序中...
用户输入程序字符串"foo"。
我需要将此字符串与我的文本文件中的字符串进行比较，以写出：这个字符串是名词！（或形容词...）
我有几个TXT文件 - 一个名词文件，第二个形容词文件...但每个文件中都有大约20万个单词。
我如何有效地将这个字符串"foo"与我的文件中的字符串进行比较？
我需要使用什么？
这是作业吗？如果是，请标记为作业。 - John Kugelman
不，这不是作业，这是一个问题。 - Kate83
1
真正的数据库怎么样？你提供的“规格”最好说是相当不完整了... - none
1
请记住，一个单词既可以是名词又可以是形容词。您将如何处理这种情况？ - Daniel Daranas
6个回答
15

使用TRIE数据结构来完成这个任务。你需要一些内存来构建这个数据结构，但是目标最有效。

1
OMG TRIE 真是太棒了。不过，如果我被迫的话，可能会重新发明它。 - Hamish Grubijan
我在1996年用C重新发明了它。速度差异让我大吃一惊（当时的PC是486）。非常酷。我相信它最早是在60年代末被写出来的。直到几年前我才好奇地知道它是一个真正的结构。如果这是作业，你比使用内置函数更能打动老师。如果这是工作，你的同事会嘲笑你浪费时间重新发明轮子！ - FastAl
14
将您的单词放入std：：set<std：：string>容器中，并对其进行查找。这将为访问提供O（log n）时间，对于您正在进行的操作可能已足够。
您还可以使用std：：map<std：：string、std：：string>，其中键是单词，值是类别（例如“名词”）。
4
std::unordered_set或std::unordered_map可能是更好的选择。无论使用哪种标准容器读取单词都可以，只要不为每个搜索重新加载数据即可。 “完美”的数据结构取决于使用方式 - trie（也称为数字树）是一种选择，三叉树稍微慢一些但更节省内存，但这些好处可能不足以证明开发时间的成本。 - user180247
@Steve314：但那些是非标准容器。 - Billy ONeal
标准并未指定使用哪种算法，仅规定了效率（map/set的O(log n)和无序版本的O(1)）。如果编译器处于C++0x模式（如g++ -std=c++0x），则无序版本也可以直接位于std命名空间中。 - Tronic
@Steve314：不，完全允许。但是如果容器是非标准的，则应向读者指出。 - Billy ONeal
3
我想为这个答案点赞，但是因为最后一句话我做不到。一个“map<string, WordCategory>”会更加节约内存，其中的“WordCategory”是一个枚举类型。 - Manuel
显示剩余9条评论
1
我建议使用sqlite来代替您的文件。
您可以为每个关键值创建一个CRC，并将键和值（int）存储到表中。 为键字段创建索引。
当您想要进行查找时，可以获取单词的CRC，在表中进行查找。
每个单词的CRC创建是一对一的吗？如果不是，那么密钥可能会发生冲突，不是吗？ - bragboy
1
@Bragaadees 如果只有 200,000 个键，你赢得彩票的机会会更大。你甚至可以使用 crc-8。如果两个匹配，你可以选择全部并进行字符串比较，但是两个可能永远不会匹配。 - Brian R. Bondy
1
不好的想法。使用CRC-32，生日碰撞在2^16 = 65536个密钥时很可能发生。有200,000个密钥，碰撞几乎是必然的。是的，任何一对冲突的机会只有40亿分之一，但有400亿个密钥对。 - MSalters
1

如果你有许多具有共同前缀/根的字符串（这在字典即包含许多形式的单词中可能是情况），那么 基数树将比“常规”字典树提供更好的字符串内存使用。

0

你只需要确认它是否匹配任何内容吗？

如果是的话，使用 Trie。

我必须告诉用户，他输入的单词是名词、形容词……还是程序不知道这个单词是什么。 - Kate83
然后使用两个Trie，一个用于名词，一个用于形容词。 - MSalters
0

您可以将外部文件存储为B树或链式哈希表进行索引，这将提供非常快的查找时间和最小的寻址来定位数据。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接