我想知道存储大量字符串和检查重复的最佳方法是什么。
我们必须考虑我们的优先事项：
- 重复检查速度
- 插入新字符串时间
- 硬盘上的存储空间
- 随机存取时间
当我们的目标是快速重复检查和插入新字符串时（没有随机访问或存储空间问题），最好的解决方案是什么？我想到了 SQL 数据库，但哪个 DB 最适合这个解决方案？如果我们使用 SQL DB，比如 MySQL，哪个存储引擎是最好的？（当然，由于数据量，我们必须排除内存）
问问题
1474 次
3 回答
5
对输入字符串使用哈希函数。输出哈希将是记录的主键/ID。
然后你可以检查数据库是否有这个哈希/id/主键：
- 如果没有：这是一个新字符串；您添加一条新记录，包括字符串和哈希作为 id。
- 如果是：检查加载记录中的字符串是否与输入字符串相同。
- 如果字符串相同：它是重复的
- 如果字符串不同：这是一个冲突。使用冲突解决方案来解决。（下面有几个例子）
您将不得不根据速度和预期的字符串数量以及哈希冲突要求/保证来考虑使用哪种哈希函数/方案/强度。
解决冲突的几种方法：
- 使用第二个散列函数在同一个表中产生一个新的散列。
- 标记记录（例如使用 NULL）并在辅助“冲突”表上使用更强的第二散列函数（具有更广泛的域）重复。在查询时，如果字符串被标记为冲突（例如 NULL），则在冲突表中再次进行查找。您可能还想使用动态完美散列来确保第二个表没有进一步的冲突。
当然，根据这需要的持久性以及您期望占用多少内存/字符串数量，您实际上可以在没有数据库的情况下直接在内存中执行此操作，这会快得多。
于 2012-04-13T09:51:34.383 回答
4
您可能需要考虑 NoSQL 解决方案：
雷迪斯。使用 Redis 解决的一些用例：
- http://highscalability.com/blog/2011/7/6/11-common-web-use-cases-solved-in-redis.html
- http://dr-josiah.blogspot.com/2011/02/some-redis-use-cases.html（Josiah L. Carlson 是Redis in Action的作者）
- http://www.paperplanes.de/2010/2/16/a_collection_of_redis_use_cases.html
内存缓存。memcached 和 Redis 的一些比较：
- http://www.quora.com/What-are-the-differences-between-memcached-and-redis
- 与 Redis 相比，memcached 是恐龙吗？
- http://coder.cl/2011/06/concurrency-in-redis-and-memcache/
Membase/Couchbase将 OMGPOP 的 Draw Something 视为他们的成功故事之一。Redis 和 Membase 的比较：
一些问题：
- 字符串集有多大？
- 应用程序会读重还是写重？或两者？
- 您希望多久将数据持久化到磁盘？
- 是否有N 最近的字符串要求？
希望这可以帮助。
于 2012-04-14T01:24:30.027 回答
1
生成后缀树来存储字符串。Ukkonen 的算法如http://www.daimi.au.dk/~mailund/slides/Ukkonen-2005.pdf将提供一些有关如何创建后缀树的见解。存储此后缀树的方法有多种。但是一旦生成，查找时间非常短。
于 2012-04-13T23:35:04.067 回答