1

让我解释一下问题：

  1. 假设我有一个图书馆，图书馆包含很多书，每本书包含章节，每章包含字符串（字符串以点“.”开头和结尾）。
  2. 再次顺序，图书馆 -> 书 -> 章节 -> 字符串。
  3. 我从书籍中提取字符串，我们称它们为“书籍字符串”。
  4. 我有一个系统，用户可以在搜索表单中输入一个字符串，系统应该从“书籍字符串”返回输入字符串的完全匹配。如果输入的字符串与书籍字符串中的任何字符串都不匹配，则不会返回任何内容。

我想了想，找到了一个解决方案，我将对所有书籍字符串进行 MD5 并保存散列的书籍字符串。当用户输入要搜索的字符串时，我也会对其进行散列并在散列的书籍字符串中搜索匹配项。它更便宜（每个字符串 32 或 64 个字符），比普通搜索更快，并且只返回完全匹配。

有任何意见、想法、更好的解决方案吗？

PS这样的算法叫什么名字？搜索或匹配？

4

9 回答 9

4

这还不错，但您应该调查一下 Lucene。它是一个以多种语言实现的公共共享软件文本索引和搜索工具，其中之一是 .Net..（您在使用什么平台/语言？）我用它在公共互联网上对网站内容进行自由文本搜索，其主要模型是在特定的细分市场中提供内容（大量杂志文章、书籍摘录等）。Lucene 对我们非常有效。

Lucene

于 2009-01-14T00:47:10.083 回答
4

有许多用于在字符串中搜索的算法，从像Boyer-Moore算法这样的简单方法到像后缀树这样的复杂数据结构。可以在以下位置找到这些内容的完整介绍：

  • Gusfield, Dan (1999)，关于字符串、序列和树的算法。剑桥：大学出版社。

但是，对于您的情况，将书籍文本拆分为单独的标记（单词）并将它们存储在索引中（例如，简单地存储在 Map 中，或使用完整的索引和搜索框架（如Lucene））可能更有意义。

于 2009-01-14T01:21:03.603 回答
3

它被称为散列，可以被认为是搜索或匹配。

您应该通过比较用于生成哈希的字符串来验证您的 MD5 哈希是否正确，这样您就没有任何误报。

要考虑的另一件事是，支持某种从搜索开始可能是有益的。 考虑

Mary Queen of Scots
Mary Livingston
Mary Had a Little Lamb, and other silly stories

A以搜索Mary 开始，应该返回这三个记录并且可能更多。尽管 MD5 类型的哈希很快，但也应考虑其他答案中介绍的技术，以找到适合您情况的最佳收益/成本平衡。

于 2009-01-14T04:49:52.403 回答
2

您应该将每本书的章节转换为后缀树。后缀树是 Trie 的一种（由 divo 提到）。

后缀树专门用于快速文本搜索。后缀树的一个优点是搜索长度为 n 的字符串是 O(n) 时间。这和你的算法想法一样好（渐近）（因为散列一个字符串需要 O(n) 时间），但更灵活，因为它甚至适用于部分句子。如果您以句点开始/结束搜索，它会简化为句子搜索。

澄清：更准确地说，您将拥有一棵后缀树。

于 2009-01-14T01:04:32.263 回答
1

您可能希望使用Trie或其他基于树的数据结构来存储字符串数据。

trie 还可用于替换哈希表，它具有以下优点：

  • 与不完美的哈希表相比，在最坏的情况下（O(m) 时间）在 trie 中查找数据会更快。一个不完美的哈希表可能有键冲突。键冲突是不同键到哈希表中相同位置的哈希函数映射。在不完美的哈希表中，最坏情况下的查找速度是 O(N) 时间，但更常见的是 O(1)，其中 O(m) 时间花费在评估哈希上。

  • 在 trie 中没有不同键的冲突。

  • 仅当单个键与多个值相关联时，才需要类似于存储键冲突的哈希表存储桶的树中的存储桶。

  • 无需提供散列函数或更改散列函数，因为将更多键添加到树中。

  • trie 可以通过键提供条目的字母顺序。

尝试也有一些缺点：

  • 在某些情况下，尝试查找数据的速度可能比哈希表慢，尤其是当数据直接在硬盘驱动器或其他随机访问时间比主存储器长的辅助存储设备上访问时。
  • 将所有键都表示为字符串并不容易，例如浮点数，对于同一个浮点数可以有多个字符串表示，例如 1、1.0、1.00、+1.0 等。
  • 尝试的空间效率通常低于哈希表。

（见http://en.wikipedia.org/wiki/Trie）

于 2009-01-14T00:51:28.827 回答
0

Trie是最好的方法。这也称为后缀映射。使用 Trie 相对于散列的想法的优势在于，使用 Trie 可以非常轻松地显示自动完成类型语法。找到一个单词的时间是 O(n)，其中 n 是单词的长度。在 Trie 中的每个节点上，您都需要存储包含特定单词的书籍列表。

于 2009-01-14T02:44:08.380 回答
0

我同意 Trie - 再加上一个，使用 soundx 算法将字符串转换为 trie id/node - 所以会考虑拼写错误

于 2009-01-14T19:58:27.327 回答
-1

首先，听起来您应该使用的是数据库——这几乎正是数据库的用途。（如果您希望将其嵌入到您自己的应用程序中，请查看SQLite，这是一种轻量级 DBMS，旨在用作嵌入式库。）

其次，您的哈希解决方案仅返回完全匹配并不完全正确......因为 MD5 摘要是 128 位，这意味着任何给定的字符串对都有 1-in-2^128 的机会产生相同的哈希值. 是的，这是一个很小的数字，但如果你有很多书，你就会有很多对字符串。因此，一旦您比较了哈希值，您就需要进行全文比较以消除误报。

于 2009-01-14T02:14:27.600 回答
-1

这称为散列。您的方法可能有效，但不是很灵活。同样，您只会检索完全匹配。也有可能两个原像共享同一个图像（两个不同的字符串散列到相同的值），但这极不可能，所以这不是一个真正的问题。由于缺乏灵活性，我建议不要这样做，但如果这不打扰您，那么我想这对您有用。这与人们用于存储和验证密码的技术基本相同（除非，您显然没有使用任何“盐”值）。

于 2009-01-14T00:46:58.540 回答